青铜 Brute Force：每次需要花费O(n*n)的时间去查找query所在的格子，求和是O(1)。总的时间复杂度达到O(n^4)，肯定会超时。
白银 Hashtable：由于所有元素的值的唯一的，我们可以使用hashtable（或者数组）来记录value所在的格子坐标，这样每次Query都是O(1)时间。
时间复杂度：初始化O(n^2)，query O(1)。
空间复杂度：O(n^2)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
class NeighborSum { public: NeighborSum(vector<vector<int>>& grid): n_(grid.size()), g_(&grid), xy_(n_ * n_) { for (int i = 0; i < n_; ++i) for (int j = 0; j < n_; ++j) xy_[grid[i][j]] = {j, i}; } int adjacentSum(int value) { auto [x, y] = xy_[value]; return val(x, y - 1) + val(x, y + 1) + val(x + 1, y) + val(x - 1, y); } int diagonalSum(int value) { auto [x, y] = xy_[value]; return val(x - 1, y - 1) + val(x - 1, y + 1) + val(x + 1, y - 1) + val(x + 1, y + 1); } private: inline int val(int x, int y) const { if (x < 0 || x >= n_ || y < 0 || y >= n_) return 0; return (*g_)[y][x]; } int n_; vector<vector<int>>* g_; vector<pair<int, int>> xy_; }; |
黄金 Precompute：在初始化的时候顺便求合，开两个数组一个存上下左右的，一个存对角线的。query的时候直接返回答案就可以了。
时间复杂度和白银是一样的，但会快一些（省去了求合的过程）。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
class NeighborSum { public: NeighborSum(vector<vector<int>>& grid) { int n = grid.size(); adj_.resize(n * n); dia_.resize(n * n); auto v = [&](int x, int y) -> int { if (x < 0 || x >= n || y < 0 || y >= n) return 0; return grid[y][x]; }; for (int y = 0; y < n; ++y) for (int x = 0; x < n; ++x) { adj_[grid[y][x]] = v(x, y - 1) + v(x, y + 1) + v(x + 1, y) + v(x - 1, y); dia_[grid[y][x]] = v(x - 1, y - 1) + v(x - 1, y + 1) + v(x + 1, y - 1) + v(x + 1, y + 1); } } int adjacentSum(int value) { return adj_[value]; } int diagonalSum(int value) { return dia_[value]; } private: vector<int> adj_; vector<int> dia_; }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment