easy – 第 8 页 – shelterofly

目标

给你一个坐标 coordinates ，它是一个字符串，表示国际象棋棋盘中一个格子的坐标。下图是国际象棋棋盘示意图。

如果所给格子的颜色是白色，请你返回 true，如果是黑色，请返回 false 。

给定坐标一定代表国际象棋棋盘上一个存在的格子。坐标第一个字符是字母，第二个字符是数字。

示例 1：

输入：coordinates = "a1"
输出：false
解释：如上图棋盘所示，"a1" 坐标的格子是黑色的，所以返回 false 。

示例 2：

输入：coordinates = "h3"
输出：true
解释：如上图棋盘所示，"h3" 坐标的格子是白色的，所以返回 true 。

示例 3：

输入：coordinates = "c7"
输出：false

提示：

coordinates.length == 2
'a' <= coordinates[0] <= 'h'
'1' <= coordinates[1] <= '8'

思路

有一个 8 x 8 的棋盘，行编号为 1 ~ 8，列编号为 a ~ h，给定一个坐标比如 c3，如果格子为白色返回 true，黑色返回 false。

经过观察，奇数行奇数列，偶数行偶数列为黑色，偶数行奇数列，奇数行偶数列为白色。我们只需判断横纵坐标之和是否为奇数即可。

需要注意的是，将字符串映射为下标数字 0 ~ 7，并不影响上面的判断。

代码


/**
 * @date 2024-12-09 0:11
 */
public class SquareIsWhite1812 {

    public boolean squareIsWhite(String coordinates) {
        int x = coordinates.charAt(0) - '1';
        int y = coordinates.charAt(1) - 'a';
        return (x + y) % 2 == 1;
    }
}

性能

目标

给定一个 8 x 8 的棋盘，只有一个白色的车，用字符 'R' 表示。棋盘上还可能存在白色的象 'B' 以及黑色的卒 'p'。空方块用字符 '.' 表示。

车可以按水平或竖直方向（上，下，左，右）移动任意个方格直到它遇到另一个棋子或棋盘的边界。如果它能够在一次移动中移动到棋子的方格，则能够吃掉棋子。

注意：车不能穿过其它棋子，比如象和卒。这意味着如果有其它棋子挡住了路径，车就不能够吃掉棋子。

返回白车将能吃掉的卒的数量。

示例 1：

输入：
[
    [".",".",".",".",".",".",".","."],
    [".",".",".","p",".",".",".","."],
    [".",".",".","R",".",".",".","p"],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".","p",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."]
]
输出：3
解释：
在本例中，车能够吃掉所有的卒。

示例 2：

输入：
[
    [".",".",".",".",".",".",".","."],
    [".","p","p","p","p","p",".","."],
    [".","p","p","B","p","p",".","."],
    [".","p","B","R","B","p",".","."],
    [".","p","p","B","p","p",".","."],
    [".","p","p","p","p","p",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."]
]
输出：0
解释：
象阻止了车吃掉任何卒。

示例 3：

输入：
[
    [".",".",".",".",".",".",".","."]
    [".",".",".","p",".",".",".","."],
    [".",".",".","p",".",".",".","."],
    ["p","p",".","R",".","p","B","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".","B",".",".",".","."],
    [".",".",".","p",".",".",".","."],
    [".",".",".",".",".",".",".","."]
]
输出：3
解释： 
车可以吃掉位置 b5，d6 和 f5 的卒。

说明：

board.length == 8
board[i].length == 8
board[i][j] 可以是 'R'，'.'，'B' 或 'p'
只有一个格子上存在 board[i][j] == 'R'

思路

8 x 8 的棋盘上有一个白车 R，若干个白象 B 和黑卒 'p'，空格由 '.' 表示。问白车能够吃掉黑卒的数量，注意车只能吃掉同行同列四个方向上第一个遇到的黑卒。

首先需要找到白车的位置，按行遍历棋盘，记录当前行上一个棋子，遇到白车时判断上一个棋子是否是黑卒，如果是计入结果，然后判断后面遇到的第一个棋子，如果是黑卒计入结果。当前行遍历完成后结束循环，按照同样方法遍历白车所在列即可。

代码


/**
 * @date 2024-12-06 9:05
 */
public class NumRookCaptures999 {

    public int numRookCaptures(char[][] board) {
        int res = 0;
        int rookRow = -1;
        int rookCol = -1;
        here:
        for (int i = 0; i < 8; i++) {
            // 首先按行遍历，找到白色车的位置(rookRow, rookCol)，同时判断它前后的棋子是否是黑卒
            char[] row = board[i];
            char last = '.';
            for (int j = 0; j < 8; j++) {
                if (row[j] == 'R') {
                    // 如果找到白车，判断当前行前面的棋子是否是黑卒
                    if (last == 'p') {
                        res++;
                    }
                    // 记录坐标
                    rookCol = j;
                    rookRow = i;
                } else if (rookCol != -1 && row[j] != '.') {
                    // 判断后面第一个棋子是否是黑卒
                    if (row[j] == 'p') {
                        res++;
                    }
                    break here;
                }
                if (row[j] != '.') {
                    last = row[j];
                }
            }
            if (rookCol != -1) {
                break;
            }
        }

        for (int i = rookRow - 1; i >= 0; i--) {
            if (board[i][rookCol] != '.') {
                // 找到上面第一个棋子
                if (board[i][rookCol] == 'p') {
                    res++;
                }
                break;
            }
        }
        for (int i = rookRow + 1; i < 8; i++) {
            if (board[i][rookCol] != '.') {
                // 找到下面第一个棋子
                if (board[i][rookCol] == 'p') {
                    res++;
                }
                break;
            }
        }
        return res;
    }

}

性能

目标

给你两个字符串 coordinate1 和 coordinate2，代表 8 x 8 国际象棋棋盘上的两个方格的坐标。

以下是棋盘的参考图。

如果这两个方格颜色相同，返回 true，否则返回 false。

坐标总是表示有效的棋盘方格。坐标的格式总是先字母（表示列），再数字（表示行）。

示例 1：

输入： coordinate1 = "a1", coordinate2 = "c3"
输出： true
解释：
两个方格均为黑色。

示例 2：

输入： coordinate1 = "a1", coordinate2 = "h3"
输出： false
解释：
方格 "a1" 是黑色，而 "h3" 是白色。

说明：

coordinate1.length == coordinate2.length == 2
'a' <= coordinate1[0], coordinate2[0] <= 'h'
'1' <= coordinate1[1], coordinate2[1] <= '8'

思路

有一个棋盘行列从 1、a 开始编号，奇数列（a c e g）奇数行（1 3 5 7）是黑色，奇数列偶数行是白色；偶数列奇数行是白色，偶数列偶数行是黑色。判断给定的两个格子颜色是否相同。

如果两个坐标的列编号奇偶性相同，要想使颜色相同，那么行编号的奇偶性也应相同。换句话说就是判断给定的横纵坐标编号的奇偶性是否同时相等或不等。

代码


/**
 * @date 2024-12-03 8:58
 */
public class CheckTwoChessboards3274 {

    public boolean checkTwoChessboards_v1(String coordinate1, String coordinate2) {
        return (coordinate1.charAt(0) + coordinate1.charAt(1)) % 2 == (coordinate2.charAt(0) + coordinate2.charAt(1)) % 2;
    }

    public boolean checkTwoChessboards(String coordinate1, String coordinate2) {
        int x1 = coordinate1.charAt(0) - 'a';
        int y1 = coordinate1.charAt(1) - '1';
        int x2 = coordinate2.charAt(0) - 'a';
        int y2 = coordinate2.charAt(1) - '1';
        if (x1 % 2 == x2 % 2) {
            return y1 % 2 == y2 % 2;
        } else {
            return y1 % 2 != y2 % 2;
        }
    }

}

性能

目标

给你一个正整数数组 nums。

Alice 和 Bob 正在玩游戏。在游戏中，Alice 可以从 nums 中选择所有个位数或所有两位数，剩余的数字归 Bob 所有。如果 Alice 所选数字之和严格大于 Bob 的数字之和，则 Alice 获胜。

如果 Alice 能赢得这场游戏，返回 true；否则，返回 false。

示例 1：

输入：nums = [1,2,3,4,10]
输出：false
解释：
Alice 不管选个位数还是两位数都无法赢得比赛。

示例 2：

输入：nums = [1,2,3,4,5,14]
输出：true
解释：
Alice 选择个位数可以赢得比赛，所选数字之和为 15。

示例 3：

输入：nums = [5,5,5,25]
输出：true
解释：
Alice 选择两位数可以赢得比赛，所选数字之和为 25。

说明：

1 <= nums.length <= 100
1 <= nums[i] <= 99

思路

只要个位数之和与两位数之和不等就可以获胜。

代码

/**
 * @date 2024-11-30 1:23
 */
public class CanAliceWin3232 {

    public boolean canAliceWin(int[] nums) {
        int one = 0;
        int two = 0;
        for (int num : nums) {
            if (num < 10) {
                one += num;
            } else {
                two += num;
            }
        }
        return one != two;
    }
}

性能

目标

给你一个整数数组 colors ，它表示一个由红色和蓝色瓷砖组成的环，第 i 块瓷砖的颜色为 colors[i] ：

colors[i] == 0 表示第 i 块瓷砖的颜色是红色。
colors[i] == 1 表示第 i 块瓷砖的颜色是蓝色。

环中连续 3 块瓷砖的颜色如果是交替颜色（也就是说中间瓷砖的颜色与它左边和右边的颜色都不同），那么它被称为一个交替组。

请你返回交替组的数目。

注意，由于 colors 表示一个环，第一块瓷砖和最后一块瓷砖是相邻的。

示例 1：

输入：colors = [1,1,1]
输出：0

解释：

示例 2：

输入：colors = [0,1,0,0,1]
输出：3

解释：

交替组包括：

说明：

3 <= colors.length <= 100
0 <= colors[i] <= 1

思路

有一个环形二进制数组（认为首尾相邻），判断存在多少个交替组，如果元素与它左右相邻的两个元素值不相等，称这三个元素为一个交替组。

直接模拟判断即可，第一个元素的左邻居以及最后一个元素的右邻居需要特殊处理。也可以通过取模统一处理，定义 i 的初值为 n，i < 2n，循环内下标使用 (i - 1) % n，i % n，(i + 1) % n，不过没有必要对循环内的所有下标进行模运算，特殊处理效率更高。

官网题解循环使用的初值是 0，i < n，不过循环内部计算的是 (i - 1 + n) % n，i，(i + 1) % n，节省了两次 i % n 取余运算。

代码

/**
 * @date 2024-11-26 8:56
 */
public class NumberOfAlternatingGroups3206 {

    public int numberOfAlternatingGroups_v1(int[] colors) {
        int n = colors.length;
        int res = 0;
        boolean b = colors[n - 1] != colors[0];
        if (colors[0] != colors[1] && b) {
            res++;
        }
        if (colors[n - 1] != colors[n - 2] && b) {
            res++;
        }
        for (int i = 1; i < n - 1; i++) {
            if (colors[i - 1] != colors[i] && colors[i + 1] != colors[i]) {
                res++;
            }
        }
        return res;
    }

    public int numberOfAlternatingGroups(int[] colors) {
        int n = colors.length;
        int res = 0;
        for (int i = n; i < 2 * n; i++) {
            if (colors[(i - 1) % n] != colors[i % n] && colors[(i + 1) % n] != colors[i % n]) {
                res++;
            }
        }
        return res;
    }
}

性能

目标

给你一个整数 n ，表示在一个游戏中的玩家数目。同时给你一个二维整数数组 pick ，其中 pick[i] = [xi, yi] 表示玩家 xi 获得了一个颜色为 yi 的球。

如果玩家 i 获得的球中任何一种颜色球的数目严格大于 i 个，那么我们说玩家 i 是胜利玩家。换句话说：

如果玩家 0 获得了任何的球，那么玩家 0 是胜利玩家。
如果玩家 1 获得了至少 2 个相同颜色的球，那么玩家 1 是胜利玩家。
...
如果玩家 i 获得了至少 i + 1 个相同颜色的球，那么玩家 i 是胜利玩家。

请你返回游戏中胜利玩家的数目。

注意，可能有多个玩家是胜利玩家。

示例 1：

输入：n = 4, pick = [[0,0],[1,0],[1,0],[2,1],[2,1],[2,0]]
输出：2
解释：
玩家 0 和玩家 1 是胜利玩家，玩家 2 和玩家 3 不是胜利玩家。

示例 2：

输入：n = 5, pick = [[1,1],[1,2],[1,3],[1,4]]
输出：0
解释：
没有胜利玩家。

示例 3：

输入：n = 5, pick = [[1,1],[2,4],[2,4],[2,4]]
输出：1
解释：
玩家 2 是胜利玩家，因为玩家 2 获得了 3 个颜色为 4 的球。

说明：

2 <= n <= 10
1 <= pick.length <= 100
pick[i].length == 2
0 <= xi <= n - 1
0 <= yi <= 10

思路

有 n 个玩家，pick[i][j] 表示第 i 次操作，玩家 pick[i][0] 捡起了颜色为 pick[i][1] 的球，如果玩家 pick[i][0] 捡起同一颜色球的数量大于 pick[i][0] 则胜出，求胜出玩家的总数。

只要达到条件就胜出，并不是零和游戏。玩家与球的颜色是一对多的关系，并且需要针对每种颜色计数，判断是否存在某些颜色球的个数大于玩家编号。

使用二维数组 playerBall[i][c] 表示玩家 i 捡起颜色为 c 的球的数目，遍历 pick 数组计算 playerBall[i][c]，然后遍历 playerBall 统计胜出玩家的数目。

代码


/**
 * @date 2024-11-23 14:17
 */
public class WinningPlayerCount3238 {

    public int winningPlayerCount(int n, int[][] pick) {
        int[][] playerBall = new int[n][11];
        for (int i = 0; i < pick.length; i++) {
            // pick的i表示的是操作次数，j为0表示用户，j为1表示球的颜色
            playerBall[pick[i][0]][pick[i][1]]++;
        }
        int res = 0;
        for (int i = 0; i < playerBall.length; i++) {
            for (int j = 0; j < playerBall[i].length; j++) {
                if (playerBall[i][j] > i){
                    res++;
                    break;
                }
            }
        }
        return res;
    }
}

性能

目标

大小为 n x n 的矩阵 grid 中有一条蛇。蛇可以朝四个可能的方向移动。矩阵中的每个单元格都使用位置进行标识： grid[i][j] = (i * n) + j。

蛇从单元格 0 开始，并遵循一系列命令移动。

给你一个整数 n 表示 grid 的大小，另给你一个字符串数组 commands，其中包括 "UP"、"RIGHT"、"DOWN" 和 "LEFT"。题目测评数据保证蛇在整个移动过程中将始终位于 grid 边界内。

返回执行 commands 后蛇所停留的最终单元格的位置。

示例 1：

输入：n = 2, commands = ["RIGHT","DOWN"]
输出：3

示例 2：

输入：n = 3, commands = ["DOWN","RIGHT","UP"]
输出：1

说明：

2 <= n <= 10
1 <= commands.length <= 100
commands 仅由 "UP"、"RIGHT"、"DOWN" 和 "LEFT" 组成。
生成的测评数据确保蛇不会移动到矩阵的边界外。

思路

有一个 n x n 矩阵 grid，初始时位置 (0, 0) 有条蛇，有一系列命令可以操作蛇移到，操作保证在矩阵内移动，问蛇最后停留的位置，格子的标识为 grid[i][j] = (i * n) + j。

直接模拟操作就可以了，将操作映射为行列的增减，直接计算位置即可。

最快的解法仅比较操作的第一个字符，并且上下移动直接减加 n，最后不用乘法计算。

代码


/**
 * @date 2024-11-21 0:39
 */
public class FinalPositionOfSnake3248 {

    /**
     * 最快题解
     */
    class Solution {
        public int finalPositionOfSnake(int n, List<String> commands) {
            int ans = 0;
            for (String c : commands) {
                if (c.charAt(0) == 'U') {
                    ans -= n;
                } else if (c.charAt(0) == 'D') {
                    ans += n;
                } else if (c.charAt(0) == 'L') {
                    --ans;
                } else {
                    ++ans;
                }
            }
            return ans;
        }
    }

    public static Map<String, int[]> map = new HashMap<>(4);

    static {
        map.put("UP", new int[]{-1, 0});
        map.put("RIGHT", new int[]{0, 1});
        map.put("DOWN", new int[]{1, 0});
        map.put("LEFT", new int[]{0, -1});
    }

    public int finalPositionOfSnake(int n, List<String> commands) {
        int[] move = new int[2];
        for (String command : commands) {
            move[0] += map.get(command)[0];
            move[1] += map.get(command)[1];
        }
        return move[0] * n + move[1];
    }

}

性能

目标

图像平滑器是大小为 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;
    }

}

性能

3258.统计满足K约束的子字符串数量I

目标

给你一个二进制字符串 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;
    }

}

性能

3242.设计相邻元素求和服务

目标

给你一个 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;
        }
    }

}

2025 年 8 月
一	二	三	四	五	六	日
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31