当前位置：首页 > article >正文

代码随想录算法训练营Day58 | 卡玛网 110.字符串接龙、卡玛网 105.有向图的完全可达性、卡玛网 106.岛屿的周长

article 2024/11/13 11:45:05

卡玛网 110.字符串接龙

题目

110. 字符串接龙

思路

代码随想录：110.字符串接龙

寻找最短路径使用BFS最合适。

重点： 读懂题

题解

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String beginStr = sc.next();
        String endStr = sc.next();
        Set<String> wordList = new HashSet<>();
        for (int i = 0; i < n; i++) {
            wordList.add(sc.next());
        }
        //将目标字符串放入字典
        wordList.add(endStr);
        int res = ladderLength(beginStr, endStr, wordList);
        System.out.println(res);
    }

    private static int ladderLength(String beginStr, String endStr, Set<String> wordList) {
        //起始值为 1，因为从起始字符串开始计数
        int res = 1;
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginStr);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                //判断是否为目标字符串
                if (cur.equals(endStr))
                    return res;
                //找到邻接字符串
                for (String str : getNeighbors(cur, wordList)) {
                    queue.offer(str);
                }
            }
            //每一层遍历后 res++
            res++;
        }
        return 0;
    }

    private static List<String> getNeighbors(String cur, Set<String> wordList) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < cur.length(); i++) {
            //重置字符串
            char[] arr = cur.toCharArray();
            //列出所有与当前字符串相差一个字符的字符串，在字典中寻找
            for (char ch = 'a'; ch <= 'z'; ch++) {
                arr[i] = ch;
                String str = new String(arr);
                //找到后移出字典，加入邻接字符串列表
                if (wordList.contains(str)) {
                    wordList.remove(str);
                    res.add(str);
                }
            }
        }
        return res;
    }
}

卡玛网 105.有向图的完全可达性

题目

105. 有向图的完全可达性

思路

代码随想录：105.有向图的完全可达性

注意邻接表的结构。

题解

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        List<ArrayList<Integer>> graph = new ArrayList<>(N + 1);
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < K; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(b);
        }
        boolean[] visited = new boolean[N + 1];
        dfs(graph, 1, visited);
        //bfs(graph, 1, visited);
        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {
                System.out.println(-1);
                return;
            }
        }
        System.out.println(1);
    }

    private static void dfs(List<ArrayList<Integer>> graph, int start, boolean[] visited) {
        visited[start] = true;
        for (int i : graph.get(start)) {
            if (!visited[i])
                dfs(graph, i, visited);
        }
    }

    private static void bfs(List<ArrayList<Integer>> graph, int start, boolean[] visited) {
        Deque<Integer> deque = new LinkedList<>();
        deque.offer(start);
        visited[start] = true;
        ArrayList<Integer> list;
        while (!deque.isEmpty()) {
            int i = deque.poll();
            list = graph.get(i);
            for (int j : list) {
                if (!visited[j]) {
                    visited[j] = true;
                    deque.offer(j);
                }
            }
        }
    }
}

卡玛网 106.岛屿的周长

题目

106. 岛屿的周长

思路

代码随想录：106.岛屿的周长

本题其实可以不用 DFS 或者 BFS。

解法一：

遍历每一个空格，遇到陆地则计算其四周的空格情况，该陆地四周的某个空格是水域或者越界，说明可以计入周长，如图：

解法二：

计算出岛屿中总的陆地数量，总的边数为陆地数量 * 4，每有一对相邻两个陆地，边的总数就要减 2，如图：

题解

DFS：

import java.util.*;

public class Main {
    private static final int[][] DIR = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[][] graph = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                graph[i][j] = sc.nextInt();
            }
        }
        boolean[][] visited = new boolean[N][M];
        int res = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (graph[i][j] == 1 && !visited[i][j]) {
                    res = bfs(graph, visited, i, j);
                }
            }
        }
        System.out.println(res);
    }

    private static int bfs(int[][] graph, boolean[][] visited, int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        visited[x][y] = true;
        queue.offer(new int[]{x, y});
        int res = 0;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int curX = cur[0];
            int curY = cur[1];
            for (int i = 0; i < 4; i++) {
                int nextX = curX + DIR[i][0];
                int nextY = curY + DIR[i][1];
                if (nextX < 0 || nextY < 0 || nextX >= graph.length || nextY >= graph[0].length || graph[nextX][nextY] == 0) {
                    res++;
                    continue;
                }
                if (visited[nextX][nextY])
                    continue;
                visited[nextX][nextY] = true;
                queue.offer(new int[]{nextX, nextY});
            }
        }
        return res;
    }
}

解法一：

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);
    }
}

解法二：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[][] grid = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                grid[i][j] = sc.nextInt();
            }
        }
        System.out.println(islandPerimeter(grid));
    }

    public static int islandPerimeter(int[][] grid) {
        int perimeter = 0;
        int rows = grid.length;
        int cols = grid[0].length;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 1) {
                    // 每个陆地格子初始有 4 条边
                    perimeter += 4;
                    // 如果上方是陆地，则减少 2 条边
                    if (i > 0 && grid[i - 1][j] == 1) {
                        perimeter -= 2;
                    }
                    // 如果左边是陆地，则减少 2 条边
                    if (j > 0 && grid[i][j - 1] == 1) {
                        perimeter -= 2;
                    }
                }
            }
        }
        return perimeter;
    }
}
             if (i > 0 && grid[i - 1][j] == 1) {
                        perimeter -= 2;
                    }
                    // 如果左边是陆地，则减少 2 条边
                    if (j > 0 && grid[i][j - 1] == 1) {
                        perimeter -= 2;
                    }
                }
            }
        }
        return perimeter;
    }
}