标签： easy

目标

图像平滑器 是大小为 3 x 3 的过滤器，用于对图像的每个单元格平滑处理，平滑处理后单元格的值为该单元格的平均灰度。

每个单元格的 平均灰度 定义为：该单元格自身及其周围的 8 个单元格的平均值，结果需向下取整。（即，需要计算蓝色平滑器中 9 个单元格的平均值）。

如果一个单元格周围存在单元格缺失的情况，则计算平均灰度时不考虑缺失的单元格（即，需要计算红色平滑器中 4 个单元格的平均值）。

给你一个表示图像灰度的 m x n 整数矩阵 img ，返回对图像的每个单元格平滑处理后的图像 。

示例 1:

输入:img = [[1,1,1],[1,0,1],[1,1,1]]
输出:[[0, 0, 0],[0, 0, 0], [0, 0, 0]]
解释:
对于点 (0,0), (0,2), (2,0), (2,2): 平均(3/4) = 平均(0.75) = 0
对于点 (0,1), (1,0), (1,2), (2,1): 平均(5/6) = 平均(0.83333333) = 0
对于点 (1,1): 平均(8/9) = 平均(0.88888889) = 0

示例 2:

输入: img = [[100,200,100],[200,50,200],[100,200,100]]
输出: [[137,141,137],[141,138,141],[137,141,137]]
解释:
对于点 (0,0), (0,2), (2,0), (2,2): floor((100+200+200+50)/4) = floor(137.5) = 137
对于点 (0,1), (1,0), (1,2), (2,1): floor((200+200+50+200+100+100)/6) = floor(141.666667) = 141
对于点 (1,1): floor((50+200+200+200+200+100+100+100+100)/9) = floor(138.888889) = 138

说明:

• m == img.length
• n == img[i].length
• 1 <= m, n <= 200
• 0 <= img[i][j] <= 255

思路

将图像中任意像素点的灰度值变为其自身以及周围八个像素灰度值的平均值。

可以使用二维前缀和，prefix[i][j] 表示左上顶点为 (0, 0) 右下顶点为 (i, j) 的矩形内的所有元素和。左上顶点为 (p, q) 右下顶点为 (i, j) 的矩形内所有元素和为 prefix[i][j] - prefix[i][q] - prefix[p][j] + prefix[p][q]。注意这里的坐标是顶点的坐标，而题目中的坐标表示格子的坐标，这样定义的前缀和表示以该格子为右下顶点的所有元素和，包括格子所在行列。

使用前缀和时多初始化一行一列可以大大简化代码逻辑，否则我们需要单独初始化第一行，第一列，并且需要在计算二维前缀和时判断下标越界。定义 prefix[i][j] 表示对角线 (0, 0) ~ (i - 1, j - 1) 矩形内的元素和，对于 m x n 矩阵，prefix[m][n] 表示所有元素和。以 (p, q) 为左上顶点，(i, j) 为右下顶点的前缀和为 prefix[i + 1][j + 1] - prefix[i + 1][q] - prefix[p][j + 1] + prefix[p][q]。

代码

/**
 * @date 2024-11-18 9:10
 */
public class ImageSmoother661 {

    public int[][] imageSmoother_v1(int[][] img) {
        int m = img.length;
        int n = img[0].length;
        int[][] prefix = new int[m + 1][n + 1];
        for (int r = 1; r <= m; r++) {
            for (int c = 1; c <= n; c++) {
                prefix[r][c] = prefix[r - 1][c] + prefix[r][c - 1] - prefix[r - 1][c - 1] + img[r - 1][c - 1];
            }
        }
        for (int r = 0; r < m; r++) {
            int i = Math.min(m - 1, r + 1);
            int p = Math.max(0, r - 1);
            for (int c = 0; c < n; c++) {
                int j = Math.min(n - 1, c + 1);
                int q = Math.max(0, c - 1);
                int cnt = (i - p + 1) * (j - q + 1);
                img[r][c] = (prefix[i + 1][j + 1] - prefix[p][j + 1] - prefix[i + 1][q] + prefix[p][q]) / cnt;
            }
        }
        return img;
    }

}

性能

目标

给你一个 二进制 字符串 s 和一个整数 k。

如果一个 二进制字符串 满足以下任一条件，则认为该字符串满足 k 约束：

• 字符串中 0 的数量最多为 k。
• 字符串中 1 的数量最多为 k。

返回一个整数，表示 s 的所有满足 k 约束 的 子字符串 的数量。

示例 1：

