今日学习记录
1. 包含所有 1 的最小矩形面积 IIleetcode.3197
关键词：矩阵 枚举 动态规划
问题分析：
- 给定一个二维二进制数组 grid.你需要找到 3 个不重叠,面积非零,的矩阵,满足 grid 中的所有 1 都在这些矩阵中;
- 类似于 2025-08-22 中的第一题,但是难度从 1300 到 2500 的跳跃实在受不住,前一个题是找一个矩阵,这个题是找三个矩阵,没啥思路
核心思路
- 没想到的是这个 2500 分的题居然可以用暴力做,分成三份,画一画图,把一个矩形分成三个矩形,也就 6 种分法,把其中的每各部分再按照 2025-08-22 中的第一题写就行
- 还有动态规划优化的手段,后续..
**最终代码：
class Solution {
//顺时针转90°
vector<vector<int>> restuts(const vector<vector<int>>&a){
int r = a.size(),c = a[0].size();
vector b(c,vector<int>(r));
for(int i = 0;i<r;i++){
for(int j = 0;j<c;j++){
b[j][r-1-i] = a[i][j];
}
}
return b;
}
//获取最小矩形面积
//3195
int minimumArea(const vector<vector<int>>&a,int u,int d,int l,int r){
int left = r,right = 0;
int h = d,bm = 0;
for(int i = u;i<d;i++){
for(int j = l;j<r;j++){
if(a[i][j]){
left = min(left,j);
right = max(right,j);
h = min(h,i);
bm = max(bm,i);
}
}
}
return (right-left+1)*(bm-h+1);
}
//分块
int solve(const vector<vector<int>>&a){
int m = a.size(), n = a[0].size();
int ans = INT_MAX;
if (m >= 3) {
for (int i = 1; i < m; i++) {
for (int j = i + 1; j < m; j++) {
// 图片上左
int area = minimumArea(a, 0, i, 0, n);
area += minimumArea(a, i, j, 0, n);
area += minimumArea(a, j, m, 0, n);
ans = min(ans, area);
}
}
}
if (m >= 2 && n >= 2) {
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
// 图片上中
int area = minimumArea(a, 0, i, 0, n);
area += minimumArea(a, i, m, 0, j);
area += minimumArea(a, i, m, j, n);
ans = min(ans, area);
// 图片上右
area = minimumArea(a, 0, i, 0, j);
area += minimumArea(a, 0, i, j, n);
area += minimumArea(a, i, m, 0, n);
ans = min(ans, area);
}
}
}
return ans;
}
public:
int minimumSum(vector<vector<int>>& grid) {
return min(solve(grid), solve(restuts(grid)));
}
};学到的点： 1.