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;
}
}