输入：s = "10101", k = 1
输出：12
解释：
s 的所有子字符串中，除了 "1010"、"10101" 和 "0101" 外，其余子字符串都满足 k 约束。

示例 2：

输入：s = "1010101", k = 2
输出：25
解释：
s 的所有子字符串中，除了长度大于 5 的子字符串外，其余子字符串都满足 k 约束。

示例 3：

输入：s = "11111", k = 1
输出：15
解释：
s 的所有子字符串都满足 k 约束。

说明：

• 1 <= s.length <= 50
• 1 <= k <= s.length
• s[i] 是 '0' 或 '1'。

思路

定义二进制字符串满足 k 约束的条件是字符串中 0 的个数 或者 1 的个数都不超过 k。求给定字符串满足 k 约束的子字符串数量。子字符串 是字符串中 连续 的 非空 字符序列。

对于非定长滑动窗口，我们可以枚举左端点，扩展右端点；也可以枚举右端点，收缩左端点。对于这个题，我们需要累加的是子数组个数，即以枚举的元素为起点或终点的子数组个数，实际就是区间内元素个数。如果枚举左端点，右端点指向的是不满足条件的点，需要复杂的判断，非常容易出错。因此选择枚举右端点，收缩左端点。

代码

/**
 * @date 2024-11-12 9:19
 */
public class CountKConstraintSubstrings3258 {

    public int countKConstraintSubstrings(String s, int k) {
        int n = s.length();
        char[] chars = s.toCharArray();
        int[] cnt = new int[2];
        int res = 0, l = 0;
        for (int i = 0; i < n; i++) {
            cnt[chars[i] - '0']++;
            while (l <= i && cnt[0] > k && cnt[1] > k) {
                cnt[chars[l++] - '0']--;
            }
            res += i - l + 1;
        }
        return res;
    }

}

性能

目标

给你一个 n x n 的二维数组 grid，它包含范围 [0, n^2 - 1] 内的不重复元素。

实现 neighborSum 类：

• neighborSum(int [][]grid) 初始化对象。
• int adjacentSum(int value) 返回在 grid 中与 value 相邻的元素之和，相邻指的是与 value 在上、左、右或下的元素。
• int diagonalSum(int value) 返回在 grid 中与 value 对角线相邻的元素之和，对角线相邻指的是与 value 在左上、右上、左下或右下的元素。

示例 1：

输入：
["neighborSum", "adjacentSum", "adjacentSum", "diagonalSum", "diagonalSum"]
[[[[0, 1, 2], [3, 4, 5], [6, 7, 8]]], [1], [4], [4], [8]]
输出： [null, 6, 16, 16, 4]
解释：
1 的相邻元素是 0、2 和 4。
4 的相邻元素是 1、3、5 和 7。
4 的对角线相邻元素是 0、2、6 和 8。
8 的对角线相邻元素是 4。

示例 2：

输入：
["neighborSum", "adjacentSum", "diagonalSum"]
[[[[1, 2, 0, 3], [4, 7, 15, 6], [8, 9, 10, 11], [12, 13, 14, 5]]], [15], [9]]
输出： [null, 23, 45]
解释：
15 的相邻元素是 0、10、7 和 6。
9 的对角线相邻元素是 4、12、14 和 15。

说明：

• 3 <= n == grid.length == grid[0].length <= 10
• 0 <= grid[i][j] <= n^2 - 1
• 所有 grid[i][j] 值均不重复。
• adjacentSum 和 diagonalSum 中的 value 均在范围 [0, n^2 - 1] 内。
• 最多会调用 adjacentSum 和 diagonalSum 总共 2 * n^2 次。

思路

有一个 n x n 的二维矩阵，其元素值的范围是 0 ~ n^2 - 1，且元素值互不相同。给定一个元素值，求其上下左右的元素和以及对角线元素和（左上、右上、左下和右下）。

首先要找到这个给定的元素，再根据其下标计算元素和，对于大量重复地查询，可以记录每个元素值对应的下标。

每次定位的时间复杂度为 100，由于存在缓存，最多搜索 100 次，总复杂度为 10^4。

我们也可以在初始化的时候直接建立 元素值 与 坐标的映射，时间复杂度降为 O(n^2) 即 100。

还可以进一步优化，由于数据值是不可变的，可以提前将 相邻元素和 都计算好，查的时候无需重复计算。此外，由于元素各不相同，可以直接将元素值映射为下标，将元素值与坐标的映射改为元素值与相邻元素和的映射。

