java 数组中边界0和1的算法

ycggw6v2  于 2023-02-14  发布在  Java
关注(0)|答案(2)|浏览(206)

考虑一个名为“zeroesAndOnes”的二维数组,它的长度和宽度是随机的,并且也随机填充了0和1。
我想知道一个算法,它可以计算与数组中的1共享边界的0的数量,在这种情况下,共享边界意味着数组中的0在其上、下、左和/或右至少有1个1,而不进行对角方向检查。
如果在上述条件下,一个零被多个零共享,则应将其计为重复零,不应添加到最终结果中。

//Test Arrays
int[][] nums1 = {
                 {0, 0, 1, 0, 1, 0, 1, 0},
                 {1, 0, 0, 0, 0, 0, 0, 0},
                 {0, 0, 0, 0, 0, 0, 0, 0},
                 {0, 0, 0, 0, 0, 0, 0, 0},
                };

int[][] nums2 = {
                 {0, 0, 0, 0, 1, 1},
                 {0, 1, 0, 0, 1, 0},
                 {0, 1, 0, 0, 0, 0},
                 {0, 1, 0, 0, 0, 0},
                 {0, 1, 0, 0, 1, 0},
                 {0, 0, 0, 0, 1, 1},
                };

//Method Definition
public static int borderZeros(int[][] nums) {
   int border = 0;
   //See instructions and examples above! I have defined a result variable called "border" to return when the procedure is defined according to the instructions above.
   //Should return the integer zero, if nums has a length <= 1 & width <= 1, as a base case.
   //Otherwise should return the number of zeroes bordering a one under the conditions described, with no duplicate zeroes.
}

//Driver Code
System.out.println(borderZeros(nums1));
System.out.println(borderZeros(nums2));
//Should print the integers 10 and 18 (I think!) respectively if coded properly.
//Should for arrays of all sizes!
//No ArrayIndexOutOfBoundsExceptions!

到目前为止,我所做的唯一一件事就是实现了一个嵌套的for循环,如果数组中的元素为1,该循环将检查周围字符是否为零,但这导致了越界索引异常,而试图减轻该异常的结果是我没有检查所有元素。
我需要找到某种方法,使我能够在不引起异常的情况下获得算法,并且我已经检查了数组中的所有元素。
任何可行的解决方案,最好是你认为“优雅”、“新颖"或”有效“的解决方案,都将受到极大的赞赏!我是一个程序员新手,而且还在学习中。)

增编

根据Jim Mischel的建议,我在下面附上了我的代码,它目前没有考虑到重复的零,或者明显的数组索引异常,或者我可能没有考虑到所有的零。

public static int borderZeros(int[][] nums) {
  int border = 0;
  for (int r = 1; r < nums.length - 1; r++) {
    for (int c = 1; c < nums[r].length - 1; c++) {
      if (nums[r][c] == 1) {
        if (nums[r - 1][c] == 0) {
          border++;
        }
        if (nums[r][c - 1] == 0) {
          border++;
        }
        if (nums[r + 1][c] == 0) {
          border++;
        }
        if (nums[r][c + 1] == 0) {
           border++;
        }
      }
      else {
        continue;
      } 
    }
  }
  return border;
}

附录结束

fdbelqdn

fdbelqdn1#

我们可以将其设为图论问题,所有的单元格都是节点,如果两个节点不同(一个是0,另一个是1),则用一条边将它们连接起来,将1节点和0节点分开。
现在你有了一个二分图,因为边只存在于0-节点和1-节点之间,你要寻找的是这个上下文被称为“最大二分匹配”或“二分图中的最大匹配”。
将其设置为二分匹配问题的优点是,它可以为您解决重复零问题。

uurity8g

uurity8g2#

一种“优雅的”算法将使用该卷积矩阵,并且在该计数之后,将〈0的值:

0 -1  0
-1  4 -1 
 0 -1  0

相关问题