图论第一天|797.所有可能的路径 200. 岛屿数量

2024-01-27 20:04

本文主要是介绍图论第一天|797.所有可能的路径 200. 岛屿数量,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • Leetcode797.所有可能的路径
  • Leetcode200. 岛屿数量

Leetcode797.所有可能的路径

文章链接:代码随想录
题目链接:797.所有可能的路径

思路:深搜入门,注意邻接表和邻接矩阵的形式

class Solution {
public:vector<vector<int>> result;vector<int> path;void dfs(vector<vector<int>>& graph, int x){if (x == graph.size() - 1){result.push_back(path);return ;}for (int i = 0; i < graph[x].size(); i++){path.push_back(graph[x][i]);dfs(graph, graph[x][i]);path.pop_back();}}vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {path.push_back(0);dfs(graph, 0);return result;}
};

Leetcode200. 岛屿数量

文章链接:代码随想录
题目链接:200. 岛屿数量

思路:深搜法

class Solution {
public:int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y){for (int i = 0; i < 4; i++){int nex = x + dir[i][0];int ney = y + dir[i][1];if (nex < 0 || nex >= grid.size() || ney < 0 || ney >= grid[0].size()) continue ;if (!visited[nex][ney] && grid[nex][ney] == '1'){visited[nex][ney] = true;dfs(grid, visited, nex, ney);}}}int numIslands(vector<vector<char>>& grid) {int result = 0;vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), 0));for (int i = 0; i < grid.size(); i++){for (int j = 0; j < grid[0].size(); j++){if (!visited[i][j] && grid[i][j] == '1'){result++;visited[i][j] = true;dfs(grid, visited, i, j);}}}return result;}
};

广搜法,用队列存储,遍序搜寻,替代深搜回溯

class Solution {
public:int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y){queue<pair<int, int>> que;que.push({x, y});visited[x][y] = true;while(!que.empty()){pair<int, int> cur = que.front();que.pop();for (int i = 0; i < 4; i++){int nex = cur.first + dir[i][0];int ney = cur.second + dir[i][1];if (nex < 0 || nex >= grid.size() || ney < 0 || ney >= grid[0].size()) continue ;if (!visited[nex][ney] && grid[nex][ney] == '1'){que.push({nex, ney});visited[nex][ney] = true;}}}}int numIslands(vector<vector<char>>& grid) {int result = 0;vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), 0));for (int i = 0; i < grid.size(); i++){for (int j = 0; j < grid[0].size(); j++){if (!visited[i][j] && grid[i][j] == '1'){result++;bfs(grid, visited, i, j);}}}return result;}
};

图论第一天打卡,加油!!!

这篇关于图论第一天|797.所有可能的路径 200. 岛屿数量的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/651334

相关文章

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

【408DS算法题】039进阶-判断图中路径是否存在

Index 题目分析实现总结 题目 对于给定的图G,设计函数实现判断G中是否含有从start结点到stop结点的路径。 分析实现 对于图的路径的存在性判断,有两种做法:(本文的实现均基于邻接矩阵存储方式的图) 1.图的BFS BFS的思路相对比较直观——从起始结点出发进行层次遍历,遍历过程中遇到结点i就表示存在路径start->i,故只需判断每个结点i是否就是stop

Android Environment 获取的路径问题

1. 以获取 /System 路径为例 /*** Return root of the "system" partition holding the core Android OS.* Always present and mounted read-only.*/public static @NonNull File getRootDirectory() {return DIR_ANDR

图的最短路径算法——《啊哈!算法》

图的实现方式 邻接矩阵法 int[][] map;// 图的邻接矩阵存储法map = new int[5][5];map[0] = new int[] {0, 1, 2, 3, 4};map[1] = new int[] {1, 0, 2, 6, 4};map[2] = new int[] {2, 999, 0, 3, 999};map[3] = new int[] {3, 7

Java基础回顾系列-第一天-基本语法

基本语法 Java基础回顾系列-第一天-基本语法基础常识人机交互方式常用的DOS命令什么是计算机语言(编程语言) Java语言简介Java程序运行机制Java虚拟机(Java Virtual Machine)垃圾收集机制(Garbage Collection) Java语言的特点面向对象健壮性跨平台性 编写第一个Java程序什么是JDK, JRE下载及安装 JDK配置环境变量 pathHe

找出php中可能有问题的代码行

前言 当你发现一个平时占用cpu比较少的进程突然间占用cpu接近100%时,你如何找到导致cpu飙升的原因?我的思路是,首先找到进程正在执行的代码行,从而确定可能有问题的代码段。然后,再仔细分析有问题的代码段,从而找出原因。 如果你的程序使用的是c、c++编写,那么你可以很容易的找到正在执行的代码行。但是,程序是php编写的,如何找到可能有问题的代码行呢?这个问题就是本文要解决的问题。 背景

vcpkg子包路径批量获取

获取vcpkg 子包的路径,并拼接为set(CMAKE_PREFIX_PATH “拼接路径” ) import osdef find_directories_with_subdirs(root_dir):# 构建根目录下的 "packages" 文件夹路径root_packages_dir = os.path.join(root_dir, "packages")# 如果 "packages"

Collection的所有的方法演示

import java.util.ArrayList;import java.util.Collection;import java.util.Iterator;public class TestCollection {/*** @param args* Collection的所有的方法演示* 此程序没有使用泛型,所以可以添加任意类型* 以后如果写到泛型会补充这一方面的内容*/public s