Day9，Hot100（图论）

news/2025/2/24 17:44:06

图论

图论部分推荐 acm 模式，因为图的输入处理不一样

DFS，类似二叉树的递归遍历
BFS，类似二叉树的层次遍历

leetcode.cn/problems/implement-trie-prefix-tree/description/?envType=study-plan-v2&envId=top-100-liked" rel="nofollow">208. 实现 Trie (前缀树)

数据结构大概如下：

  • 可以看成是 二十六叉树 （因为26个小写字母）
    在这里插入图片描述
class Node:
    def __init__(self):
        self.son = {}
        self.end = False  # end=True, 表示当前结点已经构成一个单词

class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, word: str) -> None:
        cur = self.root
        for c in word:
            if c not in cur.son:
                cur.son[c] = Node()
            cur = cur.son[c]
        cur.end = True

    def find(self, word: str) -> int:
        cur = self.root
        for c in word:
            if c not in cur.son:
                return 0
            cur = cur.son[c]
        return 2 if cur.end else 1

    def search(self, word: str) -> bool:
        return self.find(word) == 2

    def startsWith(self, prefix: str) -> bool:
        return self.find(prefix) != 0

DFS

（1）leetcode.cn/problems/number-of-islands/description/?envType=study-plan-v2&envId=top-100-liked" rel="nofollow">200. 岛屿数量

方法一：DFS

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        dx = [0,-1,0,1]
        dy = [-1,0,1,0]

        def dfs(i, j):
            if (not 0 <= i < m) or (not 0 <= j < n) or grid[i][j] == '0':
                return

            grid[i][j] = '0'

            for idx in range(4):
                x = i + dx[idx]
                y = j + dy[idx]
                dfs(x,y)

        m = len(grid)
        n = len(grid[0])
        ans = 0 
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    dfs(i,j)  # 把整个岛都标记
                    ans += 1
        return ans

ACM 代码模式：99. 岛屿数量
在这里插入图片描述

读取每一行输入map(int, input().split())

  • input().split()，将输入的行，按照空格切分每个元素，返回一个list
  • map(int, input().split())，将 list 中每个元素转化为指定的 int类型，返回一个可迭代的对象

例如输入1 2 3 4

  • input().split()，得到[‘1’, ‘2’, ‘3’, ‘4’]
  • list(map(int, input().split()))，[1, 2, 3, 4]
dx = [-1,0,1,0]
dy = [0,-1,0,1]

def dfs(i, j):
    if not (0<=i<n) or not (0<=j<m) or grid[i][j]==0:
        return 
    
    grid[i][j] = 0
    
    for idx in range(4):
        x = dx[idx] + i
        y = dy[idx] + j
        dfs(x, y)


if __name__ == '__main__':
    n,m = map(int, input().split())
    grid = []
    for i in range(n):
        grid.append(list(map(int, input().split())))
    
    # visited = [ [False] * m for _ in range(n) ]
    
    ans = 0
    
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 1:
                dfs(i, j)
                ans += 1
    
    print(ans)

（2）100. 岛屿的最大面积

在这里插入图片描述

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
s = 0

def dfs(i, j):
    if not (0 <= i < n) or not (0 <= j < m) or grid[i][j] == 0:
        return

    global s
    s += 1
    grid[i][j] = 0
    for idx in range(4):
        x = dx[idx] + i
        y = dy[idx] + j
        dfs(x, y)


if __name__ == '__main__':
    n, m = map(int, input().split())
    grid = []
    for i in range(n):
        grid.append(list(map(int, input().split())))

    ans = 0

    for i in range(n):
        for j in range(m):
            if grid[i][j] == 1:
                s = 0
                dfs(i, j)
                ans = max(ans, s)
    print(ans)

（3）101. 孤岛的总面积

在这里插入图片描述
在这里插入图片描述

步骤

  • 首先把四周靠边界的岛屿都设为 0
  • 然后遍历剩余的孤岛面积
dx = [-1,0,1,0]
dy = [0,-1,0,1]
s = 0

def dfs(i,j):
    if not (0<=i<n) or not (0<=j<m) or grid[i][j] == 0:
        return
    global s
    s += 1
    grid[i][j] = 0
    for idx in range(4):
        x = dx[idx] + i
        y = dy[idx] + j
        dfs(x,y)

if __name__ == '__main__':
    n, m = map(int, input().split())
    grid = []
    for i in range(n):
        grid.append(list(map(int, input().split())))

    # 将四周贴边的非孤岛区域转为水
    # 遍历第一列和最后一列
    for i in range(n):
        if grid[i][0] == 1:
            dfs(i,0)
        elif grid[i][m-1] == 1:
            dfs(i,m-1)

    # 遍历第一行和最后一行
    for j in range(m):
        if grid[0][j] == 1:
            dfs(0,j)
        elif grid[n-1][j] == 1:
            dfs(n-1,j)

    # 计算孤岛面积
    s = 0
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 1:
                dfs(i,j)
    print(s)

（4）102. 沉没孤岛

在这里插入图片描述

  1. 把靠四周的非孤岛标记为2
  2. 接着把剩余的1(孤岛)，标记为0
  3. 最后把2修改回1
dx = [-1,0,1,0]
dy = [0,-1,0,1]

def dfs(i,j):
    if not (0 <= i < n) or not(0 <= j < m) or grid[i][j] != 1:
        return 
    
    grid[i][j] = 2
    
    for k in range(4):
        x = dx[k] + i
        y = dy[k] + j
        dfs(x,y)

if __name__ == '__main__':
    n,m = map(int, input().split())
    grid = []
    
    for _ in range(n):
        grid.append(list(map(int, input().split())))
    
    for i in range(n):
        if grid[i][0] == 1:
            dfs(i, 0)
        if grid[i][m-1] == 1:
            dfs(i, m-1)
    
    for j in range(m):
        if grid[0][j] == 1:
            dfs(0,j)
        if grid[n-1][j] == 1:
            dfs(n-1, j)
            
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 1:
                grid[i][j] = 0
            elif grid[i][j] == 2:
                grid[i][j] = 1
        print(' '.join(map(str, grid[i])))

BFS

（1）leetcode.cn/problems/rotting-oranges/description/?envType=study-plan-v2&envId=top-100-liked" rel="nofollow">994. 腐烂的橘子

使用 BFS 是为了实现，同一个时间，当前所有腐烂的橘子同时腐烂周围

from collections import deque
class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        n, m = len(grid), len(grid[0])
        q = deque()
        
        count = 0  # 新鲜橘子数
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    count += 1
                elif grid[i][j] == 2:
                    q.append((i,j))

        dx = [-1,0,1,0]
        dy = [0,-1,0,1]

        round = 0  # 分钟数
        while count > 0 and len(q) > 0:
            round += 1
            cur = len(q)  # 这一轮有多少个腐烂的橘子一起腐烂周围
            for _ in range(cur):
                i,j = q.popleft()
                for idx in range(4):
                    x = dx[idx] + i
                    y = dy[idx] + j
                    if (0<=x<n) and (0<=y<m) and grid[x][y] == 1:
                        grid[x][y] = 2
                        count -= 1
                        q.append((x,y))

        if count > 0:
            return -1
        else:
            return round

（2）leetcode.cn/problems/course-schedule/description/?envType=study-plan-v2&envId=top-100-liked" rel="nofollow">207. 课程表

在这里插入图片描述

  1. 每次只能修当前可以修的课程——入度为0的课程
  2. 修完一轮后，再修可以休的课程——入度变为0的课程
  3. 所以我们需要记录每个课程的入度，
  4. 然后需要邻接矩阵来关联课程之间的关系，从而更新入度
    在这里插入图片描述
from collections import deque
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        indegree = [0] * numCourses  # 每个课程的入度(即先修课程有几门)
        adj = defaultdict(list) # key为当前课，value为它的后续课程,用列表存

        # 初始化入度和邻接表
        for cur,pre in prerequisites:
            indegree[cur] += 1
            adj[pre].append(cur)
        # 把入度为0的入队列
        q = deque()
        for i in range(numCourses):
            if indegree[i] == 0:
                q.append(i)
        
        while q:
            n = len(q)
            for i in range(n):
                pre = q.popleft()
                numCourses -= 1
                # 遍历课程pre的邻接表：它的后续课程
                for cur in adj[pre]:
                    # 将后续课程的入度 -1
                    indegree[cur] -= 1
                    if indegree[cur] == 0:
                        q.append(cur)
    
        return numCourses == 0

http://www.niftyadmin.cn/n/5864663.html

相关文章

C++的设计模式

C++的设计模式

1. 创建型模式 单例模式 (Singleton) 意图&#xff1a;确保类仅有一个实例&#xff0c;并提供全局访问点。&#xff08;常见的日志类&#xff09;实现&#xff1a;class Singleton { private:static Singleton* instance;Singleton() {} // 私有构造函数 public:static Singl…
阅读更多...
【深度学习】手写数字识别任务

【深度学习】手写数字识别任务

数字识别是计算机从纸质文档、照片或其他来源接收、理解并识别可读的数字的能力&#xff0c;目前比较受关注的是手写数字识别。手写数字识别是一个典型的图像分类问题&#xff0c;已经被广泛应用于汇款单号识别、手写邮政编码识别等领域&#xff0c;大大缩短了业务处理时间&…
阅读更多...
Linux 命令大全完整版（11）

Linux 命令大全完整版（11）

5.文件管理命令 diff&#xff08;differential&#xff09; 功能说明&#xff1a;比较文件的差异。语　　法&#xff1a;diff [-abBcdefHilnNpPqrstTuvwy][-<行数>][-C <行数>][-D <巨集名称>][-I <字符或字符串>][-S <文件>][-W <宽度>…
阅读更多...
DeepSeek本地搭建 和 Android

DeepSeek本地搭建 和 Android

DeepSeek 搭建和 Android 文章目录 DeepSeek 搭建和 Android一、前言二、DeepSeek 本地环境ollama搭建1、软件下载网址&#xff1a;2、Ollama的安装3、配置算法模型和使用qwen2 模型使用&#xff0c; 三、Android Studio 和 DeepSeek四、其他1、Deepseek 使用小结(1) 网页版本可…
阅读更多...
通俗理解Test time Scaling Law、RL Scaling Law和预训练Scaling Law

通俗理解Test time Scaling Law、RL Scaling Law和预训练Scaling Law

一、Scaling Law解释 1、预训练阶段的Scaling Law&#xff08;打地基阶段&#xff09; 通俗解释&#xff1a;就像建房子时&#xff0c;地基越大、材料越多、施工时间越长&#xff0c;房子就能盖得越高越稳。 核心&#xff1a;通过堆资源&#xff08;算力、数据、模型参数&am…
阅读更多...
Express + MongoDB 实现在筛选时间段中用户名的模糊查询

Express + MongoDB 实现在筛选时间段中用户名的模糊查询

使用 $gte&#xff08;大于等于&#xff09;和 $lte&#xff08;小于等于&#xff09;操作符构建时间段查询条件。使用 $regex 操作符进行模糊查询&#xff0c;$options: i 表示不区分大小写。使用 $and 操作符将它们组合起来。 // 处理查询的路由app.get("/users",…
阅读更多...
[设计模式] Builder 建造者模式

[设计模式] Builder 建造者模式

目录 意图 问题 解决 Applying the Builder pattern 主管 结构 伪代码 生成器模式适合应用场景 实现方法 生成器模式优缺点 与其他模式的关系 C代码 main.cc&#xff1a;概念示例 Output.txt&#xff1a;执行结果 意图 Builder 是一种创建性设计模式&#xff0c…
阅读更多...
C语言【指针篇】（一）

C语言【指针篇】（一）

前言 指针基础概念理解&#xff0c;从底层出发理解指针 C语言【指针篇】&#xff08;一&#xff09; 前言正文1. 内存和地址1.1 内存1.2 究竟该如何理解编址 2. 指针变量和地址2.1 取地址操作符(&)2.2 指针变量和解引用操作符(*)2.3 指针变量的大小 3. 指针变量类型的意义…
阅读更多...
最新文章

Copyright @ 2022~2023