首页 > 其他分享 >2024-02-28:用go语言,有一个由x轴和y轴组成的坐标系, “y下“和“y上“表示一条无限延伸的道路,“y下“表示这个道路的下限,“y上“表示这个道路的上限, 给定一批长方形,每一个长方形有(

2024-02-28:用go语言,有一个由x轴和y轴组成的坐标系, “y下“和“y上“表示一条无限延伸的道路,“y下“表示这个道路的下限,“y上“表示这个道路的上限, 给定一批长方形,每一个长方形有(

时间:2024-02-28 17:14:12浏览次数:30  
标签:02 right int image 长方形 像素 道路 col left

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.实现辅助函数left(image [][]byte, col int) int,用于确定左边界。采用二分查找方法,在给定的列col中向左查找,直到找到第一个出现黑色像素的位置。

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

5.实现辅助函数up(image [][]byte, row int, left int, right int) int,用于确定上边界。采用二分查找方法,在给定的行row中从左边界到右边界之间查找,直到找到第一个出现黑色像素的位置。

6.实现辅助函数down(image [][]byte, row int, left int, right int) int,用于确定下边界。采用二分查找方法,在给定的行row中从左边界到右边界之间查找,直到找到最后一个出现黑色像素的位置。

7.在minArea函数中,调用辅助函数获取左边界、右边界、上边界和下边界,并计算矩形的面积((right - left + 1) * (down - up + 1))。

8.在main函数中,定义一个示例图片image和给定的点(x, y),调用minArea函数并将结果打印出来。

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

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

go完整代码如下:

package main

import "fmt"

func minArea(image [][]byte, x int, y int) 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)
}

func left(image [][]byte, col int) int {
	l, r, m, ans := 0, col-1, 0, col
	find := false
	for l <= r {
		m = (l + r) / 2
		find = false
		for i := 0; i < len(image); i++ {
			if image[i][m] == '1' {
				find = true
				break
			}
		}
		if find {
			ans = m
			r = m - 1
		} else {
			l = m + 1
		}
	}
	return ans
}

func right(image [][]byte, col int) int {
	l, r, m, ans := col+1, len(image[0])-1, 0, col
	find := false
	for l <= r {
		m = (l + r) / 2
		find = false
		for i := 0; i < len(image); i++ {
			if image[i][m] == '1' {
				find = true
				break
			}
		}
		if find {
			ans = m
			l = m + 1
		} else {
			r = m - 1
		}
	}
	return ans
}

func up(image [][]byte, row int, left int, right int) int {
	u, d, m, ans := 0, row-1, 0, row
	find := false
	for u <= d {
		m = (u + d) / 2
		find = false
		for i := left; i <= right; i++ {
			if image[m][i] == '1' {
				find = true
				break
			}
		}
		if find {
			ans = m
			d = m - 1
		} else {
			u = m + 1
		}
	}
	return ans
}

func down(image [][]byte, row int, left int, right int) int {
	u, d, m, ans := row+1, len(image)-1, 0, row
	find := false
	for u <= d {
		m = (u + d) / 2
		find = false
		for i := left; i <= right; i++ {
			if image[m][i] == '1' {
				find = true
				break
			}
		}
		if find {
			ans = m
			u = m + 1
		} else {
			d = m - 1
		}
	}
	return ans
}

