2020 力扣杯！Code Your Future 春季全国编程大赛题解

- 日理万妓 2023-05-21 11:55 42阅读 0赞

# **目录** #

1. 拿硬币

2. 传递信息

3. 剧情触发时间

4. 最小跳跃次数

5. 二叉树任务调度

--------------------

# 1. 拿硬币 #

桌上有 `n` 堆力扣币，每堆的数量保存在数组 `coins` 中。我们每次可以选择任意一堆，拿走其中的一枚或者两枚，求拿完所有力扣币的最少次数。

**示例 1：**

> 输入：`[4,2,1]`
> 
> 输出：`4`
> 
> 解释：第一堆力扣币最少需要拿 2 次，第二堆最少需要拿 1 次，第三堆最少需要拿 1 次，总共 4 次即可拿完。

**示例 2：**

> 输入：`[2,3,10]`
> 
> 输出：`8`

**限制：**

*  `1 <= n <= 4`
 *  `1 <= coins[i] <= 10`

**解题思路：**

很明显每堆两个两个拿，不够两个拿一个

**代码：**

class Solution {
    public:
        int minCount(vector<int>& coins) {
            int ans = 0;
            for(int x:coins){
                ans += (x+1)/2;
            }
            return ans;
        }
    };

# 2. 传递信息 #

小朋友 A 在和 ta 的小伙伴们玩传信息游戏，游戏规则如下：

1.  有 n 名玩家，所有玩家编号分别为 0 ～ n-1，其中小朋友 A 的编号为 0
2.  每个玩家都有固定的若干个可传信息的其他玩家（也可能没有）。传信息的关系是单向的（比如 A 可以向 B 传信息，但 B 不能向 A 传信息）。
3.  每轮信息必须需要传递给另一个人，且信息可重复经过同一个人

给定总玩家数 `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]`

**解题思路：**

用一个队列还储存传递k次后的位置，然后统计有多少次到达了最后的位置

**代码：**

class Solution {
    public:
        int numWays(int n, vector<vector<int>>& relation, int k) {
            vector<vector<int>>res(n);
            for(auto x:relation){
                res[x[0]].push_back(x[1]);
            }
            queue<int>q;
            q.push(0);
            while(!q.empty()&&k>0){
                int size = q.size();
                while(size--){
                    auto u = q.front();
                    q.pop();
                    for(int i = 0;i<res[u].size();i++)
                        q.push(res[u][i]);
                }
                k--;
            }
            int ans = 0;
            while(!q.empty()){
                int c = q.front();
                if(c==n-1)ans++;
                q.pop();
            }
            return ans;
        }
    };

# 3. 剧情触发时间 #

在战略游戏中，玩家往往需要发展自己的势力来触发各种新的剧情。一个势力的主要属性有三种，分别是文明等级（`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`

**解题思路：**

数据量比较大，很明显不能在n平方复杂度下完成，于是可以用三个数组c\[i\],r\[i\],h\[i\]分别维护三个属性值在第i天的数值，对于每一个剧情，使用二分查找来寻找满足的天数，取三个天数的最大值就是解锁天数，注意判断第0天就满足的条件。这样时间复杂度![O(nlogm)][O_nlogm]

**代码：**

class Solution {
    public:
        vector<int> getTriggerTime(vector<vector<int>>& increase, vector<vector<int>>& requirements) {
            int n = requirements.size();
            vector<int>c(increase.size(),0);
            vector<int>r(increase.size(),0);
            vector<int>h(increase.size(),0);
            c[0] = increase[0][0];
            r[0] = increase[0][1];
            h[0] = increase[0][2];
            for(int i = 1;i<increase.size();i++){
                c[i] = c[i-1] + increase[i][0];
                r[i] = r[i-1] + increase[i][1];
                h[i] = h[i-1] + increase[i][2];
            }
            vector<int>ans;
            for(int i = 0;i<n;i++){
                if(requirements[i][0]==0&&requirements[i][1]==0&&requirements[i][2]==0){
                    ans.push_back(0);
                    continue;
                }
                int id1 = lower_bound(c.begin(),c.end(),requirements[i][0])-c.begin();
                int id2 = lower_bound(r.begin(),r.end(),requirements[i][1])-r.begin();
                int id3 = lower_bound(h.begin(),h.end(),requirements[i][2])-h.begin();
                int id = max(max(id1,id2),id3);
                // cout<<id1<<" "<<id2<<" "<<id3<<" "<<id<<endl;
                if(id==increase.size())ans.push_back(-1);
                else ans.push_back(id+1);
            }
            return ans;
        }
    };

# **4. 最小跳跃次数** #

为了给刷题的同学一些奖励，力扣团队引入了一个弹簧游戏机。游戏机由 `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`

**解题思路：**

一开始觉得是动态规划，后来发现不同位置跳跃的最远点需要按照顺序进行处理，于是考虑用一个队列，里边的两个值代表下标和跳到当前位置需要次数，当跳到位置i的时候，i+jump\[i\]≥n作为终止条件，如果没有终止则将\{i+jump\[i\]，d+1\}放入队列，然后再将i位置之前还没有访问过的位置也放入队列，这样在队列中就实现了访问的先后顺序，这里还要用vis标记是否访问过。复杂度是O(n)

**代码：**

class Solution {
    public:
        int minJump(vector<int>& jump) {
            queue<pair<int,int>>q;
            // int i = 0;
            int n = jump.size();
            vector<int>vis(n,0);
            q.push({0,0});
            int start = 0;
            while(!q.empty()){
                int u = q.front().first;
                int d = q.front().second;
                q.pop();
                if(u+jump[u]>=n)return d+1;
                if(vis[u+jump[u]]==0){
                    vis[u+jump[u]] = 1;
                    q.push({u+jump[u],d+1});
                }
                for(int i = start;i<u;i++){
                    if(!vis[i]){
                        vis[i] = 1;
                        q.push({i,d+1});
                    }
                }
                start = max(start,u);
            }
            return -1;
        }
    };

