算法-贪心+优先级队列-IPO

算法-贪心+优先级队列-IPO

1 题目概述

1.1 题目出处

https://leetcode.cn/problems/ipo/description/?envType=study-plan-v2&envId=top-interview-150

1.2 题目描述

2 回溯法

2.1 思路

2.2 代码

class Solution {
    int result = 0;
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < profits.length; i++) {
            set.add(i);
        }
        backtrack(k, w, profits, capital, set);
        return result;
    }

    // r 表示还能选的项目数
    // t 表示当前资本总数
    // Set 可选的项目序号

    private void backtrack(int r, int t, int[] profits, int[] capital, Set<Integer> set) {
        // 结束条件
        if (r == 0) {
            result = Math.max(result, t);
            return;
        }
        List<Integer> list = new ArrayList<>(set);
        int select = 0;
        // 路径选择
        for (Integer i : list) {
            // 选择
            if (t >= capital[i]) {
                select++;
                t += profits[i];
                set.remove(i);
                r--;
                // 递归回溯
                backtrack(r, t, profits, capital, set);
                // 撤销选择
                r++;
                t -= profits[i];
                set.add(i);
            }
        }
        if (select == 0) {
            // 一个都没选，也是结束条件
            result = Math.max(result, t);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

2.3 时间复杂度

直接超时了，选择路径太多了

3 贪心法+优先级队列

2.1 思路

整体思路就是，每次都贪心选择可选项目中利润最大的项目，最后累加得到最大利润。

1. 把项目按最低成本要求升序排序所有项目
2. 每次将符合成本要求的项目放入以利润排序的大顶堆
3. 贪心的取大顶堆堆顶的项目，累加利润到成本后，继续下次判断和选择
4. 如果可选项目数为0或者大顶堆为空了，代表选择完毕

2.2 代码

class Solution {

    class Node {
        public int index;
        public int profit;
        public int capital;

        public Node(int index, int profit, int capital) {
            this.index = index;
            this.profit = profit;
            this.capital = capital;
        }
    }
    int result = 0;
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        // 可选的项目综合信息
        List<Node> projectList = new ArrayList<>();
        for (int i = 0; i < profits.length; i++) {
            projectList.add(new Node(i, profits[i], capital[i]));
        }
        // 把项目按最低成本要求升序排序
        Collections.sort(projectList, (o1, o2) -> o1.capital - o2.capital);
        greed(k, w, projectList, new PriorityQueue<>((o1, o2) -> o2.profit - o1.profit), 0);
        return result;
    }

    // r 表示还能选的项目数
    // t 表示当前资本总数
    // projectList 按最低成本从小到大排序的列表
    // priorityQueue 按项目利润排序的大顶堆
    // i 当前可选择序号
    private void greed(int r, int t, List<Node> projectList, PriorityQueue<Node> priorityQueue, int i) {
        // 结束条件
        if (r == 0) {
            result = Math.max(result, t);
            return;
        }
        // 将符合成本要求的项目放入利润大顶堆
        while (i < projectList.size()) {
            if (t >= projectList.get(i).capital) {
                priorityQueue.add(projectList.get(i));
                i++;
            } else {
                break;
            }
        }
        
        if (priorityQueue.size() == 0) {
            // 一个都不符合要求
            result = Math.max(result, t);
            return;
        }

        // 贪心的选择能选的项目里利润最高的
        Node maxNode = priorityQueue.poll();
        t += maxNode.profit;

        // 继续选下一个项目
        greed(--r, t, projectList, priorityQueue, i);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

2.3 时间复杂度

2.4 空间复杂度

O(n)

• 构建大顶堆、数组