Easy
题目描述
给你一个 n x n 的二维数组 grid，其中包含范围 [0, n² - 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] <= n² - 1- 所有
grid[i][j]都是不同的。 adjacentSum和diagonalSum中的value在范围[0, n² - 1]内。- 最多调用
adjacentSum和diagonalSum总共2 * n²次。
解题思路
这道题要求设计一个数据结构来快速查询网格中某个值的相邻元素和对角元素的和。
解题思路
方法1：暴力查找 每次查询时遍历整个网格找到目标值的位置，然后计算邻居和。时间复杂度为O(n²)。
方法2：哈希表预处理（推荐） 在初始化时预处理所有元素的位置信息，使用哈希表存储每个值对应的坐标。这样查询时只需要O(1)时间找到位置，然后计算邻居和。
方法3：预计算所有和 在初始化时预计算每个值的相邻和与对角和，存储在哈希表中。这样查询时直接返回结果，时间复杂度为O(1)。
实现细节
我们采用方法3，预计算所有结果：
- 遍历网格，为每个位置计算相邻元素和与对角元素和
- 使用两个哈希表分别存储每个值的相邻和与对角和
- 定义方向数组简化邻居位置计算
- 查询时直接从哈希表返回结果
相邻方向：上下左右四个方向 [(0,1), (0,-1), (1,0), (-1,0)]
对角方向：四个对角方向 [(1,1), (1,-1), (-1,1), (-1,-1)]
代码实现
class NeighborSum {
private:
unordered_map<int, int> adjacentSums;
unordered_map<int, int> diagonalSums;
public:
NeighborSum(vector<vector<int>>& grid) {
int n = grid.size();
vector<vector<int>> adjacentDirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vector<vector<int>> diagonalDirs = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int value = grid[i][j];
// 计算相邻和
int adjSum = 0;
for (auto& dir : adjacentDirs) {
int ni = i + dir[0], nj = j + dir[1];
if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
adjSum += grid[ni][nj];
}
}
adjacentSums[value] = adjSum;
// 计算对角和
int diagSum = 0;
for (auto& dir : diagonalDirs) {
int ni = i + dir[0], nj = j + dir[1];
if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
diagSum += grid[ni][nj];
}
}
diagonalSums[value] = diagSum;
}
}
}
int adjacentSum(int value) {
return adjacentSums[value];
}
int diagonalSum(int value) {
return diagonalSums[value];
}
};
class NeighborSum:
def __init__(self, grid: List[List[int]]):
n = len(grid)
self.adjacent_sums = {}
self.diagonal_sums = {}
adjacent_dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
diagonal_dirs = [(1, 1), (1, -1), (-1, 1), (-1, -1)]
for i in range(n):
for j in range(n):
value = grid[i][j]
# 计算相邻和
adj_sum = 0
for di, dj in adjacent_dirs:
ni, nj = i + di, j + dj
if 0 <= ni < n and 0 <= nj < n:
adj_sum += grid[ni][nj]
self.adjacent_sums[value] = adj_sum
# 计算对角和
diag_sum = 0
for di, dj in diagonal_dirs:
ni, nj = i + di, j + dj
if 0 <= ni < n and 0 <= nj < n:
diag_sum += grid[ni][nj]
self.diagonal_sums[value] = diag_sum
def adjacentSum(self, value: int) -> int:
return self.adjacent_sums[value]
def diagonalSum(self, value: int) -> int:
return self.diagonal_sums[value]
public class NeighborSum {
private Dictionary<int, int> adjacentSums;
private Dictionary<int, int> diagonalSums;
public NeighborSum(int[][] grid) {
int n = grid.Length;
adjacentSums = new Dictionary<int, int>();
diagonalSums = new Dictionary<int, int>();
int[,] adjacentDirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int[,] diagonalDirs = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int value = grid[i][j];
// 计算相邻和
int adjSum = 0;
for (int k = 0; k < 4; k++) {
int ni = i + adjacentDirs[k, 0];
int nj = j + adjacentDirs[k, 1];
if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
adjSum += grid[ni][nj];
}
}
adjacentSums[value] = adjSum;
// 计算对角和
int diagSum = 0;
for (int k = 0; k < 4; k++) {
int ni = i + diagonalDirs[k, 0];
int nj = j + diagonalDirs[k, 1];
if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
diagSum += grid[ni][nj];
}
}
diagonalSums[value] = diagSum;
}
}
}
public int AdjacentSum(int value) {
return adjacentSums[value];
}
public int DiagonalSum(int value) {
return diagonalSums[value];
}
}
var NeighborSum = function(grid) {
const n = grid.length;
this.adjacentSums = new Map();
this.diagonalSums = new Map();
const adjacentDirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];
const diagonalDirs = [[1, 1], [1, -1], [-1, 1], [-1, -1]];
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
const value = grid[i][j];
// 计算相邻和
let adjSum = 0;
for (const [di, dj] of adjacentDirs) {
const ni = i + di, nj = j + dj;
if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
adjSum += grid[ni][nj];
}
}
this.adjacentSums.set(value, adjSum);
// 计算对角和
let diagSum = 0;
for (const [di, dj] of diagonalDirs) {
const ni = i + di, nj = j + dj;
if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
diagSum += grid[ni][nj];
}
}
this.diagonalSums.set(value, diagSum);
}
}
};
NeighborSum.prototype.adjacentSum = function(value) {
return this.adjacentSums.get(value);
};
NeighborSum.prototype.diagonalSum = function(value) {
return this.diagonalSums.get(value);
};
复杂度分析
| 复杂度类型 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 初始化 | O(n²) | O(n²) |
| adjacentSum | O(1) | O(1) |
| diagonalSum | O(1) | O(1) |
- 初始化时需要遍历整个 n×n 网格，时间复杂度为 O(n²)
- 空间复杂度为 O(n²)，用于存储两个哈希表
- 查询操作都是 O(1) 时间复杂度的哈希表查找