欢迎大家加QQ群：623375442，可以方便群里面交流。
100467. Stone Removal Game
Alice 和 Bob 在玩一个游戏，他们俩轮流从一堆石头中移除石头，Alice 先进行操作。
- Alice 在第一次操作中移除 恰好 10 个石头。
- 接下来的每次操作中，每位玩家移除的石头数 恰好 为另一位玩家上一次操作的石头数减 1 。
第一位没法进行操作的玩家输掉这个游戏。
给你一个正整数 n 表示一开始石头的数目，如果 Alice 赢下这个游戏，请你返回 true ，否则返回 false 。
测试样例：
输入：n = 12
输出：true
解释：
- Alice 第一次操作中移除 10 个石头，剩下 2 个石头给 Bob 。
- Bob 无法移除 9 个石头，所以 Alice 赢下游戏。
解答：暴力枚举。
class Solution {
public boolean canAliceWin(int n) {
int remove = 10, person = 0;
while (n >= remove) {
n -= remove;
remove -= 1;
person ^= 1;
}
return person != 0;
}
}100441. Shift Distance Between Two Strings
给你两个长度相同的字符串 s 和 t ，以及两个整数数组 nextCost 和 previousCost 。
一次操作中，你可以选择 s 中的一个下标 i ，执行以下操作 之一 ：
- 将 s[i] 切换为字母表中的下一个字母，如果 s[i] == 'z' ，切换后得到 'a' 。操作的代价为 nextCost[j] ，其中 j 表示 s[i] 在字母表中的下标。
- 将 s[i] 切换为字母表中的上一个字母，如果 s[i] == 'a' ，切换后得到 'z' 。操作的代价为 previousCost[j] ，其中 j 是 s[i] 在字母表中的下标。
切换距离 指的是将字符串 s 变为字符串 t 的 最少 操作代价总和。
请你返回从 s 到 t 的 切换距离 。
测试样例：
输入：s = "abab", t = "baba", nextCost = [100,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], previousCost = [1,100,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
输出：2
解释：
- 选择下标 i = 0 并将 s[0] 向前切换 25 次，总代价为 1 。
- 选择下标 i = 1 并将 s[1] 向后切换 25 次，总代价为 0 。
- 选择下标 i = 2 并将 s[2] 向前切换 25 次，总代价为 1 。
- 选择下标 i = 3 并将 s[3] 向后切换 25 次，总代价为 0 。
解答：也是暴力题。直接计算下26个字母转移到另外26个字母最小代价。计算代价的方式，就是单用下一个或者单用上一个。取2者较少数。
class Solution {
public long shiftDistance(String s, String t, int[] nextCost, int[] previousCost) {
Long[][] cost = new Long[26][26];
long res = 0;
for (int i = 0; i < s.length(); ++i) {
res += cost(s.charAt(i) - 'a', t.charAt(i) - 'a', nextCost, previousCost, cost);
}
return res;
}
private long cost(int o, int t, int[] nextCost, int[] previousCost, Long[][] cost) {
if (cost[o][t] == null) {
if (o == t) return 0;
long c1 = 0;
{
int tmp = o;
while (tmp != t) {
c1 += nextCost[tmp];
tmp = (tmp + 1) % 26;
}
}
long c2 = 0;
{
int tmp = o;
while (tmp != t) {
c2 += previousCost[tmp];
tmp = tmp - 1;
if (tmp == -1) {
tmp = 25;
}
}
}
cost[o][t] = Math.min(c1, c2);
}
return cost[o][t];
}
}100487. Zero Array Transformation III
给你一个长度为 n 的整数数组 nums 和一个二维数组 queries ，其中 queries[i] = [li, ri] 。
每一个 queries[i] 表示对于 nums 的以下操作：
- 将 nums 中下标在范围 [li, ri] 之间的每一个元素 最多 减少 1 。
- 坐标范围内每一个元素减少的值相互 独立 。
零数组 指的是一个数组里所有元素都等于 0 。
请你返回 最多 可以从 queries 中删除多少个元素，使得 queries 中剩下的元素仍然能将 nums 变为一个 零数组 。如果无法将 nums 变为一个 零数组 ，返回 -1 。
测试样例：
输入：nums = [2,0,2], queries = [[0,2],[0,2],[1,1]]
输出：1
解释：删除 queries[2] 后，nums 仍然可以变为零数组。
- 对于 queries[0] ，将 nums[0] 和 nums[2] 减少 1 ，将 nums[1] 减少 0 。
- 对于 queries[1] ，将 nums[0] 和 nums[2] 减少 1 ，将 nums[1] 减少 0 。
解答：这题有点以前Hard题目，加油站的思路。如果当前位置没有减少为0，我们就尽量把影响范围最大的query带入。
class Solution {
public int maxRemoval(int[] nums, int[][] queries) {
// 按到li排序，我是从左到右遍历，所以将能够生效的位置计算出来
Arrays.sort(queries, (a, b) -> (Integer.compare(a[0], b[0])));
// 模拟加油站的思路
PriorityQueue<Integer> effective = new PriorityQueue<>((a, b) -> (Integer.compare(queries[a][1], queries[b][1])));
PriorityQueue<Integer> potential = new PriorityQueue<>((a, b) -> (Integer.compare(queries[b][1], queries[a][1])));
int pos = 0, used = 0;
for (int i = 0; i < nums.length; ++i) {
// 把可能生效的范围加入
while (pos < queries.length && queries[pos][0] <= i) {
potential.add(pos++);
}
// 把已经失效的剔除
while (!effective.isEmpty() && queries[effective.peek()][1] < i) {
effective.poll();
}
// 当前数字没有被清零，就尽量把范围大的代入进入
while (effective.size() < nums[i] && !potential.isEmpty() && queries[potential.peek()][1] >= i) {
used += 1;
effective.add(potential.poll());
}
// 不符合要求，返回-1
if (effective.size() < nums[i]) {
return -1;
}
}
return queries.length - used;
}
}100488. Find the Maximum Number of Fruits Collected
有一个游戏，游戏由 n x n 个房间网格状排布组成。
给你一个大小为 n x n 的二位整数数组 fruits ，其中 fruits[i][j] 表示房间 (i, j) 中的水果数目。有三个小朋友 一开始 分别从角落房间 (0, 0) ，(0, n - 1) 和 (n - 1, 0) 出发。
每一位小朋友都会 恰好 移动 n - 1 次，并到达房间 (n - 1, n - 1) ：
- 从 (0, 0) 出发的小朋友每次移动从房间 (i, j) 出发，可以到达 (i + 1, j + 1) ，(i + 1, j) 和 (i, j + 1) 房间之一（如果存在）。
- 从 (0, n - 1) 出发的小朋友每次移动从房间 (i, j) 出发，可以到达房间 (i + 1, j - 1) ，(i + 1, j) 和 (i + 1, j + 1) 房间之一（如果存在）。
- 从 (n - 1, 0) 出发的小朋友每次移动从房间 (i, j) 出发，可以到达房间 (i - 1, j + 1) ，(i, j + 1) 和 (i + 1, j + 1) 房间之一（如果存在）。
当一个小朋友到达一个房间时，会把这个房间里所有的水果都收集起来。如果有两个或者更多小朋友进入同一个房间，只有一个小朋友能收集这个房间的水果。当小朋友离开一个房间时，这个房间里不会再有水果。
请你返回三个小朋友总共 最多 可以收集多少个水果。
测试样例：
输入：fruits = [[1,2,3,4],[5,6,8,7],[9,10,11,12],[13,14,15,16]]
输出：100
解释：这个例子中：
- 第 1 个小朋友（绿色）的移动路径为 (0,0) -> (1,1) -> (2,2) -> (3, 3) 。
- 第 2 个小朋友（红色）的移动路径为 (0,3) -> (1,2) -> (2,3) -> (3, 3) 。
- 第 3 个小朋友（蓝色）的移动路径为 (3,0) -> (3,1) -> (3,2) -> (3, 3) 。
他们总共能收集 1 + 6 + 11 + 1 + 4 + 8 + 12 + 13 + 14 + 15 = 100 个水果。
解答：每个孩子只能走n-1步。所以本质有点脑筋急转弯。第一个孩子只能走对角线！另外俩个孩子，我就直接暴力动态规划计算最佳结果了。
class Solution {
private static final int[][][] movess = {{{1,-1},{1,0},{1,1}},{{-1,1},{0,1},{1,1}}};
public int maxCollectedFruits(int[][] fruits) {
int n = fruits.length;
int res = 0;
for (int i = 0; i < n; ++i) {
res += fruits[i][i];
fruits[i][i] = 0;
}
res += getMax(fruits, 0, n - 1, movess[0]);
res += getMax(fruits, n - 1, 0, movess[1]);
return res;
}
private int getMax(int[][] fruits, int x, int y, int[][] moves) {
int n = fruits.length;
Integer[][] dp = new Integer[n][n];
return dfs(fruits, x, y, dp, n - 1, moves);
}
private int dfs(int[][] fruits, int x, int y, Integer[][] dp, int countDown, int[][] moves) {
if (countDown == 0) {
// 符合要求，返回0
if (x == fruits.length - 1 && y == fruits.length - 1) {
return 0;
}
// 失败，返回-1
return -1;
}
if (dp[x][y] == null) {
int res = -1;
for (int[] mv : moves) {
int xt = x + mv[0], yt = y + mv[1];
if (xt >= 0 && xt < fruits.length && yt >= 0 && yt < fruits.length) {
int next = dfs(fruits, xt, yt, dp, countDown - 1, moves);
if (next != -1) {
// 当前策略可行，计算最大结果。
res = Math.max(res, next + fruits[x][y]);
}
}
}
dp[x][y] = res;
}
return dp[x][y];
}
}