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

前言

正文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、时间最快，空间不限：数组aN，然后出现数字k就ak=1标志出现；

2、时间、空间都不限：排序，遍历一遍数组；

回到题目的要求，时间复杂度要求是O(N)，可以肯定是会用到方法1；

现在要求O(1)的空间复杂度，那么就必须利用上给出的数组。

遍历数组，如果数字k小于n且非负，那么ak-1=k-1;

然后遍历一遍，ai != 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);

这个题也可以用动态规划：

dpi表示到达i的最短步数；

那么状态方程可以写成dpi+k=min(dpi+k, dpi + 1); k∈1, nums(i)

这样对于每个i都需要去更新后面numsi状态，故而复杂度也是O(N^2);

对状态转移方程稍作修改：

dpi = min(dpi, dpk + 1); k+numk >= i 且 k < i

这样可以建一个dpi的优先队列，先按照步数排序，再按能到达的距离排序；

每次从队列的顶端拿出步数最小的dp值，判断pos的有效区间是否覆盖当前位置i；

如果不覆盖，那么对i+1必然也不覆盖，可以丢弃；

如果覆盖，则直接dpi=dpk+1，并把(dpi,i+numsi)放入优先队列；

复杂度是O(NlogN)。

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

仔细观察dpi的性质，可以得出一个结论：

步数越大，能到达的距离就越远；

那么先建一个队列，保证步数最小的在前面，后面是步数大但是覆盖距离较远的备选；

这样可以O(1)取出最优解；

并且可以设定一个maxRight，表示队列当前最远的覆盖距离，如果没有大于这个数字，可以不用放入队列；

这样可以在O(N)的时间/空间复杂度解决问题。

** 复杂度解析： **

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

84. Largest Rectangle in Histogram

题目链接

** 题目大意：**

给出一个数组，数组ai表示第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.

** 题目解析：**

动态规划。

dpi 表示s1的前i个字符，s2的前j个字符，组成的字符串是否为s3的前i+j个字符。

dp0=true，表示初始状态。

假设dpi=true，那么表示s1的前i个字符，s2的前j个字符，与s3的前i+j个字符是匹配的。

那么只要s1i+1==s3i+j+1，那么dpi+1=true;

同理，有dpi=true && s2j+1 == s3i+j+1 => dpi=true

最后看dpn是否为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。