力扣每日一题 3242. 设计相邻元素求和服务

给你一个 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 在左上、右上、左下或右下的元素。

今天这题目确实简单，因为数据范围极小，所以只要按照题目要求去模拟就可以了。

不过我选择了把数据进行预处理，开了一个数组存每个元素的相邻和与对角和。在构造函数里就遍历一遍把答案算出来，后面两个查询函数就直接返回答案就可以了。

class NeighborSum {
public:
    int getAdj(vector<vector<int>>& grid, int n, int x, int y)
    {
        int sum=0;
        if (x-1>-1) sum+=grid[x-1][y];
        if (x+1<n) sum+=grid[x+1][y];
        if (y-1>-1) sum+=grid[x][y-1];
        if (y+1<n) sum+=grid[x][y+1];
        return sum; 
    }
    int getDia(vector<vector<int>>& grid, int n, int x, int y)
    {
        int sum=0;
        if (x-1>-1)
        {
            if (y-1>-1) sum+=grid[x-1][y-1];
            if (y+1<n) sum+=grid[x-1][y+1];
        }
        if (x+1<n)
        {
            if (y-1>-1) sum+=grid[x+1][y-1];
            if (y+1<n) sum+=grid[x+1][y+1];
        }
        return sum;
    }
    vector<pair<int, int> > ans; // first=adjacentSum, second=diagonalSum
    NeighborSum(vector<vector<int>>& grid) {
        int n = grid.size();
        ans.resize(n*n);
        for (int i=0; i<n; ++i)
        {
            for (int j=0; j<n; ++j)
            {
                ans[grid[i][j]]=make_pair(getAdj(grid, n, i, j), getDia(grid, n, i, j));
            }
        }
    }
    
    int adjacentSum(int value) {
        return ans[value].first;
    }
    
    int diagonalSum(int value) {
        return ans[value].second;
    }
    
};

/**
 * Your NeighborSum object will be instantiated and called as such:
 * NeighborSum* obj = new NeighborSum(grid);
 * int param_1 = obj->adjacentSum(value);
 * int param_2 = obj->diagonalSum(value);
 */

构造函数的时间复杂度O(n*n),两个查询的函数的时间复杂度O(1)。

空间复杂度O(n*n)。

也可以直接把构造函数的参数存起来，然后在查询的函数里找元素位置再计算。要省时间的话，还可以再开个哈希表把元素值和位置做个映射，虽然以这个题来说完全没有必要

原文地址：https://blog.csdn.net/qq_41529799/article/details/143637524

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