没有合适的资源?快使用搜索试试~ 我知道了~
首页LeetCode刷题攻略:101道精选例题与知识点解析
LeetCode刷题攻略:101道精选例题与知识点解析
需积分: 0 5 下载量 36 浏览量
更新于2024-06-17
1
收藏 3.88MB PDF 举报
"LeetCode,算法大佬总结,知识点加例题" 这篇资源主要是一个由谷歌工程师编写的关于LeetCode刷题心得的书籍,适合有一定C++基础但缺乏刷题经验的读者。书中作者通过自己的刷题经历,系统性地整理并总结了LeetCode中的重要算法和数据结构,旨在帮助读者高效学习和准备技术面试。 该书分为算法和数据结构两大部分,共包含十五个章节。每个章节不仅包含了基础讲解,还提供了具体的例题和详细的解题思路。作者将题目数量精简至101道,以降低读者的学习负担,但这可能导致对算法和数据结构的全面掌握有所欠缺。因此,每章末尾都有推荐的额外练习题和解题提示,鼓励读者深入理解和实践。 书中的编程语言是C++,作者假设读者已经具备C++基础,所以不会过于详细地解释语法,而是更多地关注算法和数据结构的实现。对于使用Java的读者,大部分内容可以直接对应,只需少量语法调整。但对于Python或其他语言的用户,由于语法差异,可能需要自行适应。 作者在刷题过程中积累了丰富的经验,他在找到满意的工作后,决定将这些经验和总结分享出来,以帮助更多的人。这本书不仅是一个学习工具,也是一个自我提升的过程,通过阅读和实践,读者不仅可以提升编程技能,还能增强解决实际问题的能力。 这本书是LeetCode学习者的宝贵参考资料,通过它,读者可以学习到如何有效地刷题、理解和应用各种算法与数据结构,从而提升自身的编程能力和面试竞争力。对于想要在技术面试中脱颖而出的人来说,这是一份不可多得的学习资料。
资源详情
资源推荐
3.5 滑动窗口 – 11/143 –
输入输出样例
输入是一个链表,输出是链表的一个节点。如果没有环路,返回一个空指针。
图 3.1: 题目 142 - 输入样例
在这个样例中,值为 2 的节点即为环路的开始点。
如果没有特殊说明,LeetCode 采用如下的数据结构表示链表。
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
题解
对于链表找环路的问题,有一个通用的解法——快慢指针(Floyd 判圈法)。给定两个指针,
分别命名为 slow 和 fast,起始位置在链表的开头。每次 fast 前进两步,slow 前进一步。如果 fast
可以走到尽头,那么说明没有环路;如果 fast 可以无限走下去,那么说明一定有环路,且一定存
在一个时刻 slow 和 fast 相遇。当 slow 和 fast 第一次相遇时,我们将 fast 重新移动到链表开头,并
让 slow 和 fast 每次都前进一步。当 slow 和 fast 第二次相遇时,相遇的节点即为环路的开始点。
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
// 判断是否存在环路
do {
if (!fast || !fast->next) return nullptr;
fast = fast->next->next;
slow = slow->next;
} while (fast != slow);
// 如果存在,查找环路节点
fast = head;
while (fast != slow){
slow = slow->next;
fast = fast->next;
}
return fast;
}
3.5 滑动窗口
76. Minimum Window Substring (Hard)
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);
}
3.6 练习 – 13/143 –
3.6 练习
基础难度
633. Sum of Square Numbers (Easy)
Two Sum 题目的变形题之一。
680. Valid Palindrome II (Easy)
Two Sum 题目的变形题之二。
524. Longest Word in Dictionary through Deleting (Medium)
归并两个有序数组的变形题。
进阶难度
340. Longest Substring with At Most K Distinct Characters (Hard)
需要利用其它数据结构方便统计当前的字符状态。
第 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)
题目描述
给定一个非负整数,求它的开方,向下取整。
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)
剩余147页未读,继续阅读
Li-xy
- 粉丝: 235
- 资源: 8
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 前端面试必问:真实项目经验大揭秘
- 永磁同步电机二阶自抗扰神经网络控制技术与实践
- 基于HAL库的LoRa通讯与SHT30温湿度测量项目
- avaWeb-mast推荐系统开发实战指南
- 慧鱼SolidWorks零件模型库:设计与创新的强大工具
- MATLAB实现稀疏傅里叶变换(SFFT)代码及测试
- ChatGPT联网模式亮相,体验智能压缩技术.zip
- 掌握进程保护的HOOK API技术
- 基于.Net的日用品网站开发:设计、实现与分析
- MyBatis-Spring 1.3.2版本下载指南
- 开源全能媒体播放器:小戴媒体播放器2 5.1-3
- 华为eNSP参考文档:DHCP与VRP操作指南
- SpringMyBatis实现疫苗接种预约系统
- VHDL实现倒车雷达系统源码免费提供
- 掌握软件测评师考试要点:历年真题解析
- 轻松下载微信视频号内容的新工具介绍
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功