烟台网站制作方案,网站编写教程,wordpress阅读量没改,企业管理咨询类公司文章目录1. 比赛结果2. 题目解析2.1 拿硬币 Easy2.2 传递信息 Esay2.3 剧情触发时间 Medium2.4 最小跳跃次数 Hard2.5 二叉树任务调度 Hard1. 比赛结果
前两题比较顺利#xff0c;24分钟做出来了#xff0c;第3#xff0c;4两题试了好久#xff0c;都显示超时#xff0c;…
文章目录1. 比赛结果2. 题目解析2.1 拿硬币 Easy2.2 传递信息 Esay2.3 剧情触发时间 Medium2.4 最小跳跃次数 Hard2.5 二叉树任务调度 Hard1. 比赛结果
前两题比较顺利24分钟做出来了第34两题试了好久都显示超时第5题没心思看想着第34题应该能做出来的。
2. 题目解析
2.1 拿硬币 Easy
题目链接 桌上有 n 堆力扣币每堆的数量保存在数组 coins 中。我们每次可以选择任意一堆拿走其中的一枚或者两枚求拿完所有力扣币的最少次数。
示例 1
输入[4,2,1]
输出4
解释第一堆力扣币最少需要拿 2 次
第二堆最少需要拿 1 次
第三堆最少需要拿 1 次
总共 4 次即可拿完。示例 2
输入[2,3,10]
输出8限制
1 n 4
1 coins[i] 10解答
除以2向上取整即可
class Solution {
public:int minCount(vectorint coins) {int i, sum 0;for(i 0; i coins.size(); i)sum ceil(coins[i]/2.0);return sum;}
};执行用时4 ms 内存消耗8.4 MB 2.2 传递信息 Esay
题目链接 小朋友 A 在和 ta 的小伙伴们玩传信息游戏游戏规则如下
有 n 名玩家所有玩家编号分别为 0 n-1其中小朋友 A 的编号为 0每个玩家都有固定的若干个可传信息的其他玩家也可能没有。传信息的关系是单向的比如 A 可以向 B 传信息但 B 不能向 A 传信息。每轮信息必须需要传递给另一个人且信息可重复经过同一个人
给定总玩家数 n以及按 [玩家编号,对应可传递玩家编号] 关系组成的二维数组 relation。 返回信息从小 A (编号 0 ) 经过 k 轮传递到编号为 n-1 的小伙伴处的方案数若不能到达返回 0。
示例 1
输入n 5, relation [[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0,4]], k 3
输出3
解释信息从小 A 编号 0 处开始经 3 轮传递到达编号 4。
共有 3 种方案分别是 0-2-0-4 0-2-1-4 0-2-3-4。示例 2
输入n 3, relation [[0,2],[2,1]], k 2
输出0
解释信息不能从小 A 处经过 2 轮传递到编号 2限制
2 n 10
1 k 5
1 relation.length 90, 且 relation[i].length 2
0 relation[i][0],relation[i][1] n
且 relation[i][0] ! relation[i][1]解答
把路径的边插入set方便后面快速查找dp[i][j] 表示第i次传递到j的方案数
class Solution {
public:int numWays(int n, vectorvectorint relation, int k) {setvectorint s;for(auto re : relation)s.insert(re);vectorvectorint dp(k1,vectorint(n,0));dp[0][0] 1;//初始状态for(int i 1; i k; i)//k次传递{for(int j 0; j n; j){ //n个人如果存在传递到这的情况if(dp[i-1][j]!0){for(int k 0; k n; k){ //传给下一个人可以传给跟自己有关系的if(s.count({j,k}))//有关系dp[i][k] dp[i-1][j];}}}}return dp[k][n-1];}
};执行用时8 ms 内存消耗7.6 MB
class Solution { //更简洁的版本
public:int numWays(int n, vectorvectorint relation, int k) {int dp[6][10] {0};dp[0][0]1;for(int i0;ik;i)for(auto ss:relation)dp[i1][ss[1]] dp[i][ss[0]];return dp[k][n-1];}//参看作者xunh
};2.3 剧情触发时间 Medium
题目链接 在战略游戏中玩家往往需要发展自己的势力来触发各种新的剧情。 一个势力的主要属性有三种分别是文明等级C资源储备R以及人口数量H。 在游戏开始时第 0 天三种属性的值均为 0。
随着游戏进程的进行每一天玩家的三种属性都会对应增加我们用一个二维数组 increase 来表示每天的增加情况。 这个二维数组的每个元素是一个长度为 3 的一维数组例如 [[1,2,1],[3,4,2]] 表示第一天三种属性分别增加 1,2,1 而第二天分别增加 3,4,2。
所有剧情的触发条件也用一个二维数组 requirements 表示。 这个二维数组的每个元素是一个长度为 3 的一维数组对于某个剧情的触发条件 c[i], r[i], h[i]如果当前 C c[i] 且 R r[i] 且 H h[i] 则剧情会被触发。
根据所给信息请计算每个剧情的触发时间并以一个数组返回。 如果某个剧情不会被触发则该剧情对应的触发时间为 -1 。
示例 1
输入 increase [[2,8,4],[2,5,0],[10,9,8]]
requirements [[2,11,3],[15,10,7],[9,17,12],[8,1,14]]
输出: [2,-1,3,-1]
解释
初始时C 0R 0H 0
第 1 天C 2R 8H 4
第 2 天C 4R 13H 4此时触发剧情 0
第 3 天C 14R 22H 12此时触发剧情 2
剧情 1 和 3 无法触发。示例 2
输入 increase [[0,4,5],[4,8,8],[8,6,1],[10,10,0]]
requirements [[12,11,16],[20,2,6],[9,2,6],[10,18,3],[8,14,9]]
输出: [-1,4,3,3,3]示例 3
输入 increase [[1,1,1]] requirements [[0,0,0]]
输出: [0]限制
1 increase.length 10000
1 requirements.length 100000
0 increase[i] 10
0 requirements[i] 100000我的比赛错误解1、有重复元素没考虑2、erase 迭代器后迭代器失效
struct cmp1
{bool operator()(const vectorint a, const vectorint b)const{if(a[0]b[0]){if(a[1]b[1])return a[2] b[2];return a[1] b[1];}return a[0] b[0];}
};class Solution {
public:vectorint getTriggerTime(vectorvectorint inc, vectorvectorint req) {int t 0, n req.size(), a 0, b 0, c 0;vectorint ans(n,-1);mapvectorint, int m;setvectorint,cmp1 set1;for(int i 0; i n; i){m[req[i]]i;set1.insert(req[i]);}vectorint tp;auto end1 set1.upper_bound({a,b,c});for(auto it set1.begin(); it ! end1; it){tp *it;if(atp[0] btp[1] ctp[2]){ans[m[tp]] t;set1.erase(tp);}}for(int i 0; i inc.size(); i){t i1;a inc[i][0];b inc[i][1];c inc[i][2];auto end set1.upper_bound({a,b,c});for(auto it set1.begin(); it ! end; it){tp *it;if(atp[0] btp[1] ctp[2]){ans[m[tp]] t;set1.erase(tp);}}}return ans;}
};我的赛后正确解m.erase(it);//这样做迭代器不会失效利用multimap平衡搜索树有序可以进行二分查找
struct cmp1 //自定义排序规则
{bool operator()(const vectorint a, const vectorint b)const{if(a[0]b[0]){if(a[1]b[1])return a[2] b[2];return a[1] b[1];}return a[0] b[0];}
};class Solution {
public:vectorint getTriggerTime(vectorvectorint inc, vectorvectorint req) {int t 0, n req.size(), a 0, b 0, c 0;vectorint ans(n,-1);multimapvectorint, int, cmp1 m;for(int i 0; i n; i)m.insert(make_pair(req[i],i));vectorint tp;for(int i -1; i int(inc.size()); i)//注意坑int -1 跟 size_t 比较循环进不去{t i1;if(i 0){a inc[i][0];b inc[i][1];c inc[i][2];}auto end m.upper_bound({a,b,c});for(auto it m.begin(); it ! end; ){tp it-first;if(atp[0] btp[1] ctp[2]){ans[it-second] t;m.erase(it);//这样做迭代器不会失效}elseit;}}return ans;}
};2.4 最小跳跃次数 Hard
题目链接
为了给刷题的同学一些奖励力扣团队引入了一个弹簧游戏机。 游戏机由 N 个特殊弹簧排成一排编号为 0 到 N-1。 初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹簧处通过按动弹簧可以选择把小球向右弹射 jump[i] 的距离或者向左弹射到任意左侧弹簧的位置。 也就是说在编号为 i 弹簧处按动弹簧小球可以弹向 0 到 i-1 中任意弹簧或者 ijump[i] 的弹簧若 ijump[i]N 则表示小球弹出了机器。 小球位于编号 0 处的弹簧时不能再向左弹。
为了获得奖励你需要将小球弹出机器。 请求出最少需要按动多少次弹簧可以将小球从编号 0 弹簧弹出整个机器即向右越过编号 N-1 的弹簧。
示例 1
输入jump [2, 5, 1, 1, 1, 1]
输出3
解释小 Z 最少需要按动 3 次弹簧
小球依次到达的顺序为 0 - 2 - 1 - 6最终小球弹出了机器。限制
1 jump.length 10^6
1 jump[i] 10000我的BFS超时解 超时的例子
class Solution {
public:int minJump(vectorint jump) {int i, j, n jump.size(), t 0, size,tp;setint set;for(i 0; i n; i)set.insert(i);queueint q;q.push(0);set.erase(0);while(!q.empty()){size q.size();t;while(size--){tp q.front();q.pop();if(tpjump[tp] n)return t;if(set.count(tpjump[tp])){q.push(tpjump[tp]);set.erase(tpjump[tp]);}auto end set.upper_bound(tp);//这个地方多了lgn的查找用数组降到O(1)for(auto it set.begin(); it ! end; it){q.push(*it);set.erase(*it);}}}return t;}
};改进的BFS
class Solution {
public:int minJump(vectorint jump) {int i, n jump.size(), t 0, size, tp, prevPos 0;vectorbool vis(n,false);vis[0] true;queueint q;q.push(0);while(!q.empty()){size q.size();t;while(size--){tp q.front();q.pop();if(tpjump[tp] n)return t;if(!vis[tpjump[tp]]){ //向右跳过来q.push(tpjump[tp]);vis[tpjump[tp]] true;}for(i prevPos1; tp 0 i tp; i){ //向左位置跳if(!vis[i]){q.push(i);vis[i] true;}}prevPos max(prevPos,tp);//没有这句会超时//避免重复检查某些位置}}return t;}
};2.5 二叉树任务调度 Hard
题目链接
任务调度优化是计算机性能优化的关键任务之一。在任务众多时不同的调度策略可能会得到不同的总体执行时间因此寻求一个最优的调度方案是非常有必要的。
通常任务之间是存在依赖关系的即对于某个任务你需要先完成他的前导任务如果非空才能开始执行该任务。 我们保证任务的依赖关系是一棵二叉树其中 root 为根任务root.left 和 root.right 为他的两个前导任务可能为空root.val 为其自身的执行时间。
在一个 CPU 核执行某个任务时我们可以在任何时刻暂停当前任务的执行并保留当前执行进度。在下次继续执行该任务时会从之前停留的进度开始继续执行。暂停的时间可以不是整数。
现在系统有两个 CPU 核即我们可以同时执行两个任务但是同一个任务不能同时在两个核上执行。 给定这颗任务树请求出所有任务执行完毕的最小时间。
示例 1 输入root [47, 74, 31] 输出121 解释根节点的左右节点可以并行执行31分钟剩下的4347分钟只能串行执行因此总体执行时间是121分钟。
示例 2
输入root [15, 21, null, 24, null, 27, 26] 输出87
示例 3 输入root [1,3,2,null,null,4,4] 输出7.5
限制 1 节点数量 1000 1 单节点执行时间 1000
