前言
正文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的最大的矩形的面积;
最大面积如上,为6For 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.
** 题目解析:**
假设最后的矩形是(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。
网友评论