我的CSDN博客直达

代码模板

BFS模板

def BFS(graph, start, end):
    visited = set()
    queue = [] 
    queue.append([start]) 

    while queue: 
        node = queue.pop() 
        visited.add(node)

        process(node) 
        nodes = generate_related_nodes(node) 
        queue.push(nodes)

    # other processing work 
    ...

DFS模板

递归玩法

visited = set() 

def dfs(node, visited):
    if node in visited: # terminator
        # already visited 
        return 

    visited.add(node) 

    # process current node here. 
    ...
    for next_node in node.children(): 
        if next_node not in visited: 
            dfs(next_node, visited)

非递归玩法

def DFS(self, tree): 

    if tree.root is None: 
        return [] 

    visited, stack = [], [tree.root]

    while stack: 
        node = stack.pop() 
        visited.add(node)

        process (node) 
        nodes = generate_related_nodes(node) 
        stack.push(nodes) 

    # other processing work 
    ...

二叉树的层次遍历

BFS的高频经典题目

BFS解法

class Solution {
     public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        queue.offerLast(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> tmpList = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.pollFirst();
                tmpList.add(cur.val);
                if (cur.left != null) queue.offerLast(cur.left);
                if (cur.right != null) queue.offerLast(cur.right);
            }
            res.add(tmpList);
        }
        return res;
    }
}

虽然是经典的BFS题目，但是用DFS也可以做出来

DFS解法

public class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return new LinkedList<>();
        res = new LinkedList<>();
        dfs(root, 0);
        return res;
    }
    private void dfs(TreeNode root, int depth) {
        if (root == null) return;
        if (depth >= res.size()) res.add(new LinkedList<>());
        res.get(depth).add(root.val);
        dfs(root.left, depth + 1);
        dfs(root.right, depth + 1);
    }
}

括号生成

DFS解法：

public class Solution {

    List<String> res;
    int n;

    public List<String> generateParenthesis(int n) {
        res = new ArrayList<>();
        this.n = n;
        dfs(0, 0, "");
        return res;
    }

    /**
     * @param left  左括号个数
     * @param right 右括号个数
     * @param s     结果字符串
     */
    private void dfs(int left, int right, String s) {
        //退出条件
        if (left == n && right == n) {
            res.add(s);
            return;
        }

        //可以生成左括号的条件：左括号小于n
        if (left < n) dfs(left + 1, right, s + "(");
        //可以生成右括号的条件：右括号小于左括号
        if (left > right) dfs(left, right + 1, s + ")");

        //reserve
    }
}

在每个树行中找最大值

和二叉树的中序遍历做法几乎一模一样，只需要修改结果集产生的方式

BFS解法

public class Solution {
    public List<Integer> largestValues(TreeNode root) {
        if (root == null) return new ArrayList<>();
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<TreeNode>();
        deque.offerLast(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            int lineMax = Integer.MIN_VALUE;
            for (int i = 0; i < size; i++) {
                TreeNode cur = deque.pollFirst();
                lineMax = Math.max(lineMax, cur.val);
                if (cur.left != null) deque.offerLast(cur.left);
                if (cur.right != null) deque.offerLast(cur.right);
            }
            res.add(lineMax);
        }
        return res;
    }
}

岛屿数量

DFS解法

遍历二维数组，当发现1之后，计数+1，然后调用函数dfs递归的去将这个1的所有邻接的1都变为0，然后继续搜索

public class Solution {
    public int numIslands(char[][] grid) {

        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;

        int count = 0;
        int rows = grid.length;
        int cols = grid[0].length;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1') {
                    count++;
                    //发现岛屿，然后广度优先搜索临界的区域，全部变成海洋
                    dfs(r, c, rows, cols, grid);
                }
            }
        }
        return count;
    }

    private void dfs(int r, int c, int rows, int cols, char[][] grid) {
        if (r == -1 || c == -1 || r == rows || c == cols || grid[r][c] != '1') return;

        //将当前1标记为0
        grid[r][c] = 0;

        //向上左右进行扩展
        dfs(r + 1, c, rows, cols, grid);
        dfs(r - 1, c, rows, cols, grid);
        dfs(r, c + 1, rows, cols, grid);
        dfs(r, c - 1, rows, cols, grid);
    }

}

