乐趣区

关于算法:LeetCode-2050-并行课程3

1 题目

原题链接。

2 想法

题目实质上是一条拓扑排序的题,只不过,在拓扑排序的根底上,加上了一个工夫的限度。每门课程规定了须要肯定的工夫实现,也就是说,实现一门课程的工夫,须要依据先修课程确定。

拓扑排序能够应用广搜配合入度数组去解决,而计算某一门课程的工夫,须要依据先修工夫确定。能够必定的是,如果一门课程没有先修课程,那么修这门课程的工夫,就是 time 数组中的工夫。

而如果一门课程有先修课程,容易想到,须要依据最大的一门先修课程工夫去确定,比方 课程 3 的先修课程是 课程 1 课程 2 ,假如:

  • 课程 1 须要破费的单位工夫为3
  • 课程 2 须要破费的单位工夫为5

那么,课程 3 须要破费的工夫就是 max(课程 1, 课程 2)+ 课程 3 的工夫,也就是取 课程 1 课程 2 最大值再加上修 课程 3 的工夫。

这样,能够揣测,如果一门 课程 n +1 n 门 先修课程,那么修 课程 n +1的工夫,就是这修 n 门 课程的最大值,再加上修 课程 n +1的工夫。这实际上就是一个简略的动静布局:

dp[n+1] = max(dp[0]..dp[n])+time[n+1]

3 实现

代码有很具体的正文:

import java.util.*;

public class Solution {public int minimumTime(int n, int[][] relations, int[] time) {// 工夫 dp,留神存储的是 dp[1]..dp[n]
        int[] dp = new int[n + 1];
        // 存储入度,为了不便计算同样开了 n +1
        int[] inDegree = new int[n + 1];
        // 邻接表
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i <= n; i++) {list.add(new ArrayList<>());
        }
        // 通过邻接表建图
        for (int[] r : relations) {
            // 更新入度
            ++inDegree[r[1]];
            list.get(r[0]).add(r[1]);
        }
        // 广搜队列
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            // 如果入度为 0
            if (inDegree[i] == 0) {// 能够间接设置 dp[i]的值,因为入度为 0 代表课程 i 没有先修课程
                dp[i] = time[i - 1];
                // 退出广搜队列
                queue.addLast(i);
            }
        }
        // 广搜队列不为空
        while (!queue.isEmpty()) {
            // 获取以后队列大小
            int size = queue.size();
            // 遍历以后队列中入度为 0 的课程
            for (int i = 0; i < size; i++) {
                // 出队
                int front = queue.pollFirst();
                // 获取先修课程指向的是哪些课程
                for (int v : list.get(front)) {// 课程 v 的工夫是 dp[v]与先修课程 front+ 修课程 v 的最大值
                    dp[v] = Math.max(dp[v], dp[front] + time[v - 1]);
                    // 将课程 v 的入度减 1,示意曾经实现一门课程
                    if (--inDegree[v] == 0) {
                        // 如果入度为 0,也就是先修课程全副实现,将其入队
                        queue.addLast(v);
                    }
                }
            }
        }
        // 取最大值,不能间接 dp[n],因为最初修的课程不肯定是课程 n,所以须要遍历一次,取所有 dp 的最大值
        int res = 0;
        for (int v : dp) {res = Math.max(v, res);
        }
        return res;
    }
}

工夫与内存如下:

4 优化

4.1 队列优化

对于带队列的题目,一个常见的优化技巧是应用数组去模仿队列。

须要留神的是,这须要依据题目去确定,尽管队列中存储的是点,然而实际上存储的是边,因为每遍历到一个点就将对应的出边(的点)退出到队列中。察看题目边的范畴:

间接取这个范畴的队列即可,不会OOM

int[] queue = new int[(int) Math.min(n * (n + 1L) / 2, 5L * 10_000)];

留神因为 n 取值可能比拟大,导致 n^2 可能会爆int,所以须要做一下强制转换。

而后用两个变量代表队头和队尾:

int queueFront = 0;
int queueTail = 0;
// 入队
queue[queueTail++] = i;
// 出队
i = queue[queueFront++];

残缺代码(逻辑与下面一样,只是批改了队列局部):

import java.util.*;

