LeetCode 101道题详解：C++刷题指南

需积分: 1 170 浏览量更新于2024-06-16 收藏 3.56MB PDF 举报

"《LeetCode 101：和你一起你轻松刷题（C++版）》是一本专为有一定C++编程基础但缺乏LeetCode刷题经验的读者设计的教科书和工具书。作者高畅在2018年为了准备实习秋招，自学并整理了大量的LeetCode题目，但发现缺少系统的归纳与详解。经过一年的努力，他在2019年将这些题目精选出101道，以简洁形式编撰成书，旨在帮助读者快速掌握算法和数据结构的基础。书中详细讲解了刷LeetCode时常用的技术策略，按照算法和数据结构划分了15个章节，每个章节都围绕特定主题深入剖析，使读者能够通过实践提升技能。作者选择C++作为主要编程语言，因为其广泛应用于IT行业。尽管书中大部分算法和数据结构的概念在Java中也有对应，但对于Python或其他语言的用户，由于语法差异，可能需要自行调整理解和应用。值得注意的是，虽然101道题目旨在精简学习路径，但作者意识到这可能会限制读者对算法和数据结构的全面理解。因此，每个章节末尾都提供了推荐的额外练习题，配有解法提示，鼓励读者在理解理论之后深化实践。如果读者反响热烈，作者计划后续添加更多题目的解析。这本书的目标不仅是教授C++编程，而是提供一种系统化的学习方法，以增强读者在职场中的竞争力。作者强调，虽然书中的语法解释不会过于详尽，但仍采用了一些C++11及更新版本的特性，确保内容与时俱进。截至2019年底，本书已经发布正式版1.08，成为了LeetCode爱好者和程序员提升自我、准备面试的实用指南。"

3.3 归并两个有序数组 – 10/143 –

3.3 归并两个有序数组

88. Merge Sorted Array (Easy)

题目描述

给定两个有序数组，把两个数组合并为一个。

输入输出样例

输入是两个数组和它们分别的长度 m 和 n。其中第一个数组的长度被延长至 m + n，多出的

n 位被 0 填补。题目要求把第二个数组归并到第一个数组上，不需要开辟额外空间。

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

Output: nums1 = [1,2,2,3,5,6]

题解

因为这两个数组已经排好序，我们可以把两个指针分别放在两个数组的末尾，即 nums1 的

m − 1 位和 nums2 的 n − 1 位。每次将较大的那个数字复制到 nums1 的后边，然后向前移动一位。

因为我们也要定位 nums1 的末尾，所以我们还需要第三个指针，以便复制。

在以下的代码里，我们直接利用 m 和 n 当作两个数组的指针，再额外创立一个 pos 指针，起

始位置为 m + n − 1。每次向前移动 m 或 n 的时候，也要向前移动 pos。这里需要注意，如果 nums1

的数字已经复制完，不要忘记把 nums2 的数字继续复制；如果 nums2 的数字已经复制完，剩余

nums1 的数字不需要改变，因为它们已经被排好序。



注意这里我们使用了 ++ 和--的小技巧：a++ 和 ++a 都是将 a 加 1，但是 a++ 返回值为 a，而

++a 返回值为 a+1。如果只是希望增加 a 的值，而不需要返回值，则推荐使用 ++a，其运行速度

会略快一些。

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {

int pos = m-- + n-- - 1;

while (m >= 0 && n >= 0) {

nums1[pos--] = nums1[m] > nums2[n]? nums1[m--]: nums2[n--];

}

while (n >= 0) {

nums1[pos--] = nums2[n--];

}

3.4 快慢指针

142. Linked List Cycle II (Medium)

题目描述

给定一个链表，如果有环路，找出环路的开始点。

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

题目描述

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

剩余148页未读，继续阅读

猴叻鳢

粉丝: 695

LeetCode 101道题详解：C++刷题指南

LeetCode 101：轻松刷题指南（C++版）

谷歌高畅LeetCode刷题指南：C++版101题详解

My_leetcode代码库：系统化开源leetcode刷题

LeetCode 101：和你一起你轻松刷题（C++）.zip

leetcode_101：LeetCode 101：和你一起你轻松刷题（C ++）

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

leetcode中国-LeetCode101:《LeetCode101》例题及练习题

leetcode530-Leetcode:Leetcode刷题记录

LeetCode算法题解：C++程序员的刷题宝典

掌握LeetCode算法: Python实现与技巧

最新资源