1. 比赛结果
前两题比较顺利，24分钟做出来了，第3，4两题试了好久，都显示超时，第5题没心思看，想着第3，4题应该能做出来的。
2. 题目解析
2.1 拿硬币 Easy
题目链接 桌上有 n 堆力扣币，每堆的数量保存在数组 coins 中。我们每次可以选择任意一堆，拿走其中的一枚或者两枚，求拿完所有力扣币的最少次数。
代码语言：javascript复制示例 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
代码语言：javascript复制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 。
代码语言：javascript复制示例 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 的弹簧。
代码语言：javascript复制示例 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
