【Day31】力扣算法(超详细思路+注释)[1441. 用栈操作构建数组 ] [621. 任务调度器]
【Day31】力扣算法(超详细思路+注释)[1441. 用栈操作构建数组 ] [621. 任务调度器]
刷题打卡，第 三十一 天
题目一、1441. 用栈操作构建数组
原题链接：1441. 用栈操作构建数组
题目描述：
给你一个数组
target和一个整数n。每次迭代，需要从 list = { 1 , 2 , 3 …, n } 中依次读取一个数字。 请使用下述操作来构建目标数组 target ：
"Push"：从 list 中读取一个新元素， 并将其推入数组中。"Pop"：删除数组中的最后一个元素。- 如果目标数组构建完成，就停止读取更多元素。
题目数据保证目标数组严格递增，并且只包含 1 到 n 之间的数字。 请返回构建目标数组所用的操作序列。如果存在多个可行方案，返回任一即可。 / 示例 1： 输入：target = [1,3], n = 3 输出：[“Push”,“Push”,“Pop”,“Push”] 解释： 读取 1 并自动推入数组 -> [1] 读取 2 并自动推入数组，然后删除它 -> [1] 读取 3 并自动推入数组 -> [1,3] / 示例 2： 输入：target = [1,2,3], n = 3 输出：[“Push”,“Push”,“Push”] / 示例 3： 输入：target = [1,2], n = 4 输出：[“Push”,“Push”] 解释：只需要读取前 2 个数字就可以停止。
解题思路：
通过理解题目，我们可以知道，给定的数组target中存放的元素范围是从1到n，而且元素是严格递增的，因为数组每次迭代，需要从 list = { 1 , 2 , 3 …, n } 中依次读取一个数字。
而题目的要求就是我们需要使用堆操作，让堆中存放的元素以及元素的顺序都与给定的数组target相同，并且将对堆的操作用数组存放并返回。
规则与需求都分析清楚，接下来思路也就清晰了。
我们可以同时遍历数组target，以及可读取的数组集合： list={ 1 , 2 , 3 …, n } ，这样一来会出现两种情况：
①当前位置遍历的两个值相等，那么就说明堆中需要当前元素，我们对集合list中当前的数字进行"Push"操作，让堆中当前位置元素与数组target保持一致，之后继续对数组target与集合list向后遍历。
②当前位置遍历到的两个值不相等，就说明当前元素是堆不需要的，但是题目要求堆必须依次读取数字，我们就需要先进行"Push"操作再进行"Pop"操作从而继续向后遍历数字，需要注意的是此时遍历到的数组target的位置不变，知道遇到相同的元素。
这么一来，当我们遍历完数组target，也就得到了题目需要的对操作数组。
提交代码：
提交结果：
class Solution {
public List<String> buildArray(int[] target, int n) {
List<String> dequeStep = new ArrayList<>(); //常见数组集合，存放堆操作顺序
int len = target.length; //获取target数组的长度
int index = 0; //表示当前遍历到的target集合的下标
for(int i = 1;i <= n;++i){ //遍历从1到n个数
if(index == len) break; //遍历完整个target数组，停止
dequeStep.add("Push"); //无论是什么情况，堆都需要使用Push操作
if(target[index] == i){ //如果遍历到的元素相同，Push操作后
++index; //继续向后遍历
}else if(target[index] > i){ //遇到不同的数字
dequeStep.add("Pop"); //Push操作后还需Pop操作，继续遍历1到n中后续的元素
}
}
return dequeStep; //target遍历完，返回获取到的对操作数组
}
}
题目二、621. 任务调度器
原题链接：621. 任务调度器
题目描述：
给你一个用字符数组
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 -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A
解题思路：
为了获取到完成所有任务需求的最短时间，我们就需要获取到任务需求中出现次数最多的需求。
以最短时间完成所有需求，重要的一点就在需求最多任务的冷却时间内执行出现较少的需求或者是等待冷却时间。
按照上面的思路，我们需要关注的就是出现次数最多的需求，我们在这里记作max任务，max任务一共出现max次，而穿插在任务max完成后冷却时间中执行的其余需求或者等待时间我们无序准确地安排。
每执行一个单位之间地max任务后，需要有n时间单位的冷却时间，这么一来，执行一个max任务，到下一个max任务之前，就是n个时间单位加上其本身的一个时间单位，即：n+1.
当我们执行完max-1从max任务，也就使用了（max-1）*（n+1） 的时间，这时候还剩下最后一个max任务没有执行，所以我们最短的执行时间是（max-1）*（n+1）+1 。例如：数组 [“A”,“A”,“A”,“B”,“B”,“C”]，n = 2，顺序为： A->X->X->A->X->X->A。
这么一来我们就正确了吗？还没完全正确，任务需求中可能会出现多个数量相同的max任务，其余步骤与上述相同的情况下，会剩下的不是一个max任务，而是多个不同max任务，我们将不同max任务的数量记录下来，记作maxCount,最短的执行时间就变成了（max-1）*（n+1）+maxCount 。例如： [“A”,“A”,“A”,“B”,“B”,“B”,“C”,“C”]，最后剩下A和B，maxCount = 2.
到最后，我们得到的答案可能小于任务数组的长度，这是不正确的，这时候我们就需要返回数组长度。例如： [“X”,“X”,“L”,“L”],n=0,我们就需要返回数组长度：4。
提交代码：
class Solution {
public int leastInterval(char[] tasks, int n) {
Map<Character,Integer> map = new HashMap<>(); //创建双列集合map
int max = 0; //max记录出现最频繁的任务次数
for(int i = 0;i < tasks.length;++i){ //遍历任务数组
char curr = tasks[i];
if(!map.containsKey(curr)){ //集合中不存在此任务
map.put(curr,1); //在集合中创建记录，出现次数为1
}else{ //以及存在
map.replace(curr,map.get(curr).intValue()+1);//给对应任务的出现次数+1
}
max = Math.max(max,map.get(curr)); //记录当前出现最频繁的任务的次数
}
int maxCount = 0; //maxCount记录不同的最频繁任务数量
//使用迭代器遍历双列集合，获取键值对的值
Iterator<Map.Entry<Character,Integer>> iterator = map.entrySet().iterator();
while(iterator.hasNext()){
Map.Entry<Character,Integer> entry = iterator.next();
int value = entry.getValue();
//如果出现的次数为最频繁的
if(value == max){
maxCount++; //maxCount+1
}
}
//返回任务数组长度 与 公式结果 两者间的最大值，防止出现结果小于数组长度的错误情况
return Math.max(tasks.length,(max-1)*(n+1)+maxCount);
}
}提交结果：
