图论| 827. 最大人工岛 127. 单词接龙

827. 最大人工岛

题目：给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。返回执行此操作后，grid 中最大的岛屿面积是多少？
岛屿 由一组上、下、左、右四个方向相连的 1 形成。
题目链接：[827. 最大人工岛](https://leetcode.cn/problems/making-a-large-island/)
解题思路：暴力解法 把每一个0改为1计算岛屿面积 复杂度：改每一个0为1:n2计算岛屿最大面积n2 会超时
优化思路：遍历记录所有岛屿面积 将0附近（上下左右）的岛屿进行联通
1.遍历记录所有岛屿面积
如何记录：遍历过的岛屿标记岛屿编号（从2开始） 将岛屿编号和最大面积记录在set中
2. 将0附近（上下左右）的岛屿进行联通
如何判断0周围的面积：遍历0周围的岛屿面积进行联通，将周围的岛屿加入set以防重复叠加
代码如下：

class Solution {public int[][] mark;public int[][] move={{0,1},{0,-1},{1,0},{-1,0}};public HashMap<Integer, Integer> island = new HashMap<Integer, Integer>();public int largestIsland(int[][] grid) {//遍历岛屿并记录int maxArea=0;int masknum=2;mark=new int[grid.length][grid[0].length];for(int i=0;i<grid.length;i++){for(int j=0;j<grid[0].length;j++){if(mark[i][j]==0&&grid[i][j]==1){bfs(grid,i,j,masknum);masknum++;}}}for(int value: island.values()) {if(value>maxArea){maxArea=value;}}//修改岛屿并记录面积for(int i=0;i<grid.length;i++){for(int j=0;j<grid[0].length;j++){if(grid[i][j]==0){HashSet<Integer> sites = new HashSet<>();for(int p=0;p<4;p++){int nextx=i+move[p][0];int nexty=j+move[p][1];if(nextx<0||nextx>=grid.length||nexty<0||nexty>=grid.length){continue;}if(mark[nextx][nexty]!=0){sites.add(mark[nextx][nexty]);}}//计算面积int area=1;for(int p:sites){area+=island.get(p);}if(area>maxArea){maxArea=area;}}}}return maxArea;}public void bfs(int[][] grid,int i,int j,int masknum){int area=1;Queue<int[]> queue=new LinkedList<>();queue.offer(new int[]{i,j});mark[i][j]=masknum;while(!queue.isEmpty()){int[] node=queue.poll();for(int p=0;p<4;p++){int nextx=node[0]+move[p][0];int nexty=node[1]+move[p][1];if(nextx<0||nextx>=grid.length||nexty<0||nexty>=grid.length){continue;}if(mark[nextx][nexty]==0&&grid[nextx][nexty]==1){queue.offer(new int[]{nextx,nexty});mark[nextx][nexty]=masknum;area++;}}}island.put(masknum,area);}
}

217 单词接龙

题目：字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> … -> sk：
每一对相邻的单词只差一个字母。
对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
sk == endWord
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。
题目链接：217 单词接龙

解题思路：
为了保证从 beginWord 到 endWord 的转换序列是最短路径，我们使用广度优先搜索（BFS）算法。BFS 有一个重要特性：它首先访问距离源点（在这个场景中是 beginWord）最近的节点。因此，当我们首次到达 endWord 时，我们可以确信找到的路径是最短的。
我们使用队列进行广度优先搜索 每次从队列中取出一个单词，查找与其相差一个字母的所有单词，并将这些单词加入队列 为了防止重复处理相同的单词，我们需要从 wordList 中移除已经处理过的单词。具体是将其与对应路径长度加入map中
代码如下

class Solution {public int ladderLength(String beginWord, String endWord, List<String> wordList) {if (!wordList.contains(endWord)) {return 0;}if (!wordList.contains(beginWord)) {wordList.add(beginWord);}HashSet<String> wordSet = new HashSet<>(wordList);Queue<String> queue = new LinkedList<>();queue.offer(beginWord);Map<String, Integer> visited = new HashMap<>();visited.put(beginWord, 1);while (!queue.isEmpty()) {String currentWord = queue.poll();int currentLength = visited.get(currentWord);for (String word : wordSet) {if (isOneLetterDiff(currentWord, word)) {if (word.equals(endWord)) {return currentLength + 1;}if (!visited.containsKey(word)) {queue.offer(word);visited.put(word, currentLength + 1);}}}}return 0;}private boolean isOneLetterDiff(String word1, String word2) {if (word1.length() != word2.length()) {return false;}int diffCount = 0;for (int i = 0; i < word1.length(); i++) {if (word1.charAt(i) != word2.charAt(i)) {diffCount++;if (diffCount > 1) {return false;}}}return diffCount == 1;}
}