BFS解法

public class Solution {
    public int numIslands(char[][] grid) {

        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;

        int count = 0;
        int rows = grid.length;
        int cols = grid[0].length;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1') {
                    count++;
                    //发现岛屿，然后广度优先搜索临界的区域，全部变成海洋
                    bfs(r, c, rows, cols, grid);
                }
            }
        }
        return count;
    }

    private void bfs(int r, int c, int rows, int cols, char[][] grid) {
        Deque<Integer> deque = new LinkedList<>();
        //将二维数组换为一维进行存储
        deque.offer(r * cols + c);
        while (!deque.isEmpty()) {
            Integer cur = deque.poll();
            int row = cur / cols;
            int col = cur % cols;
            //如果已经遍历过了，就不再重复
            if (grid[row][col] == '0') {
                continue;
            }
            grid[row][col] = '0';

            if (row != (rows - 1) && grid[row + 1][col] == '1') {
                deque.offer((row + 1) * cols + col);
            }

            if (col != (cols - 1) && grid[row][col + 1] == '1') {
                deque.offer(row * cols + col + 1);
            }

            if (row != 0 && grid[row - 1][col] == '1') {
                deque.offer((row - 1) * cols + col);
            }

            if (col != 0 && grid[row][col - 1] == '1') {
                deque.offer(row * cols + col - 1);
            }

        }

    }

}

岛屿的最大面积

解决方案和上一个题岛屿数量一致，遍历整个数组，发现1之后，采用dfs或者bfs进行沉岛

DFS解法

public class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int maxSize = 0;
        int rows = grid.length;
        int cols = grid[0].length;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1) {
                    maxSize = Math.max(maxSize, dfs(r, c, rows, cols, grid));
                }
            }
        }
        return maxSize;
    }

    private Integer dfs(int r, int c, int rows, int cols, int[][] grid) {

        if (r == -1 || c == -1 || r == rows || c == cols || grid[r][c] == 0) {
            return 0;
        }
        //将访问过的岛屿弄成0
        grid[r][c] = 0;

        int num = 1;

        //每个方向都进行遍历，遍历的结果进行累加就是最终的面积
        num += dfs(r + 1, c, rows, cols, grid);
        num += dfs(r, c + 1, rows, cols, grid);
        num += dfs(r - 1, c, rows, cols, grid);
        num += dfs(r, c - 1, rows, cols, grid);

        return num;
    }
}

被围绕的区域

思路：

• 遍历查找边界‘O'
• 让边界'O'采用搜索算法（bfs or dfs）查找邻接‘O‘
• 将边界‘O’和他们的邻接‘O’都设置成‘#’
• 剩下的‘O’就都是围绕的了
• 遍历数组，将所有的‘O‘修改成‘X’，将所有的‘#’修改成‘O‘

DFS解法

public class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) return;
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
                if (isEdge && board[i][j] == 'O')
                    dfs(board, i, j);
            }
        }
        //将与边界'O'有段的'O'标记之后
        //将‘O’转换为‘X’
        //将‘#’转换为‘O’
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == '#') board[i][j] = 'O';
            }
        }
    }

    private void dfs(char[][] board, int i, int j) {
        if (i == -1 || j == -1
                || i == board.length || j == board[0].length
                || board[i][j] == 'X' || board[i][j] == '#') {
            return;
        }
        //将边界‘O’和与边界‘O’相邻的‘O’都设置为#
        board[i][j] = '#';
        dfs(board, i - 1, j);
        dfs(board, i + 1, j);
        dfs(board, i, j - 1);
        dfs(board, i, j + 1);
    }
}

