关于算法:贪心算法2金条切割问题点灯问题IPO问题

30次阅读

共计 4348 个字符,预计需要花费 11 分钟才能阅读完成。

明天再讲一篇对于利用贪婪算法解决的题目。

一、金条切割问题

1、题目形容

一块金条切成两半,是须要破费和长度数值一样的铜板的。比方长度为 20 的金条,不管怎么切,都要花费 20 个铜板。一群人想整分整块金条,怎么分最省铜板?输出一个数组,返回宰割的最小代价。

例如:

给定数组 {10,20,30},代表一共三个人,整块金条长度为 10 + 20 + 30 = 60,金条要分成 10, 20, 30 三个局部(不思考程序)。

如果先把长度 60 的金条分成 10 和 50,破费 60;再把长度 50 的金条分成 20 和 30,破费 50; 一共破费 110 铜板。

但如果先把长度 60 的金条分成 30 和 30,破费 60;再把长度 30 金条分成 10 和 20,破费 30;一共破费 90 铜板。

2、思路

(1)筹备一个小根堆。将数组放到这个小根堆里。

(2)每次弹出堆顶的两个数求和为 A,将 A 再放回小根堆里。

(3)始终执行第 2 步,直到堆只剩一个数。最初,每一次第二步 A 的累加和即是最初的后果。

例如给定的金条长度为 150,要分成 10、20、30、40、50 的块,最初破费的铜板数量即是上图中蓝色圆圈的和,即 150+60+90+30=330。

也就是咱们代码求解的时候是从叶子往根求的,求完后再从根往叶子即是金条的切割程序,最初所有的叶子即是须要切成的块的大小。

3、代码

/**
 * @author Java 和算法学习:周一
 */
public static int lessMoneySplitGold(int[] arr) {if (arr == null || arr.length == 0) {return 0;}

    // 筹备一个小根堆
    Queue<Integer> queue = new PriorityQueue<>();
    // 将所有数放到小根堆中
    for (Integer s : arr) {queue.offer(s);
    }

    int result = 0;
    int current;
    while (queue.size() > 1) {
        // 每次弹出堆顶两个数求和
        current = queue.poll() + queue.poll();
        result += current;
        queue.offer(current);
    }

    return result;
}

蕴含对数器的所有代码地址:https://github.com/monday-pro/algorithm-study/blob/master/src/basic/greedy/LessMoneySplitGold.java

二、点灯问题

1、题目形容

给定一个字符串 str,只由 ‘X’ 和 ‘.’ 两种字符形成。’X’示意墙,不能放灯,点亮不点亮都可;’.’ 示意居民点,能够放灯,须要点亮。如果灯放在 i 地位,能够让 i-1,i 和 i+1 三个地位被点亮。返回如果点亮 str 中所有须要点亮的地位,至多须要几盏灯。

2、思路

(1)i 地位是 ‘X’,不论,来到 i + 1 地位

(2)i 地位是 ‘.’,i + 1 是 ‘X’,i 地位须要放灯,来到 i + 2 地位

(3)i 地位是 ‘.’,i + 1 是 ‘.’,i + 2 是 ‘.’,i + 1 地位须要放灯,来到 i + 3 地位(此步即是贪婪)

(4)i 地位是 ‘.’,i + 1 是 ‘.’,i + 2 是 ‘X’,i 或 i + 1 地位须要放灯,来到 i + 3 地位

3、代码

/**
 * @author Java 和算法学习:周一
 */
public static int light(String light) {char[] lightChars = light.toCharArray();
    // 曾经点灯的数量
    int result = 0;
    // 以后来到的地位
    int i = 0;
    while (i < lightChars.length) {
        // i 地位是 'X’,不论,来到 i + 1 地位
        if (lightChars[i] == 'X') {i++;} else {
            // i 地位是 '.',不论后续是怎么的,都要点一个灯
            result++;
            if (i + 1 == lightChars.length) {break;} else {
                // i 地位是 '.',i + 1 是 'X’,i 地位须要放灯,来到 i + 2 地位
                if (lightChars[i + 1] == 'X') {i = i + 2;} else {
                    // i 地位是 '.',i + 1 是 '.',i + 2 是 '.',i + 1 地位须要放灯,来到 i + 3 地位
                    // i 地位是 '.',i + 1 是 '.',i + 2 是 'X’,i 或 i + 1 地位须要放灯,来到 i + 3 地位
                    i = i + 3;
                }
            }
        }
    }
    return result;
}

蕴含对数器的所有代码地址:https://github.com/monday-pro/algorithm-study/blob/master/src/basic/greedy/Light.java

三、IPO 问题

1、题目形容

链接:https://leetcode-cn.com/probl…

假如 力扣(LeetCode)行将开始 IPO。为了以更高的价格将股票卖给风险投资公司,力扣心愿在 IPO 之前发展一些我的项目以减少其资本。因为资源无限,它只能在 IPO 之前实现最多 k 个不同的我的项目(串行做我的项目)。帮忙力扣设计实现最多 k 个不同我的项目后失去最大总资本的形式。

给你 n 个我的项目。对于每个我的项目 i,它都有一个纯利润 profits[i],和启动该我的项目须要的最小资本 capital[i]。

最后,你的资本为 w。当你实现一个我的项目时,你将取得纯利润,且利润将被增加到你的总资本中。

总而言之,从给定我的项目中抉择 最多 k 个不同我的项目的列表,以最大化最终资本,并输入最终可取得的最多资本。

示例:

输出:k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]

输入:4

解释:

因为你的初始资本为 0,你仅能够从 0 号我的项目开始。

在实现后,你将取得 1 的利润,你的总资本将变为 1。

此时你能够抉择开始 1 号或 2 号我的项目。

因为你最多能够抉择两个我的项目,所以你须要实现 2 号我的项目以取得最大的资本。

因而,输入最初最大化的资本,为 0 + 1 + 3 = 4。

2、思路

(1)筹备一个小根堆,以启动我的项目须要的资本为规范,将所有我的项目放到小根堆里

(2)筹备一个大根堆,把此时能做的我的项目从小根堆弹出来(领有的资本 >= 我的项目启动资本),以利润为规范将我的项目放到大根堆中,弹出大根堆中的堆顶我的项目 A,k 加 1,w 加 A 的利润

(3)始终执行第 2 步,直到达到 k 个我的项目,最初返回 w。

和游戏中的打怪降级很像,每次都在本人打得过的怪中找到收益最大的,始终打,本人越来越强同时保障不会被战胜。

3、代码

/**
 * @author Java 和算法学习:周一
 */
public static int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
    // 筹备一个小根堆
    Queue<Program> capitalSmallQueue = new PriorityQueue<>((a, b) -> a.capital - b.capital);
    // 以启动我的项目须要的资本为规范,将所有我的项目放到小根堆中
    for (int i = 0; i < profits.length; i++) {capitalSmallQueue.offer(new Program(profits[i], capital[i]));
    }

    // 筹备一个大根堆
    // 放入的我的项目按我的项目的利润为规范
    Queue<Program> profitsBigQueue = new PriorityQueue<>((a, b) -> b.profit - a.profit);
    for (int i = 0; i < k; i++) {
        // 以后领有的资本 >= 我的项目的启动资本,将我的项目从小根堆中弹出放到大根堆中
        while (!capitalSmallQueue.isEmpty() && w >= capitalSmallQueue.peek().capital) {profitsBigQueue.offer(capitalSmallQueue.poll());
        }

        // 可能资本有余,造成当初还能做我的项目然而大根堆没有我的项目给你做了
        if (profitsBigQueue.isEmpty()) {return w;}

        w += profitsBigQueue.poll().profit;}

    return w;
}

public static class Program {
    public int profit;
    public int capital;

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

本题能够间接在 LeetCode 上测试,所以就不须要对数器来验证了。

4、测试后果

是不是发现贪婪算法的解法正如上一篇所说,难的在于贪婪策略的提出和证实,代码往往都比较简单,同时在面试时区分度也不是很高。

正文完
 0