Day47 | 110.字符串接龙 105.有向图的完全可达性 106.岛屿的周长

本文主要是介绍Day47 | 110.字符串接龙 105.有向图的完全可达性 106.岛屿的周长,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

110.字符串接龙

110. 字符串接龙

题目

题目描述

字典 strList 中从字符串 beginStr 和 endStr 的转换序列是一个按下述规格形成的序列: 

1. 序列中第一个字符串是 beginStr。

2. 序列中最后一个字符串是 endStr。 

3. 每次转换只能改变一个字符。 

4. 转换过程中的中间字符串必须是字典 strList 中的字符串,且strList里的每个字符串只用使用一次。 

给你两个字符串 beginStr 和 endStr 和一个字典 strList,找到从 beginStr 到 endStr 的最短转换序列中的字符串数目。如果不存在这样的转换序列,返回 0。

输入描述

第一行包含一个整数 N,表示字典 strList 中的字符串数量。 第二行包含两个字符串,用空格隔开,分别代表 beginStr 和 endStr。 后续 N 行,每行一个字符串,代表 strList 中的字符串。

输出描述

输出一个整数,代表从 beginStr 转换到 endStr 需要的最短转换序列中的字符串数量。如果不存在这样的转换序列,则输出 0。

思路

  1. 初始化
    • 使用HashSetset)来存储wordList中的所有单词,以便快速检查某个单词是否存在于列表中。
    • 使用Queuequeue)来存储待处理的单词,这些单词是当前已经找到但尚未探索完所有可能变化的单词。
    • 使用HashMapvisitMap)来记录每个单词被访问时的路径长度(即距离起始单词的步数)。
  2. BFS过程
    • 将起始单词加入队列和访问记录中,并设置其路径长度为1。
    • 循环处理队列中的单词,直到队列为空。
    • 对于每个单词,尝试替换其每个位置的字符为'a'到'z'之间的所有字符,生成新的单词。
    • 检查新单词是否为目标单词,如果是,则返回当前路径长度加1。
    • 如果新单词存在于set中且之前未被访问过,则将其加入队列和访问记录中,并更新其路径长度。
  3. 结果
    • 如果遍历完所有可能的单词后仍未找到目标单词,则返回0,表示无法从起始单词到达目标单词。

代码

import java.util.*;public class Main {// BFS方法public static int ladderLength(String beginWord, String endWord, List<String> wordList) {// 使用set作为查询容器,效率更高HashSet<String> set = new HashSet<>(wordList);// 声明一个queue存储每次变更一个字符得到的且存在于容器中的新字符串Queue<String> queue = new LinkedList<>();// 声明一个hashMap存储遍历到的字符串以及所走过的路径pathHashMap<String, Integer> visitMap = new HashMap<>();queue.offer(beginWord);visitMap.put(beginWord, 1);while (!queue.isEmpty()) {String curWord = queue.poll();int path = visitMap.get(curWord);for (int i = 0; i < curWord.length(); i++) {char[] ch = curWord.toCharArray();// 每个位置尝试26个字母for (char k = 'a'; k <= 'z'; k++) {ch[i] = k;String newWord = new String(ch);if (newWord.equals(endWord)) return path + 1;// 如果这个新字符串存在于容器且之前未被访问到if (set.contains(newWord) && !visitMap.containsKey(newWord)) {visitMap.put(newWord, path + 1);queue.offer(newWord);}}}}return 0;}public static void main (String[] args) {/* code */// 接收输入Scanner sc = new Scanner(System.in);int N = sc.nextInt();sc.nextLine();String[] strs = sc.nextLine().split(" ");List<String> wordList = new ArrayList<>();for (int i = 0; i < N; i++) {wordList.add(sc.nextLine());}// wordList.add(strs[1]);// 打印结果int result = ladderLength(strs[0], strs[1], wordList);System.out.println(result);}
}

易错点

  1. 输入处理
    • 在读取N(单词列表的大小)后,需要调用sc.nextLine()来跳过行尾的换行符,否则在读取第一个单词时会出错。
    • 题目中可能未明确说明,但通常假设strs[0]是起始单词,strs[1]是目标单词,而剩余的单词在wordList中。然而,在你的代码中,你直接从sc.nextLine()读取了所有单词(除了N),这可能不是题目意图。你应该根据题目要求来读取这些单词。
  2. 字符串处理
    • 在替换字符时,需要确保使用字符数组来避免在循环中多次创建新的字符串对象。
    • 替换字符后,应检查新生成的单词是否存在于set中且之前未被访问过。
  3. 边界条件
    • 如果wordList为空或未包含起始单词和目标单词,应返回适当的值(通常是0,表示无法到达)。
    • 如果起始单词和目标单词相同,应返回1(因为不需要任何变化)。

