考虑一个名为“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;
}
附录结束
2条答案
按热度按时间fdbelqdn1#
我们可以将其设为图论问题,所有的单元格都是节点,如果两个节点不同(一个是0,另一个是1),则用一条边将它们连接起来,将1节点和0节点分开。
现在你有了一个二分图,因为边只存在于0-节点和1-节点之间,你要寻找的是这个上下文被称为“最大二分匹配”或“二分图中的最大匹配”。
将其设置为二分匹配问题的优点是,它可以为您解决重复零问题。
uurity8g2#
一种“优雅的”算法将使用该卷积矩阵,并且在该计数之后,将〈0的值: