本题出自LeetCode每日一题3242，可以说比昨天的那道“每日抑题”简单不少呀，就是代码长一点，同时本题目使用了两种不同的方法，并对每一种用法进行了深度解析。本文全长5000字。
题目
给你一个
n x n的二维数组grid，它包含范围[0, n2 - 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 <= 100 <= grid[i][j] <= n2 - 1- 所有
grid[i][j]值均不重复。adjacentSum和diagonalSum中的value均在范围[0, n2 - 1]内。- 最多会调用
adjacentSum和diagonalSum总共2 * n2次。
解题思路
在交完代码看官方题解的时候，我发现LeetCode官方使用了哈希表，我个人认为使用暴力算法可能要“粗鲁而简单”一点，想了想索性两种思路都分享一下吧
题解
暴力算法
#include <vector>
using namespace std;
class NeighborSum {
private:
vector<int> diagonalSums;
vector<int> adjacentSums;
public:
NeighborSum(vector<vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
int maxVal = 0;
// 找出网格中的最大值，以确定 sums 向量的大小
for (const auto& row : grid) {
for (int val : row) {
maxVal = max(maxVal, val);
}
}
diagonalSums = adjacentSums = vector<int>(maxVal + 1, 0);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
for (int di = -1; di <= 1; ++di) {
for (int dj = -1; dj <= 1; ++dj) {
if (di == 0 && dj == 0) continue; // 跳过自身
int ni = i + di, nj = j + dj;
if (ni >= 0 && ni < n && nj >= 0 && nj < m) {
if (di != 0 && dj != 0) { // 对角线邻居
diagonalSums[grid[i][j]] += grid[ni][nj];
} else { // 上下左右邻居
adjacentSums[grid[i][j]] += grid[ni][nj];
}
}
}
}
}
}
}
int adjacentSum(int value) const {
return adjacentSums[value];
}
int diagonalSum(int value) const {
return diagonalSums[value];
}
};
/**
* Your NeighborSum object will be instantiated and called as such:
* NeighborSum* obj = new NeighborSum(grid);
* int param_1 = obj->adjacentSum(value);
* int param_2 = obj->diagonalSum(value);
*/代码分析
public: NeighborSum(vector<vector<int>>& grid) { int n = grid.size(); int m = grid[0].size(); int maxVal = 0;
public关键字表示接下来的成员函数可以在类外部访问。- 构造函数
NeighborSum接受一个二维整数数组grid作为参数。n和m分别表示网格的行数和列数。maxVal用于记录网格中的最大值，以便确定diagonalSums和adjacentSums向量的大小。// 找出网格中的最大值，以确定 sums 向量的大小 for (const auto& row : grid) { for (int val : row) { maxVal = max(maxVal, val); } }
- 使用嵌套的
for循环遍历整个网格，找到其中的最大值maxVal。这是为了确定diagonalSums和adjacentSums向量的大小，确保能够容纳网格中所有可能的值。diagonalSums = adjacentSums = vector<int>(maxVal + 1, 0);
- 初始化
diagonalSums和adjacentSums向量，大小为maxVal + 1，并用 0 填充。这是因为向量的索引从 0 开始，所以需要maxVal + 1个元素。for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { for (int di = -1; di <= 1; ++di) { for (int dj = -1; dj <= 1; ++dj) { if (di == 0 && dj == 0) continue; // 跳过自身
- 使用三层嵌套的
for循环遍历网格中的每一个元素。外层两个循环i和j遍历网格的行和列，内层两个循环di和dj遍历当前元素周围的 8 个方向（包括对角线方向）。if (di == 0 && dj == 0) continue;跳过当前元素本身，只处理周围的邻居。int ni = i + di, nj = j + dj; if (ni >= 0 && ni < n && nj >= 0 && nj < m) { if (di != 0 && dj != 0) { // 对角线邻居 diagonalSums[grid[i][j]] += grid[ni][nj]; } else { // 上下左右邻居 adjacentSums[grid[i][j]] += grid[ni][nj]; } } } } } }
- 计算邻居的坐标
ni和nj。- 检查邻居坐标是否在网格范围内，如果在范围内，则根据
di和dj的值判断是上下左右邻居还是对角线邻居，并相应地更新diagonalSums或adjacentSums。int adjacentSum(int value) const { return adjacentSums[value]; } int diagonalSum(int value) const { return diagonalSums[value]; } };
- 定义了两个公共成员函数
adjacentSum和diagonalSum，分别返回指定值的上下左右邻居和对角线邻居和。const关键字表示这些函数不会修改类的成员变量。
哈希表存储
由于询问时给定的是元素值而不是其在二维数组中的位置，因此在初始化时，我们可以使用一个哈希表
pos来存储每个元素所在的位置。哈希表pos中的每个键表示一个元素，对应的值是一个二元组，表示该元素在二维数组中的位置。同时，在初始化时，我们存储给定的二维数组
grid的一份拷贝。这样一来，在查询操作adjacentSum(value)和diagonalSum(value)中，我们首先通过pos获取value的位置，然后根据查询的类型，返回其四个相邻元素的和或四个对角线元素的和
#include <vector>
#include <unordered_map>
using namespace std;
class NeighborSum {
public:
NeighborSum(vector<vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
// 记录每个值在网格中的位置
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
pos[grid[i][j]] = {i, j};
}
}
// 移动语义，避免深拷贝
this->grid = move(grid);
}
int adjacentSum(int value) {
return getSum(value, 0);
}
int diagonalSum(int value) {
return getSum(value, 1);
}
private:
int getSum(int value, int idx) {
auto [x, y] = pos[value];
int ans = 0;
// 遍历邻居方向
for (const auto& dir : dirs[idx]) {
int nx = x + dir[0];
int ny = y + dir[1];
// 检查邻居是否在网格范围内
if (0 <= nx && nx < grid.size() && 0 <= ny && ny < grid[0].size()) {
ans += grid[nx][ny];
}
}
return ans;
}
vector<vector<int>> grid;
unordered_map<int, pair<int, int>> pos;
static constexpr int dirs[2][4][2] = {
{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}, // 上下左右
{{-1, -1}, {-1, 1}, {1, -1}, {1, 1}} // 对角线
};
};
/**
* Your NeighborSum object will be instantiated and called as such:
* NeighborSum* obj = new NeighborSum(grid);
* int param_1 = obj->adjacentSum(value);
* int param_2 = obj->diagonalSum(value);
*/这个方法的时间和空间复杂度简化了不少
构造函数
NeighborSum：
- 记录每个值在网格中的位置，使用
unordered_map存储。- 使用
move语义将传入的grid移动到类的成员变量中，避免深拷贝。成员函数
adjacentSum和diagonalSum：
- 这两个函数分别调用
getSum函数，传入不同的索引值来区分上下左右邻居和对角线邻居。私有成员函数
getSum：
- 从
pos中获取指定值的位置(x, y)。- 遍历
dirs中的方向数组，计算邻居的坐标(nx, ny)。- 检查邻居坐标是否在网格范围内，如果在范围内则累加邻居的值。
成员变量：
grid：存储网格数据。pos：存储每个值在网格中的位置。dirs：静态常量数组，定义了上下左右和对角线的方向。优化点
- 使用
unordered_map：记录每个值的位置，避免了额外的空间开销。- 移动语义：使用
move语义将传入的grid移动到类的成员变量中，避免了深拷贝。- 方向数组：使用
dirs数组来定义邻居方向，使代码更加简洁和易读
制作不易，您的关注与点赞是我最大的动力！