105.有向图的完全可达性

105. 有向图的完全可达性

题目

题目描述

给定一个有向图,包含 N 个节点,节点编号分别为 1,2,...,N。现从 1 号节点开始,如果可以从 1 号节点的边可以到达任何节点,则输出 1,否则输出 -1。

输入描述

第一行包含两个正整数,表示节点数量 N 和边的数量 K。 后续 K 行,每行两个正整数 s 和 t,表示从 s 节点有一条边单向连接到 t 节点。

输出描述

如果可以从 1 号节点的边可以到达任何节点,则输出 1,否则输出 -1。

思路

  1. 输入处理:首先,程序通过Scanner类读取图的节点数n和边数m。然后,它初始化一个大小为n+1List<List<Integer>>类型的邻接表graph,其中每个内部列表代表一个节点的所有邻居节点。由于节点编号从1开始,但数组索引从0开始,因此需要大小为n+1的列表数组。

  2. 构建邻接表:通过读取每对相连的节点st,将t添加到s的邻居列表中。注意,这里的st是节点编号,不是索引,因此它们可以直接用作graph的索引(尽管实际上它们被用作索引时减1,因为内部索引是从0开始的)。

  3. 深度优先搜索:从节点1开始进行深度优先搜索。在搜索过程中,使用一个布尔数组visited来跟踪哪些节点已经被访问过。对于每个节点,如果它尚未被访问,则标记为已访问,并递归地访问其所有邻居。

  4. 检查访问情况:在DFS完成后,程序遍历visited数组,检查是否有任何节点未被访问。如果有任何节点未被访问,则输出-1表示不是所有节点都可从起始节点访问;如果所有节点都被访问,则输出1

代码

