欢迎大家加QQ群：623375442，可以方便群里面交流。惊了，最后一题只有6分。感觉这题还挺难的。
100478. Check Balanced String
给你一个仅由数字 0 - 9 组成的字符串 num。如果偶数下标处的数字之和等于奇数下标处的数字之和，则认为该数字字符串是一个 平衡字符串。
如果 num 是一个 平衡字符串，则返回 true；否则，返回 false。
测试样例：
输入： num = "1234"
输出： false
解释：
- 偶数下标处的数字之和为 1 + 3 = 4，奇数下标处的数字之和为 2 + 4 = 6。
- 由于 4 不等于 6，num 不是平衡字符串。
解答：按照题意计算奇偶位数字之和。
class Solution {
public boolean isBalanced(String num) {
int sum = 0;
for (int i = 0; i < num.length(); ++i) {
if (i % 2 == 0) {
sum += num.charAt(i) - '0';
} else {
sum -= num.charAt(i) - '0';
}
}
return sum == 0;
}
}100469. Find Minimum Time to Reach Last Room I
有一个地窖，地窖中有 n x m 个房间，它们呈网格状排布。
给你一个大小为 n x m 的二维数组 moveTime ，其中 moveTime[i][j] 表示在这个时刻 以后 你才可以 开始 往这个房间 移动 。你在时刻 t = 0 时从房间 (0, 0) 出发，每次可以移动到 相邻 的一个房间。在 相邻 房间之间移动需要的时间为 1 秒。
请你返回到达房间 (n - 1, m - 1) 所需要的 最少 时间。
如果两个房间有一条公共边（可以是水平的也可以是竖直的），那么我们称这两个房间是 相邻 的。
测试样例：
输入：moveTime = [[0,4],[4,4]]
输出：6
解释：需要花费的最少时间为 6 秒。
- 在时刻 t == 4 ，从房间 (0, 0) 移动到房间 (1, 0) ，花费 1 秒。
- 在时刻 t == 5 ，从房间 (1, 0) 移动到房间 (1, 1) ，花费 1 秒。
解答：比较典型的BFS。
class Solution {
private static final int[] moves = {1,0,-1,0,1};
public int minTimeToReach(int[][] moveTime) {
int m = moveTime.length, n = moveTime[0].length;
int[][] mem = new int[m][n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
mem[i][j] = Integer.MAX_VALUE;
}
}
mem[0][0] = 0;
TreeSet<int[]> queue = new TreeSet<>(new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
int t = Integer.compare(mem[a[0]][a[1]], mem[b[0]][b[1]]);
if (t != 0) {
return t;
}
for (int i = 0; i < 2; ++i) {
if (a[i] != b[i]) {
return Integer.compare(a[i], b[i]);
}
}
return 0;
}
});
queue.add(new int[]{0, 0, 0});
while (!queue.isEmpty()) {
int[] tmp = queue.pollFirst();
for (int i = 0; i < 4; ++i) {
int xt = tmp[0] + moves[i], yt = tmp[1] + moves[i + 1];
// BFS 记录一下最短时间
if (xt >= 0 && xt < m && yt >= 0 && yt < n && mem[xt][yt] > Math.max(moveTime[xt][yt], mem[tmp[0]][tmp[1]]) + 1) {
int[] key = {xt, yt};
queue.remove(key);
mem[xt][yt] = Math.max(moveTime[xt][yt], mem[tmp[0]][tmp[1]]) + 1;
queue.add(key);
}
}
}
return mem[m - 1][n - 1];
}
}100470. Find Minimum Time to Reach Last Room II
有一个地窖，地窖中有 n x m 个房间，它们呈网格状排布。
给你一个大小为 n x m 的二维数组 moveTime ，其中 moveTime[i][j] 表示在这个时刻 以后 你才可以 开始 往这个房间 移动 。你在时刻 t = 0 时从房间 (0, 0) 出发，每次可以移动到 相邻 的一个房间。在 相邻 房间之间移动需要的时间为：第一次花费 1 秒，第二次花费 2 秒，第三次花费 1 秒，第四次花费 2 秒……如此 往复 。
请你返回到达房间 (n - 1, m - 1) 所需要的 最少 时间。
如果两个房间有一条公共边（可以是水平的也可以是竖直的），那么我们称这两个房间是 相邻 的。
测试样例：
输入：moveTime = [[0,4],[4,4]]
输出：7
解释：需要花费的最少时间为 7 秒。
- 在时刻 t == 4 ，从房间 (0, 0) 移动到房间 (1, 0) ，花费 1 秒。
- 在时刻 t == 5 ，从房间 (1, 0) 移动到房间 (1, 1) ，花费 2 秒。
解答：这题其实和第二题差不多。唯一区别就是移动时间会因为移动次数变化。我这里就用了比较暴力的方法，直接记录了移动的奇偶情况。
class Solution {
private static final int[] moves = {1,0,-1,0,1};
public int minTimeToReach(int[][] moveTime) {
int m = moveTime.length, n = moveTime[0].length;
int[][][] mem = new int[2][m][n];
for (int t = 0; t < 2; ++t) {
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
mem[t][i][j] = Integer.MAX_VALUE;
}
}
}
mem[0][0][0] = 0;
TreeSet<int[]> queue = new TreeSet<>(new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
int t = Integer.compare(mem[a[2]][a[0]][a[1]], mem[b[2]][b[0]][b[1]]);
if (t != 0) {
return t;
}
for (int i = 0; i < 3; ++i) {
if (a[i] != b[i]) {
return Integer.compare(a[i], b[i]);
}
}
return 0;
}
});
queue.add(new int[]{0, 0, 0});
while (!queue.isEmpty()) {
int[] tmp = queue.pollFirst();
int nt = tmp[2] ^ 1;
for (int i = 0; i < 4; ++i) {
int xt = tmp[0] + moves[i], yt = tmp[1] + moves[i + 1];
if (xt >= 0 && xt < m && yt >= 0 && yt < n && mem[nt][xt][yt] > Math.max(moveTime[xt][yt], mem[tmp[2]][tmp[0]][tmp[1]]) + tmp[2] + 1) {
int[] key = {xt, yt, nt};
queue.remove(key);
mem[nt][xt][yt] = Math.max(moveTime[xt][yt], mem[tmp[2]][tmp[0]][tmp[1]]) + tmp[2] + 1;
queue.add(key);
}
}
}
return Math.min(mem[0][m - 1][n - 1], mem[1][m - 1][n - 1]);
}
}100479. Count Number of Balanced Permutations
给你一个字符串 num 。如果一个数字字符串的奇数位下标的数字之和与偶数位下标的数字之和相等，那么我们称这个数字字符串是 平衡的 。
请你返回 num 不同排列 中，平衡 字符串的数目。
由于答案可能很大，请你将答案对 10^9 + 7 取余 后返回。
一个字符串的 排列 指的是将字符串中的字符打乱顺序后连接得到的字符串。
测试样例：
输入：num = "123"
输出：2
解释：它们之中，"132" 和 "231" 是平衡的。所以答案为 2 。
解答：这题题目范围不太大。可以利用动态规划暴力计算一下。题目比较麻烦，需要num 不同排列 中，平衡 字符串的数目。首先我们记录一下数字用0-9的分布情况。然后动态规划的目标是遍历到第n种数时，sum的情况和奇偶位剩余情况。利用组合计算所有可能性。
class Solution {
private static final int mod = 1_000_000_007;
private class InternalData {
Integer[][][] dp;
long[][] combine;
int zeroSum;
int[] nums;
public InternalData(String num) {
nums = new int[10];
for (int i = 0; i < num.length(); ++i) {
nums[num.charAt(i) - '0'] += 1;
}
zeroSum = 10 * num.length();
dp = new Integer[2 * num.length() * 10][10][num.length() / 2 + num.length() % 2 + 1];
// 计算组合
combine = calculateCombine(num.length() / 2 + 1);
}
private long[][] calculateCombine(int max) {
long[][] res = new long[max + 1][max + 1];
res[0][0] = 1;
for (int i = 1; i <= max; ++i) {
for (int j = 0; j <= i; ++j) {
if (j == 0 || j == i) {
res[i][j] = 1;
} else if (j == 1) {
res[i][j] = i;
} else {
res[i][j] = (res[i - 1][j - 1] + res[i - 1][j]) % mod;
}
}
}
return res;
}
}
public int countBalancedPermutations(String num) {
InternalData data = new InternalData(num);
return dfs(0, 0, num.length() / 2 + num.length() % 2, num.length() / 2, data);
}
// 遍历到第N个数。当前的diff情况和奇偶剩余
private int dfs(int sum, int pos, int oddRemain, int evenRemain, InternalData data) {
if (pos == 10) {
if (oddRemain == 0 && evenRemain == 0 && sum == 0) {
return 1;
} else {
return 0;
}
} else if (data.dp[sum + data.zeroSum][pos][oddRemain] == null) {
data.dp[sum + data.zeroSum][pos][oddRemain] = 0;
for (int i = 0; i <= Math.min(oddRemain, data.nums[pos]); ++i) {
// 遍历所有情况，放入奇数位则增加diff，否则减少diff
if (evenRemain >= data.nums[pos] - i) {
int nextSum = sum + i * pos - (data.nums[pos] - i) * pos;
int nextOddRemain = oddRemain - i;
int nextEvenRemain = evenRemain - (data.nums[pos] - i);
long result = dfs(nextSum, pos + 1, nextOddRemain, nextEvenRemain, data);
if (result > 0) {
result = (result * data.combine[oddRemain][i] % mod * data.combine[evenRemain][data.nums[pos] - i] % mod);
data.dp[sum + data.zeroSum][pos][oddRemain] += (int) result;
data.dp[sum + data.zeroSum][pos][oddRemain] %= mod;
}
}
}
}
return data.dp[sum + data.zeroSum][pos][oddRemain];
}
}