# 5. 二叉树任务调度 #

任务调度优化是计算机性能优化的关键任务之一。在任务众多时，不同的调度策略可能会得到不同的总体执行时间，因此寻求一个最优的调度方案是非常有必要的。

通常任务之间是存在依赖关系的，即对于某个任务，你需要先**完成**他的前导任务（如果非空），才能开始执行该任务。**我们保证任务的依赖关系是一棵二叉树，**其中 `root` 为根任务，`root.left` 和 `root.right` 为他的两个前导任务（可能为空），`root.val` 为其自身的执行时间。

在一个 CPU 核执行某个任务时，我们可以在任何时刻暂停当前任务的执行，并保留当前执行进度。在下次继续执行该任务时，会从之前停留的进度开始继续执行。暂停的时间可以不是整数。

现在，系统有**两个** CPU 核，即我们可以同时执行两个任务，但是同一个任务不能同时在两个核上执行。给定这颗任务树，请求出所有任务执行完毕的最小时间。

**示例 1：**

> ![image.png][]
> 
> 输入：root = \[47, 74, 31\]
> 
> 输出：121
> 
> 解释：根节点的左右节点可以并行执行31分钟，剩下的43+47分钟只能串行执行，因此总体执行时间是121分钟。

**示例 2：**

> ![image.png][image.png 1]
> 
> 输入：root = \[15, 21, null, 24, null, 27, 26\]
> 
> 输出：87

**示例 3：**

> ![image.png][image.png 2]
> 
> 输入：root = \[1,3,2,null,null,4,4\]
> 
> 输出：7.5

**限制：**

*  `1 <= 节点数量 <= 1000`
 *  `1 <= 单节点执行时间 <= 1000`

**解题思路：**

参考[zqy1018解法][zqy1018]

我们设f(i) 为节点 ii 的最短时间，然后分类讨论。

如果 i 是一个叶子，那么显然 f(i) = val(i)。如果 i 只有一个儿子，那么先要执行完儿子才轮得到自己，f(i) = f(son(i)) + val(i)

如果 i 有两个儿子 l, r，那么我们就可以考虑用双核来优化。一种最简单的优化策略是：两个子树分别使用双核跑完，然后再根节点跑。这样的时间消耗是 f(l)+f(r) + val(i)

还有一种策略是：在左边花费 x 时间使用双核（这里是有效使用，即两个核都必须用上，后同），在右边花费 y 时间使用双核，然后在左右两棵子树一边一个核。可以看出，第三个样例使用的正是这样的策略，在根节点的右子树先花费了 3.5 的时间，然后左右两边一边一个核花费 3 时间。

那么，这种情况下，设左右子树的任务总时间和分别为 sum(l), sum(r)。则通过利用双核，左子树剩下的任务时间变成了 sum(l) - 2x，右子树剩下的任务时间变成了 sum(r) - 2y，然后一边一个核处理完剩下的任务所需时间为这两者的较大者。因而总时间为

**val(i)+x+y+max\{sum(l)−2x,sum(r)−2y\}**

即

**val(i)+max\{sum(l)+y−x,sum(r)−(y−x)\}**

val(i)的时间消耗是逃不掉的，我们考虑后面这个 max 怎样取得尽量小。设 t=y-x，那么后面这个max 要取到最小当且仅当 t= mid =(sum(r) - sum(l))/2 ,并且如果 t 偏离 mid 越远，那么这个 max 就越大。注意到 x∈\[0,sum(l)−f(l)\],y∈\[0,sum(r)−f(r)\]，就有t∈\[f(l)−sum(l),sum(r)−f(r)\]。通过对 mid 和这个区间位置的讨论，我们就能算出这个 max 的最小值。

最后把以上这些情况统合起来，就有下面的转移方程：

**f(i)=val(i)+min\{f(l)+f(r), min(max\{sum(l)+t,sum(r)−t\}) **

其中规定如果 l或者 r 为空，对应的 sum, f均为 0。

时间复杂度 O(n)。

**代码：**

class Solution {
    public:
        pair<double,double> dfs(TreeNode* cur){
            if(cur==NULL)return {0,0};
            pair<double,double>lc = dfs(cur->left);
            pair<double,double>rc = dfs(cur->right);
            double fl = lc.first,sml = lc.second;
            double fr = rc.first,smr = rc.second;
            double f = cur->val + fl + fr;
            double sm = cur->val + sml + smr;
            double gl = sml - fl, gr = smr - fr;
            double mid = (smr-sml)/2;
            double t;
            if(mid<-gl)
                t = -gl;
            else if(mid>gr)
                t = gr;
            else
                t = mid;
            f = min(f,cur->val+max(sml+t,smr-t));
            return {f,sm};
        }
        double minimalExecTime(TreeNode* root) {
            return dfs(root).first;
        }
    };

[O_nlogm]: https://private.codecogs.com/gif.latex?O%28nlogm%29
[image.png]: /images/20230521/4abb5fb67763455ca63e781402f7fcbe.png
[image.png 1]: /images/20230521/b6e780efa9d74bec81a75265de28b013.png
[image.png 2]: /images/20230521/fd93312422b84296be164da2c7ada445.png
[zqy1018]: https://leetcode-cn.com/problems/er-cha-shu-ren-wu-diao-du/solution/c-shu-xing-dp-by-zqy1018/