Re: [閒聊] 每日leetcode

看板Marginalman作者DJYOSHITAKA (franchouchouISBEST)時間1年前 (2024/08/10 12:39)推噓4(4推 0噓 2→)

留言6則, 6人參與討論串690/1548 (看更多)

想了一下怎麼定義union-find的node 我是笨笨的想到先把一個block切成四分因為我也不知道哪裡會是\哪裡會是/ 大概像這樣編排 https://i.imgur.com/fzFpHwv.png

(n=2) 第一次union find先把虛線部分給union起來每個block跟右與下的block做，加上boundary check 第二次union find再去做題目給的slash部分 " "的話就(0,1,2,3)union起來 "\"的話就(0,1) (2,3)各自union "/"的話就(0,3) (1,2)各自union 第一次union那邊boundary check寫的有點醜就是了應該可以更簡單== 好久沒用C++了最近來回鍋一下好了 class Solution { public: int unionfind(vector<int>& parent, int n1, int n2){ int r1 = parent[n1]; while (r1 != parent[r1]) { r1 = parent[r1]; } int r2 = parent[n2]; while (r2 != parent[r2]) { r2 = parent[r2]; } if(r2 != r1) { parent[r2] = r1; return 1; } else { return 0; } } int regionsBySlashes(vector<string>& grid) { int n = grid.size(); int len = n*n*4; int ans = len; vector<int> parent(len); // init for(int i=0; i<len; i++) { parent[i] = i; } // union find 1 for(int i=0; i<len; i+=4){ // check right if (((i/4)+1)%n != 0) { ans -= unionfind(parent, i+1, i+7); } // check bottom if ((i+4*n) < len) { ans -= unionfind(parent, i+2, i+4*n); } } // union find 2 for(int i=0; i<n; i++) { for(int j=0; j<n; j++){ int idx = 4*(i*n+j); if (grid[i][j] == ' ') { ans -= unionfind(parent, idx, idx+1); ans -= unionfind(parent, idx, idx+2); ans -= unionfind(parent, idx, idx+3); } else if (grid[i][j] == '\\') { ans -= unionfind(parent, idx, idx+1); ans -= unionfind(parent, idx+2, idx+3); } else if (grid[i][j] == '/') { ans -= unionfind(parent, idx, idx+3); ans -= unionfind(parent, idx+1, idx+2); } } } return ans; } }; -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.228.146.144 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723264783.A.004.html

推

JIWP

08/10 12:40, 1年前 , 1^F

08/10 12:40, 1^F

→

rainkaras

08/10 12:45, 1年前 , 2^F

08/10 12:45, 2^F

推

sustainer123

08/10 12:48, 1年前 , 3^F

08/10 12:48, 3^F