2021-05-23周赛题解

题目一：哪种连续子字符串更长

方法一：遍历

• 时间复杂度 O(n)
• 空间复杂度 O(1)

public boolean checkZeroOnes(String s) {
    int maxOne = 0, maxZero = 0;
    int idx = 0;
    while (idx<s.length()) {
        if(s.charAt(idx)=='1'){
            int temp = 0;
            while (idx<s.length() && s.charAt(idx) == '1'){
                idx++;
                temp++;
            }
            maxOne = Math.max(maxOne,temp);
        }else {
            int temp = 0;
            while (idx<s.length() && s.charAt(idx) == '0'){
                idx++;
                temp++;
            }
            maxZero = Math.max(maxZero,temp);
        }
    }
    return maxOne>maxZero;
}

题目二：准时到达的列车最小时速

解法一：极小化极大

满足条件的最小正整数：二分法。

trick: 最后一个路径不用ceil，且浮点数最长两位，所以搜索范围：[1, max(max(dist), dist[-1]*100)]

• 时间复杂度 O(nlgk)
• 空间复杂度 O(1)

class Solution(object):
    def minSpeedOnTime(self, dist, hour):
        
        def check(dist,speed,hour):
            maxHour = 0
            for idx in range(len(dist)):
                if(idx!=len(dist)-1):
                    maxHour += math.ceil(dist[idx]/float(speed))
                else:
                    maxHour += dist[idx]/float(speed)
            return maxHour<=hour
        
        l, r = 1, max(max(dist),dist[-1]*100)
        res = r+1
        while l<= r:
            mid = (l+r)>>1;
            if check(dist,mid,hour):
                r = mid-1
                res = mid
            else: l = mid+1
        return -1 if res==max(max(dist),dist[-1]*100)+1 else res

题目三：跳跃游戏 VII

解法一：遍历+queue

题目的可行动范围在滑动出现重复检查，为了不重复进队，使用maxLen来标记当前访问的最长距离，检查起始点：min(maxLen,I+minJump)

• 时间复杂度 O(n)
• 空间复杂度 O(n)

class Solution {
    public boolean canReach(String s, int minJump, int maxJump) {
        if(s.charAt(s.length()-1)=='1') return false;
        Deque<Integer> queue = new LinkedList<>();
        int maxLen = minJump-1;
        queue.addLast(0);

        while (!queue.isEmpty()) {
            int top = queue.pollFirst();
            if(top==s.length()-1) return true;
            int start = Math.max(maxLen+1,top+minJump);
            int end =Math.min(s.length()-1,top+maxJump); 
            for(int idx =start;idx<=end;idx++){
                if(s.charAt(idx)=='0') {
                    queue.addLast(idx);
                }
            }
            maxLen = Math.max(maxLen,end);
        }
        return false;
    }
}

题目四： 石子游戏 VIII

解法一： DP

• 时间复杂度 O(n)
• 空间复杂度 O(n)

class Solution {
    public int stoneGameVIII(int[] stones) {
        int n = stones.length;
        int[] sum = new int[n];
        sum[0] = stones[0];

        for(int i=1;i<n;i++) sum[i] = sum[i-1]+stones[i];

        int[] dp = new int[n];
        dp[n-1] = sum[n-1];
        for(int i=n-2;i>=0;i--) {
            dp[i] = Math.max(dp[i+1],sum[i]-dp[i+1]);
        }
        return dp[1];
    }
}