华为OD机试 - 平面灯阵中寻找最大正方形边界 - 矩阵(Java 2024 C卷 200分)
华为OD机试 2024C卷题库疯狂收录中,刷题点这里
专栏导读
本专栏收录于《华为OD机试(JAVA)真题(A卷+B卷+C卷)》。
刷的越多,抽中的概率越大,每一题都有详细的答题思路、详细的代码注释、样例测试,发现新题目,随时更新,全天CSDN在线答疑。
一、题目描述
现在有一个二维数组来模拟一个平面灯阵,平面灯阵中每个位置灯处于点亮或熄灭,分别对应数组每个元素取值只能为1或0,现在需要找一个正方形边界,其每条边上的灯都是点亮(对应数组中元素的值为1)的,且该正方形面积最大。
二、输入描述
第一行为灯阵的高度(二维数组的行数)
第二行为灯阵的宽度(二维数组的列数)
紧接着为模拟平台灯阵的二维数组arr
1< arr.length <= 200 1< arr[0].length <= 200
三、输出描述
返回满足条件的面积最大正方形边界信息。返回信息[r,c,w],其中r,c分别代表方阵右下角的行号和列号,w代表正方形的宽度。如果存在多个满足条件的正方形,则返回r最小的,若r相同,返回c最小的正方形。
1、输入
4
5
1 0 0 0 1
1 1 1 1 1
1 0 1 1 0
1 1 1 1 1
2、输出
[3,2,3]
3、说明
满足条件且面积最大的正方形边界,其右下角的顶点为[3,2],即行号为3,列号为2,其宽度为3,因此返回信息为[3,2,3]。
四、解题思路
为了解决这个问题,我们需要找出边界全由“1”组成的最大正方形。以下是解题思路:
解题思路
辅助数组定义:
- 使用辅助二维数组 right[i][j] 和 down[i][j] 来记录从 (i, j) 位置开始向右和向下连续“1”的数量。
填充辅助数组:
- 从数组的右下角开始向上和向左遍历,因为任何位置 (i, j) 的右向和下向连续“1”的数量依赖于其右侧和下方的位置。
寻找最大正方形:
- 遍历整个矩阵,对于每个位置 (i, j),如果值为 1,则尝试构建正方形。
- 正方形的最大可能边长是 right[i][j] 和 down[i][j] 的最小值。
- 验证构成正方形的所有边是否都满足条件。
确定最优解:
- 对于所有找到的正方形,记录最大面积,并在相同面积时优先选择行号较小,若行号相同,则选择列号较小的。
五、Java算法源码
public class OdTest01 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int height = scanner.nextInt();
int width = scanner.nextInt();
int[][] arr = new int[height][width];
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
arr[i][j] = scanner.nextInt();
}
}
// 辅助数组
int[][] right = new int[height][width];
int[][] down = new int[height][width];
// 初始化辅助数组
for (int i = height - 1; i >= 0; i--) {
for (int j = width - 1; j >= 0; j--) {
if (arr[i][j] == 1) {
right[i][j] = (j == width - 1) ? 1 : right[i][j + 1] + 1;
down[i][j] = (i == height - 1) ? 1 : down[i + 1][j] + 1;
}
}
}
// 寻找最大正方形
int maxArea = 0;
int[] result = {
-1, -1, -1}; // 存储 r, c, w
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
int maxSide = Math.min(right[i][j], down[i][j]);
for (int s = maxSide; s > 0; s--) {
if (right[i + s - 1][j] >= s && down[i][j + s - 1] >= s) {
int area = s * s;
if (area > maxArea) {
maxArea = area;
result[0] = i + s - 1; // r
result[1] = j + s - 1; // c
result[2] = s; // w
}
break; // 找到最大的满足条件的正方形后停止
}
}
}
}
if (result[0] != -1) {
System.out.println("[" + result[0] + "," + result[1] + "," + result[2] + "]");
} else {
System.out.println("No valid square found");
}
}
}
六、效果展示
1、输入
3
3
1 0 0
0 1 0
0 0 1
2、输出
[0,0,1]
3、说明
满足条件且面积最大的正方形边界有三个。即为[0,0,1]、[1,1,1]、[2,2,1],根据要求,如果满足条件有多个,则返r最小,即为 [0,0,1]。
?下一篇:华为OD机试 - 简易内存池 - 逻辑分析(Java 2024 C卷 200分)
?本文收录于,华为OD机试(JAVA)真题(A卷+B卷+C卷)
刷的越多,抽中的概率越大,每一题都有详细的答题思路、详细的代码注释、样例测试,发现新题目,随时更新,全天CSDN在线答疑。
还没有评论,来说两句吧...