力扣杯春季个人赛-剧情触发时间

这次的个人赛真是让我认清了自己的实力。。两道困难题都没做出?,虽然大家的通过率也不咋地。。

力扣杯春季个人赛-剧情触发时间

最后排名

力扣杯春季个人赛-剧情触发时间

我记录一道做出来的题吧,这道题是一道中等题,通过率如下,虽然题目不难,但由于时间限制的问题,不使用技巧很容易超出时间限制

力扣杯春季个人赛-剧情触发时间

原题

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

解法

思想

见代码部分

代码

我一开始想的是用requirement里面的三元组每隔一天减去increase里面对应的三元组,然后记录答案,但是这种方法无论怎么剪枝优化都会超时,这样做的时间复杂度是O(mn)(m,n为两个数组的大小,我还省去了后面数组赋值的时间复杂度):

class Solution {
    public int[] getTriggerTime(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;
    }
}

后来想到可以计算每一天的属性值,然后二分查找,这样做的时间复杂度就是O(m+nlogm)

class Solution {
    public int[] getTriggerTime(int[][] increase, int[][] requirements) {
        int day = 0;
        int[] ans = new int[requirements.length];
        //将increase中的三元组的含义变为每一天的属性值
        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(requirements[i][0]==0&&requirements[i][1]==0&&requirements[i][2]==0) ans[i] = 0;
            else{
                int left = 0;
                int right = increase.length-1;
                //如果最后一天仍不满足,设为-1
                if(!(increase[right][0]>=requirements[i][0]&&increase[right][1]>=requirements[i][1]&&increase[right][2]>=requirements[i][2])){
                    ans[i] = -1;
                    continue;
                }
                //二分查找
                while(left <right){
                    int mid = (left+right)/2;
                    if(!(increase[mid][0]>=requirements[i][0]&&increase[mid][1]>=requirements[i][1]&&increase[mid][2]>=requirements[i][2])){
                        left = mid+1;
                    }else{
                        right = mid;
                    }
                }
                ans[i] = left+1;
            }
        }
        return ans;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e5%8a%9b%e6%89%a3%e6%9d%af%e6%98%a5%e5%ad%a3%e4%b8%aa%e4%ba%ba%e8%b5%9b-%e5%89%a7%e6%83%85%e8%a7%a6%e5%8f%91%e6%97%b6%e9%97%b4/

发表回复

登录后才能评论