单词接龙

BFS解法1

用一个boolean数组记录字典中的字符串是否被访问过了
标准的bfs遍历模板（和二叉树的层次遍历相似），只是加上了一些条件的判断

• 如果beginWord在字典中，先标记为访问过，不需要再访问
• 如果字符串被访问过了，就不再进行访问
• 如果访问的字符串不满足和当前串只差一个字符不同，也不再进行操作
• 当匹配上了endWord就直接返回（因为是层序遍历，每层的次数相同且由少到多，所以第一次发现一定是最短的）

public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (!wordList.contains(endWord)) {
            return 0;
        }
        //记录是否访问过
        boolean[] visited = new boolean[wordList.size()];
        //检验是否存在beginWord，如果存在，就置为访问过了,没必要访问
        int index = wordList.indexOf(beginWord);
        if (index != -1) {
            visited[index] = true;
        }
        //bfs暂存队列
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        int count = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            count++;
            while (size-- > 0) {
                String start = queue.poll();
                for (int i = 0; i < wordList.size(); i++) {
                    //访问过了，跳过，访问下一个
                    if (visited[i]) continue;
                    String s = wordList.get(i);
                    //不满足和当前只差一个字符不同，跳过，访问下一个
                    if (!canConvert(start, s)) {
                        continue;
                    }
                    //和endWord匹配上了，进行返回，因为是bfs，所以找到了直接返回就是最短的
                    if (s.equals(endWord)) {
                        return count + 1;
                    }
                    //访问完了将当前置为已访问
                    visited[i] = true;
                    //当前值压栈
                    queue.offer(s);
                }
            }
        }
        return 0;

    }
    //判断s1和s2是否只有一个字符不同
    private boolean canConvert(String s1, String s2) {
        int count = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                count++;
                if (count > 1) {//达到两个不同了，说明不符合
                    return false;
                }
            }
        }
        //不同字符小于两个，判断是否是一个
        return count == 1;
    }
}

BFS解法2：双向BFS

public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int end = wordList.indexOf(endWord);
        if (end == -1) return 0;
        wordList.add(beginWord);
        int start = wordList.size() - 1;

        //bfs暂存队列
        Queue<Integer> queue1 = new LinkedList<>();
        Queue<Integer> queue2 = new LinkedList<>();
        //访问记录set
        Set<Integer> visited1 = new HashSet<>();
        Set<Integer> visited2 = new HashSet<>();
        queue1.offer(start);
        queue2.offer(end);
        visited1.add(start);
        visited2.add(end);
        int count = 0;
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            count++;
            //判断两个队列的长度，把短的令成1，然后把短的进行遍历，加快速度
            if (queue1.size() > queue2.size()) {//将两个的队列和set都交换下
                Queue<Integer> tmpqueue = queue1;
                queue1 = queue2;
                queue2 = tmpqueue;
                Set<Integer> tmpset = visited1;
                visited1 = visited2;
                visited2 = tmpset;
            }
            int size = queue1.size();

            while (size-- > 0) {
                String s = wordList.get(queue1.poll());
                for (int i = 0; i < wordList.size(); i++) {
                    //访问过了，跳过，访问下一个
                    if (visited1.contains(i)) continue;

                    //不满足和当前只差一个字符不同，跳过，访问下一个
                    if (!canConvert(s, wordList.get(i))) {
                        continue;
                    }
                    //退出条件
                    if (visited2.contains(i)) {
                        return count + 1;
                    }
                    //访问完了将当前置为已访问
                    visited1.add(i);
                    //当前值压栈
                    queue1.offer(i);
                }
            }
        }
        return 0;

    }

    //判断s1和s2是否只有一个字符不同
    private boolean canConvert(String s1, String s2) {
        int count = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                if (++count > 1) {//达到两个不同了，说明不符合
                    return false;
                }
            }
        }
        //不同字符小于两个，判断是否是一个
        return count == 1;
    }
}