专栏首页机器学习入门算法细节系列(21):贪心有理?

算法细节系列(21):贪心有理?

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/72593843

算法细节系列(21):贪心有理?

详细代码可以fork下Github上leetcode项目,不定期更新。

题目摘自leetcode: 1. Leetcode 502: IPO 2. Leetcode 055: Jump Game 3. Leetcode 330: Patching Array

刷完挑战,继续刷leetcode,遇到的第一个题就是IPO,而这恰巧是贪心系列,那就顺便把贪心给学了,多门技术,多条生路。

《算法导论》也有关于贪心算法的相关章节,但我还不敢看,无非怕被书中的论述思维给限制住了。所以先刷点题,对贪心有了基本了解后,回过头来再看它的论证。

我所理解的贪心: 贪心,每一步决策都是局部最优的?一种短视的行为?好吧,这是我对贪心最真切的认识了,没有其他。日后,刷题时逐一完善加深对贪心的理解,话不多说,直接开始。

Leetcode 502: IPO

求n个项目所能累加的最大profit。

呵呵哒,leetcode的题目有个很大的特色,很多题在解释中把思路明确告诉你了,我一开始就纳闷了,直接找符合capital中的最大profit累加即可?好像也符合贪心的策略,选择局部最优。

思路: 没错,按照题目的意思来就可以了,代码如下:

    public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
        int total = W;
        for (int i = 0; i < k; i++){
            int maxProfit = 0;
            //find the max Profit
            int index = -1;
            for (int j = 0; j < Capital.length; j++){
                if (Capital[j] <= total){
                    if (maxProfit < Profits[j]){
                        maxProfit = Profits[j];
                        index = j;
                    }
                }
            }
            if (index == -1) return total;
            Capital[index] = Integer.MAX_VALUE;
            total += maxProfit;
        }
        return total;
    }

TLE了,如果有n个项目,那么上述代码时间复杂度为O(n2)O(n^2)。嘿,其实在它贪心的背后,它是一道数据结构题,用到了优先队列。

提到优先队列,相信你能很快想出了思路,但这对我来说,不够完美,如果不提优先队列这想法,我就很难想到用这数据结构了。所以,我慢慢分析下为啥用到了优先队列。

之前的博文中,我有提过所有的循环遍历,如果没有容器记录状态,都是无记忆遍历,它们是一种非常低级的手段。就拿上述代码:

for (int j = 0; j < Capital.length; j++){
    if (Capital[j] <= total){
        if (maxProfit < Profits[j]){
            maxProfit = Profits[j];
            index = j;
        }
    }
}

遍历整个capital数组,只为找到最大值?更何况,当我使用完该最大值,我还得从capital数组中把它标识为不可使用状态,所以这样一个循环遍历,每次都得遍历整个数组,然后找出一个次大的。

嘿,这个特征比较符合优先队列了,用过的元素直接poll出去,而在队头的元素是次大的,直接把它poll出来。而构建优先队列的时间复杂度只有O(logn)O(\log n),这是高级数据结构本身的特点,在构建之初就把大小关系维护进去,让它再插入新元素时,能够以较快的速度筛选出最大or最小。

思路: 1. 构造一个pair对,把profit和capital关联起来,两者有着一一对应的关系。 2. 筛选资产,在当前总资产下,把所有capital[i]小于等于当前总资产取出,并存入另外一个优先队列中。 3. 该优先队列维护profit的大小关系,队头永远是符合资产中的最大profit(一种贪心策略)

总结:

看到删除+最大or最小,想想优先队列。

代码如下:

private class Pair{
        int profit;
        int capital;

        Pair(int profit, int capital){
            this.profit = profit;
            this.capital = capital;
        }
    }

    public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
        int n = Profits.length;
        Pair[] pairs = new Pair[n];

        for (int i = 0; i < n; i++){
            pairs[i] = new Pair(Profits[i],Capital[i]);
        }

        PriorityQueue<Pair> q1 = new PriorityQueue<>((o1,o2) -> (o1.capital - o2.capital));
        PriorityQueue<Pair> q2 = new PriorityQueue<>((o1,o2) -> (o2.profit - o1.profit));

        for (int i = 0; i < n; i++){
            q1.offer(pairs[i]);
        }

        int total = W;
        for (int i = 0; i < k; i++){
            while (!q1.isEmpty() && q1.peek().capital <= total){
                q2.offer(q1.poll());
            }
            if (q2.isEmpty()) return total;
            total += q2.poll().profit;
        }
        return total;
    }

Leetcode 055: Jump Game

这道题可谓是麻雀虽小,五脏俱全啊,贪心的味道很浓,得深入分析分析。

首先,看到这道题的第一眼,我想到了递归,思路如下: 根据当前能够jump的步数,选择后续的位置,这样就变成了相同的子问题,而只要最终pos能够抵达数组末端就能返回true。可谓是信心满满啊,为了防止TLE,还加了记忆化手段,代码如下:

public boolean canJump(int[] nums) {
        boolean[] dp = new boolean[nums.length];
        return canJump(nums,0,dp);
    }

    private boolean canJump(int[] nums, int pos,boolean[] dp){
        if (dp[pos]) return false;
        if (pos >= nums.length - 1) return true;
        else{
            int step = nums[pos];
            for (int i = 1; i <= step; i++){
                if (canJump(nums,pos + i,dp)){
                    return true;
                }
            }
        }
        dp[pos] = true;
        return false;
    }

