当前位置：首页 > article >正文

LeetCode 3242.设计相邻元素求和服务：哈希表

article 2025/1/16 9:04:17

【LetMeFly】3242.设计相邻元素求和服务：哈希表

力扣题目链接：https://leetcode.cn/problems/design-neighbor-sum-service/

给你一个 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 <= 10
0 <= grid[i][j] <= n² - 1
所有 grid[i][j] 值均不重复。
adjacentSum 和 diagonalSum 中的 value 均在范围 [0, n² - 1] 内。
最多会调用 adjacentSum 和 diagonalSum 总共 2 * n² 次。

解题方法：哈希表

使用哈希表记录每个值的adjacentSum和diagonalSum，查询操作的时候直接去哈希表里查询就可以了。

时间复杂度：初始化 $O(n^2)$ 单次查询 $O (1)$
空间复杂度：初始化 $O(n^2)$ 单次查询 $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:
    vector<pair<int, int>> cache;
public:
    NeighborSum(vector<vector<int>>& 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 List

direction = [[-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 main

var direction = []struct{x, y int}{{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}}
type Value [][2]int

type NeighborSum struct {
    cache Value
}


func Constructor(grid [][]int) NeighborSum {
    n := len(grid)
    var neighborSum NeighborSum
    neighborSum.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.y
                if 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]
}