欢迎大家加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;
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *