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

Leetcode刷题Python之3242.设计相邻元素求和服务

news 2025/2/21 3:36:01

提示：题目不难，细心读题。

文章目录

一、题目描述
- 示例
二、解题思路
三、代码实现
- 代码解析
总结

一、题目描述

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

实现 neighborSum 类：
1.neighborSum(int [ ][ ]grid) 初始化对象。

2.int adjacentSum(int value) 返回在 grid 中与 value 相邻的元素之和，相邻指的是与 value 在上、左、右或下的元素。

3.int diagonalSum(int value) 返回在 grid 中与 value 对角线相邻的元素之和，对角线相邻指的是与 value 在左上、右上、左下或右下的元素。

示例

grid = [[0, 1, 2],[3, 4, 5],[6, 7, 8]
]
obj = NeighborSum(grid)
print(obj.adjacentSum(1))  # 输出: 6
print(obj.adjacentSum(4))  # 输出: 16
print(obj.diagonalSum(4))  # 输出: 16
print(obj.diagonalSum(8))  # 输出: 4

grid = [[1, 2, 0, 3],[4, 7, 15, 6],[8, 9, 10, 11],[12, 13, 14, 5]
]
obj = NeighborSum(grid)
print(obj.adjacentSum(15))  # 输出: 23
print(obj.diagonalSum(9))   # 输出: 45

二、解题思路

要实现这个类，我们首先需要解决两个核心问题：

1.如何找到指定元素的坐标位置：由于数组中的元素都是不重复的整数，我们可以在初始化时创建一个哈希表（字典），将每个元素的值映射到它在二维数组中的坐标位置，以实现快速查找。

2.如何计算相邻元素和对角线相邻元素之和：根据题意，相邻方向包括上下左右四个方向，对角线方向则包括左上、右上、左下、右下四个方向。我们可以利用这些方向的坐标偏移量来判断坐标边界，从而计算元素的相邻元素和对角线相邻元素之和。

三、代码实现

代码如下：

class NeighborSum(object):def __init__(self, grid):""":type grid: List[List[int]]"""# 存储 grid 以及每个元素值到其坐标位置的映射self.grid = gridself.pos = {}# 遍历二维数组，构建每个值到坐标位置的字典映射for i in range(len(grid)):for j in range(len(grid[0])):self.pos[grid[i][j]] = (i, j)def adjacentSum(self, value):""":type value: int:rtype: int"""# 检查是否存在该值if value not in self.pos:return 0# 获取值的坐标x, y = self.pos[value]# 定义相邻的四个方向：上、下、左、右directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]adj_sum = 0# 遍历四个方向，检查是否越界并求和for dx, dy in directions:nx, ny = x + dx, y + dyif 0 <= nx < len(self.grid) and 0 <= ny < len(self.grid[0]):adj_sum += self.grid[nx][ny]return adj_sumdef diagonalSum(self, value):""":type value: int:rtype: int"""# 检查是否存在该值if value not in self.pos:return 0# 获取值的坐标x, y = self.pos[value]# 定义对角线的四个方向：左上、右上、左下、右下directions = [(-1, -1), (-1, 1), (1, -1), (1, 1)]diag_sum = 0# 遍历四个方向，检查是否越界并求和for dx, dy in directions:nx, ny = x + dx, y + dyif 0 <= nx < len(self.grid) and 0 <= ny < len(self.grid[0]):diag_sum += self.grid[nx][ny]return diag_sum