LeetCode刷题-56. 合并区间
题目链接：56. 合并区间
¶题解：
区间合并问题，先人的总结，先按照左端点排序再进行合并！
¶题目简述：
给定一堆区间，将重叠的区间进行合并，重新返回！
¶题解：
思路：
按照左端点排序，左端点相同，按照右端点排序
使用l，r两个指针维护最大可拓展区间
若当前左端点严格大于右指针，说明当前区间无法和上一个区间合并，则将上一个区间保存起来，更新新的左右指针为当前区间
若当前左端点小于等于上一个区间，则说明当前区间可以与上一个区间进行合并，则更新最大可拓展区间的右端点（即右指针）
最后将最后一个区间也保存起来
稍做解释：
按左端点排序，再按右端点排序，那么如果有重叠部分的区间，该区间的左端点一定在上一个区间的左端点的后面！这样如果有重叠就合并，没有就插入新的容器！
时间复杂度： 排序O(nlogn)，线性扫描O(n)，总时间复杂度为O(nlogn)
注意点：
特判为空的情况，直接返回
记得要把最后一个区间插入
vector进行排序默认按照第一个值，第二个值等等进行排序
¶AC代码：
1234567891011121314151617class Solution {publ ...
LeetCode刷题-55. 跳跃游戏
题目链接：55. 跳跃游戏
¶题解：
这个是45题跳跃游戏的简化版！
¶题目简述：
本题和 LeetCode刷题-45.跳跃游戏II一样，上一题是要计算到达终点的最小步数！本题不一定能走到终点，问是否能走到终点！
¶题解一：
首先：能跳到的位置一定是连续的一段，即某个位置跳不到，后面位置一定跳不到！
反证法： 假如能跳到i + 1位置，跳不到i位置，那么跳到i + 1位置的位置应该在i位置之前，因为i位置无法跳到，无法从他开始跳，那么该位置可以调到i + 1一定可以跳到i，矛盾！假设不成立，即跳到的位置一定是连续的一段！
解法，一模一样：
同样是具有单调性的动态规划，找到第一个可以到达当前位置i的位置即可！若last已经到了当前位置i，说明到不了当前位置i，也就到不了最后的终点，直接返回false
否则：说明全部点都能到达，返回true
时间复杂度：O(n)
空间复杂度：O(1)
¶AC代码一：
1234567891011class Solution {public: bool canJump(vector<int>& nums) { ...
LeetCode刷题-54. 螺旋矩阵
题目链接：54. 螺旋矩阵
¶题解：
又是旋转相关的模拟题！
¶题目简述：
给定一个矩阵，按照右下左上的顺序进行遍历！
¶题解：
枚举 n * m个点，按照右下左上的顺序循环进行，如螺旋般，一个方向走到头，换下一个方向！
使用0,1,2,3分别表示四个方向，走到头就换一下方向，即d = (d + 1) % 4
使用dx和dy数组表示四个方向坐标的变化。
如果，坐标越界（第一次访问该方向），或者已经访问过的位置（不是第一次访问该方向），就要换到当前方向的下一个方向，同时更新当前坐标。即a < 0 || a >= n || b < 0 || b >= m || vis[a][b]
注意：数组为空的判断！
¶AC代码：
123456789101112131415161718192021222324class Solution {public: vector<int> spiralOrder(vector<vector<int>>& matrix) { vector<int> ...
LeetCode刷题-53. 最大子序和
题目链接：53. 最大子序和
¶题解：
动态规划应用！
¶题目简述：
给定一个数组，找一个连续区间，使得该区间和最大！
¶题解一：
同样使用闫式DP分析法：
状态表示： f[i]表示以i位置结尾的区间的最大和
状态计算： f[i] = max(f[i - 1] + nums[i], nums[i])
初始化： f[0] = nums[0]，res = nums[0]
稍做解释：
f[i]
nums[i]
i - 1 ~ i,i - 2 ~ i…0 ~ i ，将最后一位i抛掉以后，剩下的其实就是f[i - 1]，此种情况的和为 f[i - 1] + nums[i]
最终就是：f[i] = max(f[i - 1] + nums[i], nums[i])
时间复杂度：O(n)
空间复杂度：O(n)
¶AC代码一：
12345678910111213class Solution {public: int maxSubArray(vector<int>& nums) { vector<int> f(nums.size()); ...
LeetCode刷题-52. N皇后 II
题目链接：52. N皇后 II
¶题解：
同样是N皇后，比上一题更加简单。
¶题目简述：
N皇后问题，问最后的方案数！
¶题解：
具体思路详见上一题 51题！
由于问方案数，我们就不必开数组去存储路径了。
在递归出口i == n时， 直接进行统计即可res++.
¶AC代码：
1234567891011121314151617181920212223class Solution {public: vector<bool> col, dg, udg; int res; int totalNQueens(int n) { col = vector<bool>(n); dg = udg = vector<bool>(n * 2); dfs(0, n); return res; } void dfs(int i, int n){ if(i == n){ res ++; return; } for(in ...
LeetCode刷题-51. N 皇后
题目链接：51. N 皇后
¶题解：
经典的N皇后问题！
¶题目简述：
n * n 的棋盘放n个皇后，保证每行每列每条斜线都不能有大于一个皇后！
¶题解：
DFS来一遍即可！
使用col dg udg分别存储列和两条对角线是否有皇后。使用res存储答案，使用path存储路径。
void dfs(int i, int n)
i：代表第几层
n：代表皇后数或棋盘行列数
递归出口： i == n即n个皇后都已经找到，将当前方案加入答案res
使用dg[i + j]和udg[i - j + n] 来标识两条对角线，原因就是你可以将它看成坐标系，一条对角线为y = x + b，另一条为y = -x + b，即可解的b = y - x, b = y + x，y - x可能越界，让他偏移n，即可保证不越界。
递归开始： 只要列以及两条斜线以及没有被访问过，即可访问！使用path[i][j]记录路径，表示i行的j列有一个皇后，更新标记，最后清空标记！
注意：数组的初始化，path需要全部初始化为.，col要初始化n个位置，dg udg要初始化n * 2个位置。
¶AC代码：
1234567 ...
LeetCode刷题-50. Pow(x, n)
题目链接：50. Pow(x, n)
¶题解：
快速幂应用！
¶题目简述：
浮点数的幂运算！
¶题解：
详见之前的这道题详解！
不同之处，可能有负数，一个数的负数次幂，等于1 除以正数次幂，判断一下即可！
注意：由于有负数，要求绝对值可能会越界，使用LL强转一下即可！
¶AC代码：
123456789101112class Solution {public: double myPow(double x, int n) { typedef long long LL; double res = 1; for(LL k = abs((LL)n); k; k >>= 1){ if(k & 1) res *= x; x *= x; } return n > 0 ? res : 1 / res; }};
document.querySelectorAll('.github-emoji')
.forEac ...
LeetCode刷题-49.字母异位词分组
题目链接：49.字母异位词分组
¶题解：
又是一个好巧的做法，借用排序即可处理！
¶题目简述：
将一组字符串数组中每个字符串每个字符相同且数量一致的放到一组返回！
¶题解：
怎么处理？
既然你不一样，我就把你变成一样的，排个序不就行了，排完序后，该是一组的就都变成同一个字符串了，然后使用哈希表做一下映射即可！
具体做法：
定义一个哈希表：unordered_map<string, vector<string>> hash;第一维度存储排序后统一的字符串，第二维度存储没有排序的原始字符串。例如：aet 对应 ate, aet, tae, tea, eat, eta
然后再将第二维度导入一个新数组即可！
¶AC代码：
1234567891011121314class Solution {public: vector<vector<string>> groupAnagrams(vector<string>& strs) { unordered_map<string, vector<st ...
LeetCode刷题-48.旋转图像
题目链接：48.旋转图像
¶题解：
将一个矩阵反转，顺时针，逆时针，以及180度反转！
有更精妙的方法吗？详见下文！
¶题目简述：
将一个矩阵顺时针反转90度！
不能使用额外的数组！
¶题解：
第一想法：转圈来回换，例如1 3 9 7，2 6 8 4， …
但是找下标的关系会很复杂，我第一次就是这样做的，果然，找下标成功将我绕晕了！
有没有更好的办法了？
有的！
对于顺时针90度，先按主对角线对称，再按中间竖线对称！
对于逆时针90度，先按主对角线对称，再按中间横线对称！
对于180度，先按主对角线对称，再按副对角线对称！
顺时针90度：
逆时针90度：
180度：
¶AC代码：
12345678910111213141516class Solution {public: void rotate(vector<vector<int>>& matrix) { int n = matrix.size(); for(int i = 0; i < n; i++){ for ...
LeetCode刷题-47.全排列II
题目链接：47.全排列II
¶题解：
相比上一道多了重复元素！
¶题目简述：
给定一个可包含重复数字的序列，返回所有不重复的全排列。
¶题解：
和 46 题类似，多了重复元素和去重！
步骤也多了两步：
排序，使得相同的元素排到一起
过滤，同一个位置同一个相同元素只用没有使用的第一个元素，并且使用顺序一定是从前到后
过滤方法：i && nums[i - 1] == nums[i] && !vis[i - 1]即遇到和上一个相同，上一个没有被用过，则说明当前数不是第一次被用，就不要取用，跳过即可！
**举个例子：**1(1) 1(2) 3 可能为 1(1) 1(2) 3也可能为1(2) 1(1) 3 ，我们要去除重复的，可以只将顺序排列的留下即可！即相同数的第一个没有被用到，就不要使用第二个，第三个！可以保证相同数只有一种情况，即顺序排列的情况！
¶AC代码：
123456789101112131415161718192021222324252627class Solution {public: vector<vector&l ...
LeetCode刷题-46.全排列
题目链接：46.全排列
¶题解：
全排列问题，经典DFS！
¶题目简述：
给定没有重复元素的序列，输出全排列！
¶题解：
直接搜索加回溯就行了：
参数：
cnt：表示当前搜到第几位数
nums：传入原数组
递归出口：cnt == nums.size()
搜索过的直接跳过即可，使用vis数组标记即可！
¶AC代码：
1234567891011121314151617181920212223class Solution {public: vector<vector<int>> res; vector<int> path; vector<bool> vis; vector<vector<int>> permute(vector<int>& nums) { vis = vector<bool>(nums.size()); dfs(0, nums); return res; } void dfs(int ...
LeetCode刷题-45.跳跃游戏II
题目链接：45.跳跃游戏II
¶题解：
普通动态规划超时，需要想到是否具有单调性，再从单调性出发使用贪心求解！
动态规划难度尚可，加上单调性就复杂了许多！
¶题目简述：
给了一个非负整数数组，每个位置代表能从当前位置挑的最大步数，题目规定一定可以跳到终点，问最短步数！
¶题解一：动态规划
同样使用闫式DP分析法：
状态表示：使用f[i]数组表示跳到i位置的最小步数
状态计算： 那么f[i]应该为前面的所有位置跳到当前位置的步数中的最小值。即t = min(t, f[j] + 1)
最终答案：答案就是f[n - 1]
解释一下：j + nums[j] >= i表示能从j位置跳到i位置
时间复杂度：O(n ^ 2)
空间复杂度：O(n)
时间复杂度有点高，会超时TLE，请看题解二，利用单调性！
¶超时代码：
1234567891011121314151617class Solution {public: int jump(vector<int>& nums) { int n = nums.size(); vector< ...
