算法笔记
算法笔记
参考资料：labuladong 算法网站、代码随想录网站、B 站灵茶山艾府以及其他优质网络资料。语言以 C++、python 为主。
算法思想
双指针
双指针主要有：同向双指针（滑动窗口） 、相向双指针
两数之和 - 有序数组
给你一个下标从 1 开始的整数数组
numbers，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数target的两个数。如果设这两个数分别是numbers[index1]和numbers[index2]，则1 <= index1 < index2 <= numbers.length。以长度为 2 的整数数组
[index1, index2]的形式返回这两个整数的下标index1和index2。你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1：
输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。示例 2：
输入：numbers = [2,3,4], target = 6 输出：[1,3] 解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。示例 3：
输入：numbers = [-1,0], target = -1 输出：[1,2] 解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。提示：
2 <= numbers.length <= 3 * 104-1000 <= numbers[i] <= 1000numbers按 非递减顺序 排列-1000 <= target <= 1000- 仅存在一个有效答案
思路：因为数组是有序的，所以考虑用双指针，用两个指针 left 和 right 分别维护最小元素和最大元素。两个元素相加大于 target ， right 指针向左移；两个元素相加小于 target ， left 指针向右移。
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int n = numbers.size();
int l = 0;
int r = n - 1;
while(l < r)
{
if(numbers[l] + numbers[r] == target) break;
if(numbers[l] + numbers[r] < target) l++;
if(numbers[l] + numbers[r] > target) r--;
}
return {l + 1, r + 1};// 列表初始化语法 编译器自动帮你生成了一个 vector<int>
}
};三数之和
给你一个整数数组
nums，判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != k且j != k，同时还满足nums[i] + nums[j] + nums[k] == 0。请你返回所有和为0且不重复的三元组。** 注意：** 答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。示例 2：
输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。示例 3：
输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。提示：
3 <= nums.length <= 3000-105 <= nums[i] <= 105
思路：三数之和可以转化为两数之和。其中一个数 num[i] 固定后，就变成了两数之和， target 为 -nums[i] 。 nums[l] + nums[r] == -nums[i] 另外 nums 不是有序的，所以先要做个排序。还要注意不能有重复的三元组（元素不可以重复，顺序无所谓）。可以看示例一，不仅要去重 nums[i] 还要去重 nums[l] 和 nums[r] 。
如何去重？
去重
nums[i]比较简单：枚举nums[i]时判断下当前的nums[i]是否和上一个nums[i]相等。去重
nums[l] nums[r]：当找到合法的三元组后，两个指针都需要进行移动。移动前需要去重nums[l]和nums[r]。因为已经排过序了，重复的元素肯定是挨着的，所以对l r进行while循环，将l r指针放到最后一个重复元素上，再进行指针移动。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
sort(nums.begin(), nums.end()); //nums数组排序
int n = nums.size();
for(int i = 0; i < n - 2; i++) //如果直接写nums.size()-2，可能发生无符号下溢，导致循环异常。先用n保存下nums的size。
{
int x = nums[i];
int l = i + 1;
int r = nums.size() - 1;
if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重。
while (l < r)
{
if(x + nums[l] + nums[r] == 0) //找到三元组
{
ans.push_back({x, nums[l], nums[r]});
// 去重：跳过重复的 nums[l]
while (l < r && nums[l] == nums[l + 1]) {
l++;
}
// 去重：跳过重复的 nums[r]
while (l < r && nums[r] == nums[r - 1]) {
r--;
}
// 找到答案后 两个指针都要移动。
l++;
r--;
}
else if(x + nums[l] + nums[r] > 0) r--;
else l++;
}
}
return ans;
}
};该题还有两个优化思路：
- x 和剩下的最小的两个数加起来大于 0 那么后面都大于 0，不用再循环
nums[i] - x 和剩下的最大的两个数加起来小于 0 那么前面都大于 0，不用再循环
nums[l]nums[r]
// 核心代码模式
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
sort(nums.begin(), nums.end()); //nums数组排序
int n = nums.size();
for(int i = 0; i < n - 2; i++)
{
int x = nums[i];
int l = i + 1;
int r = n - 1;
//在遍历l和r前可以做些判断。
if (x + nums[i + 1] + nums[i + 2] > 0) break;
if (x + nums[n - 1] + nums[n - 2] < 0) continue;
if (i > 0 && nums[i] == nums[i - 1]) continue; // 三元组不能重复。
while (l < r)
{
if(x + nums[l] + nums[r] == 0) //找到三元组
{
ans.push_back({x, nums[l], nums[r]});
// 去重：跳过重复的 nums[l]
while (l < r && nums[l] == nums[l + 1]) {
l++;
}
// 去重：跳过重复的 nums[r]
while (l < r && nums[r] == nums[r - 1]) {
r--;
}
// 找到答案后 两个指针都要移动。
l++;
r--;
}
else if(x + nums[l] + nums[r] > 0) r--;
else l++;
//需要用else if 因为如果第一个if条件成立，还是会执行后面两个if，指针会发生意料之外的移动，逻辑不清晰，会导致意外的错误。
// if(x + nums[l] + nums[r] > 0) r--;
// if(x + nums[l] + nums[r] < 0) l++;
}
}
return ans;
}
};盛最多水的容器
给定一个长度为
n的整数数组height。有n条垂线，第i条线的两个端点是(i, 0)和(i, height[i])。找出其中的两条线，使得它们与
x轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
** 说明：** 你不能倾斜容器。
示例 1：
img 输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。示例 2：
输入：height = [1,1] 输出：1提示：
n == height.length2 <= n <= 1050 <= height[i] <= 104
思路：这道题要求的是容器能够盛下的最大水量。对于任意两条竖线组成的容器来说，盛水量由两个因素决定：一是左右两条边中较短的那条边，二是两条边之间的距离。
如果直接枚举所有可能的左右边界，需要使用两层循环，时间复杂度是 O(n^2) ，效率较低。因此可以使用双指针进行优化。
我们维护两个指针 l 和 r ，分别指向数组的最左端和最右端。容器的容量取决于较短的那条边。假设当前右边的高度更短，如果固定右边不动，让左边指针向右移动，那么容器的宽度一定会变小，而高度仍然不会超过右边这条短边，所以面积不可能变得更大。因此，要想找到比当前容器更大的面积，肯定不能有这条短的线。所以，每次比较左右两边的高度。也就是说，哪边更短，就移动哪边。这样可以跳过大量不可能成为最大面积的情况。
代码：
class Solution {
public:
int maxArea(vector<int>& height) {
int n = height.size();
int l = 0;
int r = n - 1;
int ans = 0;
while(l < r)
{
int s = min(height[l], height[r])*(r-l);
ans = max(ans, s);
if (height[l] < height[r]) l++;
else r--;
}
return ans;
}
};接雨水
给定
n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。示例 1：
img 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。示例 2：
输入：height = [4,2,0,3,2,5] 输出：9提示：
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
思路：这道题可以先研究每一个位置单独能接多少雨水。
对于第 i 个位置来说，它能接多少水，取决于左右两边的边界高度。具体来说，当前位置的水位不能超过左边最高柱子和右边最高柱子中较矮的那个，否则水就会从较矮的一边流出去。(为啥必须是最高柱子，以某个位置的左边为例，如果不是最高，还能盛水；如果超过最高，超过的部分就会流出去。) 因此可以开两个数组来维护这两个值。先从左往右遍历，求出每个位置左边的最高柱子；然后从右往左遍历，求出每个位置右边的最高柱子。最后再遍历每一个位置，计算当前位置能接的雨水量，把所有位置能接的雨水量加起来，就是答案。
每个位置能接多少水，取决于它左边最高柱子和右边最高柱子中较矮的那个边界。先用前缀最大值数组
pre维护每个位置左侧最高柱子，再用后缀最大值数组suf维护每个位置右侧最高柱子，最后逐个位置累加min(pre[i], suf[i]) - height[i]即可。
代码：
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
if (n == 0) return 0;
vector<int> pre(n, 0);
vector<int> suf(n, 0);
pre[0] = height[0];
suf[n - 1] = height[n - 1];
int ans = 0;
for(int i = 1; i < n; i++)
{
pre[i] = max(pre[i-1], height[i]);
}
for (int i = n - 2; i >= 0; i--)
{
suf[i] = max(suf[i+1], height[i]);
}
for (int i = 0; i < n; i++)
{
int s = min(pre[i], suf[i]) - height[i];
ans += s;
}
return ans;
}
};优化：可以用双指针来优化空间。前缀最大值和后缀最大值数组，本质上只是为了知道当前位置左右两边的最高柱子。双指针不再提前把每个位置的 pre[i] 、 suf[i] 都存下来，而是一边移动指针，一边维护当前的 leftMax 和 rightMax 。因此可以把空间从 O(n) 优化到 O(1) 。
关键问题是：什么时候移动左指针，什么时候移动右指针？
如果： leftMax < rightMax ，说明左边的最高边界更低，而右边已经有一个比它更高的边界了。此时 l 指向的当前位置的水位一定由 leftMax 决定，和右边后面还有没有更高的柱子无关。当前位置的接水容量就是 leftMax - height[l] ，然后左指针往右移。
leftMax > rightMax ， r 指向的当前位置的接水容量就是 rightMax - height[r] ，然后右指针往左移。
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
int l = 0;
int r = n - 1;
int leftMax = 0;
int rightMax = 0;
int ans = 0;
while (l < r) {
leftMax = max(leftMax, height[l]);
rightMax = max(rightMax, height[r]);
if (leftMax < rightMax) {
ans += leftMax - height[l];
l++;
} else {
ans += rightMax - height[r];
r--;
}
}
return ans;
}
};长度最小的子数组
给定一个含有
n个正整数的数组和一个正整数target。找出该数组中满足其总和大于等于
target的长度最小的 子数组[numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度 **。** 如果不存在符合条件的子数组，返回0。示例 1：
输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。示例 2：
输入：target = 4, nums = [1,4,4] 输出：1示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1] 输出：0提示：
1 <= target <= 1091 <= nums.length <= 1051 <= nums[i] <= 104
思路：子数组的定义：数组中连续的非空元素序列。
暴力做法就是两层 for 循环枚举子数组的左端点和右端点。这种做法没有用到数组元素是正整数的性质。
这道题用的是滑动窗口的思路，用两个指针维护窗口的左右边界，当窗口元素和大于 target ，就缩小窗口， l++ ；小于 target ，就扩大窗口， r++ 。
比如 [2,3,1,2,4,3] ， 1,2,4 是以 4 为右端点的满足条件的最短窗口。枚举下一个右端点 3 ，由于数组元素是正数，所以只需考虑 2,4,3 4,3 3 这三个序列。（枚举右端点，移动左端点。）大概的思路就是枚举每个元素，找到以该元素为右端点的满足条件的最短窗口，找到每个右端点对应的最短窗口，就更新答案。当然滑动窗口不一定会遍历到 “每一个右端点对应的最短子数组”，但它一定能找到全局最短子数组。
举个例子就知道了。比如 [2,2,3,1,4] 。 target 为 5。以元素 3 为右端点的最短窗口是 [2,3] 。当枚举下一个元素 1 时， l 指向 3 ； r 指向 1 。和小于 5 ，所以会继续枚举下一个元素 4 。这时候我就没有遍历到以 1 为右端点的最短窗口。 （2，3，1） 为什么枚举下一个元素 1 的时候， l 不能指向 2 呢，因为 「2，3」 符合条件， 「2，3，1」 肯定符合，得到的不是全局最短窗口。
还有个小细节，窗口大小是 r-l 还是 r - l + 1 。取决于你的 r++ 是放到更新 ans 的后面，还是前面。放在前面，窗口就是 [l,r) 放在后面，窗口就是 [l,r] 。
思考：是不是也可以枚举左端点，移动右端点。代码如何实现？
代码：
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int l = 0;
int r = 0;
int s = 0;
int ans = INT_MAX; //C++标准库的内置常量，代表int所能表示的最大数值。
while (r < nums.size())
{
s += nums[r];
while (s >= target)
{
ans = min(ans, r - l + 1);
s -= nums[l];
l++;
}
r++;
} //这种情况滑动窗口的区间[l,r]
/*
while (r < nums.size())
{
s += nums[r];
r++;
while (s >= target)
{
ans = min(ans, r - l);//不是r-l+1 target = 7 nums = [7] 此时r = 1;
s -= nums[l];
l++;
}
// 这种情况滑动窗口的区间[l,r)
}
*/
return ans < INT_MAX ? ans : 0;
}
};时间复杂度分析：指针
l, r不会回退（它们的值只增不减），所以字符串 / 数组中的每个元素都只会进入窗口一次，然后被移出窗口一次，不会说有某些元素多次进入和离开窗口，所以算法的时间复杂度就和字符串 / 数组的长度成正比。复杂度是 $O (N)$现在梳理下自己的理解：算时间复杂度就是算代码执行的次数。可以固定某个
r，看一下l的移动次数。把所有r对应的l移动次数加起来，除以n，得到的是 平均每个r会让l移动几次。l总的移动次数肯定不超过n，简单认为所有r对应的l移动次数加起来就是n，得到平均每个r会让l移动1次。然后外层 while 循环，会执行n次。所以总的执行次数就是n*1。复杂度是 $O (N)$ 。
滑动窗口思想：
维护一个窗口，这个窗口在数组或字符串上滑动，从而找到满足特定条件的子数组或子字符串。具体来说，算法会设置两个指针，一个指向窗口的左边界，一个指向窗口的右边界。开始时，窗口的大小为 0，然后右指针向右移动扩大窗口，直到满足特定条件为止。一旦满足了条件，算法会根据问题的要求更新结果。（比如记录满足条件的子数组的长度、计算子数组的和。）然后左指针向右移动缩小窗口，直到不再满足条件为止。不断重复该过程，直到右指针遍历完整个数组或字符串。
乘积小于 K 的子数组
给你一个整数数组
nums和一个整数k，请你返回子数组内所有元素的乘积严格小于k的连续子数组的数目。示例 1：
输入：nums = [10,5,2,6], k = 100 输出：8 解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2]、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。 需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。示例 2：
输入：nums = [1,2,3], k = 0 输出：0提示:
1 <= nums.length <= 3 * 1041 <= nums[i] <= 10000 <= k <= 106
思路：这道题和长度最小的子序列思路是类似的。不满足条件就扩大窗口；满足条件就缩小窗口直到不满足条件。这里的条件指的是窗口内元素乘积大于等于 k。
这道题关键是如何得到以 r 为右端点的满足条件的子数组数目。
当窗口 [l, r] 的乘积已经 < k 时，说明下面这些 以 r 结尾的子数组 都满足条件：
nums[r]
nums[r-1 ... r]
nums[r-2 ... r]
...
nums[l ... r]数量为： r - l + 1
也可以通过例子得到这个关系：比如 [10,5,2,6] ， [10,5,2] 满足条件，缩小窗口，变成 [5,2] 。不满足条件了，那此时就得到了以 2 为右端点满足条件的子数组个数： 2（「2」「5，2」） 。
还需要处理 k <= 1 的情况。因为 nums[i] 都是正整数，乘积最小也是 1 ，所以如果 k <= 1 ，不可能有乘积 < k 的子数组。如果不单独处理这种情况，就会一直执行第二个 while 循环。
代码：
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
int l = 0;
int r = 0;
int s = 1;
int ans = 0;
int n = nums.size();
// 满足条件就缩小窗口，这里的条件指的是大于等于k。
// 注意讨论k<=1的情况，此时没有满足条件的子数组。
if (k <= 1) return 0;
while (r < n)
{
s *= nums[r];
while(s >= k)
{
s /= nums[l];
l++;
}
ans += (r - l + 1);
r++;
}
return ans;
}
};无重复字符的最长子串
给定一个字符串
s，请你找出其中不含有重复字符的 最长子串 的长度。示例 1:
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。示例 2:
输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。提示：
0 <= s.length <= 5 * 104s由英文字母、数字、符号和空格组成
思路：还是滑动窗口思想：满足条件就缩小窗口，这里的条件指的是：出现了重复字符。所以需要维护一个 hash 数组，记录当前窗口里每个字符出现的次数。而不是整个字符串里的字符出现次数。当右边界的字符次数大于 1 ，就代表此时窗口中有重复字符；需要缩小窗口，左边界的字符次数要 -1 。
小细节： s 由英文字母、数字、符号和空格组成。可以看成 ASCII 字符，一共有 128 个。所以 hash 数组大小就是 128。
代码：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int l = 0;
int r = 0;
int ans = 0;
int hash[128] = {0};//记录每个字符出现的次数。
while (r < s.size())
{
hash[s[r]]++;
while (hash[s[r]] > 1)
{
hash[s[l]]--;
l++;
}
ans = max(ans, r - l + 1);
r++;
}
return ans;
}
};二分查找
很多人写二分容易错在：
left <= right还是left < right；mid命中后应该返回还是继续缩小；left = mid还是left = mid + 1；right = mid还是right = mid - 1；- 最后返回
left还是right； - 重复元素时找第一个还是最后一个。
下面讲解二分查找的一种统一理解方法：红蓝染色法。
它把二分查找看成在一段有序或单调的序列中，寻找 “红色区域” 和 “蓝色区域” 的分界点。
典型抽象：
红红红红红 蓝蓝蓝蓝蓝
↑
要找的边界对于常见的 lower_bound(nums, target) ：
红色：nums[i] < target
蓝色：nums[i] >= target
目标：找到第一个蓝色位置也就是找第一个满足 nums[i] >= target 的下标。
红蓝染色法最常用的是开区间 (left, right) 写法：
找第一个 >= target 的位置：
int lowerBound(const vector<int>& nums, int target) {
int left = -1;
int right = nums.size();
// 循环不变量：
// nums[left] < target，left 是红色边界
// nums[right] >= target，right 是蓝色边界
// left = -1 和 right = n 是虚拟哨兵
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid; // mid 是红色
} else {
right = mid; // mid 是蓝色
}
}
return right; // 第一个蓝色位置
}循环结束条件： left + 1 == right
此时红蓝边界已经相邻：
... red left | right blue ...所以 right 就是第一个蓝色位置。
我更喜欢 [left, right] 闭区间的写法。
int lowerBound(const vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
// 循环不变量：
// [0, left - 1] 中的元素都 < target，属于红色区域
// [right + 1, n - 1] 中的元素都 >= target，属于蓝色区域
// [left, right] 是还没有确定颜色的区域
while (left <= right) { //区间大小为0时结束循环 结束循环时right+1 == left
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1; // mid 是红色
} else {
right = mid - 1; // mid 是蓝色
}
}
return right + 1 //return left; // 第一个蓝色位置
}循环结束条件： right + 1 == left 。
把握好循环不变量是二分的关键：
红色区域 未知区域 蓝色区域
[0 ... left-1] [left ... right] [right+1 ... n-1]二分的过程，本质上就是不断压缩中间的未知区域。
所以二分结束后：未知区域没有了。
红色区域 蓝色区域
[0 ... right] [right+1 ... n-1]思考：如果
nums[mid] < target改为nums[mid] <= target，会发生什么？返回的是第一个 >
target的位置。为什么呢？因此循环不变量变成：
[0, left - 1] 中的元素都 <= target，属于红色区域 [right + 1, n - 1] 中的元素都 > target，属于蓝色区域 最后返回的right+1，是第一个大于target的位置。
二分查找代码细节：
middle的求法 不要用(left+right)/2，容易溢出。用left+(right-left)/2>>1等同于对正整数向下取整除以 2。
四种边界条件：
只要会写 lowerBound ，就能推出四种常见边界。
- 第一个
>= target的位置
int firstGe(const vector<int>& nums, int target) {
return lowerBound(nums, target);
}- 第一个
> target的位置
int firstGt(const vector<int>& nums, int target) {
return lowerBound(nums, (long long) target + 1);
}- 最后一个
< target的位置
int lastLt(const vector<int>& nums, int target) {
return lowerBound(nums, target) - 1;
}- 最后一个
<= target的位置
int lastLe(const vector<int>& nums, int target) {
return lowerBound(nums, (long long) target + 1) - 1;
}在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组
nums，和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值
target，返回[-1, -1]。你必须设计并实现时间复杂度为
O(log n)的算法解决此问题。示例 1：
输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]示例 2：
输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]示例 3：
输入：nums = [], target = 0 输出：[-1,-1]提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109nums是一个非递减数组-109 <= target <= 109
思路：开始位置就是第一个大于等于 target 的位置；结束位置就是最后一个小于等于 target 的位置。直接套前面说的四个边界条件就可以了。还有些小细节需要注意：需要讨论特殊情况。比如数组中元素都小于 target ，数组是空的，或得到的结果不是 target 。
代码：
class Solution {
public:
int lowerBound(const vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
// 循环不变量：
// [0, left - 1] 中的元素都 < target，属于红色区域
// [right + 1, n - 1] 中的元素都 >= target，属于蓝色区域
// [left, right] 是还没有确定颜色的区域
while (left <= right) { //区间大小为0时结束循环 结束循环时right+1 == left
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1; // mid 是红色
} else {
right = mid - 1; // mid 是蓝色
}
}
return right + 1; //return left; // 第一个蓝色位置
}
vector<int> searchRange(vector<int>& nums, int target) {
int start = lowerBound(nums, target); //>=target
// 注意不能颠倒顺序写为： if ((nums[start] != target) || start == nums.size() )
//因为如果start=nums.size(),此时nums[start]数组越界了，会报错。
if(start == nums.size() || nums[start] != target) return {-1,-1};
int end = lowerBound(nums, target + 1) - 1;
return {start, end};
}
};寻找峰值
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组
nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。你可以假设
nums[-1] = nums[n] = -∞。你必须实现时间复杂度为
O(log n)的算法来解决此问题。示例 1：
输入：nums = [1,2,3,1] 输出：2 解释：3 是峰值元素，你的函数应该返回其索引 2。示例 2：
输入：nums = [1,2,1,3,5,6,4] 输出：1 或 5 解释：你的函数可以返回索引 1，其峰值元素为 2； 或者返回索引 5， 其峰值元素为 6。提示：
1 <= nums.length <= 1000-231 <= nums[i] <= 231 - 1- 对于所有有效的
i都有nums[i] != nums[i + 1]
思路：因为题目规定用 O(log n) 时间复杂度的算法，所以本题采用二分。因为返回任何一个峰值就可以，所以可以认为数组中就只有一个峰值。还是利用红蓝染色法，红色部分 [0,l-1] 看成峰值左侧元素；蓝色部分 [r+1,n-1] 看成峰值及其峰值右侧元素。利用二分对数组染色，注意提示中有： nums[i] != nums[i + 1] ，所以当 nums[mid] < nums[mid + 1] ，说明 mid 及其左边的元素都在峰值的左侧，染成红色；当 nums[mid] >= nums[mid + 1] ，说明 mid 及其右边的元素在峰值及峰值的右侧，染成蓝色。最终得到的 r+1 就是峰值。
这里还有个问题： r 是 n-1 吗？假如 n-1 位置的元素是峰值，那最后返回 r+1 的值是 n ，数组越界了。所以 r 不是 n-1 。也可以这样想， nums[n-1] > nums[n] ，也就是说 n-1 一定是蓝色。所以直接从 n-2 开始就可以了。也可以这样想， mid 在 [l,r] 之间，如果 r 可以取到 n-1 ， mid 就有可能取到 n-1（l=r时，mid=r=l） ，此时 mid+1 是 n ，数组越界了。
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int n = nums.size();
int l = 0;
int r = n - 2;
while(l <= r)
{
int mid = l + (r - l)/2;
if (nums[mid] < nums[mid + 1]) l = mid + 1;
else r = mid - 1;
}
return r + 1;
}
};寻找旋转排序数组中的最小值
已知一个长度为
n的数组，预先按照升序排列，经由1到n次 旋转 后，得到输入数组。例如，原数组nums = [0,1,2,4,5,6,7]在变化后可能得到：
- 若旋转
4次，则可以得到[4,5,6,7,0,1,2]- 若旋转
7次，则可以得到[0,1,2,4,5,6,7]注意，数组
[a[0], a[1], a[2], ..., a[n-1]]旋转一次 的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]]。给你一个元素值 互不相同 的数组
nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。你必须设计一个时间复杂度为
O(log n)的算法解决此问题。示例 1：
输入：nums = [3,4,5,1,2] 输出：1 解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。示例 2：
输入：nums = [4,5,6,7,0,1,2] 输出：0 解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。示例 3：
输入：nums = [11,13,15,17] 输出：11 解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。提示：
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums中的所有整数 互不相同nums原来是一个升序排序的数组，并进行了1至n次旋转
思路：
仔细看上面的这张图。题目给的数组最终形式就是这两种，要么旋转变换成原先的有序数组，要么就变成断崖的形式。分成两个有序区间。第一个区间的元素都比第二个区间的元素要大。
设 x=nums[mid] 是现在二分取到的数。如何判断 x 和数组最小值的位置关系，谁在左边，谁在右边？（也就是确定染色规则）
把 x 与最后一个数 nums[n−1] 比大小：
如果 x>nums[n−1] ，那么可以推出以下结论：
nums一定被分成左右两个递增段；第一段的所有元素均大于第二段的所有元素；
x在第一段。最小值在第二段。
所以
x一定在最小值的左侧。将mid及其左边元素染成红色。
如果 x≤nums[n−1] ，那么 x 一定在第二段。（或者 nums 就是递增数组，此时只有一段。）
最小值一定在 x 或者 x 右侧。将 mid 及其右边元素染成蓝色。
所以，只需要比较 x 和 nums[n−1] 的大小关系，就间接地知道了 x 和数组最小值的位置关系，从而不断地缩小数组最小值所在位置的范围，二分找到数组最小值。
细节：最后一个数要么是最小值，要么在最小值右侧，所以最后一个数一定是蓝色的。所以二分的时候 r 可以从 n-2 开始。（从 n-1 开始也行。）
代码：
class Solution {
public:
int findMin(vector<int>& nums) {
int n = nums.size();
int l = 0;
int r = n - 2; //n-1也能过，都可以。
int s = nums[n - 1];
while (l <= r)
{
int mid = l + (r - l) / 2;
if(nums[mid] > s)
{
l = mid + 1;
}
else {
r = mid - 1;
}
}
return nums[r + 1];
}
};再来总结下红蓝染色法：
红蓝染色法的出发点是 二分的本质，是把整个区间染成红蓝两色，而我们要找的就是两色的分界点。
具体来说，你需要定义一个「染色规则」—— 一个把每个位置判定为「蓝色」或「红色」的条件，并且这个规则必须满足单调性：数组从左到右，一定是「一段红、一段蓝」, 中间只有一个分界。红色区域代表「不可能是答案 / 在答案左侧」, 蓝色区域代表「可能是答案 / 在答案右侧」(具体哪种含义由题目决定，关键是两色各占一段)。
二分的每一步，就是看
mid应该染成什么颜色：染蓝就把蓝色边界左推，染红就把红色边界右推。当蓝红相遇，分界点就确定了。这套方法最大的好处是: 你只需要想清楚一件事 ——
mid满足什么条件时染蓝。 边界怎么动、最后返回哪个指针，都由模板固定下来，不用再纠结<还是<=、mid还是mid+1这些经典坑。
搜索旋转排序数组
整数数组
nums按升序排列，数组中的值 互不相同 。在传递给函数之前，
nums在预先未知的某个下标k（0 <= k < nums.length）上进行了 向左旋转，使数组变为[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如，[0,1,2,4,5,6,7]下标3上向左旋转后可能变为[4,5,6,7,0,1,2]。给你 旋转后 的数组
nums和一个整数target，如果nums中存在这个目标值target，则返回它的下标，否则返回-1。你必须设计一个时间复杂度为
O(log n)的算法解决此问题。示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3 输出：-1示例 3：
输入：nums = [1], target = 0 输出：-1提示：
1 <= nums.length <= 5000-104 <= nums[i] <= 104nums中的每个值都 独一无二- 题目数据保证
nums在预先未知的某个下标上进行了旋转-104 <= target <= 104
思路：这道题有两种做法。第一种做法很直白，也是我们前面学过的题目的变形。用二分先找到旋转的下标，这样就把区间分成了两个有序区间。然后对比 target 和数组最后一个元素的值，要是比他小，说明 target 在第二段；反之，在第一段。然后问题就转化成在有序区间二分查找元素问题了。
代码如下：
class Solution {
public:
int findMinIndex(vector<int>& nums) {
int n = nums.size();
int l = 0;
int r = n - 2;
int last = nums[n - 1];
// 红色：nums[i] > last，说明在左边大段
// 蓝色：nums[i] <= last，说明在右边小段
// 找第一个蓝色位置，也就是最小值下标
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] > last) {
l = mid + 1; // mid 是红色
} else {
r = mid - 1; // mid 是蓝色
}
}
return l;
}
int binarySearch(vector<int>& nums, int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
return mid;
}
}
return -1;
}
int search(vector<int>& nums, int target) {
int n = nums.size();
int p = findMinIndex(nums); // 最小值下标
if (target <= nums[n - 1]) {
// target 在右边小段 [p, n - 1]
return binarySearch(nums, p, n - 1, target);
} else {
// target 在左边大段 [0, p - 1]
return binarySearch(nums, 0, p - 1, target);
}
}
};其实一次二分就可以解决问题了。还是利用红蓝染色法，红色区域一定在 target 左边；蓝色区域 target 位置以及 target 右边。我们二分要找的就是第一个蓝色位置。
难点是染色规则：什么时候染成蓝色？什么时候染成红色？
分情况讨论：
- 当
target在第一段时，如果nums[mid]大于last，说明nums[mid]也在第一段。那么比较下nums[mid]和target，如果>=（注意是大于等于，因为我们规定的蓝色区域是target位置以及target右边），就染成蓝色。如果nums[mid]小于last，说明在第二段，还是要染成蓝色。 - 当
target在第二段时，如果nums[mid]大于last，说明nums[mid]在第一段，肯定染成红色；如果nums[mid]小于last，说明在第二段，那么比较下nums[mid]和target，如果>=，就染成蓝色。
因为染色规则有些复杂，所以将规则封装成一个函数。下面代码是将染蓝封装成函数：
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
int last = nums[n - 1];
int l = 0;
int r = n - 1;
auto isBlue = [&](int i) {
// target 在左侧大段
if (target > last) {
if (nums[i] > last) {
// nums[i] 也在左侧大段，正常比较
return nums[i] >= target;
} else {
// nums[i] 在右侧小段，位置上已经在 target 后面，染蓝
return true;
}
}
// target 在右侧小段
else {
if (nums[i] > last) {
// nums[i] 在左侧大段，位置上还在 target 前面，染红
return false;
} else {
// nums[i] 也在右侧小段，正常比较
return nums[i] >= target;
}
}
};
// 找第一个蓝色位置
while (l <= r) {
int mid = l + (r - l) / 2;
if (isBlue(mid)) {
r = mid - 1;
} else {
l = mid + 1;
}
}
// l 是第一个蓝色位置
if (l == n || nums[l] != target) {
return -1;
}
return l;
}
};思考：也可以将染红封装成一个函数。
auto isRed = [&](int i) {
// target 在左侧大段
if (target > last) {
if (nums[i] > last) {
// nums[i] 也在左侧大段，正常比较
return nums[i] < target;
} else {
// nums[i] 在右侧小段，位置上已经在 target 后面，染蓝
return false;
}
}
// target 在右侧小段
else {
if (nums[i] > last) {
// nums[i] 在左侧大段，位置上还在 target 前面，染红
return true;
} else {
// nums[i] 也在右侧小段，正常比较
return nums[i] < target;
}
}
};链表相关
反转链表
给你单链表的头节点
head，请你反转链表，并返回反转后的链表。示例 1：
img 输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]示例 2：
img 输入：head = [1,2] 输出：[2,1]示例 3：
输入：head = [] 输出：[]提示：
- 链表中节点的数目范围是
[0, 5000]-5000 <= Node.val <= 5000** 进阶：** 链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
思路：我们需要维护三个指针：
prev：当前节点反转后应该指向的结点（也就是他前一个结点）。cur：当前正在处理的结点nxt：临时保存当前结点的next结点
边界条件判断： prev 初始应该是 null ，因为头结点的前一个结点是空； cur 应该是 head ；遍历完所有的结点后， prev=cur，cur=null （因为最后一个结点的 next 是 null ）。
流程其实是固定的：
nxt = cur.nextcur.next = prevprev = curcur = nxt
为什么需要单独维护一个 nxt 指针呢，因为当前结点的 next 指针指向上一个结点后， next 原先保存的数据就没了，意味着链表断裂了，没办法继续遍历链表了（遍历链表就是通过 cur = nxt 来实现的）。
代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* cur = head;
ListNode* nxt = nullptr;
while(cur != nullptr)
{
nxt = cur->next;
cur->next = prev;
prev = cur;
cur = nxt;
}
return prev;
}
};反转链表 II
给你单链表的头指针
head和两个整数left和right，其中left <= right。请你反转从位置left到位置right的链表节点，返回 反转后的链表 。示例 1：
img 输入：head = [1,2,3,4,5], left = 2, right = 4 输出：[1,4,3,2,5]示例 2：
输入：head = [5], left = 1, right = 1 输出：[5]提示：
- 链表中节点数目为
n1 <= n <= 500-500 <= Node.val <= 5001 <= left <= right <= n进阶： 你可以使用一趟扫描完成反转吗？
思路：其实这道题和上一道题是类似的，只不过这道题限制了反转链表的起始终止位置 [left, right] 。链表反转后，此时 pre 指向终止结点 4 ， cur 指向终止位置后面的第一个结点 5 。这个非常非常重要。然后需要把 pre 接到结点 1 的后面，把 left 节点 2 接到 cur 的前面。
还需要分析一个边界情况：当 left 等于第一个结点时，反转之后， head 头结点就会改变，需要返回新的头。如何优化呢？
用虚拟头节点消除边界：引入一个虚拟头节点（dummy node），让它指向原来的 head 。 dummy → 1 → 2 → 3 → 4 → 5
这样无论反转段是否包含真正的头节点， dummy 始终在最前面、永远不会被反转。最后返回 dummy.next 就一定是正确答案。
接下来思考如何定位到到 left 对应的结点呢？实际上需要定位到 left 前一个结点。用 for 循环，循环次数就是 left-1 次。得到 left 前一个结点 prev ， prev->next 就是 left 对应的结点。
之后就是上一道题的思路了，每次循环修改一个结点的 next 指针。反转之后再进行拼接， prev->next->next = cur prev->next = pre 。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode* dummy = new ListNode();
dummy->next = head;
head = dummy;
ListNode* prev = dummy; //头结点 定位到某个元素需要用
// 1. 定位到反转区间前一个节点，也就是第 left - 1 个节点
for (int i = 0; i < left - 1; i++) {
prev = prev->next;
}
// 2. start 是待反转区间的第一个节点
ListNode* start = prev->next;
// 3. 链表反转，反转 right - left + 1 个节点
ListNode* pre = nullptr;//pre初始化成谁其实都可以，但逻辑上初始化成nullptr更清晰。pre代表当前结点的前一个节点，因为翻转的是一个区间，start节点2的前一个节点（翻转后next指向的那个节点）不是1，而是5。设置成nullptr，等最后拼接链表的时候还会再设置。
// ListNode* pre = prev;
ListNode* cur = start;
ListNode* nxt = nullptr; // 临时保存当前结点的next结点，可以先初始化为0
for (int i = 0; i < right - left + 1; i++) {
ListNode* nxt = cur->next; // 暂存下一个节点
cur->next = pre; // 当前节点反向指
pre = cur; // pre 前移
cur = nxt; // cur 前移
}
// 4. 接线
prev->next = pre; // 反转区间前驱连接新头
start->next = cur; // 原来的区间头，现在变成区间尾，连接后继
return dummy->next;
}
};K 个一组翻转链表
给你链表的头节点
head，每k个节点一组进行翻转，请你返回修改后的链表。
k是一个正整数，它的值小于或等于链表的长度。如果节点总数不是k的整数倍，那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
img 输入：head = [1,2,3,4,5], k = 2 输出：[2,1,4,3,5]示例 2：
img 输入：head = [1,2,3,4,5], k = 3 输出：[3,2,1,4,5]提示：
- 链表中的节点数目为
n1 <= k <= n <= 50000 <= Node.val <= 1000** 进阶：** 你可以设计一个只用
O(1)额外内存空间的算法解决此问题吗？
思路：有了前两道题的基础，这道题其实就是第二道题的变形，第二道题是翻转某个区间的链表。这道题是翻转完某个区间的链表，再接着翻转另一个区间的链表，重复进行。
还需要注意：反转一组之后，这一组的新头需要接回前面的链表，所以必须有一个指针 grouprev 记录当前这一组前面的那个节点。
代码：
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* dummy = new ListNode();
dummy->next = head;
ListNode* grouprev = dummy;
while (1)
{
//判断下后面还够不够k个节点了
ListNode* check = grouprev;
for (int i = 0; i < k; i++)
{
check = check->next;
if (check == nullptr) return dummy->next;
}
//翻转某组的链表
//start该组的第一个元素 grouprev该组的前一个元素
ListNode* start = grouprev->next;
//翻转k个节点
ListNode* pre = nullptr;
ListNode* cur = start;
ListNode* nxt = nullptr;
for (int i = 0; i < k; i++)
{
nxt = cur->next;
cur->next = pre;
pre = cur;
cur = nxt;
}
//拼接链表
grouprev->next = pre;
start->next = cur;
//更新grouprev
grouprev = start;
}
}
};问题：
- 为什么要维护每组前一个节点，一次循环得到的
cur不就是下次要循环的首节点嘛？
维护每组的前一个节点，是为了翻转完该组之后，将原先的最后一个节点和每组前一个节点进行拼接的。如果不用 grouprev 记录，翻转完链表后就没办法和上一组进行拼接了。
接下来我们来看几道快慢指针解决链表问题。
链表的中间结点
给你单链表的头结点
head，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
示例 1：
img 输入：head = [1,2,3,4,5] 输出：[3,4,5] 解释：链表只有一个中间结点，值为 3 。示例 2：
img 输入：head = [1,2,3,4,5,6] 输出：[4,5,6] 解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。提示：
- 链表的结点数范围是
[1, 100]1 <= Node.val <= 100
思路：常规做法就是遍历一次链表，确定长度 n ；再遍历一次找到中间结点，也就是 n/2 。总的需要遍历两次。
如何只遍历一次呢？用快慢指针思想：
想象两个人在同一起点跑步，一个人速度是另一个人的两倍。当快的人到达终点时，慢的人恰好在中点 —— 因为同样的时间里，快的人走了全程，慢的人只走了一半。
设两个指针都从 head 出发， slow 每次走 1 步， fast 每次走 2 步。当 fast 走到链表末尾时， slow 正好停在中间。这里的链表末尾需要分情况讨论一下：
n为奇数，fast位于最后一个结点时，slow刚好在中点。n为偶数，fast位于最后一个结点的下一个结点时，slow刚好在中点。
代码：
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr )
//注意两个条件的顺序不能变，不能写成：while (fast->next != nullptr && fast != nullptr)。因为当fast==nullptr时，fast->next会报错。
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
};环形链表
给你一个链表的头节点
head，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪
next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回
true。 否则，返回false。示例 1：
img 输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。示例 2：
img 输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。示例 3：
img 输入：head = [1], pos = -1 输出：false 解释：链表中没有环。提示：
- 链表中节点的数目范围是
[0, 104]-105 <= Node.val <= 105pos为-1或者链表中的一个 有效索引 。** 进阶：** 你能用
O(1)（即，常量）内存解决此问题吗？
思路：这道题同样需要用到快慢指针。如果链表存在环，那么快指针肯定会追上慢指针。
为什么快指针一定追得上，不会「跳过」慢指针？
代码：
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr )
{
slow = slow->next;
fast = fast->next->next;
if (fast == slow) return true;
}
return false;
}
};环形链表 II
给定一个链表的头节点
head，返回链表开始入环的第一个节点。 如果链表无环，则返回null。如果链表中有某个节点，可以通过连续跟踪
next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。如果pos是-1，则在该链表中没有环。注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。
示例 1：
img 输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。示例 2：
img 输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。示例 3：
img 输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。提示：
- 链表中节点的数目范围在范围
[0, 104]内-105 <= Node.val <= 105pos的值为-1或者链表中的一个有效索引** 进阶：** 你是否可以使用
O(1)空间解决此题？
思路：这个题和上题的区别是要找到环的入口。感觉就是考数学，需要推导出一个公式，只能记住解题思路。
从 head 到环入口的距离为 a （直线段的长度）。从环入口到「快慢指针相遇点」的距离为 b （沿着环走的方向）。从相遇点再走回到环入口的距离为 c 。那么整个环的周长就是 b + c 。
head ──a──> 入口 ──b──> 相遇点 ──c──> (回到入口)
└────── 环周长 = b + c ──────┘
两指针都从 head 出发，到相遇时：
慢指针走的总距离 = a + b 。它走了直线段 a ，再在环里走了 b 到相遇点。
快指针走的总距离 = a + b + k(b + c) ，其中 k 是快指针在环里多绕的整数圈数（ k ≥ 1 ）。
而快指针速度是慢指针的两倍，所以快走的距离 = 2 × 慢走的距离：
a + b + k(b + c) = 2(a + b) 整理一下得到： a = (k - 1)(b + c) + c
这个式子本质含义：从 head 走 a 步到入口，等价于，从相遇点走 c 步（外加若干整圈）也到入口。
具体算法是什么样子呢？找到相遇点后，让一个指针指向 head ，另一个指针指向相遇点。两个指针每次走一步，直到相遇，相遇点就是入口。
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* low = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr)
{
low = low->next;
fast = fast->next->next;
if (low == fast)
{
low = head;
while(low != fast)
{
low = low->next;
fast = fast->next;
}
return low;
}
}
return nullptr;
}
};思考： 为什么快慢指针相遇的时候，慢指针没有走完一整圈。
可以考虑一个极限情况：快指针在慢指针前面一个单位。此时快指针距离慢指针有
n-1个单位。每走一步距离就缩小1，所以两者相遇的时候快指针走了n-1步。（这里的步不是指一个单位，而是两个单位。快指针走一步，需要跳两个结点）慢指针走了n-1，没有走完一整圈。
重排链表
给定一个单链表
L的头节点head，单链表L表示为：L0 → L1 → … → Ln - 1 → Ln请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
img 输入：head = [1,2,3,4] 输出：[1,4,2,3]示例 2：
img 输入：head = [1,2,3,4,5] 输出：[1,5,2,4,3]提示：
- 链表的长度范围为
[1, 5 * 104]1 <= node.val <= 1000
思路：重排链表这道题综合性比较强，需要用找中间结点、反转链表、拼接链表操作。代码不是很难写。贴一张 claude 生成的图直观看一下代码逻辑。
代码：
class Solution {
public:
void reorderList(ListNode* head) {
// 找到中间结点
ListNode* low = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr)
{
low = low->next;
fast = fast->next->next;
}
// 断开左右两部分 人为让左半部分大于等于右边部分的长度。
ListNode* start = low->next;
low->next = nullptr;
// 【low+1，end】链表反转
ListNode* pre = nullptr;
ListNode* cur = start;
ListNode* nxt = nullptr;
while(cur != nullptr)
{
nxt = cur->next;
cur->next = pre;
pre = cur;
cur = nxt;
}
//交替拼接链表
ListNode* p1 = head;
ListNode* p2 = pre;
while(p2 != nullptr)//因为左半部分长度大于等于右半部分，所以肯定是右半部分先结束。
{
ListNode* temp1 = p1->next;
ListNode* temp2 = p2->next;
p1->next = p2;
p2->next = temp1;
p1 = temp1;
p2 = temp2;
}
}
};删除链表中的节点
有一个单链表的
head，我们想删除它其中的一个节点node。给你一个需要删除的节点
node。你将 无法访问 第一个节点head。链表的所有值都是 唯一的，并且保证给定的节点
node不是链表中的最后一个节点。删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：
- 给定节点的值不应该存在于链表中。
- 链表中的节点数应该减少 1。
node前面的所有值顺序相同。node后面的所有值顺序相同。自定义测试：
- 对于输入，你应该提供整个链表
head和要给出的节点node。node不应该是链表的最后一个节点，而应该是链表中的一个实际节点。- 我们将构建链表，并将节点传递给你的函数。
- 输出将是调用你函数后的整个链表。
示例 1：
输入：head = [4,5,1,9], node = 5 输出：[4,1,9] 解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9示例 2：
输入：head = [4,5,1,9], node = 1 输出：[4,5,9] 解释：指定链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 ->提示：
- 链表中节点的数目范围是
[2, 1000]-1000 <= Node.val <= 1000- 链表中每个节点的值都是 唯一 的
- 需要删除的节点
node是 链表中的节点 ，且 不是末尾节点
思路：常规的删除结点的操作很简单：找到目标结点 node 的上一个结点 pre ， pre->next = node->next 。这道题有些特殊，你拿不到 head 结点，也就代表你找不到 pre 。那么应该怎么做呢？
采用值覆盖的方式，** 把下一个节点的值复制到当前节点，然后删掉下一个节点：** 把 node->next 的值抄到 node 上（ node->val = node->next->val ）。再让 node 跳过下一个节点（ node->next = node->next->next ），相当于把那个「下一个节点」从链表里摘除。
效果上，从外部看，当前节点的值变成了后继的值、后继被删掉了，整条链表看起来就像「当前这个值被删除了」一样。本质是删了后继节点，但让它顶替了自己要删的位置。
思考：为什么题目要保证「不是尾节点」
如果
node是尾节点，它的next是nullptr，没有「下一个节点」可以复制和顶替，这个偷梁换柱的技巧就失效了。所以题目特意限定待删节点不是尾节点，保证node->next一定存在。这也提示你：这个技巧对尾节点无效，尾节点的删除仍然必须靠传统的「找前驱」方式。
代码：
class Solution {
public:
void deleteNode(ListNode* node) {
node->val = node->next->val;
node->next = node->next->next;
}
};删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第
n个结点，并且返回链表的头结点。输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]示例 2：
输入：head = [1], n = 1 输出：[]示例 3：
输入：head = [1,2], n = 1 输出：[1]提示：
- 链表中结点的数目为
sz1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz** 进阶：** 你能尝试使用一趟扫描实现吗？
思路：常规思路就是先扫描一遍链表，确定长度 len 。这样倒数第 N 个结点就知道是正数第几个结点了。然后扫描链表找到该结点的上一个结点 pre ， pre->next = pre->next->next 。这样需要扫描两趟链表。如何一趟扫描解决问题呢？
想象两个指针， slow 和 head 指向头结点，先让 fast 走 N 步，那么此时 slow 和 fast 的间距就是 N 步。然后两个指针同速齐步前进，间距始终保持 N 不变。当 fast 走到链表的末尾 nullptr ，此时 slow 正好就在倒数第 N 个结点上。在纸上画个图模拟下就能看出来了。
因为我们可能会删除头结点，和之前一样引入一个头结点 dummy 。算法思路就是让 slow 和 fast 从 dummy 出发。那么当 fast 指针走到链表最后一个结点时， slow 刚好指向倒数第 N+1 个结点，也就是目标结点的上一个结点，这样就可以进行删除操作了。
代码：
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode();
dummy->next = head;
ListNode* slow = dummy;
ListNode* fast = dummy;
for (int i = 0; i < n; i++)
{
fast = fast->next;
}
while (fast->next != nullptr)
{
slow = slow->next;
fast = fast->next;
}
slow->next = slow->next->next;
return dummy->next;
}
};删除排序链表中的重复元素
给定一个已排序的链表的头
head， 删除所有重复的元素，使每个元素只出现一次 。返回已排序的链表 。示例 1：
img 输入：head = [1,1,2] 输出：[1,2]示例 2：
img 输入：head = [1,1,2,3,3] 输出：[1,2,3]提示：
- 链表中节点数目在范围
[0, 300]内-100 <= Node.val <= 100- 题目数据保证链表已经按升序 排列
思路：因为链表有序、所以重复元素一定是相邻的，只需要遍历一次，比较当前节点和它的下一个节点：如果 cur->val == cur->next->val ，说明下一个是重复的，删除该节点。（ cur->next = cur->next->next ）， cur 不前进（因为可能后面还有连续重复，要继续比）。如果两者不等，说明下一个是新值， cur 正常前进。
代码：
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* cur = head;
while(cur != nullptr && cur->next != nullptr)
{
int val = cur->val;
if (cur->next->val == val) //这里要保证cur->next不能为空，要不然报错。如何保证，看while第二个条件
{
cur->next = cur->next->next;
}
else
{
cur = cur->next;
}
}
return head;
}
};思考：为什么这道题不需要用
dummy呢？什么时候需要用dummy？需要对头结点进行操作的时候，才需要用到
dummy。这道题头结点保持不变。
删除排序链表中的重复元素 II
给定一个已排序的链表的头
head， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回已排序的链表 。示例 1：
img 输入：head = [1,2,3,3,4,4,5] 输出：[1,2,5]示例 2：
img 输入：head = [1,1,1,2,3] 输出：[2,3]提示：
- 链表中节点数目在范围
[0, 300]内-100 <= Node.val <= 100- 题目数据保证链表已经按升序 排列
思路：这道题和上道题的区别就是要删除所有的重复节点，而不是把重复节点的次数变为 1。
用 pre 指针来维护已确认无重复部分的最后一个节点。如果 cur->val == cur->next->val （发现一组重复的开头），就用一个内层循环把所有等于这个值的节点全部跳过，然后让 prev->next 直接指向跳完之后的节点。如果 cur 和后继不重复，说明 cur 是个「独苗」，保留它， prev 和 cur 一起前进。
代码：代码整体思路没有问题，但里面有个边界条件错误，看看能不能找出来。
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* dummy = new ListNode();
dummy->next = head;
ListNode* pre = dummy; //重复元素的上一个节点
ListNode* cur = head;
while(cur != nullptr && cur->next != nullptr)
{
if (cur->val == cur->next->val) //遇到重复元素
{
int val = cur->val;
while(cur->val == val)
{
cur = cur->next;
} //找到和cur重复的最后一个节点的下一个节点
pre->next = cur; //删除cur及其重复节点
}
else
{
pre = pre->next;
cur = cur->next;
}
}
return dummy->next;
}
};第 14 行 while 中的条件应该是 while(cur != nullptr && cur->val == val) 。比如 1->1->1->1 ， cur 会变成 nullptr ，此时 cur->val 就会报错。所以要加上 cur!=nullptr 的限制，而且这个限制必须放在 cur->val == val 的前面。
二叉树相关
二叉树的最大深度
给定一个二叉树
root，返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
img 输入：root = [3,9,20,null,null,15,7] 输出：3示例 2：
输入：root = [1,null,2] 输出：2提示：
- 树中节点的数量在
[0, 104]区间内。-100 <= Node.val <= 100
思路：这道题需要用递归来做。如果我已经知道了左子树和右子树各自的最大深度，那么整棵树的最大深度是多少？
整棵树的深度等于「左右子树中较深的那个深度 ＋ １」， ＋１ 是加上当前根节点这一层。这叫递归关系；还需要有递归终止条件（base case）：当节点为空（ null ）时，没有深度，返回 0。
直接贴出代码：
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
int left = maxDepth(root -> left);
int right = maxDepth(root -> right);
return max(left, right)+1;
}
};我们继续看更多的涉及递归的二叉树题目来加深熟练度。
相同的树
给你两棵二叉树的根节点
p和q，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
img 输入：p = [1,2,3], q = [1,2,3] 输出：true示例 2：
img 输入：p = [1,2], q = [1,null,2] 输出：false提示：
- 两棵树上的节点数目都在范围
[0, 100]内-104 <= Node.val <= 104
思路：假设我已经知道「p 的左子树和 q 的左子树是否相同」，也知道「p 的右子树和 q 的右子树是否相同」，那么我怎么判断 p 和 q 这两整棵树是否相同？ 只需判断 p 和 q 的值是否相等。
递归终止条件：p 节点和 q 节点都为空，返回 true；p 节点和 q 节点一空一不空，返回 false。
递归关系：根节点的值相等、左子树彼此相同、右子树彼此相同。
代码：
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (p == nullptr && q == nullptr) return true;
if (p == nullptr || q == nullptr) return false;
bool left = isSameTree(p->left, q->left);
bool right = isSameTree(p->right, q->right);
return p->val == q->val && left && right;
}
};上面的代码结构很清晰，但是效率不高。因为它先进行了递归，然后才判断节点值是否相同。其实应该先判断节点值是否相同，不相同，就不用递归算完左右子树了。
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (p == nullptr && q == nullptr) return true;
if (p == nullptr || q == nullptr) return false;
if (p->val != q->val) return false;
bool left = isSameTree(p->left, q->left);
bool right = isSameTree(p->right, q->right);
return left && right;
}
};还可以写成下面代码：结构更简洁。
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (p == nullptr && q == nullptr) return true;
if (p == nullptr || q == nullptr) return false;
return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
};对称二叉树
给你一个二叉树的根节点
root， 检查它是否轴对称。示例 1：
img 输入：root = [1,2,2,3,4,4,3] 输出：true示例 2：
img 输入：root = [1,2,2,null,3,null,3] 输出：false提示：
- 树中节点数目在范围
[1, 1000]内-100 <= Node.val <= 100** 进阶：** 你可以运用递归和迭代两种方法解决这个问题吗？
思路：这道题就是上一道题的变形，判断一个树是不是对称的，就是看左右子树是不是对称的。如何判断呢？需要判断 p 的左子树和 q 的右子树是否相同；p 的右子树和 q 的左子树是否相同。
如何写递归关系呢？假设现在已经知道 p 的左子树和 q 的右子树是否相同；p 的右子树和 q 的左子树是否相同，只需判断 p 和 q 的值是否相等。
代码：
class Solution {
public:
bool isSymmetric(TreeNode* root) {
return isMirror(root->left, root->right);
}
bool isMirror(TreeNode* p, TreeNode* q)
{
if(p == nullptr && q == nullptr) return true;
if(p == nullptr || q == nullptr) return false;
return p->val == q->val && isMirror(p -> left, q->right) && isMirror(p->right, q->left);
}
};我们来总结下递归思想：
递归直观上就是函数自己调用自己。就是把一个大问题拆解成更小规模的相同问题，再把问题拆成更小的问题，直到这个小问题能够直接被解决。
如何写递归呢？首先要确定问题，搞清楚这个函数的功能是什么；然后确定 base case，也就是终止条件，也就是能够被直接解决的最小问题；最后确定递归关系，也就是如何拆解。递归关系往往是最难的点。
思维技巧：在编写递归函数时，可以认为已经有一个同名函数能实现你所需要的功能，可以直接调用。
| 题目 | ① 函数功能 | ② base case | ③ 递归关系（怎么合并） |
|---|---|---|---|
| 最大深度 | 返回树的最大深度（数字） | 空 → 0 | max(左, 右) + 1 |
| 相同的树 | 返回是否相同（真假） | 都空 → true ；一空一非空 → false | 值相等 && 左相同 && 右相同 |
| 对称二叉树 | 返回是否互为镜像（真假） | 都空 → true ；一空一非空 → false | 值相等 && isMirror(左,右) && isMirror(右,左) |
平衡二叉树
给定一个二叉树，判断它是否是 平衡二叉树
示例 1：
img 输入：root = [1,2,2,3,3,null,null,4,4] 输出：false提示：
- 树中的节点数在范围
[0, 5000]内-104 <= Node.val <= 104
思路：确定递归关系 ==：假设现在已经知道左子树本身和右子树本身是不是平衡的，那如何判断整个树是不是平衡的？== 就是看左子树和右子树的高度相差是不是不超过 1。
代码：
class Solution {
public:
bool isBalanced(TreeNode* root) {
// base case
if (root == nullptr) return true;
int l = height(root->left);
int r = height(root->right);
int key = abs(l - r);
return (key <= 1) && isBalanced(root->left) && isBalanced(root->right);
}
int height(TreeNode* root)
{
if (root == nullptr) return 0;
int l = height(root -> left);
int r = height(root -> right);
return max(l, r) + 1;
}
};上面代码是可以 AC 的，但是有些地方还可以进行优化。我们来看一个具体的例子：
一个二叉树的结构是这样的：根是 1 ， 1 的左孩子是 2 ， 2 的左孩子是 3 ， 3 的左孩子是 4 ， 4 是叶子。一共 ４ 个节点。
一步步看 height 被调用的情况：
isBalanced会在1、2、3、4上各跑一次。每跑一次，它都对当前节点的左右孩子各调一次height：
isBalanced(1)→ 调用height(2)。height(2)要算2这棵子树的高度，于是往下走：摸了2→3→4。
isBalanced(2)→ 调用height(3)。height(3)往下走：摸了3→4。
isBalanced(3)→ 调用height(4)。height(4)：摸了4。
isBalanced(4)→ 调用height(null)，不摸任何节点。
我们会发现 3、4 节点的高度被重复计算了好几次，越靠底部的节点，就被越多次的 height 重复扫到。如果这条链有 ｎ 个节点，最底下那个节点会被摸 ｎ−１ 次，整体的计算量大约是 1 + 2 + 3 + … + (n−1) ≈ n²/2 ，时间复杂度就会变成Ｏ（ｎ²） 。所以我们需要想办法优化。
关键想法是改造 height 函数，让它计算高度的同时，顺便检查平衡。可一个函数只能返回一个值，怎么同时表达「高度是多少」和「平不平衡」两种信息？一旦发现某棵子树不平衡，就用一个特殊的返回值（比如 −1 ）当「信号」往上传，表示「这下面已经坏了，别再算了」。
递归关系怎么写呢？假设我已经拿到左右孩子的 height 结果，我该返回什么？ 如果左右孩子的 height 结果中有 - 1，就返回 - 1，表示以该节点为根节点的树不是平衡树；如果左右孩子高度差超过 1，也返回 - 1，表示以该节点为根节点的树不是平衡树。如果上述情况都不满足，说明以该节点为根节点的树是平衡树，那么就返回正常高度值。看一下具体代码来体会一下：
class Solution {
public:
bool isBalanced(TreeNode* root) {
return height(root) != -1;
}
int height(TreeNode* root)
{
if (root == nullptr) return 0;
int left = height(root -> left);
int right = height(root -> right);
if (left == -1) return -1;
if (right == -1) return -1;
if (abs(left - right) > 1) return -1;
return max(left, right) + 1;
}
};二叉树的右视图
给定一个二叉树的 根节点
root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。示例 1：
输入：root = [1,2,3,null,5,null,4] 输出：[1,3,4]解释：
示例 2：
输入：root = [1,2,3,4,null,null,null,5] 输出：[1,3,4,5]解释：
提示:
- 二叉树的节点个数的范围是
[0,100]-100 <= Node.val <= 100
思路：右视图本质就是「每一层最右边的那个节点」。这道题有两种思路：BFS 和 DFS（递归）。我们这里只讲递归的做法。
遍历时先走右孩子、再走左孩子，并且记录当前在第几层。
为什么这样可行？因为先右后左，意味着每一层里，我们最先碰到的一定是最右边的节点。于是只要维护一个「目前答案里已经收了几层」，每当递归钻到一个比已收层数更深的新层时，当前这个节点必然是这层第一个被访问到的，也就是最右的 —— 把它收进来即可。
递归关系：假设我已经遍历了右子树，更新了 ans；也遍历了左子树，更新了 ans。只需在开头根据 root 更新下 ans 就行了。
可能单纯看文字有些难以理解，我们来看下代码：
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> ans;
dfs(root, 0, ans);
return ans;
}
void dfs(TreeNode* node, int depth, vector<int>& ans)
{
if (node == nullptr) return;
if (depth == ans.size()) ans.push_back(node->val);
dfs(node->right, depth+1, ans);
dfs(node->left, depth+1, ans);
//对于 void 函数，当执行流程自然走到函数体最后那个 } 时，函数就自动结束、自动返回了，不需要手写 return
}
};以示例二为例，详细看看代码执行的过程：
接下来我们在学完递归的基础上来看一下二叉树的前序、中序、后序遍历的代码写法。
前序：根左右；中序：左根右；后序：左右根。他们的区别就是：在「访问当前节点（根）」这件事，相对于「递归左子树、递归右子树」放在什么位置。
代码具体实现：
void preorder(TreeNode* node, vector<int>& ans) {
if (node == nullptr) return;
ans.push_back(node->val); // 根：放最前
preorder(node->left, ans);
preorder(node->right, ans);
}
void inorder(TreeNode* node, vector<int>& ans) {
if (node == nullptr) return;
inorder(node->left, ans);
ans.push_back(node->val); // 根：放中间
inorder(node->right, ans);
}
void postorder(TreeNode* node, vector<int>& ans) {
if (node == nullptr) return;
postorder(node->left, ans);
postorder(node->right, ans);
ans.push_back(node->val); // 根：放最后
}可以看到前中后序遍历是用递归实现的。以前序遍历为例，如何写递归关系呢？假设我们已经知道了左子树的遍历情况、右子树的遍历情况，接下来是不是只需要把 push_back(root) 放到遍历左子树、遍历右子树的前面就可以了。中序、后序遍历都是一样的方法。就是假设我们已经有了一个 preorder 函数，能够完成对某棵树的前序遍历，不需要管怎么实现的，然后问问自己假设已经知道了左右子树的遍历情况，接下来该干什么，才能正确写出以 root 为节点的树的前序遍历。
来看一下如何用前序、中序、后序遍历验证一颗二叉树是否是搜索树（BST）。
验证二叉搜索树
给你一个二叉树的根节点
root，判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下：
- 节点的左子树只包含 严格小于 当前节点的数。
- 节点的右子树只包含 严格大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
img 输入：root = [2,1,3] 输出：true示例 2：
img 输入：root = [5,1,4,null,null,3,6] 输出：false 解释：根节点的值是 5 ，但是右子节点的值是 4 。提示：
- 树中节点数目范围在
[1, 104]内-231 <= Node.val <= 231 - 1
先来讲前序遍历：每个节点都有一个允许的取值范围 (low, high)，从根往下传。根节点范围是 (−∞, +∞) ；往左走时，所有节点都必须比父亲小，所以上界收紧成父亲的值；往右走时，下界收紧成父亲的值。判断当前节点值是否在合法区间，如果不在，那么就不是平衡二叉树。这个应该挺好理解的。
接下来来看代码： check 函数中的递归关系怎么写呢？假设我已经得到了 node 左子树是不是 BST，右子树是不是 BST，那如何判断以 node 为根结点的树是不是 BST 呢。只需判断 node 的值是不是在合法区间 (l,r) 。
class Solution {
public:
bool isValidBST(TreeNode* root) {
return check(root, LONG_MIN, LONG_MAX);
}
bool check(TreeNode* node, long long l, long long r) { //检查以node为根节点的树是不是BST
if (node == nullptr) return true;
long long val = node->val;
return l < val && val < r
&& check(node->left, l, val)
&& check(node->right, val, r);
}
};为什么区间要用 long long 呢，不能用 int 吗？
因为
val的值最大是 2 的 31 次方 - 1，也就是int能表示的最大值。所以r就不能是int了。l同理。
接着我们来看中序遍历解决 BST 问题。这个方法最简单，因为如果一棵树是 BST，那么对这棵树中序遍历之后的结果一定是严格递增。那么只需中序遍历一遍二叉树，将结点值放到 ans 数组中，然后判断数组是不是严格递增的就可以了。
class Solution {
public:
vector<int> ans;
bool isValidBST(TreeNode* root) {
dfs(root);
for (int i = 0; i < ans.size() - 1; i++)
{
if (ans[i] >= ans[i + 1]) return false;
}
return true;
}
void dfs(TreeNode* node)
{
if (node == nullptr) return;
dfs(node->left);
ans.push_back(node->val);
dfs(node->right);
}
};最后我们来看一下后序遍历。让每个节点先问清楚两棵子树的情况，再判断自己。具体让递归返回三样东西：这棵子树是否合法、子树里的最小值、最大值。父节点拿到后检查：自己要大于整个左子树的最大值、小于整个右子树的最小值。（那么是不是只需要保存左子树的最大值、右子树的最小值就可以了，其实不是的，左右子树的最小最大值都需要保存）
后序遍历的写法有些抽象，等以后再来看吧。
class Solution {
public:
bool isValidBST(TreeNode* root) {
long mn, mx;
return dfs(root, mn, mx);
}
private:
// 返回：以 node 为根的子树是不是合法 BST
// 顺便通过 mn、mx 带出这棵子树的最小值、最大值
bool dfs(TreeNode* node, long& mn, long& mx) {
if (node == nullptr) {
mn = LONG_MAX; // 空子树：最小值设成超大
mx = LONG_MIN; // 最大值设成超小，让父节点比较时自动通过
return true;
}
long lmn, lmx, rmn, rmx;
if (!dfs(node->left, lmn, lmx)) return false; // 左子树不合法，直接淘汰
if (!dfs(node->right, rmn, rmx)) return false; // 右子树不合法，直接淘汰
// 当前节点要大于整个左子树的最大值、小于整个右子树的最小值
if (node->val <= lmx || node->val >= rmn) return false;
mn = min((long)node->val, lmn); // 这棵子树的最小值
mx = max((long)node->val, rmx); // 这棵子树的最大值
return true;
}
};接下来的题目难度就更大了，需要对递归有深刻的理解。
二叉树的最近公共祖先
给定一个二叉树，找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
img 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。示例 2：
img 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。示例 3：
输入：root = [1,2], p = 1, q = 2 输出：1提示：
- 树中节点数目在范围
[2, 105]内。-109 <= Node.val <= 109- 所有
Node.val互不相同。p != qp和q均存在于给定的二叉树中。
思路：按照递归三部曲，首先要确认函数的功能，搞清楚函数要返回什么东西。由于函数传入的三个参数为 root、p、q。自然的想法就是函数的功能定义为在以 root 为根的树中找 p 和 q 的最近公共祖先。树中没有 pq，就返回 nullptr；有其中一个，就返回找到的那一个；两个都有就返回最近公共祖先。
只找到一个就返回那一个这条约定，初看确实有点莫名其妙：我要找的是公共祖先，你返回一个孤零零的
p或q给我干嘛？答案是: 这个返回值不是给「当前这层」用的，而是给「上面的祖先」用的信号。 它在向上层传递一句话 ——「
p、q这两个目标，我在这一侧找到了其中一个，你心里有数」。
终止条件好说，如果 root 是空，那就返回空；如果 root 是 p 或着 q，就返回 root。
最后就是递归关系。假设我已经知道了 root 左右子树的情况，接下来该干什么。情况一：左右子树都为空，返回空；情况二：pq 全在左或右子树，返回递归左子树或右子树得到的结果；情况三：左右子树各有一个，说明 root 就是最近公共祖先，返回 root。
代码：
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr || root == p || root == q) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if(left && right) return root; //情况三：左右子树各有一个
return left ? left : right; //这里用三元运算符表示情况一、二。
}
};下面是个例子，方便自己动手画画递归的过程：
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4 p = 5,q = 4二叉搜索树的最近公共祖先
给定一个二叉搜索树，找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
img 示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出: 2 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
思路：很明显我们需要利用二叉搜索树的性质。假如 pq 小于当前结点，说明 pq 在左子树，那么最近公共祖先也肯定在左子树；如果大于当前结点，那么最近公共祖先就在右子树。如果一个大于一个小于，那最近公共祖先就是当前结点。
我们先来看正常的写法（迭代）：
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
while (1)
{
if (p->val < root->val && q->val < root->val) root = root->left;
else if (p->val > root->val && q->val > root->val) root = root->right;
else return root;
}
return nullptr;//由于pq一定在二叉树中，所以上面的循环肯定能找到答案，这个return是多余的。但是C++编译器为了语法安全，需要写这句。
}
};再来看递归写法，同样三部曲：
① 函数功能: lowestCommonAncestor(root, p, q) 返回这棵 BST 里 p 、 q 的最近公共祖先。
诶为什么这个题不需要分情况讨论了？就能直接返回最近公共祖先了？不会出现 pq 不在这个二叉树中的情况吗？
因为我们是靠比大小来选方向的，只会往 "确定包含 LCA" 的那一侧递归，不会进入一棵不含答案的子树。这点从具体代码中也能看出来。
② base case:pq 一个大于 root 一个小于 root，就直接返回 root。需要写 if(root == nullptr) return nullptr 吗？不需要。因为题目保证 p 、 q 都在树中，所以一定会在走到空之前到达分叉点，根本不会走到 nullptr 。
③ 递归关系：如果 pq 都比 root 小，那就递归左子树；ppqq 比 root 大，就递归右子树；要是一个大一个小呢，也就是上面的 base case。
代码：
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (p->val < root->val && q->val < root->val) return lowestCommonAncestor(root->left, p, q);
if (p->val > root->val && q->val > root->val) return lowestCommonAncestor(root->right, p, q);
return root;
}
};只要递归关系和截止条件的逻辑写对，不需要一步步模拟递和归的过程，递归得到的结果一定是正确的。
二叉树的层序遍历
给你二叉树的根节点
root，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。示例 1：
img 输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]示例 2：
输入：root = [1] 输出：[[1]]示例 3：
输入：root = [] 输出：[]提示：
- 树中节点数目在范围
[0, 2000]内-1000 <= Node.val <= 1000
思路：如何一层层的访问二叉树节点，涉及到 BFS 思想。下面介绍几种主要的写法。
写法一：双数组法
用 cur 数组记录当前层结点，用 nxt 数组记录下一层结点，用 val 数组记录结点值。当 cur 数组为空时，代表遍历结束。时间复杂度 $O (n)$
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (root == nullptr) return ans;
vector<TreeNode*> cur = {root};
vector<TreeNode*> nxt;
vector<int> val;
while(!cur.empty())
{
val = {};
nxt = {};
for (int i = 0; i < cur.size(); i++)
{
if (cur[i]->left) nxt.push_back(cur[i]->left);
if (cur[i]->right) nxt.push_back(cur[i]->right);
val.push_back(cur[i]->val);
}
cur = nxt;
ans.push_back(val);
}
return ans;
}
};写法二：队列
用一个队列来维护 cur 和 nxt 数组。当前的 cur 遍历完就出队，将下一层结点入队，反复进行，直到队列为空。
思路还是很简单的，直接看代码：
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (root == nullptr) return ans;
queue<TreeNode*> q;
q.push(root);
vector<int> val;
while(!q.empty())
{
val = {};
int size = q.size();
for (int i = 0; i < size; i++)
{
TreeNode* node = q.front();
q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
val.push_back(node->val);
}
ans.push_back(val);
}
return ans;
}
};目前对 C++ 中的 vector 和 queue 还不是熟悉。结合上面两个代码加深熟练度。
之前讲的二叉树最大深度那道题就可以用层序遍历来实现， ans 的 size() 就是最大深度。
接下来再来看几道和层序遍历有关的题目，比较简单。
二叉树的锯齿形层序遍历
给你二叉树的根节点
root，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[20,9],[15,7]]示例 2：
输入：root = [1] 输出：[[1]]示例 3：
输入：root = [] 输出：[]提示：
- 树中节点数目在范围
[0, 2000]内-100 <= Node.val <= 100
思路：这道题看起来复杂，其实不复杂。如何实现锯齿形遍历呢，本质上就是偶数层的时候将遍历得到的节点反转一下。弄清楚本质，这道题的代码就不难写了。
代码：
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (root == nullptr) return ans;
queue<TreeNode*> q;
q.push(root);
vector<int> val;
bool bit = false; //代表当前是不是偶数层
while(!q.empty())
{
val = {};
int size = q.size();
for (int i = 0; i < size; i++)
{
TreeNode* node = q.front();
q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
val.push_back(node->val);
}
//偶数层val数组反转一下
if (bit) reverse(val.begin(), val.end());
ans.push_back(val);
bit = !bit;// ~bit 是按位取反 !bit 才是逻辑取反
}
return ans;
}
};找树左下角的值
给定一个二叉树的 根节点
root，请找出该二叉树的 最底层 最左边 节点的值。假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3] 输出: 1示例 2:
输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7提示:
- 二叉树的节点个数的范围是
[1,104]-231 <= Node.val <= 231 - 1
思路：这道题还是考层序遍历，最后一层的第一个节点就是题目说的树的左下角节点。还有另一种思路，就是从右往左层序遍历二叉树，得到的最后一个值就是答案。我们来实现第二个思路，如何从右往左遍历呢，只需要修改下左右孩子的入队顺序。
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
vector<int> val;
while(!q.empty())
{
val = {};
int size = q.size();
for (int i = 0; i < size; i++)
{
TreeNode* node = q.front();
q.pop();
if (node->right) q.push(node->right);
if (node->left) q.push(node->left);
val.push_back(node->val);
}
}
return val.back();//back()拿到val最后一个元素
}
};回溯算法
这一节讲解回溯算法。回溯算法一般就是用递归来实现的。回溯的本质是 "枚举所有合法方案"。
用回溯三问来写出回溯代码：
- 当前操作是什么
- 子问题是什么
- 下一个子问题是什么
回溯和 dfs 有什么区别吗？其实不需要刻意区分两者的区别。回溯就是 DFS 的特例。严格区分的话，回溯通常都会有恢复现场状态这个操作。而且回溯遍历的对象是一个虚拟的解空间树。两者都可以用递归来实现。
电话号码的字母组合
给定一个仅包含数字
2-9的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]示例 2：
输入：digits = "2" 输出：["a","b","c"]提示：
1 <= digits.length <= 4digits[i]是范围['2', '9']的一个数字。
思路：用 path 数组来表示答案的一种可能。需要做的操作就是给 path 数组每个位置添加个元素。需要用 map 数组存储数字和字母的映射关系。还需要将字符转换为数组的索引，用的方式 digits[i] - '0' 。
回溯三问：
- 当前操作：填入 path [i] 位置的数字
- 子问题：构造 path 大于等于 i 位置的部分，也就是 dfs (i) 函数的含义
- 下一个子问题：构造 path 大于等于 i+1 位置的部分
class Solution {
vector<string> ans;
string path;
string map[10] = {" ", " ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
string digits;
void dfs(int i) //dfs拿不到letter的参数digits 除了设置一个同名成员变量，将digits值赋给他；还可以直接给dfs加第二个参数，写成dfs(int i, string digits)。调用的时候写dfs(0, digits);
{
int n = digits.size();
if (i == n){ //该枚举第n个位置了，代表0-n-1位置枚举好了，就是所有位置枚举好了。
ans.push_back(path);
return;
}
int s = digits[i] - '0'; //比如把字符2变成数字2
/* 常规的for循环
for (int j = 0; j < map[s].size(); j++)
{
path.push_back(map[s][j]);
dfs(i + 1);
path.pop_back();
}
*/
for(char c : map[s]) //基于范围的for循环
{
path.push_back(c);
dfs(i + 1);
path.pop_back();//恢复现场
}
}
public:
vector<string> letterCombinations(string digits) {
this->digits = digits;
dfs(0);
return ans;
}
};隐式解空间树长的样子：
时间复杂度是多少呢？$O (n*4^n)$ 。因为一个字母中的数字最多有 4 个，那么 path 最多有 $4^n$ 个情况。又因为 ans.push_back(path) ，会对 path 进行拷贝，要花 O (n)。
凑出所有的组合花的时间就是算法的时间复杂度。**** 有多少个解（4ⁿ），乘以构造一个解的代价（n），这也是大多数回溯题分析时间复杂度的通用思路。
回溯可以分为子集型回溯、组合型回溯、排列型回溯。
子集
给定一个整数数组
nums，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]示例 2：
输入：nums = [0] 输出：[[],[0]]提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10nums中的所有元素 互不相同
思路：有两种视角，我们都要讲一下。第一个视角，从数字出发，关注选不选某个数字。
回溯三问：
- 当前操作：枚举选不选第 i 个数。
- 子问题：从下标大于等于 i 的数字中构造子集，也就是 dfs (i) 函数的含义
- 下一个子问题：从下标大于等于 i+1 的数字中构造子集
为什么撤销操作放到了选 num [i] 中？因为选 num [i] 会对 path 添加东西，所以需要 pop_back 还原现场，而不选的情况，没有对 path 做操作，就不需要还原现场了。
第二个思路：站在答案的角度。枚举选哪个，每次选一个数填入答案中。
回溯三问：
- 当前操作：枚举一个下标 j 大于等于 i 的数，加入 path。（因为 [1,2] [2,1] 是同一个子集，所以为了避免重复，我们要规定个顺序）
- 子问题：从下标大于等于 i 的数字中构造子集，也就是 dfs (i) 函数的含义
- 下一个子问题：从下标大于等于 j+1 的数字中构造子集（为什么不是 i+1 呢）
好好体会下回溯三问。
代码：
class Solution {
vector<vector<int>> ans;
vector<int> path;
vector<int> nums;
void dfs(int i)
{
int n = nums.size();
ans.push_back(path);
for (int j = i; j < n; j++)
{
path.push_back(nums[j]);
dfs(j + 1);
path.pop_back();
}
}
public:
vector<vector<int>> subsets(vector<int>& nums) {
this->nums = nums;
dfs(0);
return ans;
}
};分割回文串
给你一个字符串
s，请你将s分割成一些 子串，使每个子串都是 回文串 。返回s所有可能的分割方案。示例 1：
输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]示例 2：
输入：s = "a" 输出：[["a"]]提示：
1 <= s.length <= 16s仅由小写英文字母组成
思路：先来将从答案角度出发的思路：
- 当前操作：从下标 i 开始，枚举一个结束位置 j，构成子串 s [i,j]，如果是回文子串就加入 path。（如何判断是不是回文子串，见代码。）
- 子问题：dfs (i) 函数的含义：当前已经处理完了
s[0..i-1]，现在要从s[i..n-1]开始继续分割，得到从 i 开始的回文串方案。 - 下一个子问题：当前找到了一个回文子串 s [i,j]，递归处理后面的
s[j+1..n-1]
代码：
class Solution {
vector<vector<string>> ans;
vector<string> path;
string s;
bool isPalindrome(int l, int r) //判断是不是回文子串 双指针
{
while(l < r)
{
if (s[l] != s[r]) return false;
r--, l++;
}
return true;
}
void dfs(int i)
{
int n = s.size();
if (i == n)
{
ans.push_back(path);
return;
}
for (int j = i; j < n; j++)
{
if(isPalindrome(i, j))
{
path.push_back(s.substr(i, j - i + 1));//s.substr 是 C++ 字符串的"取子串"操作——从 s 里截一段出来,返回一个新的字符串(原来的 s 不变)。substr(起始位置，截取长度)
dfs(j + 1);
path.pop_back();
}
}
}
public:
vector<vector<string>> partition(string s) {
this->s = s;
dfs(0);
return ans;
}
};
这几道回溯的题目代码形式都是很相似的，可以总结成模版：
vector<结果类型> ans; // 全局结果集
路径类型 path; // 全局当前路径
void backtracking(参数) { // ① 返回值 void + 参数（含起始下标）
if (终止条件) { // ② 终止条件
ans.push_back(path); // 收集一个结果
return;
}
for (本层的每一个选择 choice) { // ③ 单层搜索：横向遍历
path.push_back(choice); // 做选择
backtracking(下一层参数); // 递归：纵向深入
path.pop_back(); // 撤销选择（回溯）
}
}再换一个角度，从选或不选的角度出发。什么意思呢，每个元素后面选还是不选切割。
每两个相邻字符之间有一个 "逗号位", 逐个字符地走，在每个字符 s[i] 后面决定这个逗号选还是不选 (切还是不切)。
回溯三部曲：
- 当前操作：枚举
s[i]后面这个逗号选还是不选 - 子问题：dfs (i) 函数的含义：从下标 ≥ i 的字符开始，构造
s剩余部分的回文分割 - 下一个子问题：递归处理后面的
s[i+1]后面的逗号。
class Solution {
vector<vector<string>> ans;
vector<string> path;
string s;
int n;
bool isPalindrome(int l, int r) {
while (l < r) {
if (s[l] != s[r]) return false;
l++; r--;
}
return true;
}
// i：当前考虑的字符；start：当前这一段从哪开始
void dfs(int i, int start) {
int n = s.size();
if (i == n) { // 整个串走完了
ans.push_back(path);
return;
}
// 分支一：不选 —— i 后面不切，当前段继续
if (i < n - 1) { // 最后一个字符必须结尾，不能继续
dfs(i + 1, start);
}
// 分支二：选 —— 在 i 后面切一刀，当前段是 s[start..i]
if (isPalindrome(start, i)) { // 是回文才能切
path.push_back(s.substr(start, i - start + 1));
dfs(i + 1, i + 1); // 新的一段从 i+1 开始
path.pop_back();
}
}
public:
vector<vector<string>> partition(string s) {
this->s = s;
dfs(0, 0); // 从第 0 个字符开始，第一段也从 0 开始
return ans;
}
};这个角度还没想明白，先掌握答案那个思路吧。
接下来讲组合型回溯。先看子集问题的第二种角度的搜索树。我们观察每一层。第二层就是从【1，2，3】中挑一个数的所有情况，第三层就是从【1，2，3】中挑两个数的所有情况。由此可见，组合问题可以利用子集问题解决。
从 n 个数中挑选 k 个数，相当于找长度为 k 的所有子集。
有些路径是可以被剪枝的，比如【1，2，3】我们要找长度为 3 的子集，当选 2 时，由于后面只剩下了 3，所以不可以构成长度为 3 的子集，因此不需要继续递归了。
组合
给定两个整数
n和k，返回范围[1, n]中所有可能的k个数的组合。你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2 输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]示例 2：
输入：n = 1, k = 1 输出：[[1]]提示：
1 <= n <= 201 <= k <= n
class Solution {
vector<vector<int>> ans;
vector<int> path;
void dfs(int i, int k, int n) //从下标大于等于i挑选长度为k的子集
{
//剪枝操作 当前path长度为s d=k-s 剩余数长度小于d 构不成长度为k的子集。直接返回
int s = path.size();
int d = k - s;
if (n - i < d) return;
if (path.size() == k)
{
ans.push_back(path);
return;
}
for (int j = i; j < n; j++)
{
path.push_back(j + 1);
dfs(j + 1 , k, n);
path.pop_back();
}
}
public:
vector<vector<int>> combine(int n, int k) {
dfs(0, k, n);
return ans;
}
};时间复杂度是多少呢？前面讲过，凑出所有的组合花的时间就是算法的时间复杂度。有多少个解（$C\binom {k}{n}$），乘以构造一个解的代价（k）。
组合总数 III
找出所有相加之和为
n的k个数的组合，且满足下列条件：
- 只使用数字 1 到 9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1:
输入: k = 3, n = 7 输出: [[1,2,4]] 解释: 1 + 2 + 4 = 7 没有其他符合的组合了。示例 2:
输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]] 解释: 1 + 2 + 6 = 9 1 + 3 + 5 = 9 2 + 3 + 4 = 9 没有其他符合的组合了。示例 3:
输入: k = 4, n = 1 输出: [] 解释: 不存在有效的组合。 在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。提示:
2 <= k <= 91 <= n <= 60
思路：先来看没有剪枝的版本，就是在上一道题的基础上，加一个判断，符合条件才能添加到 ans 中。
class Solution {
vector<vector<int>> ans;
vector<int> path;
int sum = 0;
void dfs(int i, int k, int n) //这里的i和前面一样都是指下标
{
if (path.size() == k && sum == n)
{
ans.push_back(path);
return;
}
for(int j = i; j < 9; j++)
{
path.push_back(j+1);
sum = sum + j + 1;
dfs(j+1, k, n);
path.pop_back();
sum = sum - j - 1;
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
dfs(0, k, n);
return ans;
}
};再来看一下有哪些剪枝优化：
- 假设当前已经选了 m 个数，还有 d=k-m 个数要选，但是剩余 9-i 个数。如果 9-i 小于 k-m 就直接返回。
- 当前选了 m 个数，还需要凑总和为 t 的数。当 t 小于 0，直接返回，当 t 大于（2 * i + d + 1）*d /2 的时候，直接返回（也就是能选的最大的 d 个数总和小于 t）。
（2 * i + d + 1）*d /2 是用等差数列和的公式算的。S=（首项 + 末项）✖️项数 / 2。
剪枝后的版本：
class Solution {
vector<vector<int>> ans;
vector<int> path;
int sum = 0;
int k, n;
void dfs(int i, int t)// 从下标大于等于i中选，需凑总和为t
{
int d = k - path.size(); //还能选几个数
if (9 - i < d) return;
if (t < 0 || t < ((2 * i + d + 1) * d) / 2) return;
if (path.size() == k && sum == n)
{
ans.push_back(path);
return;
}
for(int j = i; j < 9; j++)
{
path.push_back(j+1);
sum = sum + j + 1;
dfs(j+1, n - sum);
path.pop_back();
sum = sum - j - 1;
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
this->k = k;
this->n = n;
dfs(0, n);
return ans;
}
};其实咱们可以改一下 dfs 中 i 的含义，让代码变得更容易懂。dfs (i) 代表从大于等于 i 中挑选数字构造子集，而不是下标大于等于 i。
代码如下：
class Solution {
vector<vector<int>> ans;
vector<int> path;
int sum = 0;
int k, n;
void dfs(int i, int t)
{
int d = k - path.size();
if (9 - i + 1 < d) return;
if (t < 0 || t < ((2 * i + d - 1) * d) / 2) return;
if (path.size() == k && sum == n)
{
ans.push_back(path);
return;
}
for(int j = i; j < 10; j++)
{
path.push_back(j);
sum = sum + j;
dfs(j+1, n - sum);
path.pop_back();
sum = sum - j;
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
this->k = k;
this->n = n;
dfs(1, n);
return ans;
}
};
括号生成
数字
n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。示例 1：
输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]示例 2：
输入：n = 1 输出：["()"]提示：
1 <= n <= 8
思路：这道题可以看成从 2n 个位置中选 n 个位置填入左括号。对每个位置，左括号要么选，要么不选（换句话说就是选右括号）。这道题就可以用思路一选或不选来做。
回溯三问：
- 当前操作：枚举 path [i] 位置选不选左括号
- 子问题：构造 path 大于等于 i 的部分
- 下一个子问题：构造 path 大于等于 i+1 的部分
由于左括号个数不超过 n 个，所以我们需要一个参数 sum 来记录已经选了几个左括号。假如 sum<n，那么当前位置还可以选左括号。什么时候可以选右括号呢，这是这道题的破题点。举个例子：假如当前的 path 为 ()) ，也就是右括号个数大于左括号，这构不成一个有效括号组合。也就是说只有右括号个数小于左括号的时候，才能选右括号。（如果左右括号个数相同，那下一个只能是左括号。）
剪枝去哪了？为什么这道题好像没有剪枝优化。其实已经剪枝了，在我们思考什么时候选左右括号的时候，天然的把那些不符合有效括号组合的路径剪掉了。
代码：
class Solution {
vector<string> ans;
string path;
int n;
void dfs(int i, int sum) //左括号个数已经sum个了，当前要处理第i个位置
{
if (i == 2 * n)
{
ans.push_back(path);
return;
}
if (sum < n) //已经选的左括号个数小于最多能选的个数
{
path.push_back('(');
dfs(i + 1, sum + 1);
path.pop_back();
}
if (i - sum < sum) //右括号个数小于左括号
{
path.push_back(')');
dfs(i + 1, sum);
path.pop_back();
}
}
public:
vector<string> generateParenthesis(int n) {
this->n = n;
dfs(0, 0);
return ans;
}
};心得：在递归那节我们说过不用纠结整个递归的流程，只要把终止条件和递归关系想清楚，写出来的递归答案一定是正确的。回溯同样如此，不用在脑海中模拟出整个回溯的过程，只要把握好回溯三问，写出来的代码一定能得到正确答案。当然为了方便理解，可以在脑海中模拟一两步，来理清思路。
接下来讲回溯的最后一种类型：排列型回溯。
全排列
给定一个不含重复数字的数组
nums，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。示例 1：
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2：
输入：nums = [0,1] 输出：[[0,1],[1,0]]示例 3：
输入：nums = [1] 输出：[[1]]提示：
1 <= nums.length <= 6-10 <= nums[i] <= 10nums中的所有整数 互不相同
思路：排列和组合的区别就是关不关注顺序。对于排列来讲，[1,2] 和 [2,1] 是不一样的。有了前面题目的基础，全排列问题也不难想。
无非就是枚举每个位置能够填谁。由于我们要关注顺序，也就是说当前位置填 2，下一个位置是可以填 1 的。因此我们用一个 s 数组来维护当前还能填哪些元素。（实际是用 bool 数组来标记某个元素有没有被选过）
回溯三问：
- 当前操作：从 s 中枚举选一个元素 x 填入 path [i] 位置
- 子问题：构造 path 大于等于 i 的部分，集合为 s
- 下一个子问题：构造 path 大于等于 i+1 的部分，集合为 s-x
class Solution {
vector<vector<int>> ans;
vector<int> path;
vector<int> s;
vector<bool> visited;
void dfs(int i)
{
if (i == s.size())
{
ans.push_back(path);
return;
}
for (int j = 0; j < s.size(); j++)
{
if (visited[j]) continue;
path.push_back(s[j]);
//把s[j]从s中删掉。
visited[j] = true;
dfs(i + 1);
//恢复现场
path.pop_back();
visited[j] = false;
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
this->s = nums;
visited = vector<bool>(nums.size(), false);//创建一个长度为 nums.size() 的 vector<bool>，里面每个值都是 false，然后赋值给 visited。
dfs(0);
return ans;
}
};N 皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将
n个皇后放置在n×n的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数
n，返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中
'Q'和'.'分别代表了皇后和空位。示例 1：
img 输入：n = 4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释：如上图所示，4 皇后问题存在两个不同的解法。示例 2：
输入：n = 1 输出：[["Q"]]提示：
1 <= n <= 9
思路：皇后不能同行也不能同列，本质就是每行每列恰好只有一个皇后。可以用 path 数组记录第 i 行的皇后放置在第 path [i] 列。那么我们只需要对 path 在 [0,n-1] 进行全排列。另外皇后不能在同一斜线上，也就是左上和右上不能有其他皇后（因为我们是从第 0 行逐行枚举的，对于当前的皇后，其他皇后只会出现在它的左上或右上）。如何判断左上或右上是否有皇后呢，见下图的数学关系：可以将同一斜线是否有皇后占用封装成一个 valid 函数。
回溯三问和上一道全排列题目是类似的：
- 当前操作：从 s 中枚举选一个元素 x 填入 path [i] 位置（s 代表没有被占用的列的集合）
- 子问题：放置大于等于第 i 行的皇后，集合为 s
- 下一个子问题：放置大于等于第 i+1 行的皇后，集合为 s-x
此题的输出格式也是一个难点，仔细体会下代码中 string 的用法。
代码：
class Solution {
vector<vector<string>> ans;
vector<int> path;
vector<bool> visited;
int n;
bool valid(int r, int c) //第r行 第c列
{
for (int R = 0; R < r; R++) {
int C = path[R];
if (r + c == R + C || r - c == R - C) return false;
}
return true;
}
void dfs(int i)
{
if (i == n)
{
vector<string> board;
for (int c : path)
board.push_back(string(c, '.') + 'Q' + string(n - 1 - c, '.'));
ans.push_back(board);
return;
}
for (int c = 0; c < n; c++)
{
if (visited[c]) continue;
if (!valid(i,c)) continue; //斜线冲突
path.push_back(c);
visited[c] = true;
dfs(i + 1);
visited[c] = false;
path.pop_back();
}
}
public:
vector<vector<string>> solveNQueens(int n) {
this->n = n;
visited = vector<bool>(n, false);
dfs(0);
return ans;
}
};valid 的时间复杂度是 O (n) 可以优化成 O (1)。代码如下：
class Solution { int n; vector<vector<string>> ans; vector<int> path; vector<bool> visited, diag1, diag2; // 列、“/”(r+c)、“\”(r-c+n-1) void dfs(int r) { if (r == n) { vector<string> board; for (int c : path) board.push_back(string(c, '.') + 'Q' + string(n - 1 - c, '.')); ans.push_back(board); return; } for (int c = 0; c < n; c++) { int d1 = r + c, d2 = r - c + n - 1;//r-c可能是负数，负数不能作为下标，负数最小是-n+1所以要加n-1,变为正数。 if (visited[c] || diag1[d1] || diag2[d2]) continue; // 三个方向都没被占用 path.push_back(c); visited[c] = diag1[d1] = diag2[d2] = true; // 占用 dfs(r + 1); path.pop_back(); visited[c] = diag1[d1] = diag2[d2] = false; // 恢复现场 } } public: vector<vector<string>> solveNQueens(int N) { n = N; visited = vector<bool>(n, false); diag1 = diag2 = vector<bool>(2 * n - 1, false);//r+c r+c+n-1 范围[0,2n-2] 所以数组大小应该是2n-1。 dfs(0); return ans; } };
N 皇后 II
n 皇后问题 研究的是如何将
n个皇后放置在n × n的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数
n，返回 n 皇后问题 不同的解决方案的数量。示例 1：
img 输入：n = 4 输出：2 解释：如上图所示，4 皇后问题存在两个不同的解法。示例 2：
输入：n = 1 输出：1提示：
1 <= n <= 9
思路：这个题和上一道的区别就是只需统计方案的数量，不用给出方案。只需在找到一个合法 path 时，也就是 i==n 时，ans++ 即可。
class Solution {
int ans;
vector<int> path;
vector<bool> visited;
int n;
bool valid(int r, int c) //第r行 第i列
{
for (int R = 0; R < r; R++) {
int C = path[R];
if (r + c == R + C || r - c == R - C) return false;
}
return true;
}
void dfs(int i)
{
if (i == n)
{
ans++;
return;
}
for (int c = 0; c < n; c++)
{
if (visited[c]) continue;
if (!valid(i,c)) continue; //斜线冲突
path.push_back(c);
visited[c] = true;
dfs(i + 1);
visited[c] = false;
path.pop_back();
}
}
public:
int totalNQueens(int n) {
this->n = n;
ans = 0;
visited = vector<bool>(n, false);
dfs(0);
return ans;
}
};动态规划
从打家劫舍这道题来开启动态规划的篇章。
打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。示例 2：
输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。提示：
1 <= nums.length <= 1000 <= nums[i] <= 400
这道题首先想到的就是回溯法。因为这道题本质就是枚举每个 num [i] 选不选。所以可以用回溯法第一种思路：选或不选的思路。
回溯三问：
- 当前操作是什么：枚举第 i 个房子选不选。
- 子问题是什么：dfs (i) 的定义：前 i 个房子得到的最大金额。
- 下一个子问题是什么：如果不选，下一个子问题就是前 i-1 个房子得到的最大金额；如果选，下一个子问题就是前 i-2 个房子得到的最大金额。
直接看代码：注意这道题的 dfs 和之前做的不太一样，金额并没有作为 dfs 参数或者设置成全局变量，而是作为了 dfs 的返回值。为什么要这样做，后面会说。
class Solution {
vector<int> nums;
int dfs(int i)
{
if (i < 0) return 0;
int a = dfs(i - 1);
int b = dfs(i - 2) + nums[i];
return max(a, b);
}
public:
int rob(vector<int>& nums) {
int n = nums.size();
this->nums = nums;
return dfs(n-1);
}
};我们是从后往前递归的，能不能从前往后递归，dfs (0) 就是答案呢？
回溯三问：
- 当前操作是什么：枚举第 i 个房子选不选。
- 子问题是什么：dfs (i) 的定义：大于等于 i 的房子得到的最大金额。
- 下一个子问题是什么：如果不选，下一个子问题就是大于等于 i+1 的房子得到的最大金额；如果选，下一个子问题就是大于等于 i+2 的房子得到的最大金额。
int dfs(int i) { // 从下标 i 到 n-1 if (i >= n) return 0; int a = dfs(i + 1); // 不偷 i int b = dfs(i + 2) + nums[i]; // 偷 i return max(a, b); } // 答案就是 dfs(0)
但是时间复杂度太高了，会超时。时间复杂度大概是 O (2ⁿ)。（时间复杂度 = 状态个数✖️单个状态所需要的计算时间）。可以估算，搜索树高度为 n，如果是满二叉树，那么就是 2 的 n 次方个节点。每个节点只做了 O (1) 的工作，所以时间复杂度上界是 O (2ⁿ)。
搜索树：
还可以优化。我们注意到递归的过程其实有很多状态重复计算了。比如不选第 4 个房子，先进入 dfs (3)，之后进入 dfs (2)。而选第 4 个房子，也会进入 dfs (2)。所以我们可以保存已经计算过的状态，下一次进入该状态时，就不用重新算一遍了。这就叫做记忆化搜索。
class Solution {
vector<int> nums;
vector<int> memo;
int dfs(int i)
{
if (i < 0) return 0;
if(memo[i] != -1) return memo[i];
int a = dfs(i - 1);
int b = dfs(i - 2) + nums[i];
memo[i] = max(a, b);
return memo[i] ;
}
public:
int rob(vector<int>& nums) {
int n = nums.size();
memo.resize(n, -1);
this->nums = nums;
return dfs(n-1);
}
};搜索树：
时间复杂度：状态个数 n✖️状态计算时间 O (1)=O (n)。空间复杂度：O (n)
记忆化是从大问题 dfs(n-1) 往下递归到小问题。我们能不能反过来，从最小的子问题开始，一步步往上算？这就是递推。
如何把递归翻译成递推：
- dfs 改为 f 数组
- 递归操作变为循环
- 递归边界条件变为递推的初始条件
把递归式 dfs(i) = max(dfs(i-1), dfs(i-2) + nums[i]) 直接改写成数组 f ：
f[i] = max(f[i-1], f[i-2] + nums[i])
但有个小麻烦： i 会取到 0 ，于是 i-1 、 i-2 变成 -1 、 -2 ，数组下标不能为负。处理办法是整体右移两位，让 f[i+2] 来代表 dfs(i) ：
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
int f[n+2];//int f[n+2] 是变长数组（VLA），属于 GCC 扩展，不是标准 C++。LeetCode 用的是 GCC，所以能编译通过；但换到 MSVC 或纯标准环境会报错。想稳妥的话用 vector<int> f(n+2, 0);。
f[0] = 0;
f[1] = 0;
for (int i = 0; i < n; i++)
{
f[i+2] = max(f[i+1], f[i]+nums[i]);
}
return f[n + 1];
}
};这里就凑齐了动态规划的四大要素：
- 状态定义：
f[i+2]表示 " 前i间房能偷到的最大金额 "。 - 状态转移方程：
f[i+2] = max(f[i+1], f[i] + nums[i])，由前面的状态推出当前状态。 - 边界（初始值）：
f[0] = f[1] = 0，对应没有房子的情况。 - 遍历顺序：从小到大，保证算
f[i+2]时它依赖的f[i+1]、f[i]已经算好。
记忆化搜索和递推的区别只在于：前者从大往小递归（自顶向下），后者从小往大循环（自底向上）。转移方程完全一样。
空间复杂度为 O (n)，因为我们开了大小为 n+2 的 f 数组。
还能继续优化。再观察转移方程： f[i+2] 只依赖前两个状态 f[i+1] 和 f[i] ，更早的根本用不上。既然这样，没必要开一整个数组，用两个变量滚动就够了：
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
int fp;
int fp1 = 0;
int fp2 = 0;
for (int i = 0; i < n; i++)
{
fp = max(fp1, fp2+nums[i]);
fp2 = fp1;
fp1 = fp;
}
return fp;
}
};遇到这类 "每个元素选或不选" 的最优化问题，先想回溯，再优化成动态规划。
其实这道题的回溯代码更像是普通的递归代码，并没有涉及恢复现场操作。我们当然可以写出经典的回溯代码：
class Solution {
vector<int> nums;
int n, best = 0;
vector<int> path; // 共享可变状态
void dfs(int i) {
if (i >= n) {
int sum = 0;
for (int x : path) sum += x;
best = max(best, sum);
return;
}
dfs(i + 1); // 不选第 i 间
path.push_back(nums[i]); // 修改现场：选第 i 间
dfs(i + 2); // 选了就跳过 i+1
path.pop_back(); // 恢复现场 ← 这才叫“回溯”
}
public:
int rob(vector<int>& nums) {
this->nums = nums; n = nums.size();
dfs(0);
return best;
}
};但是大家仔细想想为什么之前的那版没有涉及恢复现场呢？经典回溯（全排列、子集、组合那一类）需要恢复现场，是因为你维护了一个共享的、会被修改的状态：通常是一个全局的 path 数组、 used[] 标记、或者累加的 sum 。这道题没有恢复现场是因为，金额是通过返回值往上传的，没有任何共享可变状态。每个 dfs(i) 自己算自己的答案、 return 出去，相互之间不共用任何会被改写的变量。既然没有 "被改脏的现场"，自然也就没有东西要恢复。
为什么要用这种写法，因为我们要讲的东西是动态规划。这种写法是动态规划的启蒙写法，一步步从记忆化搜索走向递推。
恢复现场的写法 ——"答案" 取决于一路走来的整个 path ，没有 " 给定 i 就能定下来的值 "，所以没法简单地记忆化，
接下来我们要讲解动态规划的最经典的一类题目 —— 背包问题。
从最简单的 01 背包问题入手。
有 N 件物品和一个容量是 V 的背包。每件物品最多选一次。第 i 件物品的体积是 vi，价值是 wi。求总体积不超过背包容量时的最大总价值。
还是从回溯思路出发，和打家劫舍唯一的本质区别：状态多了一维。打家劫舍的 "不能相邻" 靠下标跳到 i-2 就编码完了，一维够用；而 01 背包的约束是 "总体积不超过容量"，容量是一个会被消耗的资源，光靠下标表达不了，必须再开一维 c 记住 "还剩多少容量"。约束需要记住什么信息，就为它开一维状态。
我们写出回溯三问：
- 当前操作：枚举第 i 个物品选还是不选
- 子问题：剩余容量为 c 时，从前 i 个物品中得到的最大价值和。
- 下一个子问题：不选第 i 个物品，那剩余容量不变，下一个子问题变成从前 i-1 个物品中得到的最大价值和。选第 i 个物品，子问题变成剩余容量为 c-vi 时，从前 i 个物品中得到的最大价值和。
边界条件： if (i == -1) return 0 。没有物品可选了，价值就是 0。
class Solution {
int n;
vector<int> w, v;
int dfs(int i, int c)
{
if (i == -1) return 0; //边界条件：没有物品可选，价值为 0
if (w[i] > c) return dfs(i - 1, c); //当前物品体积大于剩余容量，只能不选
return max(dfs(i - 1, c), dfs(i - 1, c - w[i]) + v[i]);
}
public:
int knapsack(int capacity, vector<int>& w, vector<int>& v) {
this->n = w.size();
this->w = w;
this->v = v;
return dfs(n - 1, capacity);
}
};时间复杂度大概是 O (2ⁿ)，会超时。每个物品都有选 / 不选两条分支，且都走向 i-1 ，搜索树是一棵满二叉树，2ⁿ 个节点；这里的 2ⁿ 是紧界（打家劫舍因为有 i-2 分支，是斐波那契式的 1.618ⁿ ）。
改成记忆化搜索的写法：用二维数组 memo[i][c] 保存 dfs 的结果。
class Solution {
int n;
vector<int> w, v;
vector<vector<int>> memo; //-1 代表没访问过
int dfs(int i, int c)
{
if (i == -1) return 0; //边界条件
if (memo[i][c] != -1) return memo[i][c];
if (w[i] > c)
{
memo[i][c] = dfs(i - 1, c);
return memo[i][c]; //装不下，只能不选
}
memo[i][c] = max(dfs(i - 1, c), dfs(i - 1, c - w[i]) + v[i]);
return memo[i][c];
}
public:
int knapsack(int capacity, vector<int>& w, vector<int>& v) {
this->n = w.size();
this->w = w;
this->v = v;
memo = vector<vector<int>>(n, vector<int>(capacity + 1, -1));
return dfs(n - 1, capacity);
}
};时间复杂度：状态个数 n × capacity × 单状态计算 O (1) = O (n・capacity)；空间复杂度 O (n・capacity)。
在打家劫舍中我们学过如何将递归改成递推。
dfs 变成 f 数组，递归变成循环，终止条件变成初始条件。 i-1 会取到 -1 ，数组下标不能为负，所以把 i 这一维整体右移一位，让 f[i+1][c] 代表 dfs(i, c) ：
$f[i][c]=max(f[i−1][c], f[i−1][c−w[i]]+v[i])$
$f[i+1][c]=max(f[i][c], f[i][c−w[i]]+v[i])$
class Solution {
public:
int knapsack(int capacity, vector<int>& w, vector<int>& v) {
int n = w.size();
vector<vector<int>> f(n + 1, vector<int>(capacity + 1, 0));
// f[0][0] = 0; f[0][*] = 0：没有物品可考虑，价值为 0（初始化的时候已经保证了 这个可写可不写）
for (int i = 0; i < n; i++) //起始和终止范围怎么确定，见下方思考
{
for (int c = 0; c <= capacity; c++)
{
if (w[i] > c) f[i + 1][c] = f[i][c];
else f[i + 1][c] = max(f[i][c], f[i][c - w[i]] + v[i]);
}
}
return f[n][capacity];
}
};接下来用滚动数组进行空间优化：
f[i+1][·] 只依赖正上方那一行 f[i][·] ，更早的行碰都不碰，所以去掉 i 维，用一维 f[c] 原地更新。
二维怎么降成一维的 没看懂
class Solution {
public:
int knapsack(int capacity, vector<int>& w, vector<int>& v) {
int n = w.size();
vector<int> f(capacity + 1, 0);
for (int i = 0; i < n; i++)
for (int c = capacity; c >= w[i]; c--) //倒序！
f[c] = max(f[c], f[c - w[i]] + v[i]);
return f[capacity];
}
};思考：内层为什么必须倒序？
转移
f[c] = max(f[c], f[c-w[i]] + v[i])里，右边的f[c-w[i]]应该是 "还没考虑第 i 个物品" 的旧值。倒序（c 从大到小）时，更小的下标c-w[i]还没轮到、还是旧值，保证每个物品只被选一次。若正序，c-w[i]已被更新成新值（可能已经含了第 i 个物品），就会把同一物品选多次 —— 那其实是完全背包的解法。下界停在w[i]，因为c < w[i]时只能不选、f[c]保持旧值不变，不用动。
接下来我们来看一道力扣题：目标和。这道题就是 01 背包问题的变形。
目标和
给你一个非负整数数组
nums和一个整数target。向数组中的每个整数前添加
'+'或'-'，然后串联起所有整数，可以构造一个 表达式 ：
- 例如，
nums = [2, 1]，可以在2之前添加'+'，在1之前添加'-'，然后串联起来得到表达式"+2-1"。返回可以通过上述方法构造的、运算结果等于
target的不同 表达式 的数目。示例 1：
输入：nums = [1,1,1,1,1], target = 3 输出：5 解释：一共有 5 种方法让最终目标和为 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3示例 2：
输入：nums = [1], target = 1 输出：1提示：
1 <= nums.length <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000
这道题乍看和 01 背包没什么关系。需要做一些数学转换，感觉自己想肯定想不出来。这道题题面很简单，就是给数组中的某些元素添加负号，让所有元素加起来最后结果等于 target。假设正数之和是 b，数组元素总和为 s。那么 b-（s-b）== target。恒等变形得到 b=（target+s） / 2。
原问题 "有多少种添符号的方式"，被翻译成了 ——
从
nums里选一个子集，使子集和恰好等于b = (s + target) / 2，问有多少种选法。
b 不就是 01 背包中的最大体积，只不过 01 背包是不超过最大体积，而这道题是恰好等于最大体积，另外从求总价值变成了求方案数。
回溯三问：
- 当前操作：枚举第 i 个元素选不选（加不加正号）
- 子问题：在前 i 个元素中挑选一些元素，和为 c 的方案数。
- 下一个子问题：不选，子问题变成在前 i-1 个元素中挑一些元素，和为 c 的方案数；选，子问题变成在前 i-1 个元素中挑一些元素，和为 c-num [i] 的方案数。
不好想的是边界条件。
if (i == -1) return c == 0 dfs (-1,c) 代表从前 - 1 个数中（i 等于 - 1，代表没有数可以选了，也就是空集合中）选几个元素，和为 c 的方案数。什么都不选 得到的 c 就是 0，如果此时 c 恰好就是 0，那么此时合法方案就是 1（如果 c 为正数，此时没有合法的方案，因为没有数可以凑成 c）。
还要注意在 dfs 前判断一下 target + s <0 || (target + s) % 2 != 0 是否成立，成立的话一定没有合法方案。因为 b 是非负数之和，要求 target+s 一定大于等于 0；b 一定是整数，所以 target+s 不能为奇数。
这里的回溯做法更像是普通的递归，所以我们也可以用递归章节学过的方法来写出正确的代码：系统已经帮我们实现想要的功能函数，直接调用即可。
class Solution {
int n;
int target;
vector<int> num;
int dfs(int i, int c)
{
if(i == -1) return c == 0; //边界条件
if(num[i] > c) return dfs(i - 1, c); //当前的num[i]大于c，那么肯定不能选num[i]。
return dfs(i - 1, c) + dfs(i - 1, c - num[i]);
}
public:
int findTargetSumWays(vector<int>& nums, int target) {
this->n = nums.size();
num = nums;
this->target = target;
int s = 0;
for (int i = 0; i < n; i++) s+=nums[i];
int b = (target+s)/2;
if(target + s < 0 || (target + s) % 2) return 0; //这两种情况下构造不了一个表达式等于target。
return dfs(n - 1, b);
}
};改成记忆化搜索的写法：用二维数组 memo[i][v] 保存 dfs 的结果。
class Solution {
int n;
int target;
vector<int> num;
vector<vector<int>> memo; //-1代表没访问过
int dfs(int i, int c)
{
if(i == -1) return c == 0; //边界条件
if(memo[i][c] != -1) return memo[i][c];
if(num[i] > c)
{
memo[i][c] = dfs(i - 1, c);
return memo[i][c]; //当前的num[i]大于c，那么肯定不能选num[i]。
}
memo[i][c] = dfs(i - 1, c) + dfs(i - 1, c - num[i]);
return memo[i][c];
}
public:
int findTargetSumWays(vector<int>& nums, int target) {
this->n = nums.size();
num = nums;
this->target = target;
int s = 0;
for (int i = 0; i < n; i++) s+=nums[i];
int b = (target+s)/2;
if(target + s < 0 || (target + s) % 2) return 0; //这两种情况下构造不了一个表达式等于target。
memo = vector<vector<int>>(n, vector<int>(b + 1, -1));
return dfs(n - 1, b);
}
};在打家劫舍中我们学过如何将递归改成递推的形式。
dfs 变成 f 数组 递归变成循环 终止条件变成初始条件。
$f[i][c] = f[i - 1][c] + f[i - 1][c - nums[i]]$
$f[i + 1][c] = f[i][c] + f[i][c - nums[i]]$
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
vector<vector<int>> f;
int n = nums.size();
int s = 0;
for (int i = 0; i < n; i++) s+=nums[i];
if(target + s < 0 || (target + s) % 2) return 0; //这两种情况下构造不了一个表达式等于target。
int b = (target + s)/2;
f = vector<vector<int>>(n + 1, vector<int>(b + 1, 0));
f[0][0] = 1;
for(int i = 0; i < n; i++) //起始和终止范围是怎么确定的。
{
for (int c = 0; c <= b; c++)
{
if (nums[i] > c) f[i + 1][c] = f[i][c];
else f[i+1][c] = f[i][c] + f[i][c - nums[i]];
}
}
return f[n][b];
}
};思考：从递归改为递推的表达式，i 变成 i+1，为什么 num [i] 不变呢。另外循环中 i 和 c 的范围如何确定，怎么推导出来。
那个 +1 是加在
f的下标上的，不是加在i这个变量上的。我们做的事情是给 "存储位置" 换个名字，避免负下标。nums 元素就
0到n-1这n个位置，所以i范围是0..n-1。c是 "想凑出的和" 这个状态，它的取值就是从0（空集）到bag（目标和）。
用滚动数组优化空间：
01 背包问题主要有三种常见变形：
- 容量恰好为 V，求方案数 / 最大 / 最小价值和。