func main() {
	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-*-

def minArea(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)

def left_boundary(image, col):
    l, r, m, ans = 0, col-1, 0, col
    find = False
    while l <= r:
        m = (l + r) // 2
        find = False
        for i in range(len(image)):
            if image[i][m] == '1':
                find = True
                break
        if find:
            ans = m
            r = m - 1
        else:
            l = m + 1
    return ans

def right_boundary(image, col):
    l, r, m, ans = col+1, len(image[0])-1, 0, col
    find = False
    while l <= r:
        m = (l + r) // 2
        find = False
        for i in range(len(image)):
            if image[i][m] == '1':
                find = True
                break
        if find:
            ans = m
            l = m + 1
        else:
            r = m - 1
    return ans

def upper_boundary(image, row, left, right):
    u, d, m, ans = 0, row-1, 0, row
    find = False
    while u <= d:
        m = (u + d) // 2
        find = False
        for i in range(left, right+1):
            if image[m][i] == '1':
                find = True
                break
        if find:
            ans = m
            d = m - 1
        else:
            u = m + 1
    return ans

def lower_boundary(image, row, left, right):
    u, d, m, ans = row+1, len(image)-1, 0, row
    find = False
    while u <= d:
        m = (u + d) // 2
        find = False
        for i in range(left, right+1):
            if image[m][i] == '1':
                find = True
                break
        if find:
            ans = m
            u = m + 1
        else:
            d = m - 1
    return ans

image = [['0', '0', '1', '0'], ['0', '1', '1', '0'], ['0', '1', '0', '0']]
x = 0
y = 2
result = minArea(image, x, y)
print(result)

在这里插入图片描述

标签:02,right,int,image,长方形,像素,道路,col,left
From: https://www.cnblogs.com/moonfdd/p/18041063

相关文章

  • 2024-02-29-Linux高级网络编程(1-计算机网络概述)
    1.计算机网络概述1.1计算机发展简史最早的广域网:在通信双方或多方之间,通过电路交换建立电路连接的网络。1.1.1电路交换特点建立链接->使用链接->释放链接物理通路被通信双方独占1.1.2电路交换适用于电话网​计算机数据是突发式出现在数据链路上的,而电路交......
  • 面试题 02.07. 链表相交C
    利用链表的特性,如果相交的话,后面就不可能岔开!你可以想象把他们有同一个尾巴,然后从尾巴往前看。所以只要知道两个链表的长度,就可以在同一起跑线上一起比较了。/***Definitionforsingly-linkedlist.*structListNode{*intval;*structListNode*next;......
  • 2024.02.22
    1.原始jsp模板查看初始jsp创建模板:File---Setting---Editor---FileandCodeTemplates---Other---Jspfiles---JspFile.jsp,可在⑤处重新定义jsp模板,编写完成后,Apply,OK,下次在新建jsp文件时,即可建立所定义模板的jsp页面。 2.重新定义jsp页面模板    File---Sett......
  • 2024.2.14
    HomeView.vue<template><el-containerstyle="min-height:100vh"><el-asidewidth="sideWidth+'px'"style="background-color:rgb(255,255,255)"><!--width="sideWidth+'px'&......
  • 2024.1.25
    想要使用IDEA去连接mysql等数据库需要先IDEA里先下载驱动,一般当你去配置的IDEA连接数据库这个过程,IDEA会提示你没有安装驱动,并问你需不需要自动下载这里如果你们遇到自动下载的途中,下载到一半进度条卡住了,或者直接下载失败,可以先到maven中导入相应的包,然后再回到上图重新下载驱......
  • 【QBXT 2023 冬】NOIP 突破营 补题清单
    题单:第一部分第二部分题解有时间就写,一般会咕。P5691[NOI2001]方程的解数简单的折半搜索。直接搜索时间复杂度是\(O(m^6)-O(m^6\logp_i)\)的(快速幂),无法通过。考虑优化,首先我们对上面的式子做一个变形:\[\sum_{i=1}^{n}k_ix_i^{p_i}=0\]即\[\sum_{i=1}^{\lfloor\frac......
  • flask_02
    #1flask介绍 web框架---》小而精--》第三方插件--》完成更丰富的功能--》自由选择第三方插件#2wsgi协议:werkzeug:工具包uwsgi,wsgiref djagno,flask要遵循wsgi协议#3click定制命令 -定制命令--》把excel中得数据---》导入到mysql的某个表中......
  • ABC302 Ex 题解
    首先我们考虑\(v\)固定怎么做。实际上就是ARC111B。考虑建图,对每个\((a_i,b_i)\)建一条无向边,那么问题就变成了:对于每条边都要选择它以及其连接的一个点,最大化选出的点数。很明显可以对每个连通块分开考虑。记当前连通块的点数为\(V\),边数为\(E\)。那么有结论:该连通块对......
  • 『周记』2024第八周周末
    『周记』2024第八周周末  复盘周五到周日的flag:周五参加170HomeworkParty周六早上去健身房完成61B的lab5和hw2完成170的hw5完成188project3的前半部分补三门课对应的recording/notes订正所有作业和考试完成所有discussion并且对应solution整理计时完......
  • P9755 [CSP-S 2023] 种树 题解
    首先考虑如何求出第\(i\)棵树在\([l,r]\)时间段能长多高。这个东西可以差分一下然后等差数列求和。放一下代码:inlinelllcalc(inti,intx){ if(c[i]>=0){ return(lll)b[i]*x+(lll)c[i]*x*(x+1)/2; }else{ intd=(b[i]-1)/(-c[i]); if(x<=d)return(lll)b[i]*x+(l......