欢迎大家加QQ群：623375442，可以方便群里面交流。
100375. Find the Winning Player in Coin Game
给你两个 正 整数 x 和 y ，分别表示价值为 75 和 10 的硬币的数目。
Alice 和 Bob 正在玩一个游戏。每一轮中，Alice 先进行操作，Bob 后操作。每次操作中，玩家需要拿出价值 总和 为 115 的硬币。如果一名玩家无法执行此操作，那么这名玩家 输掉 游戏。
两名玩家都采取 最优 策略，请你返回游戏的赢家。
测试样例：
输入：x = 2, y = 7
输出："Alice"
解释：游戏一次操作后结束：
- Alice 拿走 1 枚价值为 75 的硬币和 4 枚价值为 10 的硬币。
解答：115只能取1个75，4个10做到。所以暴力尝试直到剩下的硬币不够为止。
class Solution {
public String losingPlayer(int x, int y) {
int pos = 0;
while (x >= 1 && y >= 4) {
x -= 1;
y -= 4;
pos ^= 1;
}
return pos == 1 ? "Alice" : "Bob";
}
}100330. Minimum Length of String After Operations
给你一个字符串 s 。
你需要对 s 执行以下操作 任意 次：
- 选择一个下标 i ，满足 s[i] 左边和右边都 至少 有一个字符与它相同。
- 删除 s[i] 左边 离它 最近 且相同的字符。
- 删除 s[i] 右边 离它 最近 且相同的字符。
请你返回执行完所有操作后， s 的 最短 长度。
测试样例：
输入：s = "abaacbcbb"
输出：5
解释：我们执行以下操作：
- 选择下标 2 ，然后删除下标 0 和 3 处的字符，得到 s = "bacbcbb" 。
- 选择下标 3 ，然后删除下标 0 和 5 处的字符，得到 s = "acbcb" 。
解答：如果一个字符出现大于3次，就能进行操作，每次去除2个相同字符，直到当前字符出现次数小于等于2.
class Solution {
public int minimumLength(String s) {
int[] count = new int[26];
for (int i = 0; i < s.length(); ++i) {
count[s.charAt(i) - 'a'] += 1;
}
int res = 0;
for (int n : count) {
if (n <= 2) {
res += n;
} else if (n % 2 == 0) {
res += 2;
} else {
res += 1;
}
}
return res;
}
}100365. Minimum Array Changes to Make Differences Equal
给你一个长度为 n 的整数数组 nums ，n 是 偶数 ，同时给你一个整数 k 。
你可以对数组进行一些操作。每次操作中，你可以将数组中 任一 元素替换为 0 到 k 之间的 任一 整数。
执行完所有操作以后，你需要确保最后得到的数组满足以下条件：
- 存在一个整数 X ，满足对于所有的 (0 <= i < n) 都有 abs(a[i] - a[n - i - 1]) = X 。
请你返回满足以上条件 最少 修改次数。
测试样例：
输入：nums = [1,0,1,2,4,3], k = 4
输出：2
解释：我们可以执行以下操作：
- 将 nums[1] 变为 2 ，结果数组为 nums = [1,2,1,2,4,3] 。
- 将 nums[3] 变为 3 ，结果数组为 nums = [1,2,1,3,4,3] 。
解答：暴力尝试所有diff的可能（最大为k）。需要注意，有些对可能需要同时修改两个数才能达到某个diff。
class Solution {
public int minChanges(int[] nums, int k) {
int[] diffCount = new int[k + 1], maxDiff = new int[k + 1];
int st = 0, ed = nums.length - 1;
int pair = nums.length / 2;
while (st < ed) {
diffCount[Math.abs(nums[st] - nums[ed])] += 1;
// 当前对所能达到的最大diff，无法满足的时候，就需要同时换两个数。
int tmp = Math.max(Math.max(nums[st], nums[ed]), Math.max(k - nums[st], k - nums[ed]));
maxDiff[tmp] += 1;
++st;
--ed;
}
int res = nums.length, doublePair = 0;
for (int i = 0; i <= k; ++i) {
if (i > 0) {
doublePair += maxDiff[i - 1];
}
res = Math.min(res, (pair - doublePair - diffCount[i]) + 2 * doublePair);
}
return res;
}
}100341. Maximum Score From Grid Operations
给你一个大小为 n x n 的二维矩阵 grid ，一开始所有格子都是白色的。一次操作中，你可以选择任意下标为 (i, j) 的格子，并将第 j 列中从最上面到第 i 行所有格子改成黑色。
如果格子 (i, j) 为白色，且左边或者右边的格子至少一个格子为黑色，那么我们将 grid[i][j] 加到最后网格图的总分中去。
请你返回执行任意次操作以后，最终网格图的 最大 总分数。
测试样例：
输入：grid = [[0,0,0,0,0],[0,0,3,0,0],[0,1,0,0,0],[5,0,0,3,0],[0,0,0,0,2]]
输出：11
解释：第一次操作中，我们将第 1 列中，最上面的格子到第 3 行的格子染成黑色。第二次操作中，我们将第 4 列中，最上面的格子到最后一行的格子染成黑色。最后网格图总分为 grid[3][0] + grid[1][2] + grid[3][3] 等于 11 。
解答：这题难度是有点大，很难得动态规划题。我们一列列遍历。每一列有一个自己的二维DP数组dp[i][j], i代表当前涂黑前i行，j代表前j行受到之前的影响，i 到 j - 1行加分。具体转移矩阵可以看代码。
class Solution {
public long maximumScore(int[][] grid) {
int n = grid.length;
long res = 0;
long[][] last = new long[n + 1][n + 1];
for (int i = 1; i < n; ++i) {
long[] rowMax = new long[n + 1];
for (int j = 0; j <= n; ++j) {
for (int k = j; k <= n; ++k) {
rowMax[j] = Math.max(rowMax[j], last[j][k]);
}
}
long[] prefixSum = new long[n + 1];
for (int j = 0; j < n; ++j) {
prefixSum[j + 1] = prefixSum[j] + grid[j][i];
}
long[][] nextLast = new long[n + 1][n + 1];
for (int j = 0; j <= n; ++j) {
for (int k = j; k <= n; ++k) {
// 前k列都涂黑的老DP，并且加上分数
nextLast[j][k] = rowMax[k] + prefixSum[k] - prefixSum[j];
res = Math.max(nextLast[j][k], res);
}
}
long[] rowTmp = new long[n + 1];
// 特殊情况，涂黑前n列，然后不加分。
for (int j = 0; j <= n; ++j) {
rowTmp[j] = last[j][j];
long bestTmp = Math.max(rowMax[j], rowTmp[j]);
for (int k = 0; k < j; ++k) {
// 特殊情况，前面涂了k行，但是加分不够j行，需要把剩下部分补上。
rowTmp[k] = Math.max(rowTmp[k] + grid[j - 1][i - 1], last[k][j]);
bestTmp = Math.max(bestTmp, rowTmp[k]);
}
nextLast[j][j] = bestTmp;
res = Math.max(res, bestTmp);
}
last = nextLast;
}
return res;
}
}