程序员进阶之算法练习（十六）

前言

正文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(), [](Interval a, Interval b){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，a[i]表示第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]区间的运算是之前求过的。
那么，考虑预处理，把这些结果存下来。

leftMax[i] 表示从左边开始，前i个的交易的最优解；
rightMax[i] 表示从右边开始，前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]也是合法的。
故而用动态规划：
dp[i][j] 表示字符串[i, j]是否为合法的子串；
枚举k∈[i, j] 来判断分割字符串的位置；
转移转移是O（N），因为需要判断区间[i, k]和[k+1, j]是否合法（用字典数配合）；
最后判断dp[1, n]是否合法。

复杂度解析：
时间复杂度是O(N^3)， N^2的状态 * N的字典数判断。
空间复杂度是O(N^2+M)，N2是状态数量，M是字典数；

优化方案：
1、dp用1维表示；dp[i] 表示前i个是否合理，转移的时候dp[i]=dp[k] && substr(k+1, i)；
2、判断substr是否存在时，可以用字典树。

总结

给自己定了一个小目标：按照ACrate排序，把第一页所有的题目刷完。
目前已完成20题，第一页共有50道题，任务艰巨。
按照每日一题的时间来算，大概还要一个月的时间才能做完。
刚好，是年后。

一步领先，步步领先？
都知道操作系统、编译原理、网络原理、数据结构重要，但是现在已经没有毅力再去重新学一遍。
忙着面对生活与工作，偶尔的休闲时间则贡献给娱乐。
这就是普通的生活。