代码

/**
 * @date 2024-11-09 11:21
 */
public class NeighborSum3242 {

    class NeighborSum {

        int[][] adjacent = new int[][]{
                new int[]{-1, 0},
                new int[]{1, 0},
                new int[]{0, -1},
                new int[]{0, 1},
        };
        int[][] diagonal = new int[][]{
                new int[]{-1, -1},
                new int[]{-1, 1},
                new int[]{1, -1},
                new int[]{1, 1},
        };
        int[] adjacentSum;
        int[] diagonalSum;

        public NeighborSum(int[][] grid) {
            int index = 0;
            int n = grid.length;
            int length = n * n;
            adjacentSum = new int[length];
            diagonalSum = new int[length];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    int value = grid[i][j];
                    adjacentSum[value] = sum(grid, i, j, adjacent);
                    diagonalSum[value] = sum(grid, i, j, diagonal);
                }
            }
        }

        public int adjacentSum(int value) {
            return adjacentSum[value];
        }

        public int diagonalSum(int value) {
            return diagonalSum[value];
        }

        private int sum(int[][] grid, int i, int j, int[][] directions){
            int res = 0;
            for (int[] direction : directions) {
                int row = direction[0] + i;
                int col = direction[1] + j;
                if (row < 0 || col < 0 || row >= grid.length || col >= grid.length) {
                    continue;
                }
                res += grid[row][col];
            }
            return res;
        }
    }

}

性能

目标

给你两个 正 整数 x 和 y ，分别表示价值为 75 和 10 的硬币的数目。

Alice 和 Bob 正在玩一个游戏。每一轮中，Alice 先进行操作，Bob 后操作。每次操作中，玩家需要拿出价值 总和 为 115 的硬币。如果一名玩家无法执行此操作，那么这名玩家 输掉 游戏。

两名玩家都采取 最优 策略，请你返回游戏的赢家。

示例 1：

输入：x = 2, y = 7
输出："Alice"
解释：
游戏一次操作后结束：
Alice 拿走 1 枚价值为 75 的硬币和 4 枚价值为 10 的硬币。

示例 2：

输入：x = 4, y = 11
输出："Bob"
解释：
游戏 2 次操作后结束：
Alice 拿走 1 枚价值为 75 的硬币和 4 枚价值为 10 的硬币。
Bob 拿走 1 枚价值为 75 的硬币和 4 枚价值为 10 的硬币。

说明：

• 1 <= x, y <= 100

思路

有价值 75 的硬币 x 个，价值 10 的硬币 y 个。Alice 与 Bob 轮流进行操作，每一次操作需要从中取出价值 115 的硬币，如果无法执行此操作则玩家输掉游戏。如果 Alice 先进行操作，最后的赢家是谁？

每次操作需要取 1 个 x，4 个 y，可以直接模拟，直到 x < 1 或 y < 4。

这道题也有数学解法，输赢实际上取决于可以进行的操作次数。总共可以进行的操作次数是 Math.min(x，y/4)，如果为偶数 Bob 胜，奇数 Alice 胜。

代码

/**
 * @date 2024-11-05 9:14
 */
public class LosingPlayer3222 {

    public String losingPlayer_v1(int x, int y) {
        return Math.min(x, y / 4) % 2 == 0 ? "Bob" : "Alice";
    }

    public String losingPlayer(int x, int y) {
        int cnt = 0;
        while (x >= 1 && y >= 4) {
            x--;
            y -= 4;
            cnt++;
        }
        return cnt % 2 == 0 ? "Bob" : "Alice";
    }

}

性能

目标

给你两个正整数 n 和 k。

你可以选择 n 的 二进制表示 中任意一个值为 1 的位，并将其改为 0。

返回使得 n 等于 k 所需要的更改次数。如果无法实现，返回 -1。

示例 1：

输入： n = 13, k = 4
输出： 2
解释：
最初，n 和 k 的二进制表示分别为 n = (1101)2 和 k = (0100)2，
我们可以改变 n 的第一位和第四位。结果整数为 n = (0100)2 = k。

示例 2：

输入： n = 21, k = 21
输出： 0
解释：
n 和 k 已经相等，因此不需要更改。

示例 3：

输入： n = 14, k = 13
输出： -1
解释：
无法使 n 等于 k。

说明：

• 1 <= n, k <= 10^6

思路

有两个整数 n 和 k，每次操作可以将 n 的二进制位从 1 改为 0，求使 n 等于 k 所需的操作次数，如果无法实现返回 -1。

