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

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

身份认证购VIP最低享 7 折!

30元优惠券

资源详情

资源推荐

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 - A LeetCode Grinding Guide (C Version).pdf

在SQL当中regexp '^[a-zA-Z]+[a-zA-Z0-9_\\.\\/\\-]*@leetcode\\.com$'什么意思

a leetcode grinding guide java

idea leetcode-edito乱码

在SQL当中'^[a-zA-Z]+[a-zA-Z0-9_\\.\\/\\-]*@leetcode\\.com$'什么意思

regexp '^[a-zA-Z]+[a-zA-Z0-9_\\.\\/\\-]*@leetcode\\.com$'什么意思

leetcode 101:和你一起你轻松刷题(c++) pdf

pycharm的leetcode插件怎么用

https://leetcode-cn.com/tag/dynamic-programming/

vscode配置leetcode c++

leetcode题目及答案pdf c++版本 csdn

leetcode hot100 随机一道题以及c++解法

leetcode-5:实现链表的首尾链接

vscode刷leetcode使用c++

leetcode 101

哪些网站可以练习sql

leetcode hot100 随机一道题以及c++代码解法

LeetCode67.二进制求和 用c++写出，确保可以运行

最新资源

LeetCode67.二进制求和用c++写出，确保可以运行