Re: [閒聊] 每日leetcode

看板Marginalman作者JIWP (神楽めあ的錢包)時間3月前 (2025/08/23 23:36)推噓0(0推 0噓 0→)

3197. Find the Minimum Area to Cover All Ones II 思路 : 就切切切先切成兩個矩形再把其中一個矩形切成另外兩個矩形看最小的三個矩形面積是多少然後可以水平切或是垂直切切切切切切切切切切切切因為題目限制邊長不超過30 就暴力解救好 golang code : func minimumSum(grid [][]int) int { n, m := len(grid), len(grid[0]) ans := math.MaxInt64 for i := 0; i < n; i++ { area1, area2, cutPos := minimumArea(grid, 0, i, 0, m), minimumArea(grid, i, n, 0, m), i tmp := [4][3]int{} tmp[0] = twoRectangleH(grid, 0, cutPos, 0, m) //area1水平切 tmp[1] = twoRectangleV(grid, 0, cutPos, 0, m) //area1垂直切 tmp[2] = twoRectangleH(grid, cutPos, n, 0, m) //area2水平切 tmp[3] = twoRectangleV(grid, cutPos, n, 0, m) //area2垂直切 ans = min(ans, area2+tmp[0][0]+tmp[0][1]) ans = min(ans, area2+tmp[1][0]+tmp[1][1]) ans = min(ans, area1+tmp[2][0]+tmp[2][1]) ans = min(ans, area1+tmp[3][0]+tmp[3][1]) } for i := 0; i < m; i++ { area1, area2, cutPos := minimumArea(grid, 0, n, 0, i), minimumArea(grid, 0, n, i, m), i tmp := [4][3]int{} tmp[0] = twoRectangleH(grid, 0, n, 0, cutPos) //area3水平切 tmp[1] = twoRectangleV(grid, 0, n, 0, cutPos) //area3垂直切 tmp[2] = twoRectangleH(grid, 0, n, cutPos, m) //area4水平切 tmp[3] = twoRectangleV(grid, 0, n, cutPos, m) //area4垂直切 ans = min(ans, area2+tmp[0][0]+tmp[0][1]) ans = min(ans, area2+tmp[1][0]+tmp[1][1]) ans = min(ans, area1+tmp[2][0]+tmp[2][1]) ans = min(ans, area1+tmp[3][0]+tmp[3][1]) } return ans } func twoRectangleV(grid [][]int, n1, n2, m1, m2 int) [3]int { minArea, area1, area2, c := math.MaxInt64, 0, 0, -1 // 垂直切 for j := m1; j < m2; j++ { left := minimumArea(grid, n1, n2, m1, j) right := minimumArea(grid, n1, n2, j, m2) tmp := left + right if tmp <= minArea { area1, area2 = left, right minArea = tmp c = j } } return [3]int{area1, area2, c} } func twoRectangleH(grid [][]int, n1, n2, m1, m2 int) [3]int { minArea, area1, area2, r := math.MaxInt64, 0, 0, -1 // 水平切 for i := n1; i < n2; i++ { up := minimumArea(grid, n1, i, m1, m2) down := minimumArea(grid, i, n2, m1, m2) tmp := up + down if tmp <= minArea { area1, area2 = up, down minArea = tmp r = i } } return [3]int{area1, area2, r} } func minimumArea(grid [][]int, n1, n2, m1, m2 int) int { b, u, l, r := n1-1, n2, m2, m1-1 for i := n1; i < n2; i++ { for j := m1; j < m2; j++ { if grid[i][j] == 1 { b = max(b, i) u = min(u, i) l = min(l, j) r = max(r, j) } } } return (r - l + 1) * (b - u + 1) } -- https://i.imgur.com/r9FBAGO.gif