回溯专题收尾+贪心专题一
5/23
T45 跳跃游戏二
1、这一题虽然代码很短，但比上一题难度高上一个档次，因为不太好想直观的解法和证明。
2、关键：直接每次找局部最远未必是最优解，需要对覆盖范围内都做处理
3、代码如下：
class Solution {
public:
int jump(vector<int>& nums) {
int ans = 0;
int cur_right = 0;
int next_right = 0;
for (int i = 0; i + 1 < nums.size(); i++) {
next_right = max(next_right, i + nums[i]);
if (i == cur_right) {
cur_right = next_right;
ans++;
}
}
return ans;
}
};
4、正确性证明待独立思考后补充
T55 跳跃游戏
1、这一题我按照贪心的思路蒙了一个算法，结果……AC了！这个思路为何正确，我写的时候不知道，但“蒙一个”是存在逻辑的： 首先，贪心是贪的局部解，最优解则是全局解。既然我们要局部最优，放在本题就对应“局部能跳得尽量远”（全局最优是跳远范围能覆盖到数组终点）。 我的思路如下：
//从开头开始，寻找当前可跳跃范围内下一个元素值+下一个元素索引之和的最大值
//若最终可以覆盖到终点，返回true；否则，返回false
2、代码如下：
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size();
// cover 表示目前能够到达的最远下标
int cover = 0;
// 只遍历当前能够到达的范围
for (int i = 0; i <= cover; i++) {
// 从当前位置 i 出发，最远可以到达 i + nums[i]
cover = max(cover, i + nums[i]);
// 如果最远覆盖范围已经到达或超过最后一个下标，说明可以到达终点
if (cover >= n - 1) {
return true;
}
}
// 如果循环提前结束，说明某个位置之后无法继续覆盖
return false;
}
};
3、正确性证明：先从直觉来看，要想跳到全局，每一个分步都应该尽量利用起最多可利用距离。下面从数学上进行严格证明：
充分性（若能由本算法跳到最终点，则题干条件下必然能跳到最终点）： 证毕，该算法已给出一套解。
必要性（若题干条件满足，则该算法必能推出可行解）：
设存在一条可行跳跃路径：
0=p₀<p₁<⋯<pₘ=n−1
且对任意：
pₜ₊₁≤pₜ+nums[pₜ]
算法维护的 cover 始终表示当前已知的最远可达位置。
证明算法一定不会在到达终点前停止。
对路径上的点做归纳：
初始：
p₀=0≤cover
所以算法一定能遍历到 p₀。
假设算法能遍历到 pₜ，则更新后：
cover≥pₜ+nums[pₜ]
又因为可行路径满足：
pₜ₊₁≤pₜ+nums[pₜ]
所以：
cover≥pₜ₊₁
因此算法也一定能继续遍历到 pₜ₊₁。
由归纳可得：
pₘ=n−1≤cover
所以算法必然在某一时刻得到：
cover≥n−1
并返回 true。
4、关键：这里的cover是一个有趣的在for循环里不断变大的上限，且前面的每一次循环都是+1这种自增，故能遍历到所有小于等于cover的情况，故上述证明成立。
5/22
T122 买卖股票的最佳时机二
1、这一题就很简单了，属于最基础的股票题。把股价变动抽象为相邻元素间的上升、下降峰，取所有单个上峰的和即为最大总利润。
2、注意，本题可删除单日多次交易的题干条件，单日只能交易一次时该算法同样正确。 关键：单日限制只影响同时卖(b)买(b)，假设第一次交易买a卖b，第二次交易买c卖d，其中c b都在同一天交易故相等。由于新卖(d>c=b>a)更大，总差（d-a）依然等于可多次交易的（d-c+b-a）
3、代码如下：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int count = 0;
//计算相邻元素差值
for (int i = 1; i < prices.size(); i++) {
int diff = prices[i] - prices[i - 1];
//有收益就加入
if (diff > 0)
count += diff;
}
return count;
}
};
T53 最大子数组和
1、这一题非常经典，虽然我一开始没有思路，但看完代码后独立想出了正确性证明。贪心代码如下：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int result = INT32_MIN;
int count = 0;
for (int i = 0; i < nums.size(); i++) {
count += nums[i];
if (count > result) { // 取区间累计的最大值（相当于不断确定最大子序终止位置）
result = count;
}
if (count <= 0) count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
}
return result;
}
};
2、正确性证明： 假设前一段【A………K】处第一次count<=0，证明这一段内的最优解已被记录，且抛弃这一段不影响后续寻找最优解，以及最终算法得到的就是最优解。
首先，【A……K】段内的最优解只有三种形式：左闭到中间、中间一段、中间到右闭。为何不会出现中间到右闭+非该段的连续序列作为全局最优解？原因很简单——既然我们第一次count非正是在K处，那么左侧任意一段左闭起始的都为正，因此整个这一段+同样右侧的子序列必然更大，而整个这一段又非正，因此比它更厉害的都被抛弃了，这个解必然非最优。
第一种形式：会被result记录最大值，如果这里面的最大值超过后面出现的解，我们仍会返回该最大值
第二种形式：同理，必然小于等于第一种形式，忽略
第三种形式：同理，必然小于等于第一种形式，忽略
而这一段count又非正，我们可以作为一个整体抛弃它。对于右侧一段，同理可寻得该段内的最优解，直到右指针遍历到数组最右侧，返回result最大值即可。
小拓展：若寻找最小连续子数字，把数组变成相反数，按最大值方法处理即可，再把结果反过来。
3、所有专题刷完后补充线段树、分治算法解法；注意：第二轮刷题时一律模拟全英面试场景
5/21
T376 摆动序列
1、这一题没有那么直观，有些难度，我一开始想错了，忽视掉它“可以删除部分元素”的意思是可以跳跃删除，而非子字符串那样是只能连续截取的（假设更改条件，最优解是否可直接双指针+左指针跳跃？）
2、最优解看起来很简洁，但不那么好想到：
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
// 长度 0/1 直接返回
if (nums.size() <= 1)
return nums.size();
// 前一个差值
int preDiff = 0;
// 当前差值
int curDiff = 0;
// 至少保留第一个元素
int count = 1;
for (int i = 1; i < nums.size(); i++) {
curDiff = nums[i] - nums[i - 1];
// 出现方向变化（峰值/谷值）
if ((preDiff <= 0 && curDiff > 0) ||
(preDiff >= 0 && curDiff < 0)) {
count++;
// 更新方向
preDiff = curDiff;
}
}
return count;
}
};
3、举例说明：如果出现333355555777775555 按照代码逻辑 3 5 过后predif=2，到后面7 5 curdif=-2满足 所以count=3 本质是5 7 5，并非计算的3 5 5这个错误序列，而是正确的中间值。为何这样的逻辑可以成功？
4、这一题的核心逻辑可以如下理解：将总序列抽象为一道道上升、下降的陡坡，相邻的同样方向的陡坡合并为一个坡（也就是不出现方向变化时count不自增），这样遍历一回后，就可以提炼为若干道上下相邻的陡坡，这时再根据题干性质删除不必要的元素，就可以连接这些陡坡，而这些陡坡数量和也必然是最优解。这样看来，会好理解很多。至于平坡的情况，在上一个例子中可以看到，连续相等的数不影响统计，因为predif在3-5的衔接处非零，所以下一个有效坡必然非陡。
5、这一题的本质还是删除连续上升/下降/平坡中的连续中间值，官方题解里有动态规划的解法和证明，后续进行到新专题可以回顾此题。
【贪心专题】
这个专题核心是证明，解题时靠的则是直觉的敏锐度，这基于对多种证明套路的了解。
T455 分发饼干
简单，直接联想到最大化利用，尺寸大的饼干满足胃口大的，排序后双指针移动即可。 代码如下：
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
// 两个数组排序
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int count = 0;
// 两个指针都先指向最大值
int child = g.size() - 1;
int cookie = s.size() - 1;
while (child >= 0 && cookie >= 0) {
// 假如饼干满足胃口
if (s[cookie] >= g[child]) {
count++;
// 两个指针同时左移
child--;
cookie--;
}
else {
// 饼干不够，当前最大胃口满足不了
// 胃口指针左移，尝试满足更小胃口
child--;
}
}
return count;
}
};
证明思路是“交换法”，简单概括为：假如把一个大饼干给小胃口的人，调换之后，另一组小饼干不一定能满足大胃口的人，因此不会出现更优解，故此为最佳解——即优先将大饼干给大胃口的人。
5/20
【回溯专题总结摘录】
1、如果是一个集合来求组合的话，就需要startIndex，如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex。
2、两种经典去重方式： 图片: https://uploader.shimo.im/f/QK6hj6p1cPbB9RZ6.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJleHAiOjE3Nzk1ODkxMDEsImZpbGVHVUlEIjoiV3IzRHAyYndyYnVFMVYzSiIsImlhdCI6MTc3OTU4ODgwMSwiaXNzIjoidXBsb2FkZXJfYWNjZXNzX3Jlc291cmNlIiwicGFhIjoiYWxsOmFsbDoiLCJ1c2VySWQiOjg2Mzc1NzV9.XvzfQmceFQAM-vlxP7pmkfVLfVweN1i7mEUGBmIVRt8
图片: https://uploader.shimo.im/f/WeTNifUdloqcfUSc.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJleHAiOjE3Nzk1ODkxMDEsImZpbGVHVUlEIjoiV3IzRHAyYndyYnVFMVYzSiIsImlhdCI6MTc3OTU4ODgwMSwiaXNzIjoidXBsb2FkZXJfYWNjZXNzX3Jlc291cmNlIiwicGFhIjoiYWxsOmFsbDoiLCJ1c2VySWQiOjg2Mzc1NzV9.XvzfQmceFQAM-vlxP7pmkfVLfVweN1i7mEUGBmIVRt8
3、回溯法性能分析汇总： 子集问题分析： 时间复杂度：O(2^n)，因为每一个元素的状态无外乎取与不取，所以时间复杂度为O(2^n) 空间复杂度：O(n)，递归深度为n，所以系统栈所用空间为O(n)，每一层递归所用的空间都是常数级别，注意代码里的result和path都是全局变量，就算是放在参数里，传的也是引用，并不会新申请内存空间，最终空间复杂度为O(n) 排列问题分析： 时间复杂度：O(n!)，这个可以从排列的树形图中很明显发现，每一层节点为n，第二层每一个分支都延伸了n-1个分支，再往下又是n-2个分支，所以一直到叶子节点一共就是 n * n-1 * n-2 * ….. 1 = n!。 空间复杂度：O(n)，和子集问题同理。 组合问题分析： 时间复杂度：O(2^n)，组合问题其实就是一种子集的问题，所以组合问题最坏的情况，也不会超过子集问题的时间复杂度。 空间复杂度：O(n)，和子集问题同理。 N皇后问题分析： 时间复杂度：O(n!) ，其实如果看树形图的话，直觉上是O(n^n)，但皇后之间不能见面所以在搜索的过程中是有剪枝的，最差也就是O（n!），n!表示n * (n-1) * …. * 1。 空间复杂度：O(n)，和子集问题同理。 解数独问题分析： 时间复杂度：O(9^m) , m是’.’的数目。 空间复杂度：O(n^2)，递归的深度是n^2
T37 解数独
1、回溯专题最后一题，也是困难标签。但是，这一题直接回溯的话本质和N皇后还是很像，格子的形状也类似，这个数字不行就换一个。无剪枝的代码也能高效运行（题目不会出大数目）：
class Solution {
public:
bool row[9][10]{};
bool col[9][10]{};
bool box[9][10]{};
bool dfs(vector<vector<char>>& board) {
// 找下一个空格
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') continue;
int bid = (i / 3) * 3 + j / 3;
// 尝试填1~9
for (int num = 1; num <= 9; num++) {
if (row[i][num] ||
col[j][num] ||
box[bid][num])
continue;
// 填入
board[i][j] = num + '0';
row[i][num] = true;
col[j][num] = true;
box[bid][num] = true;
if (dfs(board))
return true;
// 回溯
board[i][j] = '.';
row[i][num] = false;
col[j][num] = false;
box[bid][num] = false;
}
// 当前空格无解
return false;
}
}
// 全填完
return true;
}
void solveSudoku(vector<vector<char>>& board) {
// 初始化状态
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.')
continue;
int num = board[i][j] - '0';
row[i][num] = true;
col[j][num] = true;
int bid = (i / 3) * 3 + j /3;
box[bid][num] = true;
}
}
dfs(board);
}
};
2、关键：棋盘的每一个位置都要放一个数字（而N皇后是一行只放一个皇后），并检查数字是否合法，解数独的树形结构要比N皇后更宽更深。
3、二维回溯
5/19
T51 N皇后
1、第一道困难级别的题，不过我上课时做过类似的题目，毕竟这个场景太有名了哈哈。顺便，力扣企业上这道题三个月内同时被谷歌苹果考察过，因此非常重要。
2、实际上，这一题还有贪心算法，以及其他可用逻辑，在算法设计课上有详细讲过。
3、这一题可以巧妙加入不同程度的剪枝，因为一个皇后确定后，她周围横刷斜的许多位置便可以直接跳过。不过，这一题的N不超过9，每次判断is valid再回溯也是可行的。
4、经典代码如下：
class Solution {
private:
vector<vector<string>> result;
// n 为输入的棋盘大小
// row 是当前递归到棋盘的第几行了
void backtracking(int n, int row, vector<string>& chessboard) {
if (row == n) {
result.push_back(chessboard);
return;
}
for (int col = 0; col < n; col++) {
if (isValid(row, col, chessboard, n)) { // 验证合法就可以放
chessboard[row][col] = 'Q'; // 放置皇后
backtracking(n, row + 1, chessboard);
chessboard[row][col] = '.'; // 回溯，撤销皇后
}
}
}
bool isValid(int row, int col, vector<string>& chessboard, int n) {
// 检查列
for (int i = 0; i < row; i++) { // 这是一个剪枝
if (chessboard[i][col] == 'Q') {
return false;
}
}
// 检查 45度角是否有皇后
for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
if (chessboard[i][j] == 'Q') {
return false;
}
}
// 检查 135度角是否有皇后
for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (chessboard[i][j] == 'Q') {
return false;
}
}
return true;
}
public:
vector<vector<string>> solveNQueens(int n) {
result.clear();
std::vector<std::string> chessboard(n, std::string(n, '.'));
backtracking(n, 0, chessboard);
return result;
}
};
T47 全排列二
1、这一题和上一题的关键区别就是去重，去重不是在最后强行遍历，而是在回溯的过程中利用如下代码： if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { continue; }
2、完整回溯代码：
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking (vector<int>& nums, vector<bool>& used) {
// 此时说明找到了一组
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
// used[i - 1] == true，说明同一树枝nums[i - 1]使用过
// used[i - 1] == false，说明同一树层nums[i - 1]使用过
// 如果同一树层nums[i - 1]使用过则直接跳过
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
}
if (used[i] == false) {
used[i] = true;
path.push_back(nums[i]);
backtracking(nums, used);
path.pop_back();
used[i] = false;
}
}
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
result.clear();
path.clear();
sort(nums.begin(), nums.end()); // 排序
vector<bool> used(nums.size(), false);
backtracking(nums, used);
return result;
}
};
// 时间复杂度: 最差情况所有元素都是唯一的。复杂度和全排列1都是 O(n! * n) 对于 n 个元素一共有 n! 中排列方案。而对于每一个答案，我们需要 O(n) 去复制最终放到 result 数组 // 空间复杂度: O(n) 回溯树的深度取决于我们有多少个元素
5/18
T46 全排列
1、这道题用分治递归会很慢，回溯法还是更合适
2、从刚才一题加上这一题，可以看出回溯、排列组合中哈希数字used非常常见
3、最优解如下：
class Solution {
public:
vector<vector<int>> result;
// 当前排列
vector<int> path;
// nums[i] 是否已经使用
vector<bool> used;
void backtracking(vector<int>& nums) {
// 一个排列完成
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
// 已经放进排列里
if (used[i]) continue;
// 选择
used[i] = true;
path.push_back(nums[i]);
// 递归填下一个位置
backtracking(nums);
// 回溯
path.pop_back();
used[i] = false;
}
}
vector<vector<int>> permute(vector<int>& nums) {
used.resize(nums.size(), false);
backtracking(nums);
return result;
}
};
T491 非递减子序列
1、这一题我开始时思路如下： //先找出所有子序列，再看看是不是递增的（只要出现不递增就直接灭掉） //注意剪枝，子序列开头出现不递增就不必更长了，更长的包含不递增的全部剪去
2、但是，这种解法只打败了11%的leetcode题解耗时，说明还存在大量不必要的内容。最优解：回溯中保证递增+记录用过的数字
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex) {
// 至少两个元素即可加入
if (path.size() >= 2) {
result.push_back(path);
}
// 本层去重
bool used[201] = {false};
for (int i = startIndex; i < nums.size(); i++) {
// 不递增，剪掉
if (!path.empty() && nums[i] < path.back()) {
continue;
}
// 本层已经出现过
if (used[nums[i] + 100]) {
continue;
}
used[nums[i] + 100] = true;
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
backtracking(nums, 0);
return result;
}
};