LeetCode 101攻略：C++刷题指南

需积分: 9 66 浏览量更新于2024-07-09 1 收藏 5.14MB PDF 举报

"LeetCode 101：A LeetCode Grinding Guide (C++ Version) 是一本专为有一定C++编程基础但缺乏刷题经验的学习者编写的指南。作者高畅在2018年秋季为准备实习而开始系统整理LeetCode题目，随着刷题的深入，他意识到需要将这些题目进行系统的归纳和总结，以便于他人理解和学习。这本书主要针对C++编程，但提到了Java用户可以通过查找对应的实现来适应大部分算法和数据结构，只是语法上的调整相对较小。书籍分为算法和数据结构两个核心部分，细化为十五个章节，每个章节专注于讲解在刷LeetCode过程中常用的技巧。选择101道题目作为精华，一方面呼应了书名，另一方面旨在控制读者的阅读和练习时间，防止过度集中导致对基础知识掌握不足。每一章结尾，作者还推荐额外的练习题并提供解法提示，鼓励读者在深入理解每个主题后进行实践。由于不是专门教授C++语言，书中对语法的解释保持简洁，主要使用C++11或更新版本的特性。尽管对于Python或其他编程语言用户，因为语法差异较大，这本书可能不如对C++用户那样适用。然而，通过本书，读者可以提升算法和数据结构的理解，并掌握LeetCode题目中的实际应用技巧。这是一本实用的LeetCode刷题指南，不仅提供了题目的解答，还注重技巧传授和技能提升，尤其适合想要系统学习和巩固C++编程能力的读者。"

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)

第 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)

题目描述

给定一个非负整数，求它的开方，向下取整。

剩余147页未读，继续阅读

m0_52270335

粉丝: 0
资源: 1

LeetCode 101攻略：C++刷题指南

A LeetCode Grinding Guide (C++ Version).pdf

谷歌高畅Leetcode刷题笔记.pdf

leetcode-101

LeetCode 101 - A LeetCode Grinding Guide (C++ Version).rar

LeetCode 101 - A LeetCode Grinding Guide (C Version).pdf

leetcode答案-LeetCode:LeetCode问题的问答

leetcode刷题147页（c++版）.rar

算法和数据结构.rar

C++版LeetCode 101算法刷题指南

"LeetCode 101: C语言算法刷题指南，详解思路多样化

最新资源