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

前言

正文6道题目来自leetcode––为求职为生的编程网站，目的是工作闲暇之时锤炼代码功底。
如何从这篇文章受益？

先看题目大意，对照Example的样例理解题目意思；
尝试解答，得到自己的答案，并分析时间和空间复杂度；
思考完毕，看题目解析，对比分析自己解法的异同和优劣。

题目大都是LeetCode的hard难度。

正文

41.First Missing Positive
题目链接
题目大意：
给出一个数组，找到数组中没有的最小正整数。
要求：O(N)的时间和O(1)的空间复杂度；

Example
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

** 题目解析：**
先不考虑题目要求的时间、空间复杂度；
暴力的做法有两个：
1、时间最快，空间不限：数组a[N]，然后出现数字k就a[k]=1标志出现；
2、时间、空间都不限：排序，遍历一遍数组；

回到题目的要求，时间复杂度要求是O(N)，可以肯定是会用到方法1；
现在要求O(1)的空间复杂度，那么就必须利用上给出的数组。
遍历数组，如果数字k小于n且非负，那么a[k-1]=k-1;
然后遍历一遍，a[i] != i的就行是解。

** 复杂度解析：**
O(N)的时间和O(1)的空间复杂度；
** 其他解法：**
基数排序。

从低位开始，
当前第i位，统计0出现x次，1出现y次，(x+y == n)
再次扫描数组，可以直接确定每个数字该排在哪里。
if bit = 0 then
idx = total_y + (total_x-left_x)
....
基数排序解法

45. Jump Game II
题目链接
**题目大意： **
给出一个数组，数组上的值表示能前进的距离；
现在从pos=0的位置向右出发，问最少需要走几步才能到达终点。

Example
输入 A = [2,3,1,1,4]
返回 2
因为可以从pos=0走到pos=1，然后直接到达pos=4；

题目解析：
第一反应就是bfs，但是bfs需要每次判断距离[i+1, i+k]内的点是否访问，导致时间复杂度是O(N^2);
这个题也可以用动态规划：
dp[i]表示到达i的最短步数；
那么状态方程可以写成dp[i+k]=min(dp[i+k], dp[i] + 1); k∈[1, nums(i)]
这样对于每个i都需要去更新后面nums[i]状态，故而复杂度也是O(N^2);
对状态转移方程稍作修改：
dp[i] = min(dp[i], dp[k] + 1); k+num[k] >= i 且 k < i
这样可以建一个dp[i]的优先队列，先按照步数排序，再按能到达的距离排序；
每次从队列的顶端拿出步数最小的dp值，判断pos的有效区间是否覆盖当前位置i；
如果不覆盖，那么对i+1必然也不覆盖，可以丢弃；
如果覆盖，则直接dp[i]=dp[k]+1，并把(dp[i],i+nums[i])放入优先队列；
复杂度是O(NlogN)。

提交后，非常遗憾的收获TLE...

仔细观察dp[i]的性质，可以得出一个结论：
步数越大，能到达的距离就越远；
那么先建一个队列，保证步数最小的在前面，后面是步数大但是覆盖距离较远的备选；
这样可以O(1)取出最优解；
并且可以设定一个maxRight，表示队列当前最远的覆盖距离，如果没有大于这个数字，可以不用放入队列；
这样可以在O(N)的时间/空间复杂度解决问题。

** 复杂度解析： **
O(N)的时间/空间复杂度解决问题。

84. Largest Rectangle in Histogram
题目链接
** 题目大意：**
给出一个数组，数组a[i]表示第i栋楼的高度；
求出最大矩形的面积。

example,
Given heights = [2,1,5,6,2,3],
return 10。

样例的图 最大的面积

题目解析：
维护一个高度不减少的栈，每次可以通过栈，快速得出面积。

** 复杂度解析：**
时间复杂度是O(N)
空间复杂度是O(N)

** 代码量：**

int largestRectangleArea(vector<int>& heights) {
        int ret = 0;
        heights.push_back(0);
        stack<int> s;
        for (int col = 0; col < heights.size(); ++col) {
            while (!s.empty() && heights[col] < heights[s.top()]) {
                int top = s.top();
                s.pop();
                int area = heights[top] * (s.empty() ? col : (col - s.top() - 1));
                ret = max(ret, area);
            }
            s.push(col);
        }
        return ret;
    }

85. Maximal Rectangle
题目链接
** 题目大意：**
给出一个01矩阵，求全为1的最大的矩形的面积；

For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 6.

最大面积如上，为6

** 题目解析：**
假设最后的矩形是(i, j)到(x, y)，01矩阵为n*m矩阵；
从1到n枚举y，那么要求变成矩形贴着底边，然后面积尽可能大。
把与底部连着的1统计起来，例如当row=3的时候，分别为[3,1,3,2,2]；
此时，题目与84. Largest Rectangle in Histogram完全一致；
维护一个高度不减少的栈，每次可以通过栈，快速得出面积。

** 复杂度解析：**
时间复杂度是O(N)
空间复杂度是O(N)

97. Interleaving String
题目链接
题目大意：
给出三个字符串s1,s2,s3；
判断字符串s3能否由字符串s1和s2组成，要求s1的字符串内字符的相对顺序不变，s2同理。（假如s1=abc，那么在s3中，就不能变成bac，相对顺序必须是abc）

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

** 题目解析：**
动态规划。
dp[i][j] 表示s1的前i个字符，s2的前j个字符，组成的字符串是否为s3的前i+j个字符。
dp[0][0]=true，表示初始状态。
假设dp[i][j]=true，那么表示s1的前i个字符，s2的前j个字符，与s3的前i+j个字符是匹配的。
那么只要s1[i+1]==s3[i+j+1]，那么dp[i+1][j]=true;
同理，有dp[i][j]=true && s2[j+1] == s3[i+j+1] => dp[i][j+1]=true

最后看dp[n][m]是否为true即可。

** 复杂度解析：**
时间和空间复杂度是O(NM) N是s1长度，M是s2长度；

*** 135. Candy ***
题目链接
** 题目大意：**
n个人排成一行，每个人有一个rating的数值。
现在给所有人分配糖果，要求：
1、每个人至少有一个；
2、rating比身边人高的分配到更多的糖果。
问最少需要多少糖果。

题目解析：
假设所有人rating一致，那么需要n个糖果；
如果有一人rating更高，那么需要n+1；
如果有2人rating更高，则看两个人是否相邻，需要n+2或n+3个糖果；
以此，可以得出一种分配方案：
从最小的rating值开始分配，每次观看旁边的人是否有糖果：
如果身边人有糖果，则分配max(左边, 右边) + 1；
如果身边人没有糖果，则分配1；
时间复杂度为O(NLogN)，排序耗时。

收获一枚TLE；
那么对算法进行优化。
根据分配糖果的条件2，我们知道在一个单调递增中：（单调递减可以逆着看，就是单调递增）
分配的结果是1、2、3、4、5这样的序列；
那么，一个数组可以分成多个单调递增的序列；
然后反着遍历，找到单调递减的序列；
剩下的部分可以全部填1。

复杂度解析：
时间复杂度是O(N)
空间复杂度是O(N)

总结

给自己定的小目标50题，因为第一页某些题目质量较低，加了一些比较容易的目前进度33/50。