内修算法之队列

内修算法之队列

杀死进程

给你n个进程，每个进程都有一个唯一的PID（process id）和PPID（parent process id）。每个进程最多只有一个父进程，但可能有多个子进程。如果一个进程的PPID为0，表示它没有父进程。如果一个进程被杀死，那么它的子进程也会被杀死。输入两个相同长度的整数链表，第一个链表是每个进程的PID，第二个链表是对应位置进程的PPID，再输入一个将被杀死的进程的PID，请输出所有将被杀死的进程的PID。

例如，输入的PID链表为[1, 3, 10, 5]，PPID链表为[3, 0, 5, 3]，将被杀死的进程的PID为5，那么最终被杀死的进程有两个，PID分别为5和10。这是因为PID为10的进程是PID为5的进程的子进程。

public class App {public static void main(String args[]){int pidIn[]={1,2,3,4};int ppidIn[]={0,1,1,3};List<Integer>pid = Arrays.stream(pidIn).boxed().List());List<Integer>ppid = Arrays.stream(ppidIn).boxed().List());//Arrays.asList(items).forEach(item -> System.out.println(item));Arrays.asList(new App().killProcess(pid,ppid,3)).forEach(System.out::println);}/*** 用邻接表来表示一棵树，我们可以把整棵树存到一个HashMap中。* 这个HashMap的Key为进程的PID，Value为对应进程的所有子进程的PID，* 也就是树中对应节点的所有子节点。下面是根据PID和PPID链表构建树的参考代码：*  ----------------  Iterator  ------------------*  他是collection中的一个方法，可遍历数组/链表，用的是工厂模式*  通常使用Iterator的hasNext()方法结合while()来使用*/private Map<Integer, List<Integer>> buildTree(List<Integer> pid, List<Integer> ppid) {Map<Integer, List<Integer>> processTree = new HashMap<>();Iterator<Integer> iterator1 = pid.iterator();Iterator<Integer> iterator2 = ppid.iterator();while (iterator1.hasNext() && iterator2.hasNext()) {int p = ();int pp = ();if (!ainsKey(pp)) {//避免重复操作processTree.put(pp, new LinkedList<>());}(pp).add(p);}return processTree;}/*** 基于广度优先的代码通常会用到队列（queue）。我们首先把第一个待杀死的进程的PID放入队列中，* 接下来只要队列中还有待杀死的进程，就重复执行如下步骤：首先从队列中去除一个进程，杀死它（即添加到输出的链表中）；* 接着，如果该进程有子进程则把子进程添加到队列中。* @param pid* @param ppid* @param target* @return*/public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int target) {Map<Integer, List<Integer>> processTree = buildTree(pid, ppid);List<Integer> result = new LinkedList<>();Queue<Integer> queue = new LinkedList<>();queue.add(target);while (!queue.isEmpty()) {int process = ve();result.add(process);if (ainsKey(process)) {for (int child : (process)) {queue.add(child);}}}return result;}
}

任务调度器

给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。

然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。

你需要计算完成所有任务所需要的最短时间。

示例 1：

输入: tasks = ["A","A","A","B","B","B"], n = 2
输出: 8
执行顺序: A -> B -> (待命) -> A -> B -> (待命) -> A -> B.

注：
任务的总个数为 [1, 10000]。
n 的取值范围为 [0, 100]

参考：

杀死进程代码实现+详细分析
.html
任务调度器：