刷题日记 - 12

class Solution {
    public static int lengthOfLongestSubstringTwoDistinct(String s) {
        char[] chars = s.toCharArray();
        int len = chars.length;

        int left = 0;
        int right = 0; // [left,right)
        int[] cnt = new int[26];
        int count = 0;
        int res = 0;

        while(right<len){
            char rightChar = chars[right++];
            if(cnt[rightChar-'a']==0){
                count++;
            }
            cnt[rightChar-'a']++;
            while(count>2){
                char leftChar = chars[left++];
                cnt[leftChar-'a']--;
                if(cnt[leftChar-'a']==0)count--;
            }
            res = Math.max(res,right-left);
        }

        return res;
    }
}

class Solution {
    public int shortestBridge(int[][] grid) {
        int n = grid.length;

        // 1. 找到其中一个岛屿的起始点
        // 初始化坐标 x 和 y，找到第一个值为 1 的位置
        int x = -1;
        int y = -1;
        for (int i = 0; i < n; i++) {
            boolean flag = true; // 用于跳出循环的标志
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) { // 找到第一个岛屿的某个点
                    x = i; // 记录 x 坐标
                    y = j; // 记录 y 坐标
                    flag = false; // 找到后将 flag 置为 false
                    break; // 结束内层循环
                }
            }
            if (!flag) break; // 如果已经找到，结束外层循环
        }

        // 2. 使用 DFS 扩展岛屿，计算最短桥梁
        int res = -1; // 用于存储结果，初始值为 -1
        for (int i = 1; i <= n; i++) {
            if (dfs(i, x, y, grid) == true) { // 如果找到另一座岛屿
                res = i - 1; // 返回需要的步数，即 round - 1
                break; // 找到桥后，结束循环
            }
        }
        return res; // 返回结果
    }

    // 递归函数 dfs，用于扩展岛屿并寻找另一座岛
    private boolean dfs(int round, int x, int y, int[][] grid) {
        // 1. 边界检查：坐标越界时返回 false
        if (x < 0 || y < 0 || x >= grid.length || y >= grid.length) {
            return false; // 超出矩阵边界
        }
        
        // 2. 获取当前坐标的值
        int curVal = grid[x][y];
        
        // 3. 如果当前点已经被扩展到 round，继续向周围扩展
        if (curVal == round) {
            grid[x][y] = round + 1; // 将当前点的值更新为 round + 1
            
            // 递归向上下左右扩展
            boolean a = dfs(round, x - 1, y, grid) || dfs(round, x + 1, y, grid);
            boolean b = dfs(round, x, y - 1, grid) || dfs(round, x, y + 1, grid);
            
            // 返回结果，判断是否找到另一座岛
            return a || b;
        
        // 4. 如果当前点是水（值为 0），则将其标记为 round + 1，表示扩展到了该位置
        } else if (curVal == 0) {
            grid[x][y] = round + 1;  
        
        // 5. 如果当前点是另一个岛屿（值为 1），返回 true，表示找到另一座岛
        } else if (curVal == 1) {
            return true; // 找到另一座岛屿
        }

        return false; // 如果没有找到岛屿，返回 false
    }
}

class Solution {
    private int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    
    public int shortestBridge(int[][] grid) {
        int n = grid.length;
        Queue<int[]> queue = new LinkedList<>();  // 这个队列存放边界点（第一次是岛屿所有的点，后面几次才是边界点）
        boolean[][] visited = new boolean[n][n];
        
        // 1. 找到并标记第一个岛屿，同时将岛屿所有的点加入队列
        boolean found = false;
        for (int i = 0; i < n; i++) {
            if (found) break;
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    dfsMarkIsland(grid, visited, queue, i, j);
                    found = true;
                    break;
                }
            }
        }
        
        // 2. 使用 BFS 扩展边界，寻找另一座岛屿 
        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] point = queue.poll();
                int x = point[0], y = point[1];
                
                // 扩展四个方向
                for (int[] dir : directions) {
                    int newX = x + dir[0];
                    int newY = y + dir[1];
                    
                    // 检查边界
                    if (newX >= 0 && newY >= 0 && newX < n && newY < n && !visited[newX][newY]) {
                        if (grid[newX][newY] == 1) {
                            return steps; // 找到另一个岛屿，返回步数
                        }
                        if (grid[newX][newY] == 0) {
                            queue.offer(new int[]{newX, newY});
                        }
                        visited[newX][newY] = true;
                    }
                }
            }
            steps++; // 每扩展一层，步数加1
        }
        return -1; // 理论上不会走到这里
    }

    // 深度优先搜索标记第一个岛屿，并将所有点加入队列
    private void dfsMarkIsland(int[][] grid, boolean[][] visited, Queue<int[]> queue, int x, int y) {
        int n = grid.length;
        visited[x][y] = true;
        queue.offer(new int[]{x, y}); // 将岛屿点加入队列
        
        for (int[] dir : directions) {
            int newX = x + dir[0];
            int newY = y + dir[1];
            if (newX >= 0 && newY >= 0 && newX < n && newY < n && !visited[newX][newY] && grid[newX][newY] == 1) {
                dfsMarkIsland(grid, visited, queue, newX, newY);
            }
        }
    }
}