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

leetcode

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

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

30元优惠券

资源详情

资源推荐

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页未读，继续阅读

猴叻鳢

粉丝: 633
资源: 5

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

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

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

leetcode刷题，C++刷题技巧

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

vscode配置leetcode刷题

leetcode刷题手册c++版

leetcode刷题 vscode

如何在idea上leetcode刷题

用c++写一个leetcode题目：接雨水

python leetcode刷题指南

leetcode刷题java顺序

leetcode刷题指南

c++ kmp算法字符匹配_LeetCode笔记：字符串匹配——KMP算法

leetcode刷题 哈希表 c++

如何在LeetCode快速刷题

python leetcode 刷题主函数怎么写

leetcode c++ 刷题避坑指南

leetcode java 刷题指南

vscode安装leetcode刷题

vs code中的leetcode怎么用

最新资源

leetcode刷题哈希表 c++