Re: [閒聊] 每日leetcode

[sixB (6B)]

1504.

我昨天寫正方形也是先看到n < 300

直接開3個loop


class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        vector<int> cnt(n, 0);
        int res = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(mat[i][j] == 0){
                    cnt[j] = 0;
                    continue;
                }
                cnt[j]++;
                int bound = cnt[j];
                for(int k = j; k >= 0 and bound > 0; k--){
                    bound = min(bound, cnt[k]);
                    res += bound;
                }
            }
        }
        return res;
    }
};
-----
Sent from JPTT on my iPad

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.135.99.218 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1755798077.A.D25.html
推 deatheo: 大師
推 JIWP: 別捲了
推 moumoon5566: 第9行 代數錯了
→ minisung: O(mn)解呢
推 davie11333: 別卷惹