图论| 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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50