首页 > 编程语言 >2024.9.16 Python,最短的桥

2024.9.16 Python,最短的桥

时间:2024-09-17 18:49:09浏览次数:14  
标签:deque 16 Python 2024.9 int grid 内存 island nr

1.最短的桥:

这个题我最新的代码如下:

from collections import deque
class Solution:
    def shortestBridge(self,grid:List[List[int]])->int:
        nr=len(grid)
        if nr==0:
            return 0
        nc=len(grid[0])
        island=deque([])
        for r in range(nr):
            for c in range(nc):
                if grid[r][c]==1:                    
                    q=deque([(r,c)])
                    island=deque([(r,c)])
                    while q:
                        (r,c)=q.popleft()
                        grid[r][c]=-1
                        
                        for x,y in ([r+1,c],[r-1,c],[r,c+1],[r,c-1]):
                            if 0<=x<=nr-1 and 0<=y<=nc-1 and grid[x][y]==1:
                                q.append((x,y))
                                grid[x][y]=-1
                                island.append([x,y])
                    break
            if island:
                break

        
        step=0  
        while 1:
            q=island
            island=deque([]) 
            while q:
                (r,c)=q.popleft()
                for x,y in ([r+1,c],[r-1,c],[r,c+1],[r,c-1]):
                    if 0<=x<=nr-1 and 0<=y<=nc-1 and grid[x][y]==0:
                        grid[x][y]==-1
                        island.append([x,y])
                    elif 0<=x<=nr-1 and 0<=y<=nc-1 and grid[x][y]==1:
                        return step
            step+=1

1.代码能过但是超内存了,原因是我创建了大量的deque,导致旧的deque没有删掉,所以超内存了。你现在想这么个逻辑,那就是,为什么前面要用deque,是因为你现在不知道自己要遍历多久才能停,所以才用deque去搜索,现在你都有了island的列表,你根本不需要使用的确来去做这个事情,也就是说你可以直接去遍历island里的所有的元素,这样的话就不需要重复的建立新的deque。就能把内存省下来了
2.另外,在遇见0的时候别忘了置-1,我第一次做的时候忘记这个了

标签:deque,16,Python,2024.9,int,grid,内存,island,nr
From: https://blog.csdn.net/RaidenMessi/article/details/142301578

相关文章

  • 2024.9.17 Python
    1.现有字典d={‘a’:24,’g’:52,’l’:12,’k’:33}请按字典中的value值进行排序?sorted(d.items(),key=lambdax:x[1])[1]换成0即可变成按照键排序2.del列表名[index]:删除指定索引的数据3.列表名.remove(数据):删除第一个出现的指定数据4.列表名.pop(index)5.列表名......
  • python电子书,网安电子书,电脑维修电子书【免费】
    下载地址百度网盘:python电子书提取码:ihpn下载地址百度网盘:电子书合集提取码:mvvk......
  • 【python学习】深入掌握 Python RQ 任务队列库:全面处理异步任务的实战指南
    引言rq是基于Redis的Python任务队列库,用于处理异步任务。它能帮助开发者将繁重的后台任务交由独立进程执行,从而提高系统性能。在复杂项目中,任务的超时、重试、定时执行、依赖关系以及队列优先级等功能尤为重要。本文将全面介绍rq的常用和高级功能,帮助你在项目中灵活......
  • 南沙信奥老师解题:1167:再求f(x,n)
    ​ 用递归函数求解。【输入】第一数是x的值,第二个数是n的值。【输出】函数值。【输入样例】12【输出样例】0.40#include<iostream>#include<stdlib.h>usingnamespacestd;doublef(doublex,doublen){ if(n==1) returnx/(1+x); else return......
  • opencv-python学习笔记10-图像形态学处理
    目录一、基本概念: (1)结构元素(StructuringElement):(2)膨胀(Dilation):(3)腐蚀(Erosion):(4)开运算(Opening)(5)闭运算(Closing)(6)形态学梯度(MorphologicalGradient)(7)顶帽(Top-hat)和黑帽(Black-hat)转换(8)应用领域 二、膨胀:(1)基本概念:(2)原理:(3)方法:(4)OpenCV中的膨胀函数:(5)代码示例:(6)应用领域:(7......
  • python标准库模块 pickle 详解
    什么是pickle模块?pickle是Python的一个标准库,用于序列化和反序列化Python对象。所谓序列化,就是将一个Python对象转换成字节流,以便存储到磁盘或通过网络传输。反序列化则是将字节流恢复为原来的Python对象。为什么使用pickle?保存Python对象:可以将Python中的各......
  • Python使用starmap函数批量更新数据库
    在数据库操作中,有时候需要对多条记录进行批量更新操作,而这些记录的更新逻辑可能是相同的,只是参数不同。starmap函数可以更加高效地实现批量更新数据库的操作。importsqlite3fromitertoolsimportstarmap#连接数据库conn=sqlite3.connect('example.db')cursor=conn......
  • Python 之函数
    函数参数位置参数: defpower(x):默认参数: defpower(x,n=2): 默认参数必须指向不变对象!可变参数: defcalc(*numbers):关键字参数: defperson(name,age,**kw):命名关键字参数:defperson(name,age,*,city,job):参数组合:在Python中定义函数,可以用必选参数、默认参数......
  • python 提取出sql语句中where的值
    使用正则表达式来提取SQL语句中的WHERE条件的值。假设你的SQL语句格式比较标准,你可以使用以下Python代码来提取WHERE子句中的值。importredefextract_where_clause(sql_query):#使用正则表达式提取WHERE子句中的条件where_clause_pattern=re.compile(r'......
  • 2024.9.1_ChatGPT镜像列表
    收集自网络,更新于2024.9.1ChatGPT国内镜像ChatGPT外国镜像......