LeetCode刷题-79. 单词搜索
题目链接：79. 单词搜索
¶题解：
纯搜索题！
¶题目简述：
在一个矩阵中找一个字符串，看是否存在，找的时候只能上下左右找，不能走走过的地方！
¶题解：
DFS搜索： bool dfs(int x, int y, int u)
x, y：为当前位置下标
u：记录当前搜到的个数
递归出口：u == word.size() - 1
思路：
把每个点都当做起点进行搜索，每次搜索四个方向
若当前搜索位置和待匹配字符不匹配，直接return false
否则标记当前位置为*表示该位置已使用，且无法与待匹配字符进行匹配
开始搜索四个方向，保证下标不越界
如果有一个方向符合条件，直接终止搜索，返回return true，即if(dfs(tx, ty, u + 1)) return true;（可以保证有一条有效路径就直接终止搜索）
for循环结束，说明当前位置无法继续向前，还原该位置标记，返回return false
有一个起点符合即终止，全部起点都不匹配，直接返回return false
注意：
向四个方向搜索，判断条件没有写是否访问该点，其实写不写都可以，因为下一次搜索如果搜 ...
LeetCode刷题-78. 子集
题目链接：78. 子集
¶题解：
与之前的题几乎一致：AcWing-92.递归实现指数型枚举
¶题目简述：
给定一个集合，枚举所有子集，包括空集！
¶题解一：使用二进制
和之前题一样，做法一模一样：
每个数选与不选两种情况，一共有0 ~ 1 << nums.size() - 1种情况，枚举每个二进制位是否为1即可！
时间复杂度： 一共枚举2n 个数，每个数枚举n位，总时间复杂度为 O(2n * n)
注意： 当 n >= 30时，2n > 109 会超时
¶AC代码一：
12345678910111213class Solution {public: vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>> res; for(int state = 0; state < 1 << nums.size(); state ++){ vect ...
LeetCode刷题-77. 组合
题目链接：77. 组合
¶题解：
简单递归！
¶题目简述：
在 n 个数选取 k 个数的组合！
¶题解：
DFS思路：dfs(int u, int start)
u：记录当前搜到了第几个数
start：记录当前数的开始位置，即从上一个数的后一个开始，有效避免重复
res累积答案，path保存每一组合法序列！
递归出口：u == k 搜完u个数即终止！
时间复杂度： 方案数为 O(Cnk )，每个方案需要O(k)，总时间复杂度为O(Cnk * k)
¶AC代码：
12345678910111213141516171819202122class Solution {public: int n, k; vector<vector<int>> res; vector<int> path; vector<vector<int>> combine(int _n, int _k) { n = _n, k = _k; dfs(0, 1); return res; ...
LeetCode刷题-76. 最小覆盖子串
题目链接：76. 最小覆盖子串
¶题解：
滑动窗口界的一大难题！
¶题目简述：
给定两个字符串，从一个串找到包含另一个字符串所有字符的子串，并找到最短的一个！
¶题解：
双指针算法：
两个指针都从起点从左向右，i指针指向该区间终点，j指针指向该区间起点，维护一段区间i ~ j使得该区间包含待匹配字符串的每个字符。
具体做法：
为了判断该区间是否包含待匹配字符串的每个字符，我们使用一个哈希表动态存储该区间每个字符出现的次数
使用变量cnt统计该区间有效字符个数（即待匹配字符串中对应匹配的字符），只要该区间当前字符个数小于等于待匹配字符串的当前字符个数，即为有效字符，进行统计，即hs[s[j]] <= ht[s[j]]
维护起点j，若新加入的字符导致hs[s[j]] > ht[s[j]]，则说明起点j可以后移，即 hs[s[j ++ ]] --，还得保证起点j一定是一个合法字符（即起点一定不是待匹配字符串没有的字符，如：ADOBECODEBA 匹配 ABC，应该要将起点A删去，再将DOBECODE删去。剩下BA，即这里是需要while来控制的）
当cnt == t.s ...
LeetCode刷题-75. 颜色分类
题目链接：75. 颜色分类
¶题解：
通过双指针思路将区间划分开，并进行维护区间操作！
¶题目简述：
给定0、1、2三个数字的乱序序列，按照0，1，2的顺序将相同数字排到一起！
要求不使用排序函数！
¶题解：
思路：双指针，其实是三指针，i和j 从前往后扫描，k从后往前扫描，维护下面三个区间
0 ~ j - 1：保证都是0
j ~ i - 1：保证都是1
nums.size() - 1 ~ k + 1：保证都是2
i和k相遇即排好序！
nums[i]的三种情况：
nums[i] == 0：swap(nums[j++], nums[i++]) 交换后i位置为1，可以直接往后走，即i++
nums[i] == 1：该位置属于为1的区间，直接i后移，即i++
nums[i] == 2：swap(nums[i], nums[k--]) 交换后i位置未知，不可以直接往后走
时间复杂度： O(n)
¶AC代码：
12345678910class Solution {public: void sortColors(vector<int>& nums) { ...
LeetCode刷题-74. 搜索二维矩阵
题目链接：74. 搜索二维矩阵
¶题解：
二维的二分，第一次见，其实可以通过取除和取余转换为一维！
¶题目简述：
给定一个二维有序矩阵，从左到右，从上到下，都是升序序列，每行最末小于下一行最开始！
判断知否存在一个目标值！
¶题解：
嗯，暴力，使用额外数组将二维变为一维！
再进行二分！
二分条件：v[mid] >= target
注意：
对空矩阵判断，两种情况[]，[[]]，所以需要matrix.empty() || matrix[0].empty()
其实可以将一个0 ~ n * m - 1的数转变为一个二维下标的：
matrix[mid / m][mid % m]：第一个算行，第二个算列即可！
详细代码见AC代码二！
¶AC代码一：暴力
12345678910111213141516171819class Solution {public: bool searchMatrix(vector<vector<int>>& matrix, int target) { if(matrix.empty() || matr ...
LeetCode刷题-73. 矩阵置零
题目链接：73. 矩阵置零
¶题解：
LeetCode题目总是要求不使用额外空间。。导致这道题做法就特别取巧，不好想！
¶题目简述：
给定一个矩阵只有0和其他数，将是0的对应的改行与该列都变为0！
要求不使用额外空间！
¶题解：
本来这题开一个数组即可，非要求原地处理。。。
现在给出空间O(1)的算法：
使用两个变量r0和c0分别记录第一列和第一行是否有0
使用矩阵的第一行matrix[0][j]记录第j列是否有0（j 的范围为 1 - m - 1)
使用矩阵的第一列matrix[i][0]记录第i行是否有0 （i 的范围为 1 - n - 1)
现在就可以根据上面的记录去处理每一行和每一列了！
时间复杂度： O(n * m)
¶AC代码：
12345678910111213141516171819202122232425262728293031class Solution {public: void setZeroes(vector<vector<int>>& matrix) { if(matrix.empt ...
LeetCode刷题-72. 编辑距离
题目链接：72. 编辑距离
¶题解：
动态规划应用，很有意思！
¶题目简述：
将一个单词变为另一个单词，只有三种操作，替换，删除，插入！问最少步数！
¶题解：
动态规划：
状态表示： 两个字符串，使用二维数组f[i][j]表示a字符串的的0 - i和b字符串的 0 - j匹配时的最少步数！
状态计算： 处理最后一步， 三种情况
删除一个字符：f[i][j] = f[i - 1][j] + 1 即a字符串删除一个会匹配，则a字符串的前i - 1个是和b字符串的前j个匹配，所以当前最少步数就是该匹配最少步数加一（当前删除操作的一步）
插入一个字符：f[i][j] = f[i][j - 1] + 1 解释：与上面同理
替换一个字符：两种情况
a[i] == b[j]：即该字符已经匹配无需替换，f[i - 1][j - 1] + 0
a[i] != b[j]：即该字符已经匹配需要替换，f[i - 1][j - 1] + 1
综上所述： 状态转移方程为：f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1; f[i][j] = min(f[i] ...
LeetCode刷题-71. 简化路径
题目链接：71. 简化路径
¶题解：
模拟题，总是处理两个斜杠中间字符！
¶题目简述：
给定一个绝对路径，该绝对路径以/开始，不一定以/结束，并且可能会出现连续斜杠，要求转换为最简的路径！
./：当前目录
../：上层目录
根目录没有上层目录，仍为根目录
¶题解：
思路： 将两个斜杠中间的字符截取出来，进行判断
答案的格式保证一定是/xxx/xxx...
.：即为当前目录，不处理，跳过即可
..：即返回上一层目录，将当前答案字符串res从后向前删到第一个斜杠，再将此处斜杠删掉（保证不越界）
空：即两个斜杠挨着，不处理，跳过
目录名：合法目录，将在答案最后加一个斜杠，再加上当前目录名
/：即累积的中间字符结束
注意：
以防给定的绝对路径最后不是空格，导致最后一组斜杠中间的字符无法截取，我们给最后没有斜杠的绝对路径加一个斜杠进行统一！
每次将name字符串清空
对于在根目录进行上层操作的行为，会使得最后答案为空，所以在最后判断一下是否为空，是则返回一个斜杠！
string的back()和pop_back()属于C++ 11 标准！
¶AC代码：
123456789101 ...
蓝桥杯省赛-1207. 大臣的旅费
题目链接：蓝桥杯省赛-1207. 大臣的旅费
题目来源：第四届蓝桥杯省赛C++A组
¶题解：
本题用到了许多知识！下面给出参考教程及必备知识！
链式前向星：我的简单总结！点击这里！
树的直径及树形DP：秦淮岸灯火阑珊大佬的数的直径及树形DP讲义！点击这里！
秦淮岸大佬讲义对应视频：点击这里！
两次BFS搜索：DaulFrank大佬的两次BFS搜索！点击这里！
两次DFS搜索：小呆呆大佬的两次DFS搜索！点击这里！
¶两次搜索与树形DP区别：
两次搜索可以求出数的直径的路径与值！写起来略麻烦！
树形DP仅仅可以求出值！写起来简单！
¶知识积累一：树的直径
首先先引入圆的直径：
圆的直径就是圆上两点连线的最长的时候，所以树的直径就是树上最远两个点的距离！
官方解释：
在一棵树中，每一条边都有权值，树中的两个点之间的距离，定义为连接两点的路径上边权之和，那么树上最远的两个点，他们之间的距离，就被称之为，树的直径。
树的直径的别称，树的最长链。
请注意：树的直径，还可以认为是一条路径，不一定是只是一个数值。
稍做解释：
当树的边权都为1或者没有边权时，即为树的最长连
当树的边权不 ...
LeetCode刷题-70. 爬楼梯
题目链接：70. 爬楼梯
¶题解：
简单动态规划问题！
¶题目简述：
每次只能爬一个台阶或两个台阶，求爬到第 n 个台阶的方案数！
¶题解：
动态规划：
状态表示：f[i]表示爬到第 i 个台阶的方案数
状态计算：f[i] = f[i - 1] + f[i - 2]
简单解释：爬到第 i 个台阶的最后一步，一定是跨了一步或跨了两步，所以到达当前台阶的方案数一定是前 i - 1个台阶的方案数和前 i - 2 个台阶的方案数之和！
初始转态： f[0] = 1 f[1] = 1
最终结果： f[n]
优化一下，不开辟数组，降低空间复杂度，只使用三个变量即可，如下！
时间复杂度： $O(n)$
空间复杂度： $O(1)$
¶AC代码：
123456789101112131415161718192021class Solution {public: int cnt; int climbStairs(int n) { // vector<int> f(n + 1); // f[0] = 1; // f[1] = 1; ...
LeetCode刷题-69. x 的平方根
题目链接：69. x 的平方根
¶题解：
二分应用求平方根！一定要斟酌好使用哪个模板！
¶题目简述：
开平方，小数部分舍去求整数部分！
¶题解：
使用二分解决，一定要选对模板！
选不对模板，会有特别情况需要去处理！
¶AC代码一：二分模板一
防止溢出，加一个 1ll
条件：mid <= x / mid （不要使用mid * mid会溢出）最终找到的是小于等于根号x的最大整数！
123456789101112class Solution {public: int mySqrt(int x) { int l = 0, r = x; while(l < r){ int mid = l + r + 1ll >> 1; if(mid <= x / mid) l = mid; else r = mid - 1; } return r; }};
¶AC代码二：二分模板二
防止溢出，加一个 0ll
条件：mid >= x / ...
