第414 场周赛

第414 场周赛

A：✅ B：✅ C：✅ T4：❌

A. 将日期转换为二进制表示

思路：直接模拟。

public class A {
    // https://leetcode.cn/contest/weekly-contest-414/problems/convert-date-to-binary/

    public String convertDateToBinary(String date) {
        String[] split = date.split("-");
        StringBuilder ans = new StringBuilder();
        for (String s : split) {
            ans.append(Integer.toBinaryString(Integer.parseInt(s))).append("-");
        }
        ans.deleteCharAt(ans.length() - 1);
        return ans.toString();
    }
}

B. 范围内整数的最大得分

算法标签：二分答案、贪心。

思路：对于一个得分score，如果它能够作为可能的一个得分，那么score - 1、score - 2 都可以。具有单调性，可以二分。check函数的逻辑主要判断mid 能否作为一个可能的得分，第一个区间要选择start[0]，后面的区间选越大的越好。

public class B {

    // https://leetcode.cn/contest/weekly-contest-414/problems/maximize-score-of-numbers-in-ranges/
    // 二分答案
    public int maxPossibleScore(int[] start, int d) {
        Arrays.sort(start);
        long l = 0;
        long r = (long) (1e18 + 1);

        while (l < r) {
            long mid = (l + r + 1) >> 1;
            if (check(start, d, mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return (int) l;
    }

    boolean check(int[] start, int d, long mid) {
        // 0, 3, 6
        // [0, 2], [3, 5], [6, 8]
        long prev = start[0];
        for (int i = 1; i < start.length; i++) {
            long cur = Math.max(start[i], prev + mid);
            if (cur > start[i] + d) {
                return false;
            }
            prev = cur;
        }
        return true;
    }
}

C. 到达数组末尾的最大得分

算法标签：动态规划、单调栈。

思路：暴力枚举复杂度为O(N^2)，肯定过不了。使用单调栈倒着dp，一边维护单调栈的元素，一边计算dp值，最后答案为dp[0]，复杂度为O(N)。

public class C {

    // https://leetcode.cn/contest/weekly-contest-414/problems/reach-end-of-array-with-max-score/
    // 单调栈优化dp
    public static long findMaximumScore(List<Integer> nums) {
        int n = nums.size();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = nums.get(i);
        Deque<Integer> stk = new ArrayDeque<>();
        long[] dp = new long[n];
        for (int i = n - 1; i >= 0; i--) {
            while (stk.size() > 1 && a[stk.peek()] < a[i]) {
                stk.pop();
            }
            if (stk.isEmpty()) {
                dp[i] = 0;
            } else {
                dp[i] = dp[stk.peek()] + (long) (stk.peek() - i) * a[i];
            }
            stk.push(i);
        }
        return dp[0];
    }
}