LeetCode 2020 力扣杯全国春季编程大赛（1644/4093，前40.2%）数据结构与算法Michael是个半路程序员-

1. 比赛结果

前两题比较顺利，24分钟做出来了，第3，4两题试了好久，都显示超时，第5题没心思看，想着第3，4题应该能做出来的。

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(vector<int>& 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, vector<vector<int>>& relation, int k) {      set<vector<int>> s; for(auto re : relation)    s.insert(re);    vector<vector<int>> dp(k+1,vector<int>(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, vector<vector<int>>& relation, int k) { int dp[6][10]= {0};         dp[0][0]=1; for(int i=0;i<k;i++) for(auto ss:relation)                 dp[i+1][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 = 0，R = 0，H = 0 第 1 天，C = 2，R = 8，H = 4 第 2 天，C = 4，R = 13，H = 4，此时触发剧情 0 第 3 天，C = 14，R = 22，H = 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 vector<int>& a, const vector<int>& 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:     vector<int> getTriggerTime(vector<vector<int>>& inc, vector<vector<int>>& req) { int t = 0, n = req.size(), a = 0, b = 0, c =0;      vector<int> ans(n,-1);      map<vector<int>, int> m;      set<vector<int>,cmp1> set1; for(int i = 0; i < n; ++i) {       m[req[i]]=i;       set1.insert(req[i]); }       vector<int> tp; auto end1 = set1.upper_bound({a,b,c}); for(auto it = set1.begin(); it != end1; ++it) {    tp = *it; if(a>=tp[0] && b>=tp[1] && c>=tp[2]) {        ans[m[tp]] = t;        set1.erase(tp); } } for(int i = 0; i < inc.size(); ++i) {       t = i+1;       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(a>=tp[0] && b>=tp[1] && c>=tp[2]) {         ans[m[tp]] = t;         set1.erase(tp); } } } return ans; } }; 

• 我的赛后正确解：m.erase(it++);//这样做迭代器不会失效
• 利用multimap（平衡搜索树）有序，可以进行二分查找

struct cmp1 //自定义排序规则 { bool operator()(const vector<int>& a, const vector<int>& 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:     vector<int> getTriggerTime(vector<vector<int>>& inc, vector<vector<int>>& req) { int t = 0, n = req.size(), a = 0, b = 0, c =0;      vector<int> ans(n,-1);      multimap<vector<int>, int, cmp1> m; for(int i = 0; i < n; ++i)       m.insert(make_pair(req[i],i));       vector<int> tp; for(int i = -1; i < int(inc.size()); ++i)//注意坑，int -1 跟 size_t 比较，循环进不去 {       t = i+1; 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(a>=tp[0] && b>=tp[1] && c>=tp[2]) {                     ans[it->second] = t;                     m.erase(it++);//这样做迭代器不会失效 } else                     it++; } } return ans; } }; 

2.4 最小跳跃次数 Hard

题目链接

为了给刷题的同学一些奖励，力扣团队引入了一个弹簧游戏机。
游戏机由 N 个特殊弹簧排成一排，编号为 0 到 N-1。
初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹簧处，通过按动弹簧，可以选择把小球向右弹射 jump[i] 的距离，或者向左弹射到任意左侧弹簧的位置。
也就是说，在编号为 i 弹簧处按动弹簧，小球可以弹向 0 到 i-1 中任意弹簧或者 i+jump[i] 的弹簧（若 i+jump[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(vector<int>& jump) { int i, j, n = jump.size(), t = 0, size,tp;      set<int> set; for(i = 0; i < n; ++i)       set.insert(i);      queue<int> q;      q.push(0);      set.erase(0); while(!q.empty()) {       size = q.size();       t++; while(size--) {        tp = q.front();        q.pop(); if(tp+jump[tp] >= n) return t; if(set.count(tp+jump[tp])) {         q.push(tp+jump[tp]);         set.erase(tp+jump[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(vector<int>& jump) { int i, n = jump.size(), t = 0, size, tp, prevPos = 0;      vector<bool> vis(n,false);      vis[0] = true;      queue<int> q;      q.push(0); while(!q.empty()) {       size = q.size();       t++; while(size--) {        tp = q.front();        q.pop(); if(tp+jump[tp] >= n) return t; if(!vis[tp+jump[tp]]) { //向右跳过来         q.push(tp+jump[tp]);         vis[tp+jump[tp]] = true; } for(i = prevPos+1; 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分钟，剩下的43+47分钟只能串行执行，因此总体执行时间是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