程序员进阶之算法练习（十六）
前言
正文6道题目来自leetcode––为求职为生的编程网站，目的是工作闲暇之时锤炼代码功底。
没有捷径，但手熟尔；
一步领先，步步领先。
正文
5. Longest Palindromic Substring
题目大意：
输入一个回文串，输出长度最长的回文子串；
如果有多个答案，输出任意一个。
Example Input: "babad" Output: "bab" Note: "aba" is also a valid answer.
** 题目解析：**
模板题，有现成的解法。
求回文串有O(N)的算法，详见manacher解析。
** 复杂度解析：**
空间、时间复杂度都是O(N)， N是字符串的长度；
** 其他解法：**
暴力，从每个点开始枚举，判断最长的回文子串，O(N^2);
kmp，回文串s和s的转置是一样的，那么可以把原串s和s'进行匹配，判断区间是否合法；（有可能存在匹配，但是区间不重叠的情况）
30. Substring with Concatenation of All Words
***题目大意： ***
给出一个字符串s，一个字符列表words，words内的单词都是同一长度，找到一个区间，要求：
1、区间内的字符串，可以切分成若干个连续的子串，每个子串都是words的单词；
2、每个单词只出现一次；
输出所有可能的区间的起点。
For example, given: s: "barfoothefoobarman" words: "foo", "bar" You should return the indices: 0,9.
题目解析：
题目提供了一个了一个不可忽视的限制，所有的words是同一长度，这样就避免了fool和foo的情况；
并且在判断s的子串是否出现时，可以直接截取长度为m的字符串。
这样流程就变成：
1、初始位置s，截取m个字符str，查询str是否在words中，如果在则判断下m个字符；
2、如果不在words中，则回溯到最初的位置s，从s+1开始判断。
但是， 这样的复杂度会很高，因为回溯之后又要从原来的位置的下一个开始匹配。
有一种优化方案：假设len为words字符串的统一长度；
从0,1,2...到len-1，分别匹配一次即可。
这样可以采取一种策略，当(l, r)的字符串最后len个字符匹配失败后，直接从r+1的位置匹配；因为(r-len,r)的字符不存在words中；
如果(r-len, r)在之前已经在k出现过，则可以把左边界移到k+1，直到遇到右边界；
可以在len次枚举后得到结果。
** 复杂度解析： **
时间复杂度是O(N*len)，len为words中单词的长度。
空间复杂度是O(M*len)，hash的空间复杂度较高；
** 其他解法：**
有稍微慢一点，但是代码量很小的做法。
仅需20行。
详见这里
56. Merge Intervals
** 题目大意：**
给出n个数字区间，把有相交的区间合并起来。
example, Given 1,3,2,6,8,10,15,18, return 1,6,8,10,15,18.
题目解析：
区间合并只需考虑最左和最右的边界。
先排序，把可能合并到区间集合在一起。
容易知道如果前面区间的right >= 当前区间的left 的时候，是可以合并的。
那么遍历一遍，判断边界是否相交即可。
** 复杂度解析：**
时间复杂度是O(NlogN)，N是区间个数（时间都在排序上）；
空间复杂度是O(N)，有可能返回N个结果。
** 代码量：**
比较函数有简单写法。
sort(ins.begin(), ins.end(), {return a.start < b.start;});
76. Minimum Window Substring
** 题目大意：**
给出两个字符串S和T，在S中寻找一个子串s，要求：
1、s包括T出现过的所有字符；
2、s的字符串长度最小；
For example, S = "ADOBECODEBANC" T = "ABC" Minimum window is "BANC".
如果没有，返回空串；
题目保证只有一个答案。
** 题目解析：**
题目要求s出现T中所有的字符，但是没有顺序要求，那么对于一段字符串：
字符串的位置是无意义的。
假设已经选择一段字符串str，再选新的一个字符c；
如果字符c没有出现过，那么c应该并入str中；
如果字符c已经出现过，那么新出现的c比原来的c更优；
在匹配过程中，当出现所有T的字符之后，一直保存最小的字符串长度。
这里可以用反证法来证明。
假设按照这一规则，选出包括所有T字符的子串s=(l, r)，最右边的字符是c; 如果在(l, r)的位置k,k∈(l, r)，存在字符c，并且(l, k)出现过所有T的字符； 那么按照之前的过程(l, k)会是最小值。
** 复杂度解析：**
时间复杂度是O(N)，N是字符S的长度；
空间复杂度是O(M)，M是T的长度；
**实现过程： **
收获一枚WA，没想到题目还有这种数据：
Input: "a" "aa" Output: "a" Expected: ""
改改即可，记录下每个字符的数量。
123. Best Time to Buy and Sell Stock III
题目大意：
给出n个数字的数组a，ai表示第i天股票的价格；
现在要求进行最多两次买卖：
1、不考虑购买数量，利润就是价格差，要求买卖后利润最大；
2、手上不能同时持有两次股票；
3、买卖次数最多为两次，可以为1次。
举例：
1,2,3,4 利润最大是2;（只有一个选择1买、2卖、3买、4卖）
不能买1、2，在3、4卖。
** 题目解析：**
题目要求交易两次，但是两次又不能重叠。
那么可以枚举k，1, k为第一次交易，k+1, n为第二次交易，即可解决两次交易问题。
问题简化成在1, k中交易一次，求出最值。
1, k 同样可以简化为1, t区间买，t+1, k区间卖。
但是，这样的时间复杂度是O(N^2)，因为需要枚举两次区间分隔。
实际上，这里面有很多重复的操作，比如说枚举完k之后，在枚举k+1的时候，有1, k区间的运算是之前求过的。
那么，考虑预处理，把这些结果存下来。
leftMaxi 表示从左边开始，前i个的交易的最优解；
rightMaxi 表示从右边开始，前i个的交易的最优解；
这样只需要枚举k即可。
时间、空间复杂度O(n)；
其他解法：
动态规划。
因为状态数非常少，直接用4个状态来表示当前状态。
// 0: 1 buy, 1: one buy/sell, 2: 2 buys/1 sell, 3, 2 buys/sells
139. Word Break
** 题目大意：**
给出原串s，字符串数组dict，要求：
1、把s分成多个连续的子串；
2、每个子串都在dict里面；
问，是否有解。
s = "leetcode", dict = "leet", "code". Return true because "leetcode" can be segmented as "leet code".
题目解析：
把一个串分成2个串的可能性有n种可能，n是字符串长度。
那么对于串l, r 如果l, k 和 k+1, r是合法的，那么l, r也是合法的。
故而用动态规划：
dpi 表示字符串i, j是否为合法的子串；
枚举k∈i, j 来判断分割字符串的位置；
转移转移是O（N），因为需要判断区间i, k和k+1, j是否合法（用字典数配合）；
最后判断dp1, n是否合法。
复杂度解析：
时间复杂度是O(N^3)， N^2的状态 * N的字典数判断。
空间复杂度是O(N2+M)，N2是状态数量，M是字典数；
优化方案：
1、dp用1维表示；dpi 表示前i个是否合理，转移的时候dp[i]=dp[k] && substr(k+1, i)；
2、判断substr是否存在时，可以用字典树。
总结
给自己定了一个小目标：按照ACrate排序，把第一页所有的题目刷完。
目前已完成20题，第一页共有50道题，任务艰巨。
按照每日一题的时间来算，大概还要一个月的时间才能做完。
刚好，是年后。
一步领先，步步领先？
都知道操作系统、编译原理、网络原理、数据结构重要，但是现在已经没有毅力再去重新学一遍。
忙着面对生活与工作，偶尔的休闲时间则贡献给娱乐。
这就是普通的生活。