2024-02-28：用go语言，有一个由x轴和y轴组成的坐标系， “y下“

2024-02-28：用go语言，有一个由x轴和y轴组成的坐标系，

"y下"和"y上"表示一条无限延伸的道路，"y下"表示这个道路的下限，"y上"表示这个道路的上限，

给定一批长方形，每一个长方形有(x1, x2, y1, y2)，4个坐标可以表示一个长方形，

判断这条道路整体是不是可以走通的。

以下为正式题目：

图片在计算机处理中往往是使用二维矩阵来表示的，

给你一个大小为 m x n 的二进制矩阵 image 表示一张黑白图片，0 代表白色像素，1 代表黑色像素，

黑色像素相互连接，也就是说，图片中只会有一片连在一块儿的黑色像素。像素点是水平或竖直方向连接的。

给你两个整数 x 和 y 表示某一个黑色像素的位置。

请你找出包含全部黑色像素的最小矩形（与坐标轴对齐），并返回该矩形的面积。

你必须设计并实现一个时间复杂度低于 O(m*n) 的算法来解决此问题。

输入：image = [[“0”,“0”,“1”,“0”],[“0”,“1”,“1”,“0”],[“0”,“1”,“0”,“0”]], x = 0, y = 2。

输出：6。

答案2024-02-28：

来自左程云。

灵捷3.5

大体步骤如下：

1.定义一个辅助函数，用于计算包含全部黑色像素的最小矩形的面积。

minArea(image [][]byte, x int, y int) int

2.在函数中，使用二分查找来确定矩形的左边界、右边界、上边界和下边界。

minArea

3.实现辅助函数，用于确定左边界。采用二分查找方法，在给定的列col中向左查找，直到找到第一个出现黑色像素的位置。

left(image [][]byte, col int) int

4.实现辅助函数，用于确定右边界。采用二分查找方法，在给定的列col中向右查找，直到找到最后一个出现黑色像素的位置。

right(image [][]byte, col int) int

5.实现辅助函数，用于确定上边界。采用二分查找方法，在给定的行row中从左边界到右边界之间查找，直到找到第一个出现黑色像素的位置。

up(image [][]byte, row int, left int, right int) int

6.实现辅助函数，用于确定下边界。采用二分查找方法，在给定的行row中从左边界到右边界之间查找，直到找到最后一个出现黑色像素的位置。

down(image [][]byte, row int, left int, right int) int

7.在函数中，调用辅助函数获取左边界、右边界、上边界和下边界，并计算矩形的面积（）。

minArea

(right - left + 1) * (down - up + 1)

8.在函数中，定义一个示例图片和给定的点，调用函数并将结果打印出来。

main

image

(x, y)

minArea

总的时间复杂度：由于每个辅助函数都采用了二分查找的方法，时间复杂度为O(logn)，所以总的时间复杂度为O(logn)。

总的额外空间复杂度：除了存储输入数据和输出结果的额外空间外，代码没有使用其他额外的空间，因此总的额外空间复杂度为O(1)。

go完整代码如下：

packagemain
import"fmt"
funcminArea(image[][]byte,xint,yint)int{
left:=left(image,y)
right:=right(image,y)
up:=up(image,x,left,right)
down:=down(image,x,left,right)
return(right-left+1)*(down-up+1)
}
funcleft(image[][]byte,colint)int{
l,r,m,ans:=0,col-1,0,col
find:=false
forl<=r{
m=(l+r)/2
find=false
fori:=0;iifimage[i][m]=='1'{
find=true
break
}
}
iffind{
ans=m
r=m-1
}else{
l=m+1
}
}
returnans
}
funcright(image[][]byte,colint)int{
l,r,m,ans:=col+1,len(image[0])-1,0,col
find:=false
forl<=r{
m=(l+r)/2
find=false
fori:=0;iifimage[i][m]=='1'{
find=true
break
}
}
iffind{
ans=m
l=m+1
}else{
r=m-1
}
}
returnans
}
funcup(image[][]byte,rowint,leftint,rightint)int{
u,d,m,ans:=0,row-1,0,row
find:=false
foru<=d{
m=(u+d)/2
find=false
fori:=left;i<=right;i++{
ifimage[m][i]=='1'{
find=true
break
}
}
iffind{
ans=m
d=m-1
}else{
u=m+1
}
}
returnans
}
funcdown(image[][]byte,rowint,leftint,rightint)int{
u,d,m,ans:=row+1,len(image)-1,0,row
find:=false
foru<=d{
m=(u+d)/2
find=false
fori:=left;i<=right;i++{
ifimage[m][i]=='1'{
find=true
break
}
}
iffind{
ans=m
u=m+1
}else{
d=m-1
}
}
returnans
}
funcmain(){
image:=[][]byte{{'0','0','1','0'},{'0','1','1','0'},{'0','1','0','0'}}
x:=0
y:=2
result:=minArea(image,x,y)
fmt.Println(result)
}

python代码如下：

#-*-coding:utf-8-*-
defminArea(image,x,y):
left=left_boundary(image,y)
right=right_boundary(image,y)
up=upper_boundary(image,x,left,right)
down=lower_boundary(image,x,left,right)
return(right-left+1)*(down-up+1)
defleft_boundary(image,col):
l,r,m,ans=0,col-1,0,col
find=False
whilel<=r:
m=(l+r)//2
find=False
foriinrange(len(image)):
ifimage[i][m]=='1':
find=True
break
iffind:
ans=m
r=m-1
else:
l=m+1
returnans
defright_boundary(image,col):
l,r,m,ans=col+1,len(image[0])-1,0,col
find=False
whilel<=r:
m=(l+r)//2
find=False
foriinrange(len(image)):
ifimage[i][m]=='1':
find=True
break
iffind:
ans=m
l=m+1
else:
r=m-1
returnans
defupper_boundary(image,row,left,right):
u,d,m,ans=0,row-1,0,row
find=False
whileu<=d:
m=(u+d)//2
find=False
foriinrange(left,right+1):
ifimage[m][i]=='1':
find=True
break
iffind:
ans=m
d=m-1
else:
u=m+1
returnans
deflower_boundary(image,row,left,right):
u,d,m,ans=row+1,len(image)-1,0,row
find=False
whileu<=d:
m=(u+d)//2
find=False
foriinrange(left,right+1):
ifimage[m][i]=='1':
find=True
break
iffind:
ans=m
u=m+1
else:
d=m-1
returnans
image=[['0','0','1','0'],['0','1','1','0'],['0','1','0','0']]
x=0
y=2
result=minArea(image,x,y)
print(result)