【Day31】力扣算法(超详细思路+注释)[1441. 用栈操作构建数组 ] [621. 任务调度器]

简介: 学习力扣算法(超详细思路+注释)[1441. 用栈操作构建数组 ] [621. 任务调度器]。

刷题打卡,第 三十一 天


题目一、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遍历完,返回获取到的对操作数组
    }
}

微信图片_20221031121409.png

题目二、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);
    }
}

提交结果:

微信图片_20221031121416.png

⚽求关注⚽ 作者🥇 .29. 🥇 的✔博客主页✔

⚽来刷题⚽ 记录每日LeetCode✔刷题专栏✔

您的点赞,收藏以及关注是对作者最大的鼓励喔 ~~

微信图片_20221029111446.jpg




目录
打赏
0
0
0
0
4
分享
相关文章
JS数组操作方法全景图,全网最全构建完整知识网络!js数组操作方法全集(实现筛选转换、随机排序洗牌算法、复杂数据处理统计等情景详解,附大量源码和易错点解析)
这些方法提供了对数组的全面操作,包括搜索、遍历、转换和聚合等。通过分为原地操作方法、非原地操作方法和其他方法便于您理解和记忆,并熟悉他们各自的使用方法与使用范围。详细的案例与进阶使用,方便您理解数组操作的底层原理。链式调用的几个案例,让您玩转数组操作。 只有锻炼思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
|
20天前
|
关于员工上网监控系统中 PHP 关联数组算法的学术解析
在当代企业管理中,员工上网监控系统是维护信息安全和提升工作效率的关键工具。PHP 中的关联数组凭借其灵活的键值对存储方式,在记录员工网络活动、管理访问规则及分析上网行为等方面发挥重要作用。通过关联数组,系统能高效记录每位员工的上网历史,设定网站访问权限,并统计不同类型的网站访问频率,帮助企业洞察员工上网模式,发现潜在问题并采取相应管理措施,从而保障信息安全和提高工作效率。
32 7
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
80 23
随机森林算法是一种强大的集成学习方法,通过构建多个决策树并综合其结果进行预测。
随机森林算法是一种强大的集成学习方法,通过构建多个决策树并综合其结果进行预测。本文详细介绍了随机森林的工作原理、性能优势、影响因素及调优方法,并提供了Python实现示例。适用于分类、回归及特征选择等多种应用场景。
166 7
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
96 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
基于图论算法有向图PageRank与无向图Louvain算法构建指令的方式方法 用于支撑qwen agent中的统计相关组件
利用图序列进行数据解读,主要包括节点序列分析、边序列分析以及结合节点和边序列的综合分析。节点序列分析涉及节点度分析(如入度、出度、度中心性)、节点属性分析(如品牌、价格等属性的分布与聚类)、节点标签分析(如不同标签的分布及标签间的关联)。边序列分析则关注边的权重分析(如关联强度)、边的类型分析(如管理、协作等关系)及路径分析(如最短路径计算)。结合节点和边序列的分析,如子图挖掘和图的动态分析,可以帮助深入理解图的结构和功能。例如,通过子图挖掘可以发现具有特定结构的子图,而图的动态分析则能揭示图随时间的变化趋势。这些分析方法结合使用,能够从多个角度全面解读图谱数据,为决策提供有力支持。
182 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
63 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
|
5月前
|
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
46 0
Leetcode第三十三题(搜索旋转排序数组)
|
5月前
【LeetCode 24】225.用队列实现栈
【LeetCode 24】225.用队列实现栈
31 0
|
5月前
|
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
103 0