import java.util.ArrayList;  
import java.util.Arrays;  
import java.util.List;  
import java.util.Scanner;  public class Main {  static void dfs(List<List<Integer>> graph, int key, boolean[] visited) {  if (visited[key]) {  return;  }  visited[key] = true;  List<Integer> keys = graph.get(key);  for (int neighbor : keys) {  // 深度优先搜索遍历  dfs(graph, neighbor, visited);  }  }  public static void main(String[] args) {  Scanner scanner = new Scanner(System.in);  int n = scanner.nextInt();  int m = scanner.nextInt();  // 节点编号从1到n,但数组索引从0开始,所以申请 n+1 这么大的数组  List<List<Integer>> graph = new ArrayList<>(n + 1);  for (int i = 0; i <= n; i++) {  graph.add(new ArrayList<>());  }  while (m-- > 0) {  int s = scanner.nextInt();  int t = scanner.nextInt();  // 使用邻接表 ,表示 s -> t 是相连的  graph.get(s).add(t);  }  boolean[] visited = new boolean[n + 1];  dfs(graph, 1, visited);  // 检查是否都访问到了  boolean allVisited = true;  for (int i = 1; i <= n; i++) {  if (!visited[i]) {  System.out.println(-1);  allVisited = false;  break;  }  }  if (allVisited) {  System.out.println(1);  }  scanner.close();  }  
}

易错点

  1. 索引与节点编号的混淆:在这个问题中,节点编号是从1开始的,但数组索引是从0开始的。这可能导致在处理输入时出错,尤其是当直接使用节点编号作为索引时。然而,在这个特定的代码中,由于graph的索引被正确地处理(即graph.get(s)中的s是节点编号,但内部自动减1以用作索引),这个错误被避免了。

  2. 邻接表的构建:在构建邻接表时,必须确保每个节点都有一个对应的空列表。在这个例子中,通过初始化一个大小为n+1ArrayList<ArrayList<Integer>>来确保这一点。

  3. DFS的递归深度:如果图是高度递归的(例如,存在很长的路径或循环),那么DFS可能会导致堆栈溢出。虽然在这个简单的例子中不太可能出现,但在处理大型或复杂的图时需要注意。

106.岛屿的周长

106. 岛屿的周长

题目

题目描述

给定一个由 1(陆地)和 0(水)组成的矩阵,岛屿是被水包围,并且通过水平方向或垂直方向上相邻的陆地连接而成的。

你可以假设矩阵外均被水包围。在矩阵中恰好拥有一个岛屿,假设组成岛屿的陆地边长都为 1,请计算岛屿的周长。岛屿内部没有水域。

输入描述

第一行包含两个整数 N, M,表示矩阵的行数和列数。之后 N 行,每行包含 M 个数字,数字为 1 或者 0,表示岛屿的单元格。

输出描述

输出一个整数,表示岛屿的周长。

思路

目的是计算一个二维网格中所有值为1的单元格的周长总和。程序首先通过标准输入接收网格的行数M和列数N,然后读取网格的具体内容(即每个单元格的值)。接下来,程序遍历整个网格,对于每个值为1的单元格,它调用helper函数来计算该单元格的周长,并将所有值为1的单元格的周长累加到result变量中。最后,程序输出总周长。

代码

import java.util.*;public class Main {// 每次遍历到1,探索其周围4个方向,并记录周长,最终合计// 声明全局变量,dirs表示4个方向static int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};// 统计每单个1的周长static int count;// 探索其周围4个方向,并记录周长public static void helper(int[][] grid, int x, int y) {for (int[] dir : dirs) {int nx = x + dir[0];int ny = y + dir[1];// 遇到边界或者水,周长加一if (nx < 0 || nx >= grid.length || ny < 0 || ny >= grid[0].length|| grid[nx][ny] == 0) {count++;}}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 接收输入int M = sc.nextInt();int N = sc.nextInt();int[][] grid = new int[M][N];for (int i = 0; i < M; i++) {for (int j = 0; j < N; j++) {grid[i][j] = sc.nextInt();}}int result = 0; // 总周长for (int i = 0; i < M; i++) {for (int j = 0; j < N; j++) {if (grid[i][j] == 1) {count = 0;helper(grid, i, j);// 更新总周长result += count;}}}// 打印结果System.out.println(result);}
}

易错点

  1. 全局变量count的线程安全问题
    在这个程序中,count被用作全局变量来存储单个值为1的单元格的周长。由于Java的static变量是类级别的,而不是实例级别的,因此它在这个上下文中是安全的,因为程序是单线程的。然而,在多线程环境中,这种使用全局变量的方式可能会导致竞态条件。在这个特定程序中,由于不存在多线程,所以这不是一个问题。

  2. 边界条件处理
    helper函数正确地处理了边界条件和值为0的单元格,这是计算周长所必需的。然而,如果网格的大小(MN)为0或负数,程序将抛出异常。虽然这种情况在常规输入中不太可能发生,但最好添加一些额外的检查来确保输入的有效性。

总结

明天继续图论!

继续加油

成功的人不是赢在起点,而是坚持到终点

这篇关于Day47 | 110.字符串接龙 105.有向图的完全可达性 106.岛屿的周长的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3

java字符串数字补齐位数详解

《java字符串数字补齐位数详解》:本文主要介绍java字符串数字补齐位数,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java字符串数字补齐位数一、使用String.format()方法二、Apache Commons Lang库方法三、Java 11+的St

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

Linux find 命令完全指南及核心用法

《Linuxfind命令完全指南及核心用法》find是Linux系统最强大的文件搜索工具,支持嵌套遍历、条件筛选、执行动作,下面给大家介绍Linuxfind命令完全指南,感兴趣的朋友一起看看吧... 目录一、基础搜索模式1. 按文件名搜索(精确/模糊匹配)2. 排除指定目录/文件二、根据文件类型筛选三、时间

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自

Golang中拼接字符串的6种方式性能对比

《Golang中拼接字符串的6种方式性能对比》golang的string类型是不可修改的,对于拼接字符串来说,本质上还是创建一个新的对象将数据放进去,主要有6种拼接方式,下面小编就来为大家详细讲讲吧... 目录拼接方式介绍性能对比测试代码测试结果源码分析golang的string类型是不可修改的,对于拼接字

JavaScript中的Map用法完全指南

《JavaScript中的Map用法完全指南》:本文主要介绍JavaScript中Map用法的相关资料,通过实例讲解了Map的创建、常用方法和迭代方式,还探讨了Map与对象的区别,并通过一个例子展... 目录引言1. 创建 Map2. Map 和对象的对比3. Map 的常用方法3.1 set(key, v