跳转至

3242. 设计相邻元素求和服务

#python #leetcode

题目描述

关联：https://leetcode.cn/problems/design-neighbor-sum-service/description/

题目描述

给你一个 n x n 的二维数组 grid，它包含范围 [0, n^2 - 1] 内的不重复元素。

实现 neighborSum 类：

  • neighborSum(int [][]grid) 初始化对象。
  • int adjacentSum(int value) 返回在 grid 中与 value 相邻的元素之和，相邻指的是与 value 在上、左、右或下的元素。
  • int diagonalSum(int value) 返回在 grid 中与 value 对角线相邻的元素之和，对角线相邻指的是与 value 在左上、右上、左下或右下的元素。

design

它给出的 Python 的 ADT 为：

class NeighborSum:

    def __init__(self, grid: list[list[int]]):
        ...

    def adjacentSum(self, value: int) -> int:
        ...

    def diagonalSum(self, value: int) -> int:
        ...


# Your NeighborSum object will be instantiated and called as such:
# obj = NeighborSum(grid)
# param_1 = obj.adjacentSum(value)
# param_2 = obj.diagonalSum(value)

交互题的样例 I/O 有点抽象，建议看原题。

\(3 \leq n = \text{grid.length} = \text{grid}[0].\text{length} \leq 10\)

\(0 \leq \text{grid}[i][j] \leq n^2 - 1\)

所有 \(\text{grid}[i][j]\) 值均不重复。

\(\text{adjacentSum}\) 和 \(\text{diagonalSum}\) 中的 \(\text{value}\) 均在范围 \([0, n^2 - 1]\) 内。

最多会调用 \(\text{adjacentSum}\) 和 \(\text{diagonalSum}\) 总共 \(2 \times n^2\) 次。

解题思路

简单交互题直接模拟就行

class NeighborSum:

    def __init__(self, grid: list[list[int]]):
        self.grid = grid
        self.n = len(grid)
        self.value_to_pos = {}
        for i in range(self.n):
            for j in range(self.n):
                self.value_to_pos[grid[i][j]] = (i, j)

    def adjacentSum(self, value: int) -> int:
        x, y = self.value_to_pos[value]
        return sum(
            self.grid[i][j] 
            for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]
            if 0 <= i < self.n and 0 <= j < self.n
        )

    def diagonalSum(self, value: int) -> int:
        x, y = self.value_to_pos[value]
        return sum(
            self.grid[i][j] 
            for i, j in [(x - 1, y - 1), (x - 1, y + 1), (x + 1, y - 1), (x + 1, y + 1)]
            if 0 <= i < self.n and 0 <= j < self.n
        )

复杂度分析

  • 对于初始化：
    • 时间复杂度 \(O(n^2)\)
    • 空间复杂度 \(O(n^2)\)
  • 对于 adjacentSum() 和 diagonalSum()：
    • 时间复杂度 \(O(1)\)
    • 空间复杂度 \(O(1)\)

评论