所有代码详见：https://github.com/jingminglake/Leetcode
总体思路
数组的题目第一反应是暴力求解，把所有解空间找到，并进行遍历，之后再考虑优化，例如使用动态规划优化，双指针或者hash来做。 最重要的还是要找到特点：例如字符串问题，是否是固定字母开头。
字符串省空间技巧：还是用原来字符串，但是使用新的下标，表示修改后的index。 subsequence：子序列，注意的是子序列中顺序还是和母序列一致(occur in order)，这点一定要考虑到。
数学知识：cn0+cn1+cn2+…+cnn＝2^n。 理解：左边可以看作所有子序列的选择方式（选择x个的所有可能），右边可以理解为一个所有的子序列可以看作对每个元素的选或不选。
具体题目
48. Rotate Image
题意： 使用O（1）的空间来将矩阵顺时针旋转90度。
解：由于使用O（1）的空间，那么使用交换的策略，试着将矩阵沿着i，j相等的对角线两两交换，发现结果与想要的结果之间列的顺序是颠倒的。 列调整顺序不好实现，但是行调整顺序是容易实现的。所以解法是先将矩阵行逆序，然后沿着i，j相等的对角线两两交换。
121. Best Time to Buy and Sell Stock
题意：在股票价格数组中，只能买卖各一次，求最大差值。
解：暴力求解，就是选两个点看差值，时间为O（N^2）。进一步考虑解空间，发现最大差值其实是落入以每个结点为卖出点来计算差值的情况之一。 维持一个值保存最小值，每次遇到比最小值大的数，就计算更新差值，如果遇到比最小值小的数，那么更新最小值。这样保证了，每个大值总是减去他左侧的最小值。时间优化到O(N)。
122. Best Time to Buy and Sell Stock II
题意：在数组中，买卖不限次数，求最大利润。
解：此题解空间是波形图中的所有上升波段的总和。 一开始以为要找到上升的波峰和波谷，即极大值和极小值，然后累积之间的差。其实不需要，举个例子：1，4，8。不一定需要找到1和8，然后8-1。可以改为发现4比1大，就计算4-1，发现8比4大，就计算8-4，然后4-1+8-4就等于8-1。 也就是说，俩俩数进行考虑，只要后面的数比前面的大，那么就将差值计入差值总和。
123. Best Time to Buy and Sell Stock III
题意：在数组中，买卖两次，求最大利润。
解：此题变为动态规划题，数组每个点有四种状态，hold1，sold1，hold2，sold2，分别表示在当前结点i这个时刻做出买入或者卖出操作后变成这种状态，且使得当前账户余额最大是多少。 hold1，sold1，hold2，sold2其实是四个数组，而在对当前结点i进行操作想把整个买卖过程变成这种状态的时候，这四种状态其实有着牵制的，例如hold1和sold1没有发生，那么hold2就不能发生。 但是这些不发生可以使用合适的初始化来避免，例如没有发生hold1和sold1，那么sold1就是0，而正常情况下，发生sold1后，利润一定是大于0的；又例如没有发生hold2，就不能发生sold2，解决方法是hold2初始化为INT_MIN， 也就是说，基于INT_MIN直接sold2不可能作为结果。
之间相互转化关系是： hold1 = max (hold1, -price); // 在这个点第一次持有（买入）股票时候，自己的利润是负的，且这种负利润越大越好，越大意味着买入越便宜的股票；显然，在只单独考虑第一次买入的时候，最优解就是当前遇到的最小价格。
sold1 = max (sold1, hold1 + price); // 在这个点进行第一次卖出股票的时候，考虑当前价格和之前买入的最便宜股票，也要考虑是不是当前点卖出确实比之前卖出都要好
hold2 = max (hold2, sold1 - price); // 在这个点进行第二次买入的时候，其实和第一次考虑的点一样，只不过买入前的利润不是0，而是sold1
sold2 = max (sold2, hold2 + price); // 在这个点进行第二次卖出股票的时候，和第一次卖出进行同样考虑，只不过需要基于第二次买入的价格进行考虑
price表示当前访问股票的price。 注意：这种公式其实是对数组结构的优化：每次状态变化的时候，考虑的只是之前的关联状态下的最大账户值。 初始化hold1是-prices[0], hold2是INT_MIN，sold1和sold2为0，循环之后，sell2就是要求的结果。
PS. 洞见：hold1到sold1始终是扫描过程中会更新到遇到的最大上升波峰。hold2到sold2始终是当前最大波峰，加上之前尚未更新的hold1到sold1。
188. Best Time to Buy and Sell Stock IV
题意：在数组中，买卖k次，求最大利润。
解：此题是动态规划，如果买卖次数大于数组一半，那么相当于股票第二题。如果小于数组一半，那么相当于第三题的通用情况，也就是加入了买卖次数的维度。 假设dp[i][j]表示i天里面进行j次交易的最大利润，那么有关系式： dp[i][j] = max {dp[i - 1][j], dp[x][j - 1] + prices[i] - prices[x]), 0 <= x < i。
理解：第i天要么不操作（也就是等于之前的最优结果），要么就是第i天进行卖出操作完成最后一笔交易，并考虑需要考虑在第x天进行买入的情况下的最大利润。
编码思路：从依赖关系知道，循环是：i: 0, n - 1; j: 0 ～ k。但是需要考虑二维矩阵的初始化，第一天所有的最大利润应该是0，而且交易次数不是1，而是0。
时间复杂度：如果是每次计算时候，都计算前面j-1个dp[x][j - 1] + prices[i] - prices[x]结点，那么时间复杂度是O(n * n * k)。优化的方法是双重循环过程中，记录前一列的最小的dp[x][j - 1] - prices[x]，需要按列访问。
空间复杂度：O(n * k)。由于(i, j)格子的信息只依赖(i - 1, j)和(x, j - 1)，所以空间可以使用滚动数组压缩到两列，也就是O(n)，此时需要按列访问。
PS. 为什么不考虑第i天买入呢？因为买入时候会对总利润进行减少，显然不可能使得dp[i][j]最优。 参考：https://www.hrwhisper.me/leetcode-best-time-to-buy-and-sell-stock-i-ii-iii-iv/
56. Merge Intervals
题意：给出一些区间，把其中有重叠的区间进行合并。
解：暴力求解，对每个区间看其他区间是否有重复，然后合并，这样时间复杂度很高，O(N^x)。对于二维题目，优化的技巧就是首先固定一个维度。
此题，先将所有区间按区间的左端点大小排序。好处就是每次只需要考虑当前的区间和之前合并后的最后一个区间，且当前区间的左端点一定在 该区间的右侧。
当前区间和之前的最后区间的关系是：合并或者不合并。
具体举例来说是三种情况：例如：（1，4）和（5，6）； （1，4）和 （3，5）； （1，4）和（2，3）。
其中后两种都是属于可以合并的情况，如果合并，那么将合并后的区间变成最新的最后数组，如果不能，那么当前区间直接变成最新的最后数组。
时间复杂度是O(nlogn)，因为需要排序。
697. Degree of an Array
题意：数组的度是指数组中出现次数最多的元素的次数多少，注意的是数组的众数可能不止一个，它们的元素大小不一样，但是数量（出现次数）是一样的。 现在要求和数组的度相等的最小连续数组的大小。
解：对某个众数找到出现在最左侧的元素和最右侧元素时候，这就是当作答案的候选者之一，答案是其中最小的跨度。
第一步：找到众数的大小，方法是扫描数组，使用hash记录元素出现次数，并使用一个额外变量degree记录次数的最大值。 第二步：找出和度一样多的元素的最左下标和最右下标。 第三步：找出第二步坐标中差值最小的。
简化为： 第一遍扫描数组，使用一个hash表记录数组元素的个数，并使用一个degree变量记录遇到最大的元素次数，另一个记录元素出现的最左和最右下标。 第二遍扫描，找出次数与degree相等的元素里跨度最小的即可。
686. Repeated String Match
题意：重复扩充字符串A，看是否可以包含另一个字符串B。
解：字符串A每个字母开头，长度足够的情况下，如果其中一种能包含字符串B，那么能包含，否则不能包含。 扩充字符串A，直到A的长度不小于B，然后看是否能包含，如果不能包含，再继续扩充一次，再看看是否包含，如果还不能包含，那就不可能能包含。
459. Repeated Substring Pattern
题意：是判断字符串s是否是s自己一个子串t的重复。
解：暴力求解，一个串的子串有n^2个，然后比较每个串能不能拼成s，这样花费O(n^3)。
仔细观察，发现子串t必然是以第一个字母开头的，不然肯定不符合要求。 因此，只需要考虑第一个字母开头长度为1，2，…size/2的子串，然后看是否能恢复成原串就好。 注意边界条件：空串返回false； “a”，”abc” 返回false，因为自己不能作为自己的子串，花费时间O(n^2)。
119. Pascal’s Triangle II
题意：求杨辉三角的第k行。
解：我们知道杨辉三角的从上到下的每行分别是: (1), (1,1), (1,2,1), (1,3,3,1), (1,4,6,4,1)… 例如我们求第4行，首先知道，第4行是有四个元素，设立结果为(1,1,1,1)，然后，第一行和第二行的时候，结果是不变的， 但是对于第三行，它的第二个元素是存在左右肩膀的，所以需要更新为左右肩膀之和，数组更新为(1,2,1,1)； 同理，对于第四行，它的中间两个元素是存在左右肩膀的，更新为 (1,3,3,1)。 也就是说，求第i行，就是需要按行规律来不断的更新中间的元素。 注意修改顺序是按下标从大到小修改的：因为每一行要更新的元素对之前元素的依赖是: vec[i] = prev[i] + prev[i - 1]。 从小到大顺序会影响之和的元素，反之则是保留了之前的变化。
238. Product of Array Except Self
题意：修改数组：对于每个元素，修改为除了该元素外其余元素的乘积，且不准使用除法，以及空间复杂度要求为O（n）。
解：对于每个元素，除他以外的乘积其实分为两个部分：一个部分是左边元素的乘积，另一个部分是右边元素的乘积。所以，可以建立一个左侧累乘数组和右侧累乘数组。这样保证了O（n）的时间复杂度。
如果要减少些空间使用，可以只使用一个左侧累乘数组，右侧累乘数组可以改为使用一个变量保存当前的累乘，辅助当前元素得出最终结果即可。
186. Reverse Words in a String II
题意：翻转一个字符数组（包含空格字符），里面的字符连起来的单词还原到正常单词。
解：先翻转。然后，双指针，一个指针指向新单词开头，另一个扫描。一扫描到空格，就将空格前的部分翻转，并更新第一个指针到新单词的开头。 边界条件: 数组中只有一个单词，此时没有空格。
151. Reverse Words in a String
题意：翻转一个字符串，里面的单词得还原到正常单词。
解：此题麻烦之处在于不是简单的翻转，而是要删除开头结尾多余的空格，中间的空格也只能留一个。 先整个翻转。然后，双指针，一个指针start指向新单词开头，另一个扫描。一扫描到非空格，看start是否等于0，如果等于0，说明当前扫描的是第一个单词，那么不用增加空格，如果不为0，那么start先加1，并把当前位置置为空格表示插入了一个空格。 在结束后，还要将start之后的部分（都是空格）切除掉。 方法二：使用istringstream。
8. String to Integer (atoi)
题意：实现atoi，atoi输入的串，例如： “ ＋0012a123 ” 都是合法的，结果为12。
解：判断输入串的合法性是不现实的，所以，正确做法是，用一个指针进行扫描。扫描前，先把前面空格吃掉，然后，在后面一步步累加数的时候，每加一个字符，先判断是否是数，如果是数，那么累加数，然后判断当前结果是否超过了INT_MAX和INT_MIN，如果超过了就返回相应最大值。如果不是数字，那么返回最新值即可。
553. Optimal Division
题意：X1/X2/X3/../Xn中加入括号，让整体值最大，其中X都是正整数。
解：此题关键在于得知X1/(X2/X3/../Xn)就是答案。因为除法之间是有先后顺序的，也就是没有结合律的。现在要使得分子最大，分母最小。也就是X1/(X2/X3/../Xn) = (X1 X3 *..Xn)/X2的时候（公式理解：分子分母同时乘以Xn, Xn-1, …X3）。 同理，使得分母最小，那么就要尽可能的除，而且(X2/X3/…/Xn) < (X3/X4/…/Xn)。此时使得分子最大，分母最小，也就是说：。
PS.为什么（X1/X2）/(X3/../Xn) < X1/(X2/X3/../Xn)？对（X1/X2）/(X3/../Xn)进行推导，分子分母依次同乘以Xn, Xn-1, …, X4，得到 （X1/X2）* (X4X5…Xn) / X3，然后分子分母乘以X2,得到 (X1 * X4 * X5 …Xn) / (X2 *X3)。其中(X1 * X4 * X5 *…Xn) < (X1 *X3 *..Xn),且(X2 *X3) > X2。 从X3, X4开始进行分割也是一样。
73. Set Matrix Zeroes
题意：如果矩阵里有一个数为0，那么他所在的行列都清零。要求是空间复杂度为O（1）。
解：此题的困难之处是保持O（1）空间。 技巧就是，利用第一列和第一行的空间来标记该行和列是否要被清空，然后只要先使用两个bool来分别保存第一列和第一行是否该被清空，然后在最后把第一列，第一行清空。
如果第一行第一个元素为1，假设第一行有0，那么把他变为0没关系，因为迟早要被清零；如果第一行没有0，那么他还一直是1，没问题。
如果第一行第一个元素为0，那么说明第一行有0，那么还是应该被清空。
396. Rotate Function
题意：F函数等于B的下标乘以对应下标值的总和。数组B每次循环右移一位。求所有的F函数中最大的那个。
解：这是数学题。如果使用暴力求解，那么每次移动是O（n）时间，也就是计算一次F需要O（n）时间，所以计算所有的F的总时间是O（n^2）。 而使用数学技巧，可以将时间复杂度降到O（n）。如何做到的呢？大致思路就是F和上一项F之间存在公式关系，且该公式只需要消耗O（1）时间。 以Fk - Fk-1为例：计算的关键在于理解Bk-1[0]=Bk[1], Bk-1[1]=Bk[2]…这样计算出来Fk - Fk-1 = sum - nBk[0]。 这样只需要两边循环就可以求解，第一遍计算sum和F0，第二遍利用公式来递推F，保存其中的最大值即可。
13. Roman to Integer
题意：罗马数字转整数。
解:罗马数字特殊计数进制不是固定一个进制的，而是按1，5，50，100，500，1000来计算。靠近大整数的罗马数喜欢用后面整数，减去前面数字来表示。 所以解法是，先加上每个字母对应数字，如果该字母比前一个字母大，那么减去前面的双倍即可。
28. Implement strStr()
题意：实现子串匹配。
解：经典算法是KMP。但是如果想简单实现，可以使用n方的方法。求解的过程中加入优化，就可以减少时间消耗。考虑母串，所有可能的解就是，从下标0开始的直到母串长度减去子串长度的下标。然后匹配过程中只要一个失配，那么马上进入下一个下标。 KMP：先根据子串构建next数组，然后在匹配过程中，一旦失配，那么子串根据next数组跳到相应的下标，继续匹配。
306. Additive Number
题意：AdditiveNum是指：”112358” = {1, 1, 2, 3, 5, 8}； “199100199” = {1, 99, 100, 199}。 检验否是这样的数。
解：一开始以为是动态规划。但是不是。此题解题关键在于三点： 1.只要确定了前两个数，那么就可以知道整个串基于这两个数是否可以为Additive Number。
2.要以长度为限制来遍历前两个数，这样比双指针要好操作的多。
3.第一个的长度限制是i <= len / 2; 第二个长度限制是 size - i - j >= max(i, j)。这是因为第三个数的长度一定不小于前两个数长度中最大的那个。 注意：number是long long型的，int不够用。
348. Design Tic-Tac-Toe
题意：判断Tic-Tac-Toe游戏每一步之后的输赢。输入保证有效。
解：每一步只需要O（1）时间判断输赢。方法如下：玩家1下的被标记为1，玩家2下的被标记为-1。对每列每行都维持一个数，代表总和。那么我们知道，当总和的绝对值等于行列大小的时候，说明玩家1或玩家2占满了这一行（列）。 同理在正反对角线都维持一个数，表示对角线是否被占满。对当前一步下的棋，如果当前行列和两条对角线之中有一个满了，那么就说明赢棋。
567. Permutation in String
题意：给出串s1和串s2，判断s1的一种排列是不是可以是s2的子串。
解：注意是s2的子串，也就是说在n^2的空间中长度等于s1串中寻找，有len(s2) - len(s1)个。
方法：找出len(s2) - len(s1)个子串，并分别计算字符种类对应的数量，看是否等于s1的字符数量。
找len(s2) - len(s1)子串可以使用双指针，维持一个s1串大小的窗口，可以加入或者丢弃字符。
其中字符种类可以使用大小26的int数组，这样只需要常量时间就可以判断两个串是不是这种”异构”字符串了。
165. Compare Version Numbers
题意：比较版本号之间的大小。
解：此题的坑在于：1.0和1版本一致。那么按.切分数字的时候，空要被当做0来算,也就是说1和1.0.0.1来比较，其实是把之前的1看做是1.0.0.0。所以循环选两个长度中大的，在另一个越界的时候，全当作0来处理。
419. Battleships in a Board
题意：2D棋盘上，一行或一列（不一定满）的被称作战船，而且题目保证战船之间至少有一格间隙，也就是说不会出现不合法的战船。要求的是战船的数量。
解：此题一开始以为是BFS。后来发现并不是。只需要按照从左到右，从上到下的顺序扫描一遍棋盘即可。一旦是X，那么看他的左边或者上边是否也是X，如果是说明重复计算了，该点不用考虑了。如果不是，则结果加1。
54. Spiral Matrix
题意：螺旋顺序打印出矩阵中的数。
解：此题可以使用DFS，不过也可以直接循环求解。方法是：维持四个指针，指向行列的两头。然后每轮安排四个方向的扫描。首先沿着行头从左向右访问，访问之后行头指针加1，然后沿着列尾从上到下访问，访问之后列尾指针减1。然后沿着行尾从向右向左访问，如果行头仍然小于等于行尾的话；最后是沿着行头从下向上访问，如果列头仍然小于等于列尾的话。循环得出结果。 也可以使用dfs，保持四个方向，每次吃掉一个方向，把吃掉的点、也就是已经处理的点进行标记，防止重复访问，然后每次吃不动的时候，就切换到下一个方向继续。
722. Remove Comments
题意：删除代码里面的注释。给出的是按行分割的代码。如果是\/**/注释，那么后面行的内容将被处理成一行。
解：迭代，分两种注释进行处理，\/**/注释，后面行的内容将被处理成一行。取出每一个单词，取出当前单词处于非注释状态下的部分，然后看当前单词会不会产生新的注释，或者在已经注释状态下，会不会产生结束注释。
245. Shortest Word Distance III
题意：给出一个单词数组和其中的两个单词，求两单词最小的下标距离，因为单词可以在数组中多次出现。两个目标单词可以是同一个单词，但是答案不是0，因为一个单词从数组只能算一次。
此题并非是244的follow up，而是最初始题目的follow up，也就是说不需要多次计算，计算最近单词的下标距离。
解：此题分两种情况处理，第一种是单词相同，那么一遍循环，找出俩俩相邻的下标距离，找出最小的；
第二种是两个单词不同，
首先，暴力求解就是得出两个单词所在下标的数组，然后比较这两个数组，暴力俩俩比较是O(n^2)，
实际上下标数组本来就是有序的。因此，可以使用双指针，一开始两个指针分别指向两个数组的开头， 每次移动指向较小数的指针，因为移动意味着数字变大，所以移动较大数毫无意义。时间复杂度是O(n)，空间复杂度O(n)。
也可以不使用额外数组：两个不同单词的时候，还是一遍扫描数组，只是在发现单词进行切换后，就计算下标差距作为候选值。 时间复杂度是O(n * w) ，w是目标单词的长度，空间复杂度O(1)。
PS. 此技巧适用于244题。
311. Sparse Matrix Multiplication
题意：给两个稀疏矩阵，求乘积。
解：暴力计算只需一个三重循环就可以，一开始的两重循环是第一个矩阵的行和第二个矩阵的列，然后每一行和每一列里面有着第一个矩阵的列次（或者是第二个矩阵的行次）乘法然后累加。 暴力计算在稀疏矩阵时候不是很好，因为有大量的0重复相乘，因此要优化0的处理。 计算的时候，不要一个数一次计算出来，而是考虑第一个矩阵每个数所在的位置，对最终矩阵的最终位置的单独影响。 第一个矩阵A中的元素(Ai,Aj)，在第二个矩阵B中能够进行乘法结合的就是(Bj, Bk), 0 <= k <= nB;而对最终矩阵C的贡献在于 (Ci, Ck)。每次计算都累加到最终结果。能够优化之处就是，一旦发现(Ai, Aj)为0，那么就省去计算它的贡献了。 使用双重循环，循环A中的每个元素。
PS.稀疏矩阵有一个常见的压缩算法，那就是http://www.cs.cmu.edu/~scandal/cacm/node9.html
大致思想就是：稀疏矩阵转为邻接表。每行只需要保留值不为0坐标的下标和值，也就是(index, val)作为元素的链表就可以了。
这样压缩之后，可以方便的对一行进行点乘，例如和一个vector
也可以对同样的压缩方式的坐标数组进行点乘，使用双指针。
835. Image Overlap
题意：两个图片（01矩阵）都是正方形且大小一样，现在移动两个图片，求包含最多1的相交部分。
解：暴力求解就是计算AB两个图片之间的相对位置，然后对相交部分进行双循环计算重合的1，这样时间复杂度是O(n^4)。
但是此题可以使用311稀疏矩阵的套路来进行优化。 记录两图片同位置一个点的所有的相对位置delta，例如图片B相对于图片A，我们知道B可以出现在A的八个方向上，考虑图片B的左上角（设图片A的左上角是原点）相对于A的左上角，坐标取值范围是 delta_x：-n ~ n， delta_y：-n ~ n。delta可能为负数，但是可以之前就全部加上n来平移。一种delta代表一种重复的情况。 不要一次性的计算重合部分，而是在整个的O(n^4)的循环过程中，零星的累加记录不同delta里面重合1的个数。具体来说，把图片B作为背景图片，现在研究图片A每个像素对delta的贡献： 对A进行双重循环，也就是对A中一个点PA，然后相对B中某个像素点PB，其实可以理解为把PA移到PB，产生的效果，最终效果就是对delta_x = i2 - i1, delta_y = j2 - j1产生的 贡献（如果两个坐标所在值都为1，那么才为1， 如果有一个为0，那么就为0）。 这样好处是在图片B像素点为0的时候跳过对整个图片A的一个双重循环。
277. Find the Celebrity
题意：找名人，名人就是一个人不认识其他任何人，而被其他人所认识。名人有就只能有一个。
解：暴力求解就是一个二重循环，每个人做不成名人的条件就是：他认识其他任何人中的一个，或者有一个人不认识他。
优化成O(n)的解法就是：首先要知道，名人只可能有一个。发现这种有向图中，只可能有一个结点是没有出边的，其他点都是存在出边的。
首先，先将0作为候选人，然后从1开始循环到n-1，将被认识的人更新当作候选人，因为候选人不认识的人做不成名人，与此同时，之前的候选者必然不是候选人，因为他们至少认识一个人。
第二步，再次循环一遍，判断该候选人是否是真的名人。名人必然是不认识其他人和被其他人认识的。第一步无法保证候选人不认识任何一个其他人以及其他人都认识他，也就是说，第一步做的其实是一个粗糙的排除法。 此题本质是有向图，找出有向图的没有出边的点。第一步，从一个结点出发bfs，直到找到一个没有出边的点作为非候选者；第二步，看是不是其他点有这个邻居。
14. Longest Common Prefix
题意：一个字符串数组，求其中所有串的最长公共前缀。
解：暴力求解，基于第一个字符串，遍历后面的串，所有都相等则都移动一步，一旦出现不匹配，或者下标越界，那么立即返回第一个字符串0到当前下标的子串。
161. One Edit Distance
题意：判断字符串s和t是不是一个编辑距离。
解：所谓一个编辑距离有两种情况：（1）s和t长度相等，只有一个字符不同； （2）s和t之间长度相差1，多出来的那个元素可以在字符串的任何位置，剩余字符串元素必须一一相等对应。 其余情况都要返回false，只有满足（1）或（2）的才能返回true。
此题解的时候可以分情况去写，但是有一些节省循环代码的优化：关键是先找到s和t第一个不等的元素，如果是情况（1），那么剩余的子串要相等，否则返回false；如果是情况（2），那么长的一个去除当前不等元素开始到结尾的子串应该和短的不去除当前元素到结尾的子串相等，否则返回false。 如果找不到不相等的元素，那么看二者长度相差是否为1，为1就是true，否则为false。
PS.使用c++要注意，字符串的length取出来是无符号数，进行减法计算前要强制转换为带符号的类型。 abcd和acd也属于one edit，在b和c失配的时候，要比较cd和cd，也就是较长的串直接跳过失配字符，短串仍然需要考虑失配字符。 还有一个坑就是s等于t的时候，是不算只有一个距离的，应该返回false。
43. Multiply Strings
题意：实现字符串的乘法。假设俩串为s和t。
解：关键是要在乘法的解法中找规律。对简单的示例（例如s =“123”，t = ”45“）进行观察，首先，总的结果长度不会超过s+t（理解：即使是9999，那么也是小于10000的）。这样，首先设置总的结果存放的数组，初始时候每位都为0. 其次，列出发现s下标i和t下标j乘法后的规律：就是只会对结果数组的第i+j和i+j+1的下标进行影响。接下来要考虑乘法计算内部相加的顺序，发现对i+j位的影响是不可能变成0然后对i+j-1位造成进位的，理解：例如99 = 81。从右向左计算的时候，即使81的1变成0，进位，那么也只可能是8变9，而不会变成0进位给i+j-1。所以对i+j+1位要考虑进位，对i+j位则是直接加等就好。 计算顺序的技巧，记住即可：双重的for循环，每个循环都从右向左进行计算。 计算结束后，记得要把结果数组中的前面的0去掉,如果是全0，那么直接返回0。
88. Merge Sorted Array
题意：大意是把num2数组合并到num1数组里面去。num1的空间足够大（num1后面的空间是可以用的）。
解：肯定是可以不使用额外空间的，要想办法利用num1的空间。方法就是，从后往前合并。
57. Insert Interval
题意：给出一些区间数组，然后在给一个区间t，求把该区间合并到之前区间中。原始区间已经按照头排好序。
解：被t影响后，原来数组会更新一个区间，关键是找到新区间的头和尾。 新区间的头是扫描数组区间的时候看哪个区间的尾大于新区间的头，找到第一个该区间后，看该区间的头与t的头哪个小，返回其中小的作为新区间的头。 新区间的尾是扫描数组区间，看哪个区间的头大于t的尾，此时说明当前区间以及之后的区间和新区间没关系了。此时再看之前一个区间的结尾和t的结尾哪个大，选择大的作为新区间的尾。 边界情况：第一，如果是t区间很小，不跨越任何区间，那么发现不受影响。
第二，如果t区间出现在所有区间的前面，那么新区间的头判断没问题，尾判断可能会遇到没有之前区间的问题。此时要看t区间的尾和第一个区间的头，来判断新区间的尾，更巧妙的方法是将新区间的尾初始化为第一个区间的头。
第三，如果t区间出现在所有区间后面，那么找不到比t尾大的区间头，此时如果是t区间的头比最后一个区间的头大，那么只需要直接把t区间加入，反之新区间的尾是t的尾。 程序过程：首先，扫描，如果区间end小于t的start，那么加入区间结果。扫描后，看是不是后面没有区间了，如果没有区间了，说明出现了边界情况3，这时把t加入结果，返回就可以了。如果不是，那么看当前区间的start和t的start相比，小的作为新区间的头。 接着扫描，这次看每个区间的开头，如果开头小于t的结尾，说明这些区间都可以被合并到新区间，因此接着扫描并更新最新的end，直到出现区间的开头小于t的结尾，跳出此次扫描，然后把最新合并的区间放入结果。此时，如果没有区间了，说明是边界条件3，直接返回就行了。否则，继续扫描后续区间，此时后面区间与前面区间无关了，只需要加入结果就可以了。
68. Text Justification
题意：给出单词数组和每行长度，现在要求把单词按顺序按行排列，要求左右对齐。
解：此题解法就是双指针字符串操作，双指针的窗口就是left指向的单词和right指向的单词能够放一行最大数，然后在安排单词之间的间隔数，即计算每个间隔的空格数。 每行计算出该有的单词数之后，分三种情况，第一种，单词数量大于1，那么得计算间隔数，以及余数，来填充单词间空格。 第二种，只有一个单词，那么加入单词后，后面全部填入空格。 第三种，数组中没有单词了，那么说明这一行填不满，这种情况下也当作只有一个单词来处理。
498. Diagonal Traverse
题意：按对角线来打印矩阵，扫描顺序是交替变化的。
解：此题一开始想使用模拟遍历法，发现遇到边角的时候，很难处理边界情况，例如矩阵[(1,2),(3,4)]中，遇到2，下一个访问的应该是3，但是对于一个奇数的矩阵[(1,2,3),(4,5,6),(7,8,9)]来说，遍历到右上角的3的时候，下一个访问的是6。这种边界条件难以区分。
现在考虑另一种做法：可以知道，此题相当于矩阵对角线遍历的follow up。对角线的遍历，是先从第一列的列头开始向右上方遍历，然后是最后一行的第二个元素开始向右上方遍历，这样，一旦走出矩阵，那么当前层的遍历就结束了。
所以，此题可以利用这样的方法，唯一的区别在于，交替的时候方向发生变化。
也就是说，如果是偶数层的时候，使用反方向的遍历就可以了。不过反向时候要新方法找起点。
另外，此题需要先将结果数组大小确定出来，然后更新相应下标就可以了，如果使用边遍历边记录的话，太耗费时间在数组增长上了。
两个关键：一个是对对角线进行标记，第0条，第1条，…第i条
另一个是对角线上的点(x, y)满足一个性质：x + y == i。
463. Island Perimeter
题意：求二维矩阵小岛的周长。
解：直接判断，方法一：扫描所有格子，如果是1，那么看该格子四周的格子，如果出界了，或者是水的话（等于0），说明岛屿旁出现了边界，总周长加1。
方法二：遇到为1的，就加4，然后，看左边和上边的格子，如果是1，说明共边，那么结果减去2。
推荐方法一。
763. Partition Labels
题意：给出一个串S，尽可能多的分为子串，子串内字符可以重复，但是子串之间的字符不重复，要求返回各个子串大小。
解：此题看起来比较难，但是如果能够观察一个实例，就会发现，此题本质是区间题，每个字符在串S中的最左和最右下标代表了字符的作用范围。首先就扫描一遍串S，使用hashmap记录下每个字符的在串S中出现的开头和结尾下标。
然后我们再扫描串S，对于每个出现的字符，看做是区间的覆盖问题，显然，当出现某个字符的起始下标大于之前所有区间的结尾下标时候，才会新加区间，否则，贪心的不需要加区间。这样就能得出结果。
可以继续优化，不需要保存区间的起始点，只需要记录每个字符在串S中出现的最右下标，每次更新时候，把前一次的最右下标作为起始下标即可, 加入新区间的时机是当前扫描下标和当前字母对应下标一致的时候。
758. Bold Words in String
题意：给出单词数组W和一个字符串s，现在要把s中出现的W中的单词给加粗，也就是给开头结尾加上</b>标签。要求是使用最少的标签。
解：此题方法多样。 方法一：建立s对应的标记数组，标记下标所在之处的单词是否要加粗。 接下来就是，建立函数，传入一个单词并在s中每个字符开头进行搜索，如果能够找到，那么把相应部分全部打上标记。 这样对单词数组中每个独一无二的单词调用一次函数后，就可以计算出标记数组。 最后，根据标记数组来构建新的结果字符串。遇到true的时候，先加入，然后，跳过之后连续的true，然后加入。再次遇到新的true的时候，继续加入，依次类推，得出最终答案。具体一种字符串操作的技巧是：如果遇到的true之前并不是true，或者之前的越界了，那么说明是开头，如果遇到的true之后的并不是true或者之后的越界了，那么说明该放入。 时间复杂度：s中每个字母开头，每次比较所有单词长度，O(len_s * total_word_len)。
方法二：对s进行扫描，首先考虑第一个元素开头，与所有单词进行比较，找出最长匹配的单词，然后记录能加粗最远下标，然后对第二个字符，对所有单词扫描，看能否继续扩大加粗最右下标，依次类推，每次看当前扫描字符是否落在可加粗下标的左侧，如果是，说明当前下标应该进行加粗。 时间复杂度：s中每个字母开头，每次比较所有单词长度，O(len_s * total_word_len)。
PS. （1）隐藏点：以当前字母开头不存在单词时候，该字母仍然可能被加粗，因为该字母可以作为单词的后缀存在被加粗。 （2）如果先对单词按长度从大到小排序，然后s中匹配了大的单词，后面就直接不比较。O(len_s * logn * total_word_len)，时间复杂度更大。 （3）使用find比取substr要快。使用方法一比较快。
616. Add Bold Tag in String
题意：给出串S和单词字典，现在要把S中的单词子串加粗，如果单词有重叠，那么把整个重叠部分加粗。
解：此题和758题一模一样。关键在于求单词重叠部分，如果是先找出所有单词的开始和结束，那么此题和merge interval一模一样。 使用758的方法一。
448. Find All Numbers Disappeared in an Array
题意：数组里存的是下标范围内的数，一种元素只出现两次或一次。现在求下标中缺失的数（不止一个）。
解：一开始使用hashmap，空间复杂度是O(n)，也就是使用和下标数一样大小的bool数组记录每个数字是否出现。 优化方法是发现本来数组就是n大小，且里面数字都是正的，现在将该数对应下标处（如果数字是负的，那么取绝对值）的数字变为负数（如果本来是负数了，那么不变）。 然后再扫描一遍数组，如果数不是负数，那么说明原数组中该下标对应的数不存在。这种技巧使得空间复杂度变为O(1)。
280. Wiggle Sort
题意：将数组变为nums[0] <= nums[1] >= nums[2] <= nums[3]… ，就是让奇数位置大于等于偶数位置的数。
解：采用交换的方式，O（N）的时间解决问题。 思路就是：循环不变式思考。如果只有一个数，那么直接满足条件，如果是两个数，且第二个数违反规律，那么直接交换。如果是三个数， 且之前两个数已经是满足条件了，只要看第三个数，如果它大于第二个数，那么发现与第二个数交换，刚好满足条件；如果它大于等于第二个数，那么不用变换就恰好满足规则。 再看四个数的情况，第四个数如果大于等于第三个数，那么满足规律，否则，可以进行交换，有满足了条件。
可以得出通用规律： 如果当前位处理的是奇数下标位置，如果小于之前的元素，那么与之前元素进行交换。如果当前处理的是偶数位置，如果大于之前元素，那么与之前元素进行交换。 我们从下标1开始处理，一直满足循环不变式，也就是说这样的性质每次得以维持，一直处理就可以得出答案。
324. Wiggle Sort II
题意：修改一个无序数组，使得满足nums[0] < nums[1] > nums[2] < nums[3]… 尽量达到n时间，1空间。
解：此题和280的区别在于，要严格的大于或者小于。这样的话，如果相邻的数相等，那么简单的交换就不起作用了，也就是不具备第一题的解法性质了。 方法一：思路就是把固定大小的数填入位置。大致思路：先排序，然后按中位数， （1）奇数位置放比中位数大的数，无论放什么数，后半部分数总比前半部分大； （2）偶数位置放比中位数小的数； 其中要改进的思想精髓就是尽可能把中间靠近中位数的几个可能相等的数给错开，所以前半部分要倒着放入，后半部分同理也是倒着放。 例如：{4,5,5,6} -> {5,6,4,5}，{1，1，1，1，2, 2, 2} -> {1, 2, 1, 2, 1，2，1}。 奇数时候，中位数的处理情况：根据公式的大小关系可以知道，大的数字比小的数字少一个，因此，此时中位数应该被作为前半部分的数处理。 时间复杂度O(nlogn)。 方法二：时间复杂度O(n)，空间复杂度O(1)。 使用下标映射，首先使用库函数nth_element找出median。使用库函数的好处是时间复杂度平均O(N)。而且，找出median后，数组会被自动分成两个部分，第一个部分数全部大于median，后半部分都小于median。例如 0 1 2 3 4 5 6 7, 其中4位置是median，那么0到3指向的数大于median，5到7指向的数都小于median。现在要做的就是把前面部分填入0 2 4 6的位置，而把后面的数填入1 3 5的位置， 最后7的位置放median。 这样，所要做的就是把所在下标与计算后的下标所在元素进行交换即可。由于不是两两交换的，还是要使用其他技巧。现在我们知道访问0下标的时候，其实我们访问的是我们关心的第一个奇数位，访问7的时候，其实访问的是我们关心的最后一个偶数位，那么简单了，保持一个扫描指针cur从头开始访问，如果发现其映射后当前下标所在数是比median大的话，那么与0指向的第一个奇数位交换，否则与7指向的最后一个偶数位进行交换。相当于说扫描cur就作为了保存临时结果。 实际上，对新映射位置的处理相当于彩虹排序。其中下标映射的公式为 (1 + 2*i) % (n | 1)。其中n或1是表示把n补成奇数。
370. Range Addition
题意：一开始给出一个长度为n的全0数组，然后给出k个下标区间，每个区间对应一个数表示数组需要自增的大小，求更新后的数组。
解：考虑暴力求解，也就是所有下标区间对数组进行扫描，把坐标进行加一。时间复杂度为O(k*n)，也就是最坏情况下（每个区间都是[0, n - 1]）所有区间的总长度。
优化的思路是下标区间实际上有用的部分只是开头和结尾。
总体的动态的考虑这个增加坐标的过程：进入某个叠加区间，增加的幅度加1，出去某个区间，增加的幅度减1。
所以做法就是，先遍历所有下标区间的开头和结尾，并在原数组中标记：区间开始下标处加1，区间结尾下标处减1。
然后从头到尾扫描一遍数组，使用inc记录当前坐标的增加幅度，每次先看所在处的增加数是多少，然后更新增加幅度，当前坐标更新为0 + 最新增加幅度。 时间复杂度O(n + k)，一开始将k标记到全0数组，花费k时间，在扫描一遍数组花费n时间。
PS.如果不是全0数组，那么可以使用两个hashmap，分别记录下来一个点处对应的区间起点有多少和区间终点有多少。 多消耗空间O(k)。
809. Expressive Words
题意：给出一个串S和单词集合，然后看单词能不能扩展成串，扩展机制是：字母扩展必须到3倍及以上，比如hello不能由helo扩展得到，而helllo可以由helo扩展得到。
解： 注意此题描述存在潜在问题，看下面例子：
- ee可以扩充到eeee，因为前一个e可以不扩充，后面的e扩充3倍。没问题。
- ee居然可以扩充到eee，如果按照每个字符扩充3倍就解释不通了。
所以此题真正的要求是，ee只看作是一个字符e，只要求其最终扩展的结果大于3且比原来长度长。
解题思路是： 单词的顺序是需要考虑的，因此不能直接使用hash，例如business，这个单词中s出现在非连续的地方。
本质是对串S的一种字符数字压缩形式的判断，例如heeellooo，本质信息是h : 1, e : 3, l : 2, o : 3；
然后对于单词例如heelo，h:1,e:2,l:1,o:1， 按照字母顺序一一对应，看S串字母对应的数字，如果小于单词的字母对应的数字，那么无法扩展；
接下来看S串字母对应的数字是不是大于等于3，大于的话就可以，否则无法扩展。
具体解法：
- 当作压缩字符串
先压缩S和每个单词，压缩为数组形式，数组的元素是<字母，字母数量>的pair。
然后，如果压缩后的两个数组长度不等，那么说明无法扩展，直接返回。
否则，按下标进行一一比较，需要字母相等，且字母数量满足要求。
此法缺点是需要额外空间来存储。优化的思路是进行动态比较，也就是在循环的过程中，进行比较。
注意：循环条件是一开始从0开始，两个指针都不能越界。最后两个指针都要指向末尾。
- 双指针 + 循环不变式
解法： 采用贪心策略，能不扩充就不扩充，实在不行在比较。构建循环不变式：
一种情况是，ee扩充到eee，下标0和1处的e由于和S中对应上所以都当作不扩充，但是在下标2的时候，去看 S中当前扫描的最后三个字符是否相同，也就是S[i - 2] == S[i - 1] == S[i]。
还有一种情况，e扩充到eee，此时看的是下标1所在字符作为中心字符的三个连续字符是否相同，也就是S[i - 1] == S[i] == S[i + 1]。
总结起来就是：单词中扫描到于S不同字符的时候，就看两种情况，有一项满足即可。
777. Swap Adjacent in LR String
题意:RX变XR, XL变LX，现在求start串能不能唯一的变为end串。
解：此题不能bfs暴力解，而是采用观察规律的方法。此题去掉X之后的start串和end串必须一样。另外，我们比较下去掉X的start串和end串：RXXLRXRXL => XRLXXRRLX RX变成XR意味着end串中R一定出现在原来start串R的右边，反之，XL变成LX意味着end串中的L一定出现在原来start串L的左边。这一个性质要在串的任何位置得到满足，也就是说，从左向右扫描串，期间要保证start串里面R个数要严格小于等于end串，而start串L的个数要严格大于等于end串。
816. Ambiguous Coordinates
题意: 给出一个串S，求将串切分为坐标(x, y)的所有情况，其中坐标内部可以加上“.”构造小数。当然也存在不合法的情况：例如0.0，00，001，00.01都是不合法的情况。
解：暴力求解，先从第i（1 <= i <= n - 1）个位置考虑把S断成两个部分A和B，然后每个部分内部在考虑使用“.”来进行分割，返回的两个集合在进行组合，就可以得出一个位置切分后的答案。
判断A、B不合法的情况：首先，如果串A大小为0，那么不合法，或者A的大小大于0，但是A同时以0开头和结尾，那么也不合法。如果是以0开头，那么唯一的合法形式就是0.xxxx。如果是以0结尾，那么唯一合法形式就是不加“.”的串本身。此外就是从1到i-1都能加“.”以及串本身的情况。 PS.原来的串是带有()的。
769. Max Chunks To Make Sorted
题意：给出0到n-1的排列，问需要分成多少组，然后组内排序（不是翻转）之后，最后总体排列还原成0到n-1的有序情况。例如4，3，2，1，0变成0，1，2，3，4只能是分一组排序。
解：观察规律，4出现在第0位，意味着第0位到最后一位必须作为一组了，不然无法满足条件。同理，0出现在第n-1位，那么意味着第0到第n-1位必须作为一组。这两种考虑是等价的。
假设就从元素最终所在的位置的左侧进行考虑：4出现在第0位，不考虑后面3，2，1，0的位置，由于4最终一定出现在下标为4的位置，所以对于4的分组一定会包含3，也就是3的考虑被4的情况给覆盖了。
所以，此题又可以与区间问题关联起来，例如串3，4，0，1，2。我们看第一个3的时候，对3的理解变为它的覆盖范围是下标区间[0, 3]，也就是{3,4,0,1}。而后面4的作用范围是[1, 4]。我们发现两个下标区间是重叠的，对于最终答案，我们发现结果是1，也就是意味着此题转化为求[0, n -1]会出现多少个独立的小区间,和大楼轮廓问题有一些相似之处，可以覆盖的范围就是高度。
所以，此题的一种解法就是扫描，记录当前元素的从当前下标开始的区间的覆盖范围的当前最大值，（1）如果扫描下标比当前最大值小，意味着当前下标是被最大值所在区间给覆盖住的，也就不计入结果。（2）会不会出现当前下标大于最大值呢？也就是说最大值覆盖不到当前下标呢？不存在的，即使严格按照升序来排也做不到。（3）当前下标等于最大值，意味着之前最大值的覆盖范围在此处消失，此时对结果数加1，也就是说之前的区间是一个独立的区间。 最大值进行更新意味着什么？如果之前最大值覆盖范围已经消失，意味着新区间的开始，如果之前最大值覆盖范围还没有消失，意味着出现区间重叠（此时区间数不变），也就好比是一个楼被后面的高楼给覆盖了。
163. Missing Ranges
题意：给出上下界，再给出若干数，现在求数之间的区间。
解：此题处理上下界的方法必须独特，给出几个例子：一个是元素等于上界的情况：[-1]在下界为-2，上界为-1的情况下，答案是{[-2]}。做法是扫描，如果发现lower与当前扫描元素有差距0以上，那么就把差距区间记录到答案中，然后lower更新为扫描元素大小+1。扫描完之后，在对lower和上限做最后的处理。 最后还要注意元素+1会导致整数越界的情况，所以统一使用long型。
766. Toeplitz Matrix
题意：验证一个矩阵是不是Toeplitz矩阵，也就是左上到右下的对角线元素全都相同。
解：此题思路是带有方向的矩阵遍历，也就是说：下一步该访问的格子可以通过方向计算得出，接下来就是确定所有出发的格子，此题中第一行和第一列是出发的格子。然后全部验证完就可以。 还有一种解题方式是混合遍历，也就是说，每次扫描的不一定和上面有关，但是是与之前处理过的部分有关，这样即使依次访问的格子之间没有直接依赖，但是还是可以正确的得出答案，而且代码更简洁。
859. Buddy Strings
题意：给出串A和串B，问串A是不是有且只能交换一次元素来达到B。
解：理解题意的关键：串A是必须交换一次的，所以”ab”和”ab”返回false，而“aa”和“aa”是返回true的， “aba”和“aba”也是返回true的。 理解题意，举出各种例子之后，才开始构思编程。 先找规律，发现，如果两串相同位置出现相同字符，且字符重复了，剩余位置字符相同，那么一定是返回true的。然后就会发现，两串其实是相等的，也就是说AB相等条件下，必须要包含重复字符才能满足要求。 不等的情况，就按照A，B差一个字符方式来调整。不能多于一个位置不同。
821. Shortest Distance to a Character
题意：给出串S和字符c，求出串S所有字符离字符c最近的距离。
解：此题是wall and gates的简化版，使用并行的bfs层序遍历就可以解。 还有一种是字符串处理的思路：可以从左向右扫描一遍，看每个字符离自己左侧最近的c的距离，如果不存在，那么先把距离定义为比串S长度负数还要小的数，这样不干扰最终结果。 在从右向左扫描一遍找最右边的c距离，取较小值。
647. Palindromic Substrings
题意：求substring里面，回文串的个数。
解：对于求substring是否回文串的题目，起点是每一个元素以及一对元素当作回文串的中心，并做两种情况考虑：（1）该元素是是奇串的中心；（2）该元素是偶串的中心对的第一个元素。然后每次向两边方向，每次取两个元素进行观察，看是否能扩充当前的串。 此题是对每一个位置作为中心进行考虑，看能扩充多少个回文串。这样考虑的好处就是，如果发现不能扩充了，那么后面的也不可能作回文串了，而发现可以扩充，那就是找到了以当前坐标为中心的新的一个回文串。
334. Increasing Triplet Subsequence
题意：看未排序的数组中是否存在三个递增的元素序列（不需要连续）。
解：此题一开始以为是求最长子序列的动态规划题目，但是该方法消耗时间O(n^2)，并不能通过。
此题其实只需要扫描一遍就能知道是否存在这样的三元组。
对于当前扫描过的结点中，我们记录下最小结点，然后在扫描新结点的过程中，我们看是否存在比最小值大的结点，如果存在，那么可以作为三元组中的第二个元素进行考虑，如果当前扫描过的序列中存在（最小值，第二个元素），那么如果在碰到一个比第二个元素大的，那么返回true。
如果新扫描的点nums[i]比最小值小，那么更新最小值，不必更新第二个元素，因为之前序列0~i-1就存在（旧最小值，第二小的元素）这样的候选者。如果下一个元素大于第二个元素(都不用考虑最小值被更新了，只需要知道存在第二小的元素)，那么仍然可以返回true，如果下一个元素介于新最小值和第二个元素之间，那么可以更新第二个元素，组成新的候选者：（新最小值，新第二个元素）。
还有一种方法，是在O(N)时间计算i左侧的最小值：dp[i] = min{dp[i-1], nums[i]}，然后在扫描一遍求出i右侧的最大值，这样，最后再扫描一遍，看所有的nums[i]是否有比左边最小值大，是否比右边最大值小的。
628. Maximum Product of Three Numbers
题意：给出整数数组（有正数也有负数），求其中乘积起来最大的三个值。
解：此题其实是数学题，乘积起来的三个最大值，正负数都有的情况下，要么是三个最大的正数相乘，要么是两个最小的负数乘以最大的正数；
如果只有负数，那么三个值相乘的结果必然是负数，此时选最大的三个负数。
如果只有正数，那么选最大的三个正数。
因此，答案必在最大的三个数，或者是最小的两个数乘以最大数二者之间产生。可以使用一遍循环，记录下这些数，然后计算这两个数返回较大者。 花费时间O(N)。
1002. Find Common Characters
题意：给出string数组，元素是小写字母组成的string。现在要求出现在所有元素中的共同字母。输入 [“bella”,”label”,”roller”]，输出是[“e”,”l”,”l”]
解：此题首先要思路清晰，首先要知道这种共同字母其实与位置无关，而只和数量有关，所以只需要计算每个字母在每个 元素中出现的次数，然后每个字母对应的次数中选出最小的就是公共部分。
1576. Replace All ?’s to Avoid Consecutive Repeating Characters
题意：给出字符串s，s只包含小写字母和’?’，现在要求把’?’变为任何一个小写字母，但是 要求该字母与前后一个字符不一样。返回任意一种满足要求的替换即可。
解：本以为此题是dfs，因为害怕有存在先转化的’?’可能最终结果不正确导致。
实际上，只需要3种字符就可以完成整个的替换。因为即使存在’??????????…‘这种极端情况， 也可以使用’abcabcabc…‘来替换。
可以进行一遍替换得出最终结果，替换的策略是，如果前一个字母是a，那么当前的替换为b， 也就是总是替换成前一个字符的下一个字符，如果该字符等于后一个字符，那么替换为后一个 字符的下一个字符。这样的替换不会出现矛盾，因为？总是可以选择一种字符来替换，且不会 产生冲突。
1375. Bulb SwitcherIII
题意：有n个灯泡，一开始都是关闭的，现在给出灯泡的下标数组（下标数组是0-n-1的排列），表示每次点亮该下标处的灯泡。 现在要求出每次点亮的时候，恰好该灯泡左侧都是点亮的，返回这种情况的次数。
解：此题本来以为是使用并查集来解：
每个点把最左连通点当作老板，然后使用一个全局变量记住当前的公司数。只有当前公司数为一个时候， 且老板是一开始的下标0时候，该点必然是满足条件的点。时间空间复杂度都是O(N)。
但是实际上，此题有个巧妙的解法，由于不存在关闭灯泡的操作，因此，满足条件等于满足一个 特殊的等式：当前点亮的灯泡数量i等于最右侧被点亮的灯泡。也就是说，该次点亮的 灯泡恰好是最后一个灯泡。时间复杂度O(N)，空间复杂度O(1)。
