LeetCode刷题-91. 解码方法
题目链接：91. 解码方法
¶题解：
简单的动态规划题！
¶题目简述：
将A ~ Z编码为 1 ~ 26，给定一个数字字符串求共有多少种解码方式！
¶题解：
动态规划：
状态表示： f[i]表示前i个字符的解码方法数
**状态计算：**考虑最后一步
最后一位不为0时，解码数为f[i - 1]
最后两位为10 ~ 26时，解码数为f[i - 2]
综上所述，状态转移方程为： f[i] = f[i - 1] + f[i - 2]
最终结果： f[n]
初始转态： f[0] = 1 ，初始转态为0还是1由是否能满足所有状态的正确性决定，由于f[1] = s[1] != '0' ? 1: 0;，所以f[0] = 1!
时间复杂度：O(n)
注意：
为了使得处理边界简单，将字符串前面加空格处理！
¶AC代码：
1234567891011121314151617class Solution {public: int numDecodings(string s) { int n = s.size(); s = ' ' + s; vect ...
LeetCode刷题-90. 子集 II
题目链接：90. 子集 II
¶题解：
又是不能重复的递归问题，和LeetCode刷题-47.全排列II此题的关键位置有点像！
¶题目简述：
给定一个包含重复元素的无序序列，返回该序列可以构成的不能重复的所有组合！
¶题解：
递归：
关键部分：如何去重？
首先将数组排序，使得相同元素挨到一起
对于1 2 2来说，处理1 x x时，第二位只使用第一个2即可，不要让他使用第二个2即可！
i <= start ：保证该位置的第一次选择直接使用第一个重复元素
i <= start && nums[i] == nums[i - 1]：保证该位置的下一种选择方案要保证不是重复元素
时间复杂度：最多有 2^n 个子集，每个子集存储需要O(n)计算量，总时间复杂度为：O(n * 2^n)
¶AC代码一：
for循环去处理长度为0 ~ n的情况！
递归出口：当前位数 == 需要位数，即u == n
AC代码二更加简洁！
1234567891011121314151617181920212223class Solution {public: vector< ...
LeetCode刷题-89. 格雷编码
题目链接：89. 格雷编码
¶题解：
一个有趣的题，做法也是特殊的，需要记住！
¶题目简述：
格雷编码是一个二进制数组合，每两个二进制数对应位数只能有一位不同，所有的组合对应的数集合称之为格雷编码！
给定一个数，为二进制位数，返回该位数的格雷编码集合！
¶题解：
特殊题目： 特殊做法，记住即可！
思路：
n位二进制，共有2^n种组合！
先将n-1位的二进制位，上下轴对称，再将轴上方的最后补0，轴下方的最后补1即可！
如下图：
简单解释一下正确性：
对n - 1来说，已经满足格雷编码性质，现在来看n的情况：
对于轴上部分，原来相邻的都差一位不同，在最后都加一个相同的0则还是相邻之间差一位
对于轴下部分，原来相邻的都差一位不同，在最后都加一个相同的1则还是相邻之间差一位
对于轴上下相邻部分，由于轴对称，原来是完全一致的，现在一个加0，一个加1，也满足差一位的性质
对于数组具体存储数字的处理：
轴上的部分在最后加0，相当于整体左移一位，即res[i] *= 2 或 res[i] << 1，没有产生新数据，原数据发生改变
轴下的部分在最后加1，相当于原数加1产生 ...
LeetCode刷题-88. 合并两个有序数组
题目链接：88. 合并两个有序数组
¶题解：
挺有意思的题，使用原数组多余空间来存储！
¶题目简述：
给定两个有序序列，第一个序列的总长度为两序列之和，多出来的长度为0，即空的！要求使用原数组（可以放得下两数组的数据）不开辟空间进行有序存储！
¶题解：
嗯，如果从前向后扫描，会将第一个数组的前面覆盖掉！
既然第一个数组后面是空的，何不利用起来，先往第一个数组最后从后向前放数据，这样就不会造成覆盖问题！
**具体：**从后向前扫描，较大的放到第一个数组最后，依次向前放
双指针？一个指针i指向第一个数组最后一个元素，一个指针j指向第二个数组最后一个元素，然后从后向前扫描即可！
nums1[i] > nums2[j]：nums1[k--] = nums1[i--];
nums1[i] <= nums2[j]：nums1[k--] = nums1[i--];
结束条件：其中一个数组扫描完了
**最后：**两种情况
第二个数组没扫描完，则从后向前依次放到第一个数组
第一个数组没扫描完，则不用操作，想想，是不是？因为剩下的空间和第一个数组空间一致，并且，第一个数组本来就是 ...
LeetCode刷题-87. 扰乱字符串
题目链接：87. 扰乱字符串
¶题解：
本题也可以使用动态规划，但是似乎是三位数组的表示，及其复杂！
本题可以使用递归分解子问题求解！较为简单一些！
¶题目简述：
给定一个字符串，我们可以把它逐层分解为子串，类似于二叉树，我们可以对非叶子节点（叶子节点只有一个字符）进行交换，然后该节点对应的儿子节点和父节点就会发生改变，最终的字符串就会发生一部分的反转！
给定原串和一个待确认字符串，求解是否是原串通过反转得到的，即为扰乱字符串！
¶题解：
由于动态规划及其复杂，我们这里换一种思路来做！
递归思想：
对于该扰乱字符串的简单理解，就是将一部分长度内的字符串在某个位置进行了前后对调，既然如此，我们就可以通过递归找到该长度的字符串，进而和待匹配串对应的位置进行比较即可！
**两种情况：**该区间反转和该区间未反转
简单举例：以gr区间和eat区间为例， 此时区间长度i = 2：
不反转，great和great：则需要原串的前i个字符和待匹配串的前i个字符匹配，并且原串的后n - i个字符与待匹配串的后n - i个字符匹配，即isScramble(s1.substr(0, i), s ...
LeetCode刷题-86. 分隔链表
题目链接：86. 分隔链表
¶题解：
又是一道链表题，自己做又写成了死循环。。。
一定要画图去做！
¶题目简述：
给定一个无序链表，给定一个目标值，将小于目标值的节点放到大于等于目标值的左边！
¶题解：
很明显：要将链表一分为二，一部分放小于目标值，一部分放大于目标值。
具体思路：如下图
遇到小的放到一个链表，遇到大的放到另一个链表，最后将小的链表尾指向大的链表头，再将大的链表的末尾指向空即可！
注意：为了防止两个链表头找不到，一定要预先设置两个头lh, rh，并设置虚拟头结点，否则lt, rt后面的指向会乱，而且会构成死循环！（我好像就错到了这里）
时间复杂度：O(n)
¶AC代码：
1234567891011121314151617181920212223/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solu ...
LeetCode刷题-85. 最大矩形
题目链接：85. 最大矩形
¶题解：
似乎动态规划也可以做，但好像是三维的数组表示，比较复杂！
本题可以借助上一题思想，使用单调栈求矩形面积！
本题求矩形面积，使用动态规划较为复杂，如果求的是正方形，使用动态规划就简单了！
¶题目简述：
给定一个只包含0，1的矩阵，找到一个只包含1的面积最大的矩形！
¶题解：
暴力思想：枚举每个点，将其作为右下角，枚举长宽，枚举长宽围成的矩形内的0，1。
时间复杂度为：O(n^2 * n^2 * n^2)，爆炸级别的复杂度！
正确思想：
本题竟然能和单调栈求矩形面积的上一题有关联！
我们按照矩阵的每一行作为可能出现都是1的矩形的底边，从该底边求一个最大矩形即可，和上一题类似，求最大矩形面积一样，将所有行作为底边枚举一遍求出来的就是所有可以形成的矩形，最大矩形就是答案！
完全使用上一题求最大矩形的函数
枚举每一行，并取最大值即可
关键问题：如何求柱子高度，即从当前点可以向上走的高度（即该柱子都是1）？
可以使用动态规划：
状态表示：h[i][j]表示该位置向上可以走的最大距离
状态计算：h[i][j] = 1 + h[i - 1][j]，即 ...
LeetCode刷题-84. 柱状图中最大的矩形
题目链接：84. 柱状图中最大的矩形
¶题解：
第二次遇到单调栈了，不太好理解的一个算法和思路！
和LeetCode刷题-42.接雨水很是类似！
¶题目简述：
给了一堆高高低低的柱子，要求从中找到一个面积最大的矩形！
¶题解：
首先想一下以某一个柱子为矩形上边界怎样得到该最大矩形？
很好想，只要在其左右两边找到离他最近的第一个比他矮的柱子即可！因为比他高，则说明可以继续向外拓展，比他矮就不行了！
到了这里，就会发现本题的实质就是：找到一个数左边第一个比他小的数和右边第一个比他大的数即可，面积就是左右间隔乘以该柱子高度取最大值即可！
这里就要想到使用单调栈了，单调栈的核心就是：找到一个数左边第一个比他小的数！
现在先稍微解释一下单调栈实现的原理：
由于该栈单调递增，对于当前处理的柱子来说，需要找到左边第一个比他矮的柱子
所以从栈顶开始往回看第一个比他矮的，比他高则该栈顶出栈，直到找到比他矮的，然后该柱子进栈
一个问题：删了该栈顶不会影响后面的柱子吗，当然不会！对于后面的柱子，也要找左边第一个比他矮的柱子，如果下一个柱子比当前栈顶高，则第一个矮的就是当前栈顶（即上一个柱子）否则， ...
LeetCode刷题-83. 删除排序链表中的重复元素
题目链接：83. 删除排序链表中的重复元素
¶题解：
与上一个题类似，链表操作！
¶题目简述：
给定一个有序链表，将有重复的元素删掉（有重复的保留一个）
与上一题全删有点不同
¶题解：
由于重复元素可以保留一个，所以第一个节点处理和后面一样，所以这里不需要建立虚拟头结点了！
思路：
判断后面节点和当前已扫描节点形成的链表的最后一个节点是否相同
若相同，则跳过当前节点，指向该节点下一个节点l->next = l->next->next
若不同，则指向当前节点，即l = l->next
相同时，保证末尾l不动，next移动，不同时，l直接移到不同的节点。
时间复杂度：O(n)
¶AC代码：
1234567891011121314151617181920/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */cla ...
LeetCode刷题-82. 删除排序链表中的重复元素 II
题目链接：82. 删除排序链表中的重复元素 II
¶题解：
链表的操作题，感觉对这类链表操作还不太熟练，多做做吧！
¶题目简述：
给定一个有序链表，只要出现重复元素，就将该段重复元素删去（注意：不是删的只留一个，而是该段全删）
¶题解：
类似双指针做法：
一个指针p->next指向已扫描位置的下一个位置，一个指针q指向第一个与上一个指针值不一样的位置。(直到与上一个指针不同是为止！)
此时有两种情况：
两指针相距一即p->next->next == q：即待扫描该位后面无重复元素，已扫描链表后移p = p->next
两指针相距大于一即p->next->next != q：即待扫描的该位后面有重复元素，跳过重复一段，直接指向第一个不重复元素p，即p->next = q
注意：
由于要从没有扫描的下一个位置开始，为了方便，建立虚拟头结点，此时未扫描部分对第一个节点的处理就和其他节点统一了，最终返回dummy->next
时间复杂度：O(n)
¶AC代码：
12345678910111213141516171819202122 ...
LeetCode刷题-81. 搜索旋转排序数组 II
题目链接：81. 搜索旋转排序数组 II
¶题解：
和之前题目类似：LeetCode刷题-33.搜索旋转排序数组
¶题目简述：
给定一个有序有重复元素的序列，从某一个点反转一下，问该序列是否存在目标值！
比之前类似题目多了一个重复元素！
¶题解一：二分
其实不需要使用二分，因为二分最坏时间复杂度也为O(n)！
我们使用二分的思路来做一下：
与之前写法完全一致，就是多了一点，不能直接进行二分！
由于多了重复元素，会使得，该序列前一个升序的开始和后一个升序的结尾会有重合部分，无法通过二分得到中间值！
所以：将第二个升序序列从末尾开始，如果和第一个升序序列开始一样，就删去，这样就完全转化为之前的题目了！
具体操作：
while(R >= 0 && nums[0] == nums[R]) R--; 就多了这一句，将重复部分删掉，注意删到只有一个元素的情况，直接判断返回即可
接下来和之前类似题目一模一样
先二分得到两端升序序列的分隔点
再判断在哪个序列
进行第二次二分找目标值
最后判断返回结果
具体思路：参考之前题目：LeetCode刷题-33.搜索旋转排序数组 ...
LeetCode刷题-80. 删除排序数组中的重复项 II
题目链接：80. 删除排序数组中的重复项 II
¶题解：
与之前一道题几乎类似：LeetCode刷题-26.删除排序数组中的重复项
¶题目简述：
类似题目是删除排序数组重复项，最多出现一次，这个题是最多出现两次！
要求：使用原地算法，即不开辟额外空间！
¶题解：
思路：
k < 2时，直接存储到原数组
k > 2时，判断当前元素和和该元素之前的前两个元素是否相同，若之前已经有两个和当前元素相同，则该元素多余直接跳过，否则累积起来，即nums[k ++ ] = x
最后返回长度k
时间复杂度：O(n)
¶AC代码：
12345678910class Solution {public: int removeDuplicates(vector<int>& nums) { int k = 0; for(auto& x : nums) if(k < 2 || nums[k - 1] != x || nums[k - 2] != x) nums[k ++ ...
