Re: [閒聊] 每日leetcode

看板Marginalman作者sixB (6B)時間1年前 (2024/10/27 23:50)推噓0(0推 0噓 1→)

※ 引述《dont (dont)》之銘言： : 1277. Count Square Submatrices with All Ones 我覺得我的解法超酷酷一半後面找的有點醜要跳過的話也很醜== ## 查區域不用更新把mat做成prefix sum 然後slide window 國小數學算面積 class Solution { public: int countSquares(vector<vector<int>>& mat) { int m = mat.size(), n = mat[0].size(); int cnt = 0; // row: prefix sum from left to right for(int i = 0; i < m; i++){ cnt += mat[i][0]; for(int j = 1; j < n; j++){ cnt += mat[i][j]; mat[i][j] += mat[i][j-1]; } } // col prefix sum for(int j = 0; j < n; j++){ for(int i = 1; i < m; i++){ mat[i][j] += mat[i-1][j]; } } int sq = min(m, n); for(int len = 2; len <= sq; len++){ for(int i = 0; i <= m - len; i++){ for(int j = 0; j <= n - len; j++){ //cout << i << " " << j << " \n"; cnt += check(i, j, len, mat); } } } return cnt; } bool check(int x, int y, int len, vector<vector<int>>& mat){ x--; y--; int total = mat[x+len][y+len]; if(x >= 0) total -= mat[x][y+len]; if(y >= 0) total -= mat[x+len][y]; if(x >= 0 and y >= 0) total += mat[x][y]; return (len * len) == total; } }; 想得到dp解好厲害ㄛ== 太聰明了吧我一開始還看不懂 -- 很姆的咪姆之咪 http://i.imgur.com/5sw7QOj.jpg