2025-01-27：包含所有 1 的最小矩形面积Ⅱ。用go语言，给定一个二维二进制数组，找到三个非重叠且面积非零的矩形，这三个
2025-01-27：包含所有 1 的最小矩形面积Ⅱ。用go语言，给定一个二维二进制数组，找到三个非重叠且面积非零的矩形，这三个
福大大架构师每日一题
发布于 2025-02-05 14:03:31
发布于 2025-02-05 14:03:31
代码可运行
运行总次数：0
代码可运行
2025-01-27：包含所有 1 的最小矩形面积Ⅱ。用go语言，给定一个二维二进制数组，找到三个非重叠且面积非零的矩形，这三个矩形在水平和垂直方向上覆盖了数组中的所有1，返回这三个矩形的面积之和的最小值。这些矩形可以相互接触。
1 <= grid.length, grid[i].length <= 30。
grid[i][j] 是 0 或 1。
输入保证 grid 中至少有三个 1 。
输入： grid = [[1,0,1],[1,1,1]]。
输出： 5。
解释：
位于 (0, 0) 和 (1, 0) 的 1 被一个面积为 2 的矩形覆盖。
位于 (0, 2) 和 (1, 2) 的 1 被一个面积为 2 的矩形覆盖。
位于 (1, 1) 的 1 被一个面积为 1 的矩形覆盖。
答案2025-01-27：
chatgpt[1]
题目来自leetcode3197。
大体步骤如下：
Go完整代码如下：
package main
import (
"fmt"
"math"
)
func minimumArea(a [][]int) [][]int {
m, n := len(a), len(a[0])
// f[i+1][j+1] 表示包含【左上角为 (0,0) 右下角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
f := make([][]int, m+1)
for i := range f {
f[i] = make([]int, n+1)
}
type data struct{ top, left, right int }
border := make([]data, n)
for j := range border {
border[j].top = -1// 无
}
for i, row := range a {
left, right := -1, 0
for j, x := range row {
if x > 0 {
if left < 0 {
left = j
}
right = j
}
preB := border[j]
if left < 0 { // 这一排目前全是 0
f[i+1][j+1] = f[i][j+1] // 等于上面的结果
} elseif preB.top < 0 { // 这一排有 1，上面全是 0
f[i+1][j+1] = right - left + 1
border[j] = data{i, left, right}
} else { // 这一排有 1，上面也有 1
l, r := min(preB.left, left), max(preB.right, right)
f[i+1][j+1] = (r - l + 1) * (i - preB.top + 1)
border[j] = data{preB.top, l, r}
}
}
}
return f
}
func minimumSum(grid [][]int)int {
ans := math.MaxInt
f := func(a [][]int) {
m, n := len(a), len(a[0])
type pair struct{ l, r int }
lr := make([]pair, m) // 每一行最左最右 1 的列号
for i, row := range a {
l, r := -1, 0
for j, x := range row {
if x > 0 {
if l < 0 {
l = j
}
r = j
}
}
lr[i] = pair{l, r}
}
// lt[i+1][j+1] = 包含【左上角为 (0,0) 右下角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
lt := minimumArea(a)
a = rotate(a)
// lb[i][j+1] = 包含【左下角为 (m-1,0) 右上角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
lb := rotate(rotate(rotate(minimumArea(a))))
a = rotate(a)
// rb[i][j] = 包含【右下角为 (m-1,n-1) 左上角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
rb := rotate(rotate(minimumArea(a)))
a = rotate(a)
// rt[i+1][j] = 包含【右上角为 (0,n-1) 左下角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
rt := rotate(minimumArea(a))
if m >= 3 {
for i := 1; i < m; i++ {
left, right, top, bottom := n, 0, m, 0
for j := i + 1; j < m; j++ {
if p := lr[j-1]; p.l >= 0 {
left = min(left, p.l)
right = max(right, p.r)
top = min(top, j-1)
bottom = j - 1
}
// 图片上左
area := lt[i][n] // minimumArea(a[:i], 0, n)
area += (right - left + 1) * (bottom - top + 1) // minimumArea(a[i:j], 0, n)
area += lb[j][n] // minimumArea(a[j:], 0, n)
ans = min(ans, area)
}
}
}
if m >= 2 && n >= 2 {
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
// 图片上中
area := lt[i][n] // minimumArea(a[:i], 0, n)
area += lb[i][j] // minimumArea(a[i:], 0, j)
area += rb[i][j] // minimumArea(a[i:], j, n)
ans = min(ans, area)
// 图片上右
area = lt[i][j] // minimumArea(a[:i], 0, j)
area += rt[i][j] // minimumArea(a[:i], j, n)
area += lb[i][n] // minimumArea(a[i:], 0, n)
ans = min(ans, area)
}
}
}
}
f(grid)
f(rotate(grid))
return ans
}
// 顺时针旋转矩阵 90°
func rotate(a [][]int) [][]int {
m, n := len(a), len(a[0])
b := make([][]int, n)
for i := range b {
b[i] = make([]int, m)
}
for i, row := range a {
for j, x := range row {
b[j][m-1-i] = x
}
}
return b
}
func main() {
grid := [][]int{{1,0,1},{1,1,1}}
result := minimumSum(grid)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
import math
defminimum_area(a):
m, n = len(a), len(a[0])
# f[i+1][j+1] 表示包含【左上角为 (0,0) 右下角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
f = [[0] * (n + 1) for _ inrange(m + 1)]
border = [{'top': -1, 'left': 0, 'right': 0} for _ inrange(n)]
for i inrange(m):
left, right = -1, 0
for j inrange(n):
if a[i][j] > 0:
if left < 0:
left = j
right = j
preB = border[j]
if left < 0: # 这一排目前全是 0
f[i + 1][j + 1] = f[i][j + 1] # 等于上面的结果
elif preB['top'] < 0: # 这一排有 1，上面全是 0
f[i + 1][j + 1] = right - left + 1
border[j] = {'top': i, 'left': left, 'right': right}
else: # 这一排有 1，上面也有 1
l = min(preB['left'], left)
r = max(preB['right'], right)
f[i + 1][j + 1] = (r - l + 1) * (i - preB['top'] + 1)
border[j] = {'top': preB['top'], 'left': l, 'right': r}
return f
defminimum_sum(grid):
ans = math.inf
deff(a):
nonlocal ans
m, n = len(a), len(a[0])
lr = [(0, 0)] * m # 每一行最左最右 1 的列号
for i inrange(m):
l, r = -1, 0
for j inrange(n):
if a[i][j] > 0:
if l < 0:
l = j
r = j
lr[i] = (l, r)
lt = minimum_area(a)
a_rotated = rotate(a)
lb = rotate(rotate(rotate(minimum_area(a_rotated))))
a_rotated = rotate(a)
rb = rotate(rotate(minimum_area(a_rotated)))
a_rotated = rotate(a)
rt = rotate(minimum_area(a_rotated))
if m >= 3:
for i inrange(1, m):
left, right, top, bottom = n, 0, m, 0
for j inrange(i + 1, m):
p = lr[j - 1]
if p[0] >= 0:
left = min(left, p[0])
right = max(right, p[1])
top = min(top, j - 1)
bottom = j - 1
# 图片上左
area = lt[i][n] # minimumArea(a[:i], 0, n)
area += (right - left + 1) * (bottom - top + 1) # minimumArea(a[i:j], 0, n)
area += lb[j][n] # minimumArea(a[j:], 0, n)
ans = min(ans, area)
if m >= 2and n >= 2:
for i inrange(1, m):
for j inrange(1, n):
# 图片上中
area = lt[i][n] # minimumArea(a[:i], 0, n)
area += lb[i][j] # minimumArea(a[i:], 0, j)
area += rb[i][j] # minimumArea(a[i:], j, n)
ans = min(ans, area)
# 图片上右
area = lt[i][j] # minimumArea(a[:i], 0, j)
area += rt[i][j] # minimumArea(a[:i], j, n)
area += lb[i][n] # minimumArea(a[i:], 0, n)
ans = min(ans, area)
f(grid)
f(rotate(grid))
return ans
# 顺时针旋转矩阵 90°
defrotate(a):
m, n = len(a), len(a[0])
b = [[0] * m for _ inrange(n)]
for i inrange(m):
for j inrange(n):
b[j][m - 1 - i] = a[i][j]
return b
if __name__ == "__main__":
grid = [[1, 0, 1], [1, 1, 1]]
result = minimum_sum(grid)
print(result)
Javascript完整代码如下：
function minimumArea(a) {
const m = a.length;
const n = a[0].length;
const f = Array.from({ length: m + 1 }, () =>Array(n + 1).fill(0));
const border = Array.from({ length: n }, () => ({ top: -1, left: 0, right: 0 }));
for (let i = 0; i < m; i++) {
const row = a[i];
let left = -1;
let right = 0;
for (let j = 0; j < n; j++) {
const x = row[j];
if (x > 0) {
if (left < 0) {
left = j;
}
right = j;
}
const preB = border[j];
if (left < 0) { // 当前行全为 0
f[i + 1][j + 1] = f[i][j + 1]; // 等于上面的结果
} elseif (preB.top < 0) { // 当前行有 1，上面全为 0
f[i + 1][j + 1] = right - left + 1;
border[j] = { top: i, left: left, right: right };
} else { // 当前行有 1，上面也有 1
const l = Math.min(preB.left, left);
const r = Math.max(preB.right, right);
f[i + 1][j + 1] = (r - l + 1) * (i - preB.top + 1);
border[j] = { top: preB.top, left: l, right: r };
}
}
}
return f;
}
functionminimumSum(grid) {
let ans = Number.MAX_SAFE_INTEGER;
constf = (a) => {
const m = a.length;
const n = a[0].length;
const lr = Array.from({ length: m }, () => ({ l: -1, r: 0 }));
for (let i = 0; i < m; i++) {
let l = -1;
let r = 0;
for (let j = 0; j < n; j++) {
if (a[i][j] > 0) {
if (l < 0) {
l = j;
}
r = j;
}
}
lr[i] = { l: l, r: r };
}
const lt = minimumArea(a);
a = rotate(a);
const lb = rotate(rotate(rotate(minimumArea(a))));
a = rotate(a);
const rb = rotate(rotate(minimumArea(a)));
a = rotate(a);
const rt = rotate(minimumArea(a));
if (m >= 3) {
for (let i = 1; i < m; i++) {
let left = n;
let right = 0;
let top = m;
let bottom = 0;
for (let j = i + 1; j < m; j++) {
const p = lr[j - 1];
if (p.l >= 0) {
left = Math.min(left, p.l);
right = Math.max(right, p.r);
top = Math.min(top, j - 1);
bottom = j - 1;
}
// 图片上左
let area = lt[i][n]; // minimumArea(a[:i], 0, n)
area += (right - left + 1) * (bottom - top + 1); // minimumArea(a[i:j], 0, n)
area += lb[j][n]; // minimumArea(a[j:], 0, n)
ans = Math.min(ans, area);
}
}
}
if (m >= 2 && n >= 2) {
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
// 图片上中
let area = lt[i][n]; // minimumArea(a[:i], 0, n)
area += lb[i][j]; // minimumArea(a[i:], 0, j)
area += rb[i][j]; // minimumArea(a[i:], j, n)
ans = Math.min(ans, area);
// 图片上右
area = lt[i][j]; // minimumArea(a[:i], 0, j)
area += rt[i][j]; // minimumArea(a[:i], j, n)
area += lb[i][n]; // minimumArea(a[i:], 0, n)
ans = Math.min(ans, area);
}
}
}
};
f(grid);
f(rotate(grid));
return ans;
}
// 顺时针旋转矩阵 90°
functionrotate(a) {
const m = a.length;
const n = a[0].length;
const b = Array.from({ length: n }, () =>Array(m).fill(0));
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
b[j][m - 1 - i] = a[i][j];
}
}
return b;
}
// 测试
const grid = [[1, 0, 1], [1, 1, 1]];
const result = minimumSum(grid);
console.log(result);
引用链接
[1] chatgpt: https://chatbotsplace.com/?rc=nnNWSCJ7EP
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2025-01-27，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
