没有合适的资源?快使用搜索试试~ 我知道了~
首页谷歌高畅LeetCode刷题指南:C++版101题详解
谷歌高畅LeetCode刷题指南:C++版101题详解
![](https://csdnimg.cn/release/wenkucmsfe/public/img/star.98a08eaa.png)
"谷歌高畅的《LeetCode刷题笔记》是一本专门为C++编程基础者设计的教材和参考书,由作者ChangGao编撰,针对缺乏刷题经验的学习者提供系统性的指导。该书是在作者攻读硕士期间,为准备实习秋招而整理LeetCode题目,并在经历了一年的刷题和初步总结后,于2019年秋季升级为正式版1.04,旨在帮助读者更好地理解和掌握算法与数据结构。 书中的主要内容包括101道精选题目,这些题目代表了刷题过程中常用的技巧,既符合书名中的"一起轻松刷题",也控制了读者的学习负担。每个章节都详细讲解了相应的算法和数据结构,并提供了清晰的题解。为了确保读者能全面理解,作者在每个章节末尾推荐了额外的练习题,并给予了解题思路的提示。尽管书是以C++作为主要编程语言,但对于Java用户来说,大部分内容可以迁移,只是语法上需要做一些调整。然而,对于Python或其他语言的用户,由于语法差异较大,可能需要适度适应。 值得注意的是,作者并非单纯教授C++语言,而是注重算法和数据结构的实际应用,因此书中不会深入讲解语法细节,而是采用C++11及以上版本的语法,以保持内容的现代性和实用性。如果读者对该书反响热烈,作者计划未来会添加更多题解。 《LeetCode刷题笔记》是一本实用且有针对性的刷题指南,尤其适合那些希望通过刷题提升C++技能和算法理解能力的读者。通过阅读此书,读者不仅能提升技术能力,还能了解到如何将理论知识应用于实际问题解决中。"
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/20704905/bg10.jpg)
3.6 练习 – 12/143 –
题目描述
给定两个字符串 S 和 T,求 S 中包含 T 所有字符的最短连续子字符串的长度,同时要求时间
复杂度不得超过 O(n)。
输入输出样例
输入是两个字符串 S 和 T ,输出是一个 S 字符串的子串。
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
在这个样例中,S 中同时包含一个 A、一个 B、一个 C 的最短子字符串是“BANC”。
题解
本题使用滑动窗口求解,即两个指针 l 和 r 都是从最左端向最右端移动,且 l 的位置一定在
r 的左边或重合。注意本题虽然在 for 循环里出现了一个 while 循环,但是因为 while 循环负责移
动 l 指针,且 l 只会从左到右移动一次,因此总时间复杂度仍然是 O(n)。本题使用了长度为 128
的数组来映射字符,也可以用哈希表替代;其中 chars 表示目前每个字符缺少的数量,flag 表示
每个字符是否在 T 中存在。
string minWindow(string S, string T) {
vector<int> chars(128, 0);
vector<bool> flag(128, false);
// 先统计T中的字符情况
for (int i = 0; i < T.size(); ++i) {
flag[T[i]] = true;
++chars[T[i]];
}
// 移动滑动窗口,不断更改统计数据
int cnt = 0, l = 0, min_l = 0, min_size = S.size() + 1;
for (int r = 0; r < S.size(); ++r) {
if (flag[S[r]]) {
if (--chars[S[r]] >= 0) {
++cnt;
}
// 若目前滑动窗口已包含T中全部字符,
// 则尝试将l右移,在不影响结果的情况下获得最短子字符串
while (cnt == T.size()) {
if (r - l + 1 < min_size) {
min_l = l;
min_size = r - l + 1;
}
if (flag[S[l]] && ++chars[S[l]] > 0) {
--cnt;
}
++l;
}
}
}
return min_size > S.size()? "": S.substr(min_l, min_size);
}
![](https://csdnimg.cn/release/download_crawler_static/20704905/bg12.jpg)
第 4 章 居合斩!二分查找
内容提要
h 算法解释
h 求开方
h 查找区间
h 旋转数组查找数字
4.1 算法解释
二分查找也常被称为二分法或者折半查找,每次查找时通过将待查找区间分成两部分并只取
一部分继续查找,将查找的复杂度大大减少。对于一个长度为 O(n) 的数组,二分查找的时间复
杂度为 O(log n)。
举例来说,给定一个排好序的数组 {3,4,5,6,7},我们希望查找 4 在不在这个数组内。第一次
折半时考虑中位数 5,因为 5 大于 4, 所以如果 4 存在于这个数组,那么其必定存在于 5 左边这一
半。于是我们的查找区间变成了 {3,4,5}。(注意,根据具体情况和您的刷题习惯,这里的 5 可以
保留也可以不保留,并不影响时间复杂度的级别。)第二次折半时考虑新的中位数 4,正好是我们
需要查找的数字。于是我们发现,对于一个长度为 5 的数组,我们只进行了 2 次查找。如果是遍
历数组,最坏的情况则需要查找 5 次。
我们也可以用更加数学的方式定义二分查找。给定一个在 [a, b] 区间内的单调函数 f (x),若
f (a) 和 f (b) 正负性相反,那么必定存在一个解 c,使得 f (c) = 0。在上个例子中,f (x) 是离散函数
f (x) = x + 2,查找 4 是否存在等价于求 f (x) − 4 = 0 是否有离散解。因为 f (1) − 4 = 3 − 4 = −1 < 0、
f (5) − 4 = 7 − 4 = 3 > 0,且函数在区间内单调递增,因此我们可以利用二分查找求解。如果最后
二分到了不能再分的情况,如只剩一个数字,且剩余区间里不存在满足条件的解,则说明不存在
离散解,即 4 不在这个数组内。
具体到代码上,二分查找时区间的左右端取开区间还是闭区间在绝大多数时候都可以,因此
有些初学者会容易搞不清楚如何定义区间开闭性。这里我提供两个小诀窍,第一是尝试熟练使用
一种写法,比如左闭右开(满足 C++、Python 等语言的习惯)或左闭右闭(便于处理边界条件),
尽量只保持这一种写法;第二是在刷题时思考如果最后区间只剩下一个数或者两个数,自己的写
法是否会陷入死循环,如果某种写法无法跳出死循环,则考虑尝试另一种写法。
二分查找也可以看作双指针的一种特殊情况,但我们一般会将二者区分。双指针类型的题,
指针通常是一步一步移动的,而在二分查找里,指针每次移动半个区间长度。
4.2 求开方
69. Sqrt(x) (Easy)
题目描述
给定一个非负整数,求它的开方,向下取整。
![](https://csdnimg.cn/release/download_crawler_static/20704905/bg13.jpg)
4.3 查找区间 – 15/143 –
输入输出样例
输入一个整数,输出一个整数。
Input: 8
Output: 2
8 的开方结果是 2.82842...,向下取整即是 2。
题解
我们可以把这道题想象成,给定一个非负整数 a,求 f (x) = x
2
− a = 0 的解。因为我们只考
虑 x ≥ 0,所以 f (x) 在定义域上是单调递增的。考虑到 f (0) = −a ≤ 0, f (a) = a
2
− a ≥ 0,我们
可以对 [0, a] 区间使用二分法找到 f (x) = 0 的解。
注意,在以下的代码里,为了防止除以 0,我们把 a = 0 的情况单独考虑,然后对区间 [1, a]
进行二分查找。我们使用了左闭右闭的写法。
int mySqrt(int a) {
if (a == 0) return a;
int l = 1, r = a, mid, sqrt;
while (l <= r) {
mid = l + (r - l) / 2;
sqrt = a / mid;
if (sqrt == mid) {
return mid;
} else if (mid > sqrt) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return r;
}
另外,这道题还有一种更快的算法——牛顿迭代法,其公式为 x
n+1
= x
n
− f (x
n
)/ f
′
(x
n
)。给
定 f (x) = x
2
− a = 0,这里的迭代公式为 x
n+1
= (x
n
+ a/x
n
)/2,其代码如下。
注意 这里为了防止 int 超上界,我们使用 long 来存储乘法结果。
int mySqrt(int a) {
long x = a;
while (x * x > a) {
x = (x + a / x) / 2;
}
return x;
}
4.3 查找区间
34. Find First and Last Position of Element in Sorted Array (Medium)
![](https://csdnimg.cn/release/download_crawler_static/20704905/bg14.jpg)
4.3 查找区间 – 16/143 –
题目描述
给定一个增序的整数数组和一个值,查找该值第一次和最后一次出现的位置。
输入输出样例
输入是一个数组和一个值,输出为该值第一次出现的位置和最后一次出现的位置(从 0 开
始);如果不存在该值,则两个返回值都设为-1。
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
数字 8 在第 3 位第一次出现,在第 4 位最后一次出现。
题解
这道题可以看作是自己实现 C++ 里的 lower_bound 和 upper_bound 函数。这里我们尝试
使用左闭右开的写法,当然左闭右闭也可以。
// 主函数
vector<int> searchRange(vector<int>& nums, int target) {
if (nums.empty()) return vector<int>{-1, -1};
int lower = lower_bound(nums, target);
int upper = upper_bound(nums, target) - 1; // 这里需要减1位
if (lower == nums.size() || nums[lower] != target) {
return vector<int>{-1, -1};
}
return vector<int>{lower, upper};
}
// 辅函数
int lower_bound(vector<int> &nums, int target) {
int l = 0, r = nums.size(), mid;
while (l < r) {
mid = l + (r - l) / 2;
if (nums[mid] >= target) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
// 辅函数
int upper_bound(vector<int> &nums, int target) {
int l = 0, r = nums.size(), mid;
while (l < r) {
mid = l + (r - l) / 2;
if (nums[mid] > target) {
r = mid;
} else {
l = mid + 1;
}
剩余145页未读,继续阅读
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://profile-avatar.csdnimg.cn/aa035495f97e4af0b151b33a9af59efa_qiyihan.jpg!1)
KryHan
- 粉丝: 148
- 资源: 5
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 贵州煤矿矿井水分类与处理策略:悬浮物、酸性与非酸性
- 醛固酮增多症肾上腺静脉采样对比:ACTH后LR-CAV的最优评估
- 开源云连接传感器监控平台:农业土壤湿度远程监测
- 母婴用品企业年度生产计划线性规划优化模型:实证与应用
- 井下智能变电站:Rogowski线圈电流检测系统的研发与性能验证
- 霍州矿区煤巷稳定性分析及支护策略
- ARM嵌入式系统远程软件更新方案:基于TFTP协议
- 煤炭选煤中汞分布规律与洗选脱汞效果
- 提升码垛机器人性能:拉格朗日动力学模型与滑模模糊控制的应用
- 增强现实技术提升学前手写教学:设计与开发案例
- 不规则工作面沉陷三角剖分算法提升与应用
- 卡尔曼滤波在瞬变电磁干扰压制中的应用研究
- 煤矿安全能力研究:理论与系统构建
- LonWorks总线技术在斜巷运输车辆定位与跑车防护中的应用
- 神东煤炭集团高效煤粉锅炉系统:节能环保新实践
- Ti/SnO2+Sb2Ox/PbO2电极分形维数与电催化性能研究
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)