华为OD机试 - 平面灯阵中寻找最大正方形边界 - 矩阵(Java 2024 C卷 200分)

╰半橙微兮° 2024-05-28 10:25 67阅读 0赞

在这里插入图片描述

华为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”组成的最大正方形。以下是解题思路:

解题思路

  1. 辅助数组定义:

    • 使用辅助二维数组 right[i][j] 和 down[i][j] 来记录从 (i, j) 位置开始向右和向下连续“1”的数量。
  2. 填充辅助数组:

    • 从数组的右下角开始向上和向左遍历,因为任何位置 (i, j) 的右向和下向连续“1”的数量依赖于其右侧和下方的位置。
  3. 寻找最大正方形:

    • 遍历整个矩阵,对于每个位置 (i, j),如果值为 1,则尝试构建正方形。
    • 正方形的最大可能边长是 right[i][j] 和 down[i][j] 的最小值。
    • 验证构成正方形的所有边是否都满足条件。
  4. 确定最优解:

    • 对于所有找到的正方形,记录最大面积,并在相同面积时优先选择行号较小,若行号相同,则选择列号较小的。

五、Java算法源码

  1. public class OdTest01 {
  2. public static void main(String[] args) {
  3. Scanner scanner = new Scanner(System.in);
  4. int height = scanner.nextInt();
  5. int width = scanner.nextInt();
  6. int[][] arr = new int[height][width];
  7. for (int i = 0; i < height; i++) {
  8. for (int j = 0; j < width; j++) {
  9. arr[i][j] = scanner.nextInt();
  10. }
  11. }
  12. // 辅助数组
  13. int[][] right = new int[height][width];
  14. int[][] down = new int[height][width];
  15. // 初始化辅助数组
  16. for (int i = height - 1; i >= 0; i--) {
  17. for (int j = width - 1; j >= 0; j--) {
  18. if (arr[i][j] == 1) {
  19. right[i][j] = (j == width - 1) ? 1 : right[i][j + 1] + 1;
  20. down[i][j] = (i == height - 1) ? 1 : down[i + 1][j] + 1;
  21. }
  22. }
  23. }
  24. // 寻找最大正方形
  25. int maxArea = 0;
  26. int[] result = {
  27. -1, -1, -1}; // 存储 r, c, w
  28. for (int i = 0; i < height; i++) {
  29. for (int j = 0; j < width; j++) {
  30. int maxSide = Math.min(right[i][j], down[i][j]);
  31. for (int s = maxSide; s > 0; s--) {
  32. if (right[i + s - 1][j] >= s && down[i][j + s - 1] >= s) {
  33. int area = s * s;
  34. if (area > maxArea) {
  35. maxArea = area;
  36. result[0] = i + s - 1; // r
  37. result[1] = j + s - 1; // c
  38. result[2] = s; // w
  39. }
  40. break; // 找到最大的满足条件的正方形后停止
  41. }
  42. }
  43. }
  44. }
  45. if (result[0] != -1) {
  46. System.out.println("[" + result[0] + "," + result[1] + "," + result[2] + "]");
  47. } else {
  48. System.out.println("No valid square found");
  49. }
  50. }
  51. }

六、效果展示

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在线答疑。

在这里插入图片描述

发表评论

表情:
评论列表 (有 0 条评论,67人围观)

还没有评论,来说两句吧...

相关阅读