注意到这两个整数最大为 10^6，而 2^20 = 1048576，因此最高 bit 位不会超过 20。

依次比较这两个数的第 19 位到第 0 位：

• 如果相等则跳过
• 如果 n 的 bit 位为 0 则返回 -1，因为这时 k 对应位置的 bit 位为 1，无法通过操作使之相等
• 否则累加操作次数

官网题解提供了另一种解法，将每个 bit 为 1 的位置视为一个元素，如果可以通过操作将 n 变为 k， 说明 k 的 bit 1 的集合是 n 的 bit 1 集合的子集。因此 n & k = k，这时我们需要统计 n 与 k bit 位不同的个数，直接使用异或运算统计 bit 1 的个数即可。

return (n & k) == k ? Integer.bitCount(n ^ k) : -1;。

代码

/**
 * @date 2024-11-02 5:00
 */
public class MinChanges3226 {

    public int minChanges(int n, int k) {
        int res = 0;
        for (int i = 19; i >= 0; i--) {
            int bitn = n & 1 << i;
            int bitk = k & 1 << i;
            if (bitn == bitk) {
                continue;
            }
            if (bitn == 0) {
                return -1;
            } else {
                res++;
            }
        }
        return res;
    }
}

性能

目标

给你两个整数 red 和 blue，分别表示红色球和蓝色球的数量。你需要使用这些球来组成一个三角形，满足第 1 行有 1 个球，第 2 行有 2 个球，第 3 行有 3 个球，依此类推。

每一行的球必须是 相同 颜色，且相邻行的颜色必须 不同。

返回可以实现的三角形的 最大 高度。

示例 1：

输入： red = 2, blue = 4
输出： 3
解释：
上图显示了唯一可能的排列方式。

示例 2：

输入： red = 2, blue = 1
输出： 2
解释：
上图显示了唯一可能的排列方式。

示例 3：

输入： red = 1, blue = 1
输出： 1

示例 4：

输入： red = 10, blue = 1
输出： 2
解释：
上图显示了唯一可能的排列方式。

说明：

• 1 <= red, blue <= 100

思路

有红球 red 个，蓝球 blue 个，使用这两种球组成三角形，要求每一行只能由同一种颜色的球组成，且相邻行球的颜色不同，问三角形的最大高度。

三角形第 i 行球的个数为 i，奇数行的总个数为 1 + 3 + 5 + …… 偶数行的总个数为 2 + 4 + 6 + ……，根据等差数列求和公式，奇数行所需球的总个数为 oddRowCnt^2，偶数行所需球的总个数为 evenRowCnt^2 + evenRowCnt。

假设 red 放在奇数行，代入可得 redOddRowCnt = sqrt(red)，如果放在偶数行，则 redEvenRowCnt = (sqrt(1 + 4 * red) - 1) / 2。同理可求出 blueOddRowCnt blueEvenRowCnt。

接下来分两种情况讨论：

1. 红色球放第一行：如果 |redOddRowCnt - blueEvenRowCnt| > 1，取 Math.min(redOddRowCnt, blueEvenRowCnt) * 2 + 1，否则取 Math.min(redOddRowCnt, blueEvenRowCnt) * 2。
2. 蓝色球放第一行：如果 |blueOddRowCnt - redEvenRowCnt| > 1，取 Math.min(blueOddRowCnt, redEvenRowCnt) * 2 + 1，否则取 Math.min(blueOddRowCnt, redEvenRowCnt) * 2。

取上面两种情况的最大值即可。

代码

/**
 * @date 2024-10-15 9:25
 */
public class MaxHeightOfTriangle3200 {

    public int maxHeightOfTriangle(int red, int blue) {
        int redOddRowCnt = (int) Math.sqrt(red);
        int redEvenRowCnt = (int) ((Math.sqrt(1 + 4 * red) - 1) / 2);
        int blueOddRowCnt = (int) Math.sqrt(blue);
        int blueEvenRowCnt = (int) ((Math.sqrt(1 + 4 * blue) - 1) / 2);
        int r, b;
        if (redOddRowCnt - blueEvenRowCnt >= 1) {
            r = 2 * blueEvenRowCnt + 1;
        } else {
            r = 2 * redOddRowCnt;
        }
        if (blueOddRowCnt - redEvenRowCnt >= 1) {
            b = 2 * redEvenRowCnt + 1;
        } else {
            b = 2 * blueOddRowCnt;
        }
        return Math.max(r, b);
    }

}

性能