2020 力扣杯!Code Your Future 春季全国编程大赛 个人赛

五题做了四题,第四题原以为会超时,最后抱着尝试一下的心态,居然就过了。

稍微看了一下排名,从98名开始,都是只做了四题的参赛选手,看来解题时间还是很关键。

记录一下参赛。

以下题目均来自leetcode网站:https://leetcode-cn.com/

1. 拿硬币

https://leetcode-cn.com/contest/season/2020-spring/problems/na-ying-bi/

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

示例 1:

输入:[4,2,1]

输出:4

解释:第一堆力扣币最少需要拿 2 次,第二堆最少需要拿 1 次,第三堆最少需要拿 1 次,总共 4 次即可拿完。

示例 2:

输入:[2,3,10]

输出:8

限制:

  • 1 <= n <= 4
  • 1 <= coins[i] <= 10

没啥好说的,签到题,每一堆单独计算。

    public int minCount(int[] coins) {
        int sum = 0;
        for(int i = 0; i < coins.length; i++){
            sum += (coins[i] + 1) / 2;
        }
        return sum;
    }

2. 传递信息

https://leetcode-cn.com/contest/season/2020-spring/problems/chuan-di-xin-xi/

小朋友 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]

动态规划:用一个DP数组记录,dp[i][j]记录第i轮,传到第j个小朋友的方案。

状态转移方程 2020 力扣杯!Code Your Future 春季全国编程大赛 个人赛

 

 

其中path[k][j]表示编号为k的小朋友到编号为j的小朋友是否有直接传递路径,若有,则path[k][j] = 1,若没有则path[k][j] = 1。

public int numWays(int n, int[][] relation, int k) {
    int ans = 0;
    int[][] dp = new int[k+1][n];
    dp[0][0] = 1;
    for(int i = 1; i <= k; i++){
        for(int j = 0; j < n; j++){
            for(int p = 0; p < relation.length; p++){
                if(relation[p][1] == j){
                    dp[i][j] += dp[i-1][relation[p][0]];
                }
            }
        }
    }
    return dp[k][n-1];
}

3. 剧情触发时间

https://leetcode-cn.com/contest/season/2020-spring/problems/ju-qing-hong-fa-shi-jian/

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

这题写的不好,代码方面看上去太冗余不美观,可读性很差。

具体思路就是,将所有requirements以(下标,需求量)的形式定义成一个类,后来觉得不定义也行,用三个二维数组int[requirements.length][2]就可以搞定。然后分别按照三个资源的顺序,从小到大排列。

用一个map记录requirements满足某一资源要求的时间(这里好像用数组也行,因为长度固定,没必要散列),用一个times数组记录requirements满足资源的次数。

若某一requirements满足了三种资源要求,即times[i] == 3,则map中记录的,满足三种资源中,最后满足的那项资源的时间,就是整个requirements的满足时间。

public class Requirements{

    int index;
    int[] requirements;

    public Requirements(int index, int[]requirements){
        this.index = index;
        this.requirements = requirements;
    }

}

public int[] getTriggerTime(int[][] increase, int[][] requirements) {
    int[] ans = new int[requirements.length];
    Arrays.fill(ans,-1);
    Requirements[] requirements1 = new Requirements[requirements.length];
    Requirements[] requirements2 = new Requirements[requirements.length];
    Requirements[] requirements3 = new Requirements[requirements.length];
    HashMap<Integer,Integer> hashmap = new HashMap<>();
    int[] times = new int[requirements.length];

    for (int i = 0; i < requirements.length; i++) {
        if (requirements[i][0] == 0 && requirements[i][1] == 0 && requirements[i][2] == 0){
            ans[i] = 0;
        }
        requirements1[i] = new Requirements(i,requirements[i]);
        requirements2[i] = new Requirements(i,requirements[i]);
        requirements3[i] = new Requirements(i,requirements[i]);
    }
    Arrays.sort(requirements1, new Comparator<Requirements>() {
        @Override
        public int compare(Requirements o1, Requirements o2) {
            return o1.requirements[0] - o2.requirements[0];
        }
    });
    Arrays.sort(requirements2, new Comparator<Requirements>() {
        @Override
        public int compare(Requirements o1, Requirements o2) {
            return o1.requirements[1] - o2.requirements[1];
        }
    });
    Arrays.sort(requirements3, new Comparator<Requirements>() {
        @Override
        public int compare(Requirements o1, Requirements o2) {
            return o1.requirements[2] - o2.requirements[2];
        }
    });

    int C = 0, R = 0, H = 0;
    int in1 = 0;
    int in2 = 0;
    int in3 = 0;
    for (int i = 0; i < increase.length; i++) {
        C += increase[i][0];
        R += increase[i][1];
        H += increase[i][2];
        while (in1 < requirements.length && C >= requirements1[in1].requirements[0]){
            times[requirements1[in1].index]++;
            hashmap.put(requirements1[in1].index,i+1);
            in1++;
        }
        while (in2 < requirements.length && R >= requirements2[in2].requirements[1]){
            times[requirements2[in2].index]++;
            hashmap.put(requirements2[in2].index,i+1);
            in2++;
        }
        while (in3 < requirements.length && H >= requirements3[in3].requirements[2]){
            times[requirements3[in3].index]++;
            hashmap.put(requirements3[in3].index,i+1);
            in3++;
        }
    }
    for (int i = 0; i < requirements.length; i++) {
        if (times[i] == 3 && ans[i] == -1){
            ans[i] = hashmap.get(i);
        }
    }
    return ans;
}

4. 最小跳跃次数

https://leetcode-cn.com/contest/season/2020-spring/problems/zui-xiao-tiao-yue-ci-shu/

为了给刷题的同学一些奖励,力扣团队引入了一个弹簧游戏机。游戏机由 N 个特殊弹簧排成一排,编号为 0N-1。初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹簧处,通过按动弹簧,可以选择把小球向右弹射 jump[i] 的距离,或者向左弹射到任意左侧弹簧的位置。也就是说,在编号为 i 弹簧处按动弹簧,小球可以弹向 0i-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,做着做着,居然做了一个多小时,后面又想是不是跟单调栈有关。

最后时间快到了,才用一种O(n^2)的代码提交了上去,居然通过了,我估计有两种可能,一种是我的代码其实不是O(n^2),但是我以为是O(n^2),因为这题最后我也没想的特别清楚。

还有一种可能就是O(n^2)可以通过,但看到 1 <= jump.length <= 10^6 感觉也不太可能。

我大致的思路是,先按只能向右移动。求出每个位置的移动次数。

int[] dp = new int[jump.length];
for(int i = jump.length - 1; i >= 0; i--){
    if (i+jump[i] >= jump.length){
        dp[i] = 1;
    }
    else {
        dp[i] = dp[i+jump[i]] + 1;
    }
}

再用一个min数组记录,min[i]表示从下标0到下标i(包括i)的最小值。

int[] min = new int[jump.length];
min[0] = dp[0];
for (int i = 1; i < jump.length; i++) {
    min[i] = Math.min(min[i-1],dp[i]);
}

最后,从后往前更新,通过判断,得出最终的最小值。

这个while语句是最后加上去的,因为之前一直以为这样会超时。。。。。

for (int i = jump.length - 1; i >= 0; i--) {
    if (i+jump[i] >= jump.length){
        dp[i] = 1;
    }
    else {
        dp[i] = Math.min(Math.min(dp[i],min[i] + 1),dp[i+jump[i]] + 1);
        int k = i + 1;
        while (k < jump.length && dp[k] > dp[i]){
            dp[k] = dp[i] + 1;
            k++;
        }
    }
}

因为在做的过程中,发现并不能再从后往前的第一次计算中,就确定当前位置跳出界的最小移动次数。原因就在于:



dp[i] = Math.min(Math.min(dp[i],min[i] + 1),dp[i+jump[i]] + 1);

这句代码中,min[i]并不是真正的min[i],假设min[i]取得的值是下标x的值,若在后续更新时,有j<i且dp[j]<min[i],那么先前求出来的dp[i]就是错误的。

这边举一个例子。

int[] jump = new int[]{2, 6, 1, 1, 1, 1, 4, 1, 1, 1};

当输入数组为{2, 6, 1, 1, 1, 1, 4, 1, 1, 1}的时候,正确的走法应该是,从下标0->2->1->7->6->结束。总共要跳5次。

而如果按我最先的想法。

求出来的dp数组为:

6 3 5 4 3 2 1 2 2 1

可以看到答案错了,其根本原因就在于,dp[2]在更新的时候,此时dp[1]还没有更新,所以dp[2]更新后的值,不是最终的值,所以是错误的。那么dp[0]自然也就跟着错了。

为了解决这个问题,加上了while判断,在当前dp[i]变小后,要往后搜索,更新之前求出来的dp[i]。

也许这种方法看似两层循环但并非O(n^2),因为while里可能执行的是一种双指针的操作,就是假设最开始j=length-1是最右边界。每一次进行while从i到j向后搜索并更新,更新后j移动到i的位置,下一次while循环,就只遍历到之前的位置。这样实际上就只遍历了一次。参赛结束后我试图去证明这一点,如果能证明这一点那就能说明该方法是O(n)的时间复杂度,奈何还是太菜。等Leetcode上出了题解再去学习学习吧。

 

完整通过代码:

public int minJump(int[] jump) {
    int[] dp = new int[jump.length];
    for(int i = jump.length - 1; i >= 0; i--){
        if (i+jump[i] >= jump.length){
            dp[i] = 1;
        }
        else {
            dp[i] = dp[i+jump[i]] + 1;
        }
    }
    int[] min = new int[jump.length];
    min[0] = dp[0];
    for (int i = 1; i < jump.length; i++) {
        min[i] = Math.min(min[i-1],dp[i]);
    }
    for (int i = jump.length - 1; i >= 0; i--) {
        if (i+jump[i] >= jump.length){
            dp[i] = 1;
        }
        else {
            dp[i] = Math.min(Math.min(dp[i],min[i] + 1),dp[i+jump[i]] + 1);
            int k = i + 1;
            while (k < jump.length && dp[k] > dp[i]){
                dp[k] = dp[i] + 1;
                k++;
            }
        }
    }if (jump[0] >= jump.length){
        return 1;
    }
    else {
        return dp[0];
    }
}

5. 二叉树任务调度

最后没时间了,看了一下,也没啥想法。

https://leetcode-cn.com/contest/season/2020-spring/problems/er-cha-shu-ren-wu-diao-du/

 

上一篇:1306. Jump Game III


下一篇:LC 1340. Jump Game V