Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者oin1104 (是oin的說)時間1年前 (2024/01/28 17:05)推噓1(1推 0噓 6→)

留言7則, 3人參與討論串624/719 (看更多)

今天是問在一個2d的陣列裡面有多少個子陣列加起來==target 我用prefix sum做的然後我剛剛看好像可以用hashmap加上去做好扯喔 class Solution { public: int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) { int ans = 0; vector<vector<int>> summat ; summat = matrix; int n = matrix[0].size(); int m = matrix.size(); for(int i = 1 ; i < n ; i ++) { summat[0][i] += summat[0][i-1]; } for(int i = 1 ; i < m ; i ++) { summat[i][0] += summat[i-1][0]; } for(int i = 1 ; i < m ; i ++) { for(int j = 1 ; j < n ; j ++) { summat[i][j] = summat[i][j] + summat[i-1][j] + summat[i][j-1] - summat[i-1][j-1]; } } for(int na = 0 ; na < n ; na ++) { for(int ma = 0 ; ma < m ; ma ++) { for(int nb = na ; nb < n ; nb ++) { for(int mb = ma ; mb < m ; mb ++) { int k = 0 ; if((na > 0)&&(ma > 0)) { k = summat[mb][nb] - summat[mb][na-1] - summat[ma-1] [nb] + summat[ma-1][na-1]; } else if(na > 0) { k = summat[mb][nb] - summat[mb][na-1] ; } else if(ma > 0) { k = summat[mb][nb] - summat[ma-1][nb] ; } else { k = summat[mb][nb] ; } if(k == target) ans ++; } } } } return ans; } }; -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.0.147 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1706432707.A.3C0.html

推

wu10200512

01/28 17:06, 1年前 , 1^F

01/28 17:06, 1^F

→

wu10200512

01/28 17:06, 1年前 , 2^F

01/28 17:06, 2^F

→

oin1104

01/28 17:06, 1年前 , 3^F

01/28 17:06, 3^F