| comments | difficulty | edit_url | rating | source | tags | |||||
|---|---|---|---|---|---|---|---|---|---|---|
true |
简单 |
1334 |
第 409 场周赛 Q1 |
|
给你一个 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次。
我们可以用一个哈希表
时间复杂度方面，初始化哈希表的时间复杂度为
class NeighborSum:
def __init__(self, grid: List[List[int]]):
self.grid = grid
self.d = {}
self.dirs = ((-1, 0, 1, 0, -1), (-1, 1, 1, -1, -1))
for i, row in enumerate(grid):
for j, x in enumerate(row):
self.d[x] = (i, j)
def adjacentSum(self, value: int) -> int:
return self.cal(value, 0)
def cal(self, value: int, k: int):
i, j = self.d[value]
s = 0
for a, b in pairwise(self.dirs[k]):
x, y = i + a, j + b
if 0 <= x < len(self.grid) and 0 <= y < len(self.grid[0]):
s += self.grid[x][y]
return s
def diagonalSum(self, value: int) -> int:
return self.cal(value, 1)
# Your NeighborSum object will be instantiated and called as such:
# obj = NeighborSum(grid)
# param_1 = obj.adjacentSum(value)
# param_2 = obj.diagonalSum(value)class NeighborSum {
private int[][] grid;
private final Map<Integer, int[]> d = new HashMap<>();
private final int[][] dirs = {{-1, 0, 1, 0, -1}, {-1, 1, 1, -1, -1}};
public NeighborSum(int[][] grid) {
this.grid = grid;
int m = grid.length, n = grid[0].length;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
d.put(grid[i][j], new int[] {i, j});
}
}
}
public int adjacentSum(int value) {
return cal(value, 0);
}
public int diagonalSum(int value) {
return cal(value, 1);
}
private int cal(int value, int k) {
int[] p = d.get(value);
int s = 0;
for (int q = 0; q < 4; ++q) {
int x = p[0] + dirs[k][q], y = p[1] + dirs[k][q + 1];
if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length) {
s += grid[x][y];
}
}
return s;
}
}
/**
* 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);
*/class NeighborSum {
public:
NeighborSum(vector<vector<int>>& grid) {
this->grid = grid;
int m = grid.size(), n = grid[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
d[grid[i][j]] = {i, j};
}
}
}
int adjacentSum(int value) {
return cal(value, 0);
}
int diagonalSum(int value) {
return cal(value, 1);
}
private:
vector<vector<int>> grid;
unordered_map<int, pair<int, int>> d;
int dirs[2][5] = {{-1, 0, 1, 0, -1}, {-1, 1, 1, -1, -1}};
int cal(int value, int k) {
auto [i, j] = d[value];
int s = 0;
for (int q = 0; q < 4; ++q) {
int x = i + dirs[k][q], y = j + dirs[k][q + 1];
if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size()) {
s += grid[x][y];
}
}
return s;
}
};
/**
* 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);
*/type NeighborSum struct {
grid [][]int
d map[int][2]int
dirs [2][5]int
}
func Constructor(grid [][]int) NeighborSum {
d := map[int][2]int{}
for i, row := range grid {
for j, x := range row {
d[x] = [2]int{i, j}
}
}
dirs := [2][5]int{{-1, 0, 1, 0, -1}, {-1, 1, 1, -1, -1}}
return NeighborSum{grid, d, dirs}
}
func (this *NeighborSum) AdjacentSum(value int) int {
return this.cal(value, 0)
}
func (this *NeighborSum) DiagonalSum(value int) int {
return this.cal(value, 1)
}
func (this *NeighborSum) cal(value, k int) int {
p := this.d[value]
s := 0
for q := 0; q < 4; q++ {
x, y := p[0]+this.dirs[k][q], p[1]+this.dirs[k][q+1]
if x >= 0 && x < len(this.grid) && y >= 0 && y < len(this.grid[0]) {
s += this.grid[x][y]
}
}
return s
}
/**
* Your NeighborSum object will be instantiated and called as such:
* obj := Constructor(grid);
* param_1 := obj.AdjacentSum(value);
* param_2 := obj.DiagonalSum(value);
*/class NeighborSum {
private grid: number[][];
private d: Map<number, [number, number]> = new Map();
private dirs: number[][] = [
[-1, 0, 1, 0, -1],
[-1, 1, 1, -1, -1],
];
constructor(grid: number[][]) {
for (let i = 0; i < grid.length; ++i) {
for (let j = 0; j < grid[0].length; ++j) {
this.d.set(grid[i][j], [i, j]);
}
}
this.grid = grid;
}
adjacentSum(value: number): number {
return this.cal(value, 0);
}
diagonalSum(value: number): number {
return this.cal(value, 1);
}
cal(value: number, k: number): number {
const [i, j] = this.d.get(value)!;
let s = 0;
for (let q = 0; q < 4; ++q) {
const [x, y] = [i + this.dirs[k][q], j + this.dirs[k][q + 1]];
if (x >= 0 && x < this.grid.length && y >= 0 && y < this.grid[0].length) {
s += this.grid[x][y];
}
}
return s;
}
}
/**
* Your NeighborSum object will be instantiated and called as such:
* var obj = new NeighborSum(grid)
* var param_1 = obj.adjacentSum(value)
* var param_2 = obj.diagonalSum(value)
*/