leetcode热题100java实现代码

package com.example.leetcode; import java.util.*; public class LC621 { /** * 给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。 * * 然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。 * * 你需要计算完成所有任务所需要的 最短时间 。 * *   * * 示例 1： * * 输入：tasks = ["A","A","A","B","B","B"], n = 2 * 输出：8 * 解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B * 在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。 * 示例 2： * * 输入：tasks = ["A","A","A","B","B","B"], n = 0 * 输出：6 * 解释：在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0 * ["A","A","A","B","B","B"] * ["A","B","A","B","A","B"] * ["B","B","B","A","A","A"] * ... * 诸如此类 * 示例 3： * * 输入：tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2 * 输出：16 [A,6] [B,1] [C,1] [D,1] [E,1] [F,1] [G,1] * 解释：一种可能的解决方案是： * A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A * */ class Pair{ public Character ch; public Integer freq; public Pair(Character ch, Integer freq){ this.ch = ch; this.freq = freq; } } // 贪心？ public int leastInterval(char[] tasks, int n) { Map<Character, Integer> map = new HashMap<>(); int totalElems = 0; int res = 0; List<Character> resList = new ArrayList<>(); for(int i=0; i<tasks.length; i++){ map.put(tasks[i], map.getOrDefault(tasks[i], 0) + 1); totalElems++; } //LinkedHashMap<Character, Boolean> LRUCache = new LinkedHashMap<>(); //LRUCache -- LinkedList<Character> curList = new LinkedList<>(); Set<Character> curSet = new HashSet<>(); List<Pair> list = new ArrayList<>(); for(Map.Entry<Character, Integer> entry: map.entrySet()){ Character ch = entry.getKey(); Integer freq = entry.getValue(); list.add(new Pair(ch, freq)); // 从大到小 排序 list.sort((o1, o2) -> o2.freq - o1.freq); } while(totalElems > 0){ // find one elem boolean found = false; for(int i=0; i<list.size(); i++){ Pair curPair = list.get(i); if(!curSet.contains(curPair.ch) && curPair.freq > 0){ //add this to res res++; totalElems--; found = true; //update list curPair.freq--; list.sort((o1, o2) -> o2.freq - o1.freq); //update set if(curList.size() == n){ Character needToRemove = curList.removeFirst(); curSet.remove(needToRemove); curSet.add(curPair.ch); curList.add(curPair.ch); } else if(curSet.size() < n){ curSet.add(curPair.ch); curList.add(curPair.ch); } resList.add(curPair.ch); break; } } if(!found){ res++; resList.add('*'); if(curList.size() == n){ Character needToRemove = curList.removeFirst(); curSet.remove(needToRemove); curSet.add('*'); curList.add('*'); } else if(curSet.size() < n){ curSet.add('*'); curList.add('*'); } } } //output result for(Character ch: resList){ System.out.print(ch + " -> "); } System.out.println(); return res; } public static void main(String[] args) { char[] tasks = {'A','A','A','A','A','A','B','C','D','E','F','G'}; LC621 instance = new LC621(); int res = instance.leastInterval(tasks, 2); System.out.println(res); } }