【Leetcode】top 100 图论
基础知识补充
1.图分为有向图和无向图,有权图和无权图;
2.图的表示方法:邻接矩阵适合表示稠密图,邻接表适合表示稀疏图;
邻接矩阵:
邻接表:
基础操作补充
1.邻接矩阵:
class GraphAdjacencyMatrix:def __init__(self, num_vertices):self.num_vertices = num_verticesself.matrix = [[0] * num_vertices for _ in range(num_vertices)]def add_edge(self, start, end): # 无向图self.matrix[start][end] = 1self.matrix[end][start] = 1
2.邻接表:
from collections import defaultdictclass GraphAdjacencyList:def __init__(self):self.graph = defaultdict(list)def add_edge(self, start, end): # 无向图self.graph[start].append(end)self.graph[end].append(start)
3.图的遍历:
# 深度优先搜索(DFS): # 从上到下,递归或栈实现 def dfs(graph, start, visited=None):if visited is None:visited = set()visited.add(start)print(start, end=" ")for neighbor in graph[start]:if neighbor not in visited:dfs(graph, neighbor, visited)# 广度优先搜索(BFS): # 从左到右,队列实现 from collections import dequedef bfs(graph, start):visited = set()queue = deque([start])visited.add(start)while queue:current = queue.popleft()print(current, end=" ")for neighbor in graph[current]:if neighbor not in visited:queue.append(neighbor)visited.add(neighbor)
题目
200 岛屿数量
给你一个由 '1'
(陆地)和 '0'
(水)组成的的二维网格,请你计算网格中岛屿的数量。岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外,你可以假设该网格的四条边均被水包围。
方法一:深度优先搜索 DFS
若当前点是岛屿时,向上下左右四个点做深度搜索;终止条件:越界;当前是水;class Solution(object):def numIslands(self, grid):""":type grid: List[List[str]]:rtype: int"""def dfs(nums, x, y):if x<0 or x>len(nums)-1: return if y<0 or y>len(nums[0])-1: return if nums[x][y] =='0':return else:nums[x][y] = '0' # 必须先置0,否则会在两个'1'间连续递归至超过栈长dfs(nums, x-1, y)dfs(nums, x+1, y)dfs(nums, x, y-1)dfs(nums, x, y+1)cnt = 0for i in range(len(grid)):for j in range(len(grid[0])):if grid[i][j] == '1':dfs(grid, i, j)cnt += 1return cnt
方法二:广度优先搜索 BFS
若当前点是岛屿时,将其上下左右四个点都加入队列;终止条件:越界;当前是水;
class Solution(object):def numIslands(self, grid):""":type grid: List[List[str]]:rtype: int"""def bfs(nums, x, y):queue = [(x, y)]while queue:(x, y) = queue.pop(0)if x<0 or x>len(nums)-1: continue elif y<0 or y>len(nums[0])-1: continue elif nums[x][y] =='0':continue else:nums[x][y] = '0' # 必须先置0,否则会在两个'1'间连续递归至超过栈长queue.append((x-1, y))queue.append((x+1, y))queue.append((x, y-1))queue.append((x, y+1))cnt = 0for i in range(len(grid)):for j in range(len(grid[0])):if grid[i][j] == '1':bfs(grid, i, j)cnt += 1return cnt
994 腐烂的橘子
在给定的 m x n
网格 grid
中,每个单元格可以有以下三个值之一:
- 值
0
代表空单元格; - 值
1
代表新鲜橘子; - 值
2
代表腐烂的橘子。
每分钟,腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1
。
第一次遍历将所有新鲜橘子腐烂,统计腐烂次数;第二次遍历统计是否还有剩余的新鲜橘子;(若初始就不含有新鲜橘子呢?)
一次遍历统计新鲜橘子数量的同时记录腐烂橘子的位置(队列);
遍历队列,若当前位置是腐烂橘子则将其上下左右四个点入队,若当前位置是新鲜橘子则将新鲜橘子数量-1再将其上下左右四个点入队;需要将处理过的位置的值置为0,代表不再处理;
class Solution(object):def orangesRotting(self, grid):""":type grid: List[List[int]]:rtype: int"""cnt, queue = 0, []m, n = len(grid), len(grid[0])for i in range(m):for j in range(n):if grid[i][j] == 1:cnt += 1elif grid[i][j] == 2:queue.append([i,j])if cnt == 0: return 0time, stack = -1, []while queue:[x, y] = queue.pop(0)if -1<x<m and -1<y<n and grid[x][y]:if grid[x][y] == 1: cnt -= 1grid[x][y] = 0 # 不再处理这个点stack.append([x-1, y])stack.append([x+1, y])stack.append([x, y-1])stack.append([x, y+1])if not queue and stack:queue = stacktime += 1 stack = []return -1 if cnt else time
计算遍历深度用BFS
207 课程表
你这个学期必须选修 numCourses
门课程,记为 0
到 numCourses - 1
。在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites
给出,其中 prerequisites[i] = [ai, bi]
,表示如果要学习课程 ai
则 必须 先学习课程 bi
。
- 例如,先修课程对
[0, 1]
表示:想要学习课程0
,你需要先完成课程1
。
请你判断是否可能完成所有课程的学习?如果可以,返回 true
;否则,返回 false
。
方法一:广度优先搜索
from collections import deque from collections import defaultdictclass Solution(object):def canFinish(self, numCourses, prerequisites):""":type numCourses: int:type prerequisites: List[List[int]]:rtype: bool"""degree = [0]*numCourses maps = defaultdict(list) queue = deque()for cur, pre in prerequisites:degree[cur] += 1 # 统计每门课的先修课程数maps[pre].append(cur) # 记录基础课和对应的进阶课for i in range(numCourses):if degree[i] == 0: queue.append(i) # 无先修课程(基础课)时入队count = 0while queue:course = queue.popleft()count += 1for i in maps[course]: # 将以course为基础课的进阶课的先修课数-1degree[i] -= 1if degree[i] == 0: # 已修完全部基础课queue.append(i) return count == numCourses
方法二:深度优先搜索
class Solution(object):def canFinish(self, numCourses, prerequisites):""":type numCourses: int:type prerequisites: List[List[int]]:rtype: bool"""degree = [0]* numCoursesmaps = defaultdict(list)def dfs(i):if degree[i]==-1: return False # degree[i]==-1 表示会陷入循环if degree[i]==1: return True # degree[i]==1 表示能完成课 degree[i]=-1 # 防止 1-0-1 转回来的情况for pre in maps[i]: # 遍历每门基础课if not dfs(pre): return Falsedegree[i]=1 # 该门课可以完成return Truefor cur, pre in prerequisites: # 记录先修课和其基础课程maps[cur].append(pre)for i in range(numCourses): # 遍历每门课dfs(i)return sum(degree) == numCourses # 若每门课都完成应该全为1
208 实现Trie(前缀树)
Trie(发音类似 "try")或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。
请你实现 Trie 类:
Trie()
初始化前缀树对象。void insert(String word)
向前缀树中插入字符串word
。boolean search(String word)
如果字符串word
在前缀树中,返回true
(即,在检索之前已经插入);否则,返回false
。boolean startsWith(String prefix)
如果之前已经插入的字符串word
的前缀之一为prefix
,返回true
;否则,返回false
。
核心:使用「边」来代表有无字符,使用「点」来记录是否为「单词结尾」以及「其后续字符串的字符是什么」
class TrieNode:def __init__(self):self.children = {}self.is_end = Falseclass Trie(object):def __init__(self):self.root = TrieNode()def insert(self, word):""":type word: str:rtype: None"""node = self.rootfor c in word:if c not in node.children:node.children[c] = TrieNode()node = node.children[c]node.is_end = Truedef searchPrefix(self, word):node = self.rootfor c in word:if c not in node.children: return Nonenode = node.children[c]return nodedef search(self, word):""":type word: str:rtype: bool"""node = self.searchPrefix(word)return node is not None and node.is_enddef startsWith(self, prefix):""":type prefix: str:rtype: bool"""node = self.searchPrefix(prefix)return node is not None
额外补充
flood fill 带你学习Flood Fill算法与最短路模型 - 时间最考验人 - 博客园 (cnblogs.com)
相关文章:
【Leetcode】top 100 图论
基础知识补充 1.图分为有向图和无向图,有权图和无权图; 2.图的表示方法:邻接矩阵适合表示稠密图,邻接表适合表示稀疏图; 邻接矩阵: 邻接表: 基础操作补充 1.邻接矩阵: class GraphAd…...
【沈阳航空航天大学】 <C++ 类与对象计分作业>
C类与对象 1. 设计用类完成计算两点距离2. 设计向量类3. 求n!4. 出租车收费类的设计与实现5. 定义并实现一个复数类6. 线性表类的设计与实现7. 数组求和8. 数组求最大值 1. 设计用类完成计算两点距离 【问题描述】设计二维点类Point,包括私有成员:横坐标…...
Vue3 自定义指令Custom Directives
简介 在vue中重用代码的方式有:组件、组合式函数。组件是主要的构建模块,而组合式函数更偏重于有状态的逻辑。 指令系统给我们提供了例如:v-model、v-bind,vue系统允许我们自定义指令,自定义指令也是一种重用代码的方式…...
蓝桥杯 【日期统计】【01串的熵】
日期统计 第一遍写的时候会错了题目的意思,我以为是一定要八个整数连在一起构成正确日期,后面发现逻辑明明没有问题但是答案怎么都是错的才发现理解错了题目的意思,题目的意思是按下标顺序组成,意思就是可以不连续,我…...
CSP201409T5拼图
题意:给出一个 n m nm nm的方格图,现在要用如下L型的占3个的积木拼到这个图中,总共有多少种拼法使图满。 #include<bits/stdc.h> using namespace std; long long n,m,k1,Now; int Mod1000000007; struct Matrix {long long a[129][129];Matrix(…...
mongoDB 优化(2)索引
执行计划 语法:1 db.collection_xxx_t.find({"param":"xxxxxxx"}).explain(executionStats) 感觉这篇文章写得很好,可以参考 MongoDB——索引(单索引,复合索引,索引创建、使用)_mongo…...
【2024系统架构设计】案例分析- 5 Web应用
目录 一 基础知识 二 真题 一 基础知识 1 Web应用技术分类 大型网站系统架构的演化:高性能、高可用、可维护、应变、安全。 从架构来看:MVC,MVP,MVVM,REST,Webservice,微服务。...
布隆过滤器详解及java实现
什么是布隆过滤器? 布隆过滤器(Bloom Filter)是一种数据结构,用于判断一个元素是否属于一个集合。它的特点是高效地判断一个元素是否可能存在于集合中,但是存在一定的误判率。 布隆过滤器的基本原理是使用一个位数组…...
CloudCompare 点云工具
CloudCompare 点云工具 1. CloudCompare简介1.1 CloudCompare下载 2. CloudCompare安装 1. CloudCompare简介 CloudCompare 是一款开源的三维点云处理软件,它提供了一系列功能来处理、查看和分析三维点云数据。这个软件可以用于许多不同的应用领域,包括…...
Linux 著名的sudo、su是什么?怎么用?
一、su 什么是su? su命令(简称是:substitute 或者 switch user )用于切换到另一个用户,没有指定用户名,则默认情况下将以root用户登录。 为了向后兼容,su默认不改变当前目录,只设…...
C语言分支语句
一、什么是语句 C语句可分为以下五类: 表达式语句 函数调用语句 控制语句 复合语句 空语句 本周后面介绍的是控制语句。 控制语句用于控制程序的执行流程,以实现程序的各种结构方式,它们由特定的语句定义符组成,C语 言有…...
android 资源文件混淆
AGP7.0以上引用AndResGuard有坑 记录下 在项目的build.gradle中添加如下 buildscript {ext.kotlin_version "1.4.31"repositories {google()jcenter()maven {url "https://s01.oss.sonatype.org/content/repositories/snapshots/"}}dependencies {class…...
注册接口和前置SQL及数据生成及封装
注册接口 演示注册接口的三步操作:【注册流程逻辑】 第一步:发送注册短信验证码接口请求 请求方法: put 请求地址:http://shop.lemonban.com:8107/user/sendRegisterSms 请求参数:{“mobile”:“13422337766”} 请求头…...
鸿蒙实战开发-通过输入法框架实现自绘编辑框
介绍 本示例通过输入法框架实现自会编辑框,可以绑定输入法应用,从输入法应用输入内容,显示和隐藏输入法。 效果预览 使用说明 1.点击编辑框可以绑定并拉起输入法,可以从输入法键盘输入内容到编辑框。 2.可以点击attach/dettac…...
深度学习中的注意力模块的添加
在深度学习中,骨干网络通常指的是网络的主要结构或主干部分,它负责从原始输入中提取高级特征。骨干网络通常由卷积神经网络(CNN)或者类似的架构组成,用于对图像、文本或其他类型的数据进行特征提取和表示学习。 注意力…...
Docker 部署开源远程桌面工具 RustDesk
RustDesk是一款远程控制,远程协助的开源软件。完美替代TeamViewer ,ToDesk,向日葵等平台。关键支持自建服务器,更安全私密远程控制电脑!官网地址:https://rustdesk.com/ 环境准备 1、阿里云服务器一 台&a…...
intellij idea 使用git ,快速合并冲突
可以选择左边的远程分支上的代码,也可以选择右边的代码,而中间是合并的结果。 一个快速合并冲突的小技巧: 如果冲突比较多,想要快速合并冲突。也可以直接点击上图中 Apply non-conflicting changes 旁边的 All 。 这样 Idea 就会…...
AcWing26. 二进制中1的个数。三种解法Java
输入一个 3232 位整数,输出该数二进制表示中 11 的个数。 注意: 负数在计算机中用其绝对值的补码来表示。 数据范围 −100≤ 输入整数 ≤100 样例1 输入:9 输出:2 解释:9的二进制表示是1001,一共有2个…...
【ADB】常见命令汇总(持续更新)
▒ 目录 ▒ 🛫 导读开发环境 1️⃣ 设备连接和识别2️⃣ 应用程序管理3️⃣ 文件传输和管理4️⃣ 设备信息和日志5️⃣ 设备操作和控制6️⃣ 截图相关🛬 文章小结📖 参考资料 🛫 导读 Android调试桥(ADB)是…...
【递归与递推】数的计算|数的划分|耐摔指数
1.数的计算 - 蓝桥云课 (lanqiao.cn) 思路: 1.dfs的变量>每一次递归什么在变? (1)当前数的大小一直在变:sum (2)最高位的数:k 2.递归出口:最高位数字为1 3.注意&#…...
企业案例:金蝶云星空集成钉钉,帆软BI
正文:在数字化转型的大潮中,众多企业开始探索并实践高效的数据流转与集成,以提升内部管理效率和决策质量。本文将以某企业为例,详细介绍如何通过将钉钉审批流程的数据实时同步至金蝶云星空,并进一步在帆软报表平台上实…...
简单设计模式讲解
设计模式是在软件开发中经常使用的最佳实践,用于解决在软件设计中经常遇到的问题。它们提供了可重用的设计,使得代码更加灵活、可维护和可扩展。下面我将为你讲解几种常见的设计模式,并提供相应的C#代码示例。 1. 单例模式(Single…...
基于springboot的社区医疗服务系统
文章目录 项目介绍主要功能截图:部分代码展示设计总结项目获取方式 🍅 作者主页:超级无敌暴龙战士塔塔开 🍅 简介:Java领域优质创作者🏆、 简历模板、学习资料、面试题库【关注我,都给你】 &…...
影院座位选择简易实现(uniapp)
界面展示 主要使用到uniap中的movable-area,和movable-view组件实现。 代码逻辑分析 1、使用movable-area和movea-view组件,用于座位展示 <div class"ui-seat__box"><movable-area class"ui-movableArea"><movab…...
调用飞书获取用户Id接口成功,但是没有返回相应数据
原因: 该自建应用没有开放相应的数据权限。 解决办法: 在此处配置即可。...
STM32 GPIO输入检测——按键
前言 在嵌入式系统开发中,对GPIO输入进行检测是一项常见且关键的任务。STM32微控制器作为一款功能强大的处理器,具有丰富的GPIO功能,可以轻松实现对外部信号的检测和处理。在本文中,我们将深入探讨如何在STM32微控制器上进行GPIO…...
Rustdesk二次编译,新集成AI功能开源Gpt小程序为远程协助助力,全网首发
环境: Rustdesk1.1.9 sciter版 问题描述: Rustdesk二次编译,新集成AI功能开源Gpt小程序为远程协助助力,全网首发 解决方案: Rustdesk二次编译,新集成开源AI功能Gpt小程序,为远程协助助力,…...
面试(03)————多线程和线程池
一、多线程 1、什么是线程?线程和进程的区别? 2、创建线程有几种方式 ? 3、Runnable 和 Callable 的区别? 4、如何启动一个新线程、调用 start 和 run 方法的区别? 5、线程有哪几种状态以及各种状态之间的转换? 6、线程…...
纯CSS实现未读消息显示99+
在大佬那看到这个小技巧,我觉得这个功能点还挺常用,所以给大家分享下具体的实现。当未读消息数小于100的时候显示准确数值,大于99的时候显示99。 1. 实现效果 2. 组件封装 <template><span class"col"><sup :styl…...
【C++】C++ primer plus 第十二章--类和动态内存分配
动态内存和类 关于静态数据成员 类之作声明,不分配内存,因此静态成员变量在类中不能进行初始化,需要在类外进行。特殊情况: 存在可以在类中声明静态成员并初始化的情况,成员类型为const整型或者const枚举类型。 特殊…...
网站改版 打造企业文化/百度站长工具怎么关闭教程视频
1 含义 HTTP来源地址(referer,或 HTTP referer)是HTTP表头的一个字段,用来表示从哪儿链接到目前的网页,采用的格式是URL。换句话说,借着HTTP来源地址,目前的网页可以检查访客从哪里而来…...
网站开发课设/奉化首页的关键词优化
官方的说明文档: http://appium.io/docs/en/writing-running-appium/caps/index.html#general-capabilities...
wordpress日志文件/沧州网站seo公司
本文是i春秋论坛作家「flag0」表哥原创的一篇技术文章,关于定位MFC中SDK创建窗口API位置的相关内容,感兴趣的小伙伴快来学习吧。SDK中用于创建窗口的API在SDK中创建窗口的过程,我们可以将其称为为创建窗口6要素。其分别为:1、设计…...
windows网站建设教程/浙江seo博客
查过网上的资源,基本都是认为是php线程打开文件句柄受限导致的错误。具体的解决的办法如下:1、提升服务器的文件句柄打开打开/etc/security/limits.conf : (增加)* soft nofile 51200* hard nofile 51200# vi /etc/security/limits.co…...
网站如何做原创文章/武汉seo优
直播app软件的更新优化速度非常快,而互动小游戏也是现在主流直播app中的常见功能。当然单独拿出某一个小游戏,我们都可以将它看做一个个体,如果与视频直播结合,就可以为直播软件增光添彩了。那么,直播app软件开发时&am…...
广东网页空间网站平台/网络推广平台有哪些渠道
根据API这句话,就很自然想到重写该方法,代码如下: $.messager.defaults { ok: "通过", cancel: "不通过" ,width:350};$.messager.confirm(系统提示,....,function(r){ if (r){ //通过...}else{//不通过...} }…...