public class Solution {public int minimumTime(int n, int[][] relations, int[] time) {int[] dp = new int[n + 1];
        int[] inDegree = new int[n + 1];
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i <= n; i++) {list.add(new ArrayList<>());
        }
        for (int[] r : relations) {++inDegree[r[1]];
            list.get(r[0]).add(r[1]);
        }
        int[] queue = new int[(int) Math.min(n * (n + 1L) / 2, 5L * 10_000)];
        int queueFront = 0;
        int queueTail = 0;
        for (int i = 1; i <= n; i++) {if (inDegree[i] == 0) {dp[i] = time[i - 1];
                // 入队
                queue[queueTail++] = i;
            }
        }
        // 判断队列是否为空
        while (queueFront < queueTail) {
            // 获取队列大小
            int size = queueTail - queueFront;
            for (int i = 0; i < size; i++) {
                // 出队
                int front = queue[queueFront++];
                for (int v : list.get(front)) {dp[v] = Math.max(dp[v], dp[front] + time[v - 1]);
                    if (--inDegree[v] == 0) {
                        // 入队
                        queue[queueTail++] = v;
                    }
                }
            }
        }
        int res = 0;
        for (int v : dp) {res = Math.max(v, res);
        }
        return res;
    }
}

工夫:

有一点点的优化,然而不多。

4.2 算法细节优化

开端能够看到有一处计算最大值的中央:

int res = 0;
for (int v : dp) {res = Math.max(v, res);
}

为什么须要再次遍历 dp 计算最大值呢?

因为不晓得哪一个 dp 最大,然而,能够在每一次 dp 计算完结的时候,计算res

import java.util.*;

public class Solution {public int minimumTime(int n, int[][] relations, int[] time) {int[] dp = new int[n + 1];
        int[] inDegree = new int[n + 1];
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i <= n; i++) {list.add(new ArrayList<>());
        }
        for (int[] r : relations) {++inDegree[r[1]];
            list.get(r[0]).add(r[1]);
        }
        int[] queue = new int[(int) Math.min(n * (n + 1L) / 2, 5L * 10_000)];
        int queueFront = 0;
        int queueTail = 0;
        int res = 0;
        for (int i = 1; i <= n; i++) {if (inDegree[i] == 0) {
                // 计算最大值
                res = Math.max(res, time[i - 1]);
                dp[i] = time[i - 1];
                queue[queueTail++] = i;
            }
        }
        while (queueFront < queueTail) {
            int size = queueTail - queueFront;
            for (int i = 0; i < size; i++) {int front = queue[queueFront++];
                // dp[front]曾经确定是计算结束了,用 dp[front]计算最大值
                res = Math.max(res, dp[front]);
                for (int v : list.get(front)) {dp[v] = Math.max(dp[v], dp[front] + time[v - 1]);
                    if (--inDegree[v] == 0) {queue[queueTail++] = v;
                    }
                }
            }
        }
        return res;
    }
}

工夫:

貌似没影响,再持续优化一下。

4.3 建图优化

没错,就是应用链式前向星代替邻接表进行建图优化。

链式前向星介绍能够参考此处,不细说了。

最终代码:

import java.util.*;

public class Solution {public int minimumTime(int n, int[][] relations, int[] time) {int[] dp = new int[n + 1];
        int[] inDegree = new int[n + 1];
        int[] last = new int[n + 1];
        int edgeCount = relations.length;
        int[] pre = new int[edgeCount + 1];
        // 初始化 last 为 -1
        Arrays.fill(last, -1);
        for (int i = 0; i < edgeCount; i++) {int v0 = relations[i][0];
            int v1 = relations[i][1];
            ++inDegree[v1];
            // 建图
            pre[i] = last[v0];
            last[v0] = i;
        }
        int[] queue = new int[(int) Math.min(n * (n + 1L) / 2, 5L * 10_000)];
        int queueFront = 0;
        int queueTail = 0;
        int res = 0;
        for (int i = 1; i <= n; i++) {if (inDegree[i] == 0) {res = Math.max(res, time[i - 1]);
                dp[i] = time[i - 1];
                queue[queueTail++] = i;
            }
        }
        while (queueFront < queueTail) {
            int size = queueTail - queueFront;
            for (int i = 0; i < size; i++) {int front = queue[queueFront++];
                res = Math.max(res, dp[front]);
                // 遍历所有边
                for (int lastEdge = last[front]; lastEdge != -1; lastEdge = pre[lastEdge]) {int v = relations[lastEdge][1];
                    dp[v] = Math.max(dp[v], dp[front] + time[v - 1]);
                    if (--inDegree[v] == 0) {queue[queueTail++] = v;
                    }
                }
            }
        }
        return res;
    }
}

工夫:

至此优化实现。

5 总结

题目以拓扑排序为根底,再其中退出了计算工夫的动静布局。

实现时,拓扑排序能够广搜 + 队列实现,计算工夫的 dp 是比较简单的一维dp,转移方程也比拟好推。

写代码时有些细节要留神:

  • 数组调配 n+1 而不是n
  • 因为一开始的算法不欠缺导致了计算实现 dp 后还须要再遍历一次 dp 取最大值

优化次要依附链式前向星的工夫优化,队列优化以及算法细节优化成果并不显著。

退出移动版