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

作者: 落影loyinglin | 来源:发表于2017-03-01 17:56 被阅读629次

    前言

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

    相关文章

      网友评论

      • Liusr:lin,没有过算法专门学习,但是大学学过数据结构,准备面试的话直接刷leetcode吗,还是看些什么书,循序渐进。
        落影loyinglin:@Liu_sr 直接做题,看书枯燥。从easy开始

      本文标题:程序员进阶之算法练习(十七)

      本文链接:https://www.haomeiwen.com/subject/potxittx.html