呵呵哒,stackoverflow了,这只能说明我还太嫩,递归显然无法解决该问题了,那这样,就用动规咯,所以又想了个动规的方案。代码如下:

    public boolean canJump(int[] nums) {
        boolean[] dp = new boolean[nums.length];
        dp[0] = true;
        for (int i = 0; i < nums.length; i++) {
            if (!dp[i]) continue;
            int step = nums[i];
            for (int j = 1; j <= step; j++) {
                if (i + j >= nums.length)
                    continue;
                dp[i + j] = dp[i] || dp[i + j];
            }
        }
        return dp[nums.length - 1];
    }

结果TLE了,TLE的原因在于step,上述代码,i每递增一次,都会更新step步的dp,如:

nums = [25000,25000,24000,1]
显然没必要更新step步,25000能走的位置涵盖了所有位置,应该直接返回true即可。

此时,有了贪心,该贪心的含义是说,每到一个新的位置时,更新我能覆盖的所有范围(取最大),这就意味着,dp的状态没必要全部更新,因为我们知道在该范围内的dp都可以是true,换句话说,我们只需要知道一个边界即可。

所以代码如下:

public boolean canJump(int[] nums) {
        int max = 0;
        for (int i = 0; i < nums.length; i++){
            if (i > max) return false;
            max = Math.max(max, nums[i] + i);
            if (max >= nums.length-1) return true;
        }
        return true;
    }

结构比起动规简单很多,只需要O(n)O(n)的时间复杂度。

Leetcode 330: Patching Array

这道题还未理解它,它的思路尝试来证明下,帮助理解这道题为什么是贪心。

思路: Patching Array该问题的关键点在于用nums原有的数据集去构造0~n的数,举个最简单的例子:

nums = [1,2,5] n = 7

如何构造所有的和数?我们知道它们所有的和可以用三位1来表示:
111 表示 1+2+5=8
110 表示 1+2 = 3
所以总共有8种表示方法,如下:
000,001,010,011,100,101,110,111
得到的和从小到大排列为:
0,1,2,3,5,6,7,8
此处,我们可以明显看到当n=7时,缺了一个4,所以我们必须得补上。所以,
nums = [1,2,4,5] n = 7
以同样的方式构造所有和,得到:
0,1,2,3,4,5,6,7  (由1,2,4得)
在此处,我们还发现一个规律,当打一个补丁满足连续的数后,
我们在构造5的所有和时,可以直接在原来构造的和上加个5,所以有:
0,1,2,3,4,5,6,7
          5,6,7,8,9,10,11,12
所以n在0~12之内都能满足条件,此时我们再来nums = [1,2,4,5,23], n = 100
我们知道:[1,2,4,5]构造的连续和为:
0,1,2,3,4,5,6,7,8,9,10,11,12
而为了能够构造尽可能多的和,构造的补丁一定为13,因为:
0,1,...,12
          | 13,14,...,25
在这里你看到了贪心,nums = [1,2,4,5],但我们没有构造7的原因是因为构造7所能覆盖的范围非常少,如下:
0,1,2,...,6,...,12
          | 7,8,9,10,...,19
构造7得到的范围为0-19,构造13能够得到的范围为0-25,你选谁?

在这里明确一个补丁的性质,在已有的连续和上,新的连续和是【补丁+已有连续和】,想想000-111,扩展到4位的情况。

而连续和我们只要维护一个界即可,所以有了网上大多数的做法,对具体做法感兴趣的,可以搜搜。

代码如下:

    public int minPatches(int[] nums, int n) {
        long miss = 1;
        int added = 0, i = 0;
        while (miss <= n){
            if (i < nums.length && nums[i] <= miss){
                miss += nums[i++];
            }
            else{
                miss += miss;
                added++;
            }
        }
        return added;
    }

注意miss的long,防止溢出,进入死循环。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 674. Longest Continuous Increasing Subsequence

    用户1147447
  • LWC 54:698. Partition to K Equal Sum Subsets

    LWC 54:698. Partition to K Equal Sum Subsets 传送门:698. Partition to K Equal Sum S...

    用户1147447
  • 算法细节系列(35):不一样的排序

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 动态规划设计

    输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。

    用户7625070
  • 程序员面试金典 - 面试题 16.17. 连续数列(DP/分治)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/contiguous-sequence-lcci 著...

    Michael阿明
  • 【LeetCode算法】两数之和

    LeetCode第一题:两数之和题目描述题目分析题目解答思路一:双重for循环(1)代码(2)提交结果思路二:hashmap键值对一次遍历(1)代码(2)提交结...

    程序员周同学
  • 漫画:动态规划系列 第二讲

    在上一篇文章中,我们讲解了DP的概念并且通过示例了解了什么是动态规划。本篇中,我们将继续通过1道简单题型,进一步学习动态规划的思想。

    程序员小浩
  • LeetCode 300. Longest Increasing Subsequence (DP)

    有O(n^2)效率,还有O(n*logn)效率的。 O(n^2)的效率很好理解的啦,就是大家最常见的那种DP

    ShenduCC
  • LeetCode45|数组中重复的数据

    给定一个整数数组 a,其中1 ≤ a[i] ≤ n (n为数组长度), 其中有些元素出现两次而其他元素出现一次。

    后端Coder
  • 详解三道一维的动态规划算法题

    在一条直线上,有n个房屋,每个房屋中有数量不等的财宝,有一个盗 贼希望从房屋中盗取财宝,由于房屋中有报警器,如果同时从相邻的两个房屋中盗取财宝就会触发报警器。问...

    帅地

扫码关注云+社区

领取腾讯云代金券