Biweekly Contest 127

100250. Minimum Levels to Gain More Points

给你一个长度为 n 的二进制数组 possible 。

莉叩酱和冬坂五百里正在玩一个有 n 个关卡的游戏，游戏中有一些关卡是 困难 模式，其他的关卡是 简单 模式。如果 possible[i] == 0 ，那么第 i 个关卡是 困难 模式。一个玩家通过一个简单模式的关卡可以获得 1 分，通过困难模式的关卡将失去 1 分。

游戏的一开始，莉叩酱将从第 0 级开始 按顺序 完成一些关卡，然后冬坂五百里会完成剩下的所有关卡。

假设两名玩家都采取最优策略，目的是 最大化 自己的得分，莉叩酱想知道自己 最少 需要完成多少个关卡，才能获得比冬坂五百里更多的分数。

请你返回莉叩酱获得比冬坂五百里更多的分数所需要完成的 最少 关卡数目，如果 无法 达成，那么返回 -1 。

注意，每个玩家都至少需要完成 1 个关卡。

测试样例：

输入：possible = [1,0,1,0]

输出：1

解释：我们来看一下莉叩酱可以完成的关卡数目：

• 如果莉叩酱只完成关卡 0 ，冬坂五百里完成剩下的所有关卡，那么莉叩酱获得 1 分，冬坂五百里获得 -1 + 1 - 1 = -1 分。
• 如果莉叩酱完成到关卡 1 ，冬坂五百里完成剩下的所有关卡，那么莉叩酱获得 1 - 1 = 0 分，冬坂五百里获得 1 - 1 = 0 分。
• 如果莉叩酱完成到关卡 2 ，冬坂五百里完成剩下的所有关卡，那么莉叩酱获得 1 - 1 + 1 = 1 分，冬坂五百里获得 -1 分。

莉叩酱需要完成至少一个关卡获得更多的分数。

解答：根据题意计算后缀和，然后正向遍历，找到第一个满足条件的位置。

class Solution {
    public int minimumLevels(int[] possible) {
        int len = possible.length;
        int[] right = new int[len];
        for (int i = len - 1; i >= 0; --i) {
            right[i] += possible[i] == 0 ? -1 : 1;
            if (i + 1 < len) {
                right[i] += right[i + 1];
            }
        }
        int left = 0;
        for (int i = 0; i + 1 < len; ++i) {
            left += possible[i] == 0 ? -1 : 1;
            if (left > right[i + 1]) {
                return i + 1;
            }
        }
        return -1;
    }
}

100271. Shortest Subarray With OR at Least K II

给你一个 非负 整数数组 nums 和一个整数 k 。

如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ，那么我们称这个数组是 特别的 。

请你返回 nums 中 最短特别非空 子数组的长度，如果特别子数组不存在，那么返回 -1 。

测试样例：

输入：nums = [1,2,3], k = 2

输出：1

解释：子数组 [3] 的按位 OR 值为 3 ，所以我们返回 1 。

解答：利用双指针可以方便的计算出最短的子数组。

class Solution {
    public int minimumSubarrayLength(int[] nums, int k) {
        int res = Integer.MAX_VALUE;
        int st = 0, ed = 0;
        int[] count = new int[31];
        while (ed < nums.length) {
            for (int i = 0; i < 31; ++i) {
                if (isMark(nums[ed], i)) {
                    count[i] += 1;
                }
            }
            while (st <= ed && curNum(count) >= k) {
                res = Math.min(ed - st + 1, res);
                for (int i = 0; i < 31; ++i) {
                    if (isMark(nums[st], i)) {
                        count[i] -= 1;
                    }
                }
                ++st;
            }
            ++ed;
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    private boolean isMark(int num, int offset) {
        int t = (num >> offset) & 1;
        return t == 1;
    }

    private int curNum(int[] count) {
        int res = 0;
        for (int i = 0; i < 31; ++i) {
            if (count[i] > 0) {
                res += (1 << i);
            }
        }
        return res;
    }
}

100218. Find the Sum of Subsequence Powers

给你一个长度为 n 的整数数组 nums 和一个 正 整数 k 。

一个子序列的 能量 定义为子序列中 任意 两个元素的差值绝对值的 最小值 。

请你返回 nums 中长度 等于 k 的 所有 子序列的 能量和 。

由于答案可能会很大，将答案对 10^9 + 7 取余 后返回。

测试样例：

输入：nums = [1,2,3,4], k = 3

输出：4

解释：nums 中总共有 4 个长度为 3 的子序列：[1,2,3] ，[1,3,4] ，[1,2,4] 和 [2,3,4] 。能量和为 |2 - 3| + |3 - 4| + |2 - 1| + |3 - 4| = 4 。

解答：这道题目，有一个好处，2 <= n == nums.length <= 50。范围非常小，直觉说可以暴力。所以我就直接排序，然后寻找到所有diff的可能性。然后做一个动态规划的数组，记录从当前index开始，所有diff和k组合的可能性。

class Solution {
    private static final int mod = 1_000_000_007;

    public int sumOfPowers(int[] nums, int k) {
        Arrays.sort(nums);
        int len = nums.length;
        Map<Integer, Integer> posMap = getAllPossible(nums);
        List<Map.Entry<Integer, Integer>> posList = new ArrayList<>(posMap.entrySet());
        Integer[][][] dp = new Integer[len][posMap.size()][k + 1];
        for (int i = 0; i < len; ++i) {
            for (int j = 0; j < i; ++j) {
                int curDiff = nums[i] - nums[j];
                int diffPos = posMap.get(curDiff);
                for (int t = 2; t <= k; ++t) {
                    if (t == 2) {
                        int oldVal = dp[i][diffPos][2] == null ? 0 : dp[i][diffPos][2];
                        dp[i][diffPos][2] = (oldVal + 1) % mod;
                    } else {
                        for (Map.Entry<Integer, Integer> posEntry : posList) {
                            if (dp[j][posEntry.getValue()][t - 1] != null) {
                                int oldVal = dp[i][Math.min(posEntry.getValue(), diffPos)][t] == null ? 0 : dp[i][Math.min(posEntry.getValue(), diffPos)][t];
                                dp[i][Math.min(posEntry.getValue(), diffPos)][t] = (dp[j][posEntry.getValue()][t - 1] + oldVal) % mod;
                            }
                        }
                    }
                }
            }
        }

        int res = 0;
        for (int i = 0; i < len; ++i) {
            for (Map.Entry<Integer, Integer> posEntry : posList) {
                if (dp[i][posEntry.getValue()][k] != null) {
                    long tmp = posEntry.getKey();
                    tmp *= dp[i][posEntry.getValue()][k];
                    tmp %= mod;
                    res = (int) ((res + tmp) % mod);
                }
            }
        }
        return res;
    }

    private Map<Integer, Integer> getAllPossible(int[] nums) {
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < nums.length; ++i) {
            for (int j = i + 1; j < nums.length; ++j) {
                set.add(nums[j] - nums[i]);
            }
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        int c = 0;
        for (int n : set) {
            map.put(n, c++);
        }
        return map;
    }
}