欢迎大家加QQ群：623375442，可以方便群里面交流。这周可以称之为脑经急转弯周。
100456. Construct the Minimum Bitwise Array II
给你一个长度为 n 的质数数组 nums 。你的任务是返回一个长度为 n 的数组 ans ，对于每个下标 i ，以下 条件 均成立：
- ans[i] OR (ans[i] + 1) == nums[i]
除此以外，你需要 最小化 结果数组里每一个 ans[i] 。
如果没法找到符合 条件 的 ans[i] ，那么 ans[i] = -1 。
质数 指的是一个大于 1 的自然数，且它只有 1 和自己两个因数。
测试样例：
输入：nums = [2,3,5,7]
输出：[-1,1,4,1]
解释：
- 对于 i = 0 ，不存在 ans[0] 满足 ans[0] OR (ans[0] + 1) = 2 ，所以 ans[0] = -1 。
- 对于 i = 1 ，满足 ans[1] OR (ans[1] + 1) = 3 的最小 ans[1] 为 1 ，因为 1 OR (1 + 1) = 3 。
- 对于 i = 2 ，满足 ans[2] OR (ans[2] + 1) = 5 的最小 ans[2] 为 4 ，因为 4 OR (4 + 1) = 5 。
- 对于 i = 3 ，满足 ans[3] OR (ans[3] + 1) = 7 的最小 ans[3] 为 3 ，因为 3 OR (3 + 1) = 7 。
解答：第一题和第二题一样，就放个第二题的题解。这题需要一点耐心找找规律。寻找到第一个非1的位数，然后进行操作。
class Solution {
public int[] minBitwiseArray(List<Integer> nums) {
int pos = 0;
int[] res = new int[nums.size()];
for (int n : nums) {
if (n == 2) {
res[pos] = -1;
} else {
int mark = lastOne(n);
if (mark == 1) {
res[pos] = n - 1;
} else {
for (int i = 0; i < 31; ++i) {
if (i < mark - 1) {
res[pos] += (1 << i);
} else if (i == mark - 1) {
continue;
} else {
res[pos] += n & (1 << i);
}
}
}
}
++pos;
}
return res;
}
private int lastOne(int num) {
for (int i = 0; i < 31; ++i) {
int o = (num >> i) & 1;
if (o == 0) {
return i;
}
}
return -1;
}
}100355. Find Maximum Removals From Source String
给你一个长度为 n 的字符串 source ，一个字符串 pattern 且它是 source 的 子序列 ，和一个 有序 整数数组 targetIndices ，整数数组中的元素是 [0, n - 1] 中 互不相同 的数字。
定义一次 操作 为删除 source 中下标在 idx 的一个字符，且需要满足：
- idx 是 targetIndices 中的一个元素。
- 删除字符后，pattern 仍然是 source 的一个 子序列 。
执行操作后 不会 改变字符在 source 中的下标位置。比方说，如果从 "acb" 中删除 'c' ，下标为 2 的字符仍然是 'b' 。
请你返回 最多 可以进行多少次删除操作。
子序列指的是在原字符串里删除若干个（也可以不删除）字符后，不改变顺序地连接剩余字符得到的字符串。
返回 result 。
测试样例：
输入：source = "abbaa", pattern = "aba", targetIndices = [0,1,2]
输出：1
解释：
不能删除 source[0] ，但我们可以执行以下两个操作之一：
- 删除 source[1] ，source 变为 "a_baa" 。
- 删除 source[2] ，source 变为 "ab_aa" 。
解答：动态规划。如果source.charAt(s1) == pattern.charAt(s2)，那么dp[s1][s2] = Math.max(dp[s1 + 1][s2] + 1, dp[s1 + 1][s2 + 1])。否则dp[s1][s2] = dp[s1 + 1][s2] + 1。然后要考虑一下无法匹配上的特殊情况。
class Solution {
private class InternalData {
String source, pattern;
boolean[] targets;
int[] rightCount;
Integer[][] dp;
public InternalData(String source, String pattern, int[] targetIndices) {
this.source = source;
this.pattern = pattern;
targets = new boolean[source.length()];
rightCount = new int[source.length() + 1];
for (int n : targetIndices) {
targets[n] = true;
}
for (int i = source.length() - 1; i >= 0; --i) {
rightCount[i] = rightCount[i + 1];
if (targets[i]) {
rightCount[i] += 1;
}
}
dp = new Integer[source.length()][pattern.length()];
}
}
public int maxRemovals(String source, String pattern, int[] targetIndices) {
InternalData data = new InternalData(source, pattern, targetIndices);
return Math.max(helper(data, 0, 0), 0);
}
private int helper(InternalData data, int s1, int s2) {
if (s2 >= data.pattern.length()) {
return data.rightCount[s1];
} else if (s1 >= data.source.length()) {
return -1;
} else if (data.dp[s1][s2] == null) {
int l1 = helper(data, s1 + 1, s2);
if (l1 > -1 && data.targets[s1]) {
++l1;
}
if (data.source.charAt(s1) == data.pattern.charAt(s2)) {
int l2 = helper(data, s1 + 1, s2 + 1);
l1 = Math.max(l1, l2);
}
data.dp[s1][s2] = l1;
}
return data.dp[s1][s2];
}
}100450. Find the Number of Possible Ways for an Event
给你三个整数 n ，x 和 y 。
一个活动总共有 n 位表演者。每一位表演者会 被安排 到 x 个节目之一，有可能有节目 没有 任何表演者。
所有节目都安排完毕后，评委会给每一个 有表演者的 节目打分，分数是一个 [1, y] 之间的整数。
请你返回 总 的活动方案数。
答案可能很大，请你将它对 10^9 + 7 取余 后返回。
注意 ，如果两个活动满足以下条件 之一 ，那么它们被视为 不同 的活动：
- 存在 一个表演者在不同的节目中表演。
- 存在 一个节目的分数不同。
测试样例：
输入：n = 1, x = 2, y = 3
输出：6
解释：
- 表演者可以在节目 1 或者节目 2 中表演。
- 评委可以给这唯一一个有表演者的节目打分 1 ，2 或者 3 。
解答：概率统计题目。具体背景知识可以看：“n个球放到m个盒子”问题整理(Twelvefold way)
class Solution {
private static final int mod = 1_000_000_007;
public int numberOfWays(int n, int x, int y) {
long[] stages = new long[x + 1];
long[] scores = new long[x + 1];
stages[0] = 1;
scores[0] = 1;
for (int i = 1; i <= x; ++i) {
stages[i] = (stages[i - 1] * (x - i + 1)) % mod;
scores[i] = (scores[i - 1] * y) % mod;
}
long[][] dp = new long[n + 1][Math.min(x + 1, n + 1)];
dp[1][1] = 1;
long res = 0;
for (int i = 1; i <= Math.min(x, n); ++i) {
long pos = dfsDP(dp, n, i);
pos *= stages[i];
pos %= mod;
pos *= scores[i];
pos %= mod;
res = (res + pos) % mod;
}
return (int) res;
}
private long dfsDP(long[][] dp, int rp, int rs) {
if (rp == 0 || rs == 0 || rp < rs) {
return 0;
} else if (dp[rp][rs] == 0) {
dp[rp][rs] = rs * dfsDP(dp, rp - 1, rs) + dfsDP(dp, rp - 1, rs - 1);
dp[rp][rs] %= mod;
}
return dp[rp][rs];
}
}