网站设计哪家公司好,2021年十大购物网站排名,自己怎么做网站优化,seo课程在哪培训好【LetMeFly】3242.设计相邻元素求和服务#xff1a;哈希表
力扣题目链接#xff1a;https://leetcode.cn/problems/design-neighbor-sum-service/
给你一个 n x n 的二维数组 grid#xff0c;它包含范围 [0, n2 - 1] 内的不重复元素。
实现 neighborSum 类#xff1a;
…【LetMeFly】3242.设计相邻元素求和服务哈希表
力扣题目链接https://leetcode.cn/problems/design-neighbor-sum-service/
给你一个 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 次。
解题方法哈希表
使用哈希表记录每个值的adjacentSum和diagonalSum查询操作的时候直接去哈希表里查询就可以了。
时间复杂度初始化 O ( n 2 ) O(n^2) O(n2)单次查询 O ( 1 ) O(1) O(1)空间复杂度初始化 O ( n 2 ) O(n^2) O(n2)单次查询 O ( 1 ) O(1) O(1)
AC代码
C
const int adj[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
const int dia[4][2] {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};class NeighborSum {
private:vectorpairint, int cache;
public:NeighborSum(vectorvectorint grid) {int n grid.size();cache.resize(n * n);for (int i 0; i n; i) {for (int j 0; j n; j) {int cntAdj 0, cntDia 0;for (int k 0; k 4; k) {int x i adj[k][0], y j adj[k][1];if (x 0 x n y 0 y n) {cntAdj grid[x][y];}x i dia[k][0], y j dia[k][1];if (x 0 x n y 0 y n) {cntDia grid[x][y];}}cache[grid[i][j]] {cntAdj, cntDia};}}}int adjacentSum(int value) {return cache[value].first;}int diagonalSum(int value) {return cache[value].second;}
};Python
from typing import Listdirection [[-1, 0], [1, 0], [0, -1], [0, 1], [-1, -1], [1, 1], [-1, 1], [1, -1]]class NeighborSum:def __init__(self, grid: List[List[int]]):n len(grid)self.cache [[0, 0] for _ in range(n * n)]for i in range(n):for j in range(n):for th, (x, y) in enumerate(direction):if 0 x i n and 0 y j n:self.cache[grid[i][j]][th // 4] grid[x i][y j]def adjacentSum(self, value: int) - int:return self.cache[value][0]def diagonalSum(self, value: int) - int:return self.cache[value][1]Java
class NeighborSum {private static final int[][] direction {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};private int[][] cache;public NeighborSum(int[][] grid) {int n grid.length;cache new int[n * n][2];for (int i 0; i n; i) {for (int j 0; j n; j) {for (int k 0; k 8; k) {int x i direction[k][0], y j direction[k][1];if (x 0 x n y 0 y n) {cache[grid[i][j]][k / 4] grid[x][y];}}}}}public int adjacentSum(int value) {return cache[value][0];}public int diagonalSum(int value) {return cache[value][1];}
}Go
package mainvar direction []struct{x, y int}{{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}}
type Value [][2]inttype NeighborSum struct {cache Value
}func Constructor(grid [][]int) NeighborSum {n : len(grid)var neighborSum NeighborSumneighborSum.cache make(Value, n * n)for i, row : range grid {for j, v : range row {for k, d : range direction {x, y : i d.x, j d.yif x 0 x n y 0 y n {neighborSum.cache[v][k / 4] grid[x][y]}}}}return neighborSum
}func (this *NeighborSum) AdjacentSum(value int) int {return this.cache[value][0]
}func (this *NeighborSum) DiagonalSum(value int) int {return this.cache[value][1]
}同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/143698347
