【LeetCode】每日一题 2024_11_9 设计相邻元素求和服务（构造，哈希）

前言

每天和你一起刷 LeetCode 每日一题~

LeetCode 启动！

题目：设计相邻元素求和服务

近几天不知道力扣发什么疯，每日一题出的太抽象了，我题解是写不了一点了 . . . 今天稍微正常了些，就又来更新了~

代码与解题思路

先读题：

题目给出一个矩阵，让我们求矩阵中元素的上下左右或者对角线的和；一道比较好理解的构造题

比较方便的思路是，在构造矩阵的环节遍历矩阵的所有元素，通过哈希表将矩阵每个元素对应的上下左右以及对角线的和用 kv 的形式存储，后续需要使用的时候就能直接通过 O(1) 的复杂度查询了~

具体细节有详细的注释，代码如下：

// 前 4 个是上下左右，后 4 个是对角线
var dir = []struct{x, y int}{
    {1, 0},
    {-1, 0},
    {0, -1},
    {0, 1},
    {1, 1},
    {1, -1},
    {-1, 1},
    {-1, -1},
}

// 下标 0 保存 AdjacentSum 的 kv，下标 1 保存 DiagonalSum 的 kv
type NeighborSum [][2]int

// 初始化
func Constructor(grid [][]int) NeighborSum {
    n := len(grid)
    s := make(NeighborSum, n*n)
    // 遍历整个 grid，初始化每个元素的上下左右/对角线，对应的 kv 值
    for i, row := range grid {
        for j, value := range row {
            for k, d := range dir {
                x, y := i+d.x, j+d.y 
                if x >= 0 && x < n && y >= 0 && y < n { // 防止越界
                    // k/4：假设是前 4 个，结果就为 0，是后四个结果为 1
                    // 用于区分是上下左右还是对角线的和
                    s[value][k/4] += grid[x][y]
                }
            }
        }
    }
    return s
}

// 上下左右
func (t NeighborSum) AdjacentSum(value int) int {
    return t[value][0]
}

// 对角线
func (t NeighborSum) DiagonalSum(value int) int {
    return t[value][1]
}


/**
 * Your NeighborSum object will be instantiated and called as such:
 * obj := Constructor(grid);
 * param_1 := obj.AdjacentSum(value);
 * param_2 := obj.DiagonalSum(value);
 */

每天进步一点点，我们明天不见不散~

可以和我刷一辈子的每日一题吗？
一题一题，积累起来就是一辈子。

原文地址：https://blog.csdn.net/Locky136/article/details/143643713

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！