Re: [閒聊] 每日leetcode

看板Marginalman作者sustainer123 (caster )時間2周前 (2024/04/20 19:58)推噓3(3推 0噓 1→)

留言4則, 4人參與討論串139/184 (看更多)

※ 引述《JIWP (神楽めあ的錢包)》之銘言： : 1992. Find All Groups of Farmland : 有一塊m*n的土地 : 1代表農地、0代表森林 : 且農地根森林一定是矩形 : 請找出所有農地的左上座標和右上座標 : 思路 : : 農地右下的座標其x、y一定是整塊農地裡最大的值 : 從上到下、從左到右去遍歷整塊土地 : 當遇到1就進到dfs函式 : dfs函式裡面就是把land[i][j]變成0 : 並且不斷找最大的x,y : 這樣就可以找到答案了 : 然後不用4個方向都去找 : 只要找右邊、下面就可以遍歷完整個農地了 : golang code: : var r, c int : func findFarmland(land [][]int) [][]int { : r = len(land) : c = len(land[0]) : ans := make([][]int, 0) : for i := 0; i < r; i++ { : for j := 0; j < c; j++ { : if land[i][j] == 1 { : temp := []int{i, j, 0, 0} : find(&land, i, j, &temp) : ans = append(ans, temp) : } : } : } : return ans : } : func find(land *[][]int, i, j int, temp *[]int) { : if i < r && j < c && (*land)[i][j] == 1 { : (*land)[i][j] = 0 : (*temp)[2] = max((*temp)[2], i) : (*temp)[3] = max((*temp)[3], j) : find(land, i, j+1, temp) : find(land, i+1, j, temp) : } : } 思路: 遍歷整個list 遇到1就dfs 因為右下角必然是整個矩形的最大值用max()找到最大值就可以得到答案 Python Code: class Solution: def findFarmland(self, land: List[List[int]]) -> List[List[int]]: def dfs(x,y): dx = [1,0] dy = [0,1] for i in range(2): new_x = x + dx[i] new_y = y + dy[i] if new_x>=0 and new_x<m and new_y>=0 and new_y<n and land[new_y][new_x] == 1: land[new_y][new_x] = 0 result[-1][2] = max(result[-1][2],new_y) result[-1][3] = max(result[-1][3],new_x) dfs(new_x,new_y) result = [] n,m = len(land),len(land[0]) for i in range(n): for j in range(m): if land[i][j] == 1: result.append([i,j,i,j]) land[i][j] = 0 dfs(j,i) return result -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.43.137.148 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1713614283.A.02B.html

推

digua

04/20 19:58, 2周前 , 1^F

04/20 19:58, 1^F

推

oinishere

04/20 19:59, 2周前 , 2^F

04/20 19:59, 2^F

→

DJYOSHITAKA

04/20 20:02, 1周前 , 3^F

04/20 20:02, 3^F