You are given an m x n
integer matrix grid
.
A rhombus sum is the sum of the elements that form the border of a regular rhombus shape in grid
. The rhombus must have the shape of a square rotated 45 degrees with each of the corners centered in a grid cell. Below is an image of four valid rhombus shapes with the corresponding colored cells that should be included in each rhombus sum:
Note that the rhombus can have an area of 0, which is depicted by the purple rhombus in the bottom right corner.
Return the biggest three distinct rhombus sums in the grid
in descending order. If there are less than three distinct values, return all of them.
Example 1:
Input: grid = [[3,4,5,1,3],[3,3,4,2,3],[20,30,200,40,10],[1,5,5,4,1],[4,3,2,2,5]] Output: [228,216,211] Explanation: The rhombus shapes for the three biggest distinct rhombus sums are depicted above. - Blue: 20 + 3 + 200 + 5 = 228 - Red: 200 + 2 + 10 + 4 = 216 - Green: 5 + 200 + 4 + 2 = 211
Example 2:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]] Output: [20,9,8] Explanation: The rhombus shapes for the three biggest distinct rhombus sums are depicted above. - Blue: 4 + 2 + 6 + 8 = 20 - Red: 9 (area 0 rhombus in the bottom right corner) - Green: 8 (area 0 rhombus in the bottom middle)
Example 3:
Input: grid = [[7,7,7]] Output: [7] Explanation: All three possible rhombus sums are the same, so return [7].
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 50
1 <= grid[i][j] <= 105
Solution: Brute Force
Just find all Rhombus…
Time complexity: O(mn*min(n,m)2)
Space complexity: O(mn*min(n,m)2)
C++
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 30 31 32 33 34 |
// Author: Huahua class Solution { public: vector<int> getBiggestThree(vector<vector<int>>& grid) { const int m = grid.size(); const int n = grid[0].size(); vector<int> ans; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) ans.push_back(grid[i][j]); for (int a = 2; a <= min(m, n); ++a) for (int cy = a - 1; cy + a <= m; ++cy) for (int cx = a - 1; cx + a <= n; ++cx) { int s = grid[cy][cx - a + 1] + grid[cy][cx + a - 1] + grid[cy + a - 1][cx] + grid[cy - a + 1][cx]; for (int i = 1; i < a - 1; ++i) s += grid[cy - i][cx - a + i + 1] + grid[cy - i][cx + a - i - 1] + grid[cy + i][cx - a + i + 1] + grid[cy + i][cx + a - i - 1]; ans.push_back(s); } sort(rbegin(ans), rend(ans)); vector<int> output; for (int x : ans) { if (output.empty() || output.back() != x) output.push_back(x); if (output.size() == 3) break; } return output; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment