LeetCode杯 2020 春季个人赛 题解

自动前几天笔试阿里之后，我痛定思痛！为啥总共两个题目，你就整出来一个，而且Case通过率0.00%？ 这不是完败吗！
所以我开始我的刷题 目标是好多好多题目，LeetCode还有剑指Offer，加油。
现在开始整理 LeetCode杯 2020 春季个人赛

第1题来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/na-ying-bi/

第2题来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/chuan-di-xin-xi

第3题来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ju-qing-hong-fa-shi-jian/

第4题来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zui-xiao-tiao-yue-ci-shu/

第5题来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-shu-ren-wu-diao-du/

第1题：拿硬币

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

示例 1：

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

示例 2：

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

限制：
  • 1 <= n <= 4
  • 1 <= coins[i] <= 10
题目分析

1.保存在数组之中，可以拿任意一堆，然后每次1-2个硬币。那就是先按照多的拿？剩下的1就一次，如果只有只就拿一次
2.伪代码 如下

  1. 在数组外定义总共的次数 count = 0 循环遍历数组，取出每个位置的值
    1.1 把取出的值 取模 2 if(coins[i]%2==0) 就是偶数，需要拿 count += coins[i] / 2
    1.2 如果是 if(coins[i]%2==1) 就是奇数，需要拿 count += coins[i] / 2 +1 因为 Java中去整数会向下取整，所以需要多加一个1
  2. 返回结果 count

3.代码实现 minCount2 是装x写法，本质一样

public class _2020_04_18_01_TakeCoins {
    public static void main(String[] args) {
        int[] num = {4, 2, 1};
        int result = minCount2(num);
        System.out.println(result);
    }

    public static int minCount2(int[] coins) {
        int resultCounts = 0;
        for (int i = 0; i < coins.length; i++) {
            resultCounts += (coins[i] % 2 == 0) ? (coins[i] / 2) : (coins[i] / 2 + 1);
        }
        return resultCounts;
    }


    public static int minCount(int[] coins) {
        if (coins == null || coins.length < 1 || coins.length > 4) {
            throw new RuntimeException("参数不合法");
        }
        int resultCounts = 0;
        for (int i = 0; i < coins.length; i++) {
            if (coins[i] < 1 || coins[i] > 10) {
                throw new RuntimeException("参数不合法");
            }
            if (coins[i] % 2 == 0) {
                //如果等于0 就是偶数 就需要拿偶数次
                resultCounts += coins[i] / 2;
            } else {
                //是奇数
                resultCounts += coins[i] / 2 + 1;
            }
        }
        return resultCounts;
    }
}
第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]
题目分析

我当时在做这个题目的时候，真的是毫无头绪，感觉像是图，然后又在纸上画树，图的遍历，不会了，阿里的笔试也是死于图的遍历。 这题就是DFS算法，话不多说，
直接上代码了，我也解释不清楚。

代码实现

public class _2020_04_18_02_TransmitInformation {

    public static void main(String[] args) {
        int n = 5, k = 3;
        int[][] relation = {{0, 2}, {2, 1}, {3, 4}, {2, 3}, {1, 4}, {2, 0}, {0, 4}};
        int result = numWays(n, relation, k);
        System.out.println(result);
    }

    public static int numWays(int n, int[][] relation, int k) {
        return dfs(n, relation, k, n - 1);
    }

    public static int dfs(int n, int[][] relation, int k, int tail) {
        if (k == 1) {
            int count = 0;
            for (int i = 0; i < relation.length; i++) {
                if (relation[i][1] == tail && relation[i][0] == 0) {
                    count++;
                }
            }
            return count;
        }
        int count = 0;
        for (int i = 0; i < relation.length; i++) {
            int time = 0;
            if (relation[i][1] == tail) {
                time += dfs(n, relation, k - 1, relation[i][0]);
            }
            count += time;
        }
        return count;
    }
}
第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
题目分析

这个题目我当时看的第一眼就是想到，把要求计算出来，然后一个一个去减法，求出值，但是有一个地方一直做不做来，就是控制指定天数是指定的方案。然后评论区的大哥们有的是使用二分法，我糊涂了，没明白。

代码演示

public class _2020_04_18_03_PlotTriggerTime {

    public static void main(String[] args) {
        int[][] increase = {{2, 8, 4}, {2, 5, 0}, {10, 9, 8}};
        int[][] requirements = {{2, 11, 3}, {15, 10, 7}, {9, 17, 12}, {8, 1, 14}};
        int[] triggerTime = getTriggerTime2(increase, requirements);
        for (int trig : triggerTime) {
            System.out.print(trig + " ");
        }
    }

    public static int[] getTriggerTime(int[][] increase, int[][] requirements) {
        int[] result = new int[requirements.length];
        Arrays.fill(result, -1);
        for (int i = 1; i < increase.length; i++) {
            increase[i][0] += increase[i - 1][0];
            increase[i][1] += increase[i - 1][1];
            increase[i][2] += increase[i - 1][2];
        }
        for (int i = 0; i < requirements.length; i++) {
            if (isEqual(requirements[i], new int[]{0, 0, 0})) {
                result[i] = 0;
            }
        }

        for (int i = 0; i < requirements.length; i++) {
            if (result[i] != -1) {
                continue;
            }
            int left = 0;
            int right = increase.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (isDay(increase[mid], requirements[i])) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
                if (left >= 0 && left < increase.length && isDay(increase[left], requirements[i])) {
                    result[i] = left + 1;
                }
            }
        }
        return result;
    }

    public static boolean isDay(int[] incr, int req[]) {
        return incr[0] >= req[0] && incr[1] >= req[1] && incr[2] >= req[2];
    }

    public static boolean isEqual(int[] incr, int[] req) {
        return incr[0] == req[0] && incr[1] == req[1] && incr[2] == req[2];
    }


    public static int[] getTriggerTime2(int[][] increase, int[][] requirements) {
        Integer[] ans = new Integer[requirements.length];
        for (int day = 0; day <= increase.length; day++) {
            boolean hasRemain = false;
            for (int i = 0; i < requirements.length; i++) {
                if (day == 0) {
                    if (requirements[i][0] == 0 && requirements[i][1] == 0 && requirements[i][2] == 0) {
                        ans[i] = 0;
                    } else {
                        continue;
                    }
                }
                if (ans[i] != null) {
                    continue;
                }
                hasRemain = true;
                requirements[i][0] -= increase[day - 1][0];
                requirements[i][1] -= increase[day - 1][1];
                requirements[i][2] -= increase[day - 1][2];
                if (requirements[i][0] <= 0 && requirements[i][1] <= 0 && requirements[i][2] <= 0) {
                    ans[i] = day;
                }
            }
            if (day != 0 && !hasRemain) {
                break;
            }
        }
        int[] realAns = new int[requirements.length];
        for (int i = 0; i < ans.length; i++) {
            if (ans[i] == null) {
                realAns[i] = -1;
            } else {
                realAns[i] = ans[i];
            }
        }
        return realAns;
    }
}
PS:关于二分查找法 给个 不错的文章 https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/er-fen-cha-zhao-xiang-jie
第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
题目分析

这个是个动态规划题目，我又不会了，来看大佬的解答
从右向左计算dp值(从后向前)，当前位置如果为i 则它如果直接跳到右边（前面）去就是dp[jump[i]+i]+1（这个值已经计算过了），计算出当前位置dp[i]之后，当前位置i可以影响 i+1到dp[j] >= dp[i]+1位置上的值（因为某个位置可以跳到左边任意位置）注意遍历到dp[j]>=dp[i]+1即可。

作者：dongyangliu
链接：https://leetcode-cn.com/problems/zui-xiao-tiao-yue-ci-shu/solution/jian-dan-yi-dong-de-dong-tai-gui-hua-wan-fa-by-don/
来源：力扣（LeetCode）

代码演示

public class _2020_04_18_04_MinimumNumberOfJumps {
    public static void main(String[] args) {
        int[] jump = {2, 5, 1, 1, 1, 1};
        System.out.println(minJump(jump));
    }

    public static int minJump(int[] jump) {
        //dp[]数组 每一位 代表该位到跳出的最少次数
        int[] dp = new int[jump.length];
        dp[jump.length - 1] = 1;
        for (int i = jump.length - 2; i >= 0; i--) {
            //遍历当前位置更新后影响到的后面的位置，只需要更新到dp[j] >= dp[i] + 1 即可
            //如果遍历到某dp[j]<dp[i]+1就不需要向右遍历了,因为j到dp.length的值会被当前遍历到的dp[j]更新而不是dp[i]+1
            dp[i] = jump[i] + i >= jump.length ? 1 : dp[jump[i] + i] + 1;
            for (int j = i + 1; j < dp.length && dp[j] >= dp[i] + 1; j++) {
                dp[j] = dp[i] + 1;
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[0];
    }
}
第5题：二叉树任务调度

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

通常任务之间是存在依赖关系的，即对于某个任务，你需要先完成他的前导任务（如果非空），才能开始执行该任务。我们保证任务的依赖关系是一棵二叉树，其中 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
思路分析

我不会我就CV了一份来emmm 大佬真的强
解题思路
任务调度存在依赖关系，任何一个node节点任务，都依赖于node.left和node.right前置节点任务的完成。所以，这是一个很明显的后序遍历思路。

这里很多人应该都会想到递归左右子树，获取左右子树的最小执行时间的较大值+当前节点的时间，得到解。

于是乎，卡在了测试用例3的7.5中。

上面思想类似贪心选择，局部最优，统一起来，不一定是整体最优。因为任务是可以暂时中断的，在这个情况下，我们可以把所有的前置任务看成一个整体来思考，摒弃细节，这样思路会清晰一些。

其他题解也说了大体的思路，就是如果left>right，就要把left多出来的串行时间往right的并行时间里摊，反之亦然。

这里我谈一下自己的理解，也许存在问题，也希望各位大佬可以指正。

首先，假设不存在多个cpu的情况(即只有一个cpu)，要执行完所有的前置任务，那前置任务的总时间肯定是preTime = sum(node.left) + sum(node.right)preTime=sum(node.left)+sum(node.right)。这时，我们将preTime看成一个整体。

那么现在变成双核CPU了。一个整体的preTime开始双核并行了，那么一个整体下的preTime是多少呢？

很显然，是preTime/2

是不是豁然开朗了？在前置任务最为理想的情况下，所有任务都能一直并行，不存在串行时间。这个类似于动态规划的前置条件。至于前置任务再往前的任务，和任务它到底是怎么分配时间的，怎么去分摊时间，我们并不关心，总之，你能在preTime/2的时间内完成，就OK了。如果CPU核心更多，就是preTime/n。

当然，前置任务最优的解preTime/2，是一个理想情况，具体的任务执行，是非常有可能达不到这种情况。比如题目的测试用例1。

所以，每个节点的任务执行时间的最小值，应该是Max(time(node.left),time(node.right),preTime/2) + node.valMax(time(node.left),time(node.right),preTime/2)+node.val。

即左子树执行完成的最小时间、右子树执行完成的最小时间、左右子树全部节点并行执行的时间，三者的最大值，再加上当前节点的任务时间。

最后将最优时间往根节点递推。抵达根节点后的最优解，就是全局的最优解。

作者：burning-summer
链接：https://leetcode-cn.com/problems/er-cha-shu-ren-wu-diao-du/solution/hou-xu-bian-li-di-gui-fan-hui-zuo-you-zi-shu-zui-y/
来源：力扣（LeetCode）

代码实现

public class _2020_04_18_05_BinaryTreeTaskScheduling {

    /**
     * LCP 10. 二叉树任务调度
     *
     * @param root
     * @return
     */
    public double minimalExecTime(TreeNode root) {
        double[] res = execTime(root, 2);
        return res[0];
    }

    /**
     * 获取node最小执行时间
     *
     * @param node node
     * @param n    并行数
     * @return [0]执行完当前节点最小耗时，[1]当前node为根的时间串行之和
     */
    private double[] execTime(TreeNode node, int n) {
        if (node == null) {
            // [0]执行完当前节点最小耗时，[1]当前node为根的时间串行之和
            return new double[]{0.0D, 0.0D};
        }
        // 获取左右子树的值
        double[] leftTime = execTime(node.left, n);
        double[] rightTime = execTime(node.right, n);
        // 左右子树节点之和
        double sum = leftTime[1] + rightTime[1];
        // 当前节点执行完的最小消耗时间
        double minTime = Math.max(Math.max(leftTime[0], rightTime[0]), sum / n) + node.val;
        return new double[]{minTime, sum + node.val};
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}
少年还需要继续努力~
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 215,133评论 6赞 497
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,682评论 3赞 390
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 160,784评论 0赞 350
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,508评论 1赞 288
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,603评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,607评论 1赞 293
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,604评论 3赞 415
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,359评论 0赞 270
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,805评论 1赞 307
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,121评论 2赞 330
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,280评论 1赞 344
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,959评论 5赞 339
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,588评论 3赞 322
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,206评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,442评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,193评论 2赞 367
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,144评论 2赞 352