程序员进阶之算法练习(十七)

前言

正文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。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏轮子工厂

设计模式(四) | 简历复印与原型模型不得不说的一些事

743
来自专栏java一日一条

5 分钟搞定 Java Comparable 接口

还有一个不错的视频(https://marcus-biel.com/java-comparable-interface-video-tutorial/)。

1104
来自专栏CDA数据分析师

技能 | 利用SAS进行数据清洗技术——缺失值查询

数据清洗技术是统计分析之前必做的一步,而且也是非常麻烦的一步,有时甚至花费的时间比统计分析都长。所以没有一定的技巧,这将是个非常烦人的工作。本篇文章介绍如何利用...

32310
来自专栏算法channel

其他|二维指针,数组指针,指针数组

望时间的流逝不仅仅丰富了我们的阅历,更重要的是通过提炼让我们得以升华,走向卓越。 1c++ c/c++的重要性毋庸置疑,凡是对性能要求很高的系统和算法,其中核...

3295
来自专栏一个爱吃西瓜的程序员

每天学习一点儿算法--快速排序

快速排序是一种常用的优雅的排序算法,它使用分而治之的策略。 那么分而治之(D&C)是一种怎样的策略呢? 分而治之 分而治之(D&C)的要点只有两个: 找出简单...

3104
来自专栏青青天空树

成绩大排队

其中姓名和学号均为不超过10个字符的字符串,成绩为0到100之间的一个整数,这里保证在一组测试用例中没有两个学生的成绩是相同的。

862
来自专栏C语言C++游戏编程

C语言内置运算符丰富到令人头皮发麻,C语言基础教程之运算符篇

运算符是告诉编译器执行特定数学或逻辑函数的符号。C语言内置运算符丰富,并提供以下类型的运算符 -

1311
来自专栏coding for love

JS进阶系列

在JS入门难点解析系列中,我们对JS的一些重要概念,比如:作用域,作用域链,原型,原型链,继承,活动对象,this,执行环境,变量声明,函数声明等进行了详细的分...

831
来自专栏java一日一条

5 分钟搞定 Java Comparable 接口

我们应该如何对事物进行比较和排序?这问题听上去有点莫名其妙,但我希望你认真考虑一下。比方说,我们有一组苹果:

541
来自专栏数据结构与算法

等差数列与等比数列

数列中的每一项都和它的序号有关,排在第一位的数称为这个数列的第一项(通常也叫做首项)

942

扫码关注云+社区

领取腾讯云代金券