算法笔记-递归/DFS/BFS类型

image.png

递归类型

递归最好的理解方式就是画出递归树

1
2
f(n)=f(n-1)+f(n-2)
f(5)=f(4)+f(3)

递归树

递归需要考虑的问题：
1.返回值
2.由全局缩小为局部看待问题

深度优先遍历 DFS

示意图

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
  	//二叉树的深度优先遍历（借助栈）
    public List<Integer> DFS(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode tmp = stack.pop();
            list.add(tmp.val);
            if (tmp.left != null) stack.push(tmp.left);
            if (tmp.right != null) stack.push(tmp.right);
        }
        return list;
    }
    //其他递归方式进行遍历也是深度优先遍历
}

广度优先遍历 BFS

示意图

模板

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
	  //二叉树的广度优先遍历（借助队列）
    public void BFS(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (!Objects.isNull(root)) queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();//出队
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
    }
}

相关题目

括号生成(中等)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

 

示例：

输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<String>();//存储结果
        generate(res, "", 0, 0, n);//函数入口
        return res;//返回结果
    }
    //count1统计“(”的个数，count2统计“)”的个数
    public void generate(List<String> res , String ans, int count1, int count2, int n){
        if(count1 > n || count2 > n) return;//递归结束条件
        if(count1 == n && count2 == n)  res.add(ans);//相等返回
        if(count1 >= count2){//左括号数量大于等于右括号
            String ans1 = new String(ans);
            generate(res, ans+"(", count1+1, count2, n);//增加左边个数
            generate(res, ans1+")", count1, count2+1, n);//增加右括号个数
        }
    }
}

回溯思想、

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
class Solution {
    
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<String>();
        backtrack(ans, new StringBuilder(), 0, 0, n);
        return ans;
    }
    //回溯函数
    public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
        //递归结束条件
        if (cur.length() == max * 2) {
            ans.add(cur.toString());//添加入结果
            return;
        }
        //
        if (open < max) {
            cur.append('(');
            backtrack(ans, cur, open + 1, close, max);
            cur.deleteCharAt(cur.length() - 1);
        }
        //
        if (close < open) {
            cur.append(')');
            backtrack(ans, cur, open, close + 1, max);
            cur.deleteCharAt(cur.length() - 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
51
52
53
54
55
56
57
58
59
60
61
62
//利用前序遍历
class Solution {
        // 先序遍历--从顶向下交换
        public TreeNode invertTree(TreeNode root) {
            if (root == null) return null;
            // 保存右子树
            TreeNode rightTree = root.right;
            // 交换左右子树的位置
            root.right = invertTree(root.left);
            root.left = invertTree(rightTree);
            return root;
        }
    }

//利用中序遍历
class Solution {
    public TreeNode invertTree(TreeNode root) {
            if (root == null) return null;
            invertTree(root.left); // 递归找到左节点
            TreeNode rightNode= root.right; // 保存右节点
            root.right = root.left;
            root.left = rightNode;
            // 递归找到右节点 继续交换 : 因为此时左右节点已经交换了,所以此时的右节点为root.left
            invertTree(root.left); 
    }
}

//利用后序遍历
 class Solution {
        public TreeNode invertTree(TreeNode root) {
            // 后序遍历-- 从下向上交换
            if (root == null) return null;
            TreeNode leftNode = invertTree(root.left);
            TreeNode rightNode = invertTree(root.right);
            root.right = leftNode;
            root.left = rightNode;
            return root;
        }
    }

//利用层次遍历
   class Solution {
        public TreeNode invertTree(TreeNode root) {
            // 层次遍历--直接左右交换即可
            if (root == null) return null;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()){
                TreeNode node = queue.poll();
                TreeNode rightTree = node.right;
                node.right = node.left;
                node.left = rightTree;
                if (node.left != null){
                    queue.offer(node.left);
                }
                if (node.right != null){
                    queue.offer(node.right);
                }
            }
            return root;
        }
    }

验证二叉搜索树(中等)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 访问左子树
        if (!isValidBST(root.left)) {
            return false;
        }
        // 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
        if (root.val <= pre) {
            return false;
        }
        pre = root.val;
        // 访问右子树
        return isValidBST(root.right);
    }
}

二叉树的最大深度(简单)

1
2
3
4
5
class Solution {
    public int maxDepth(TreeNode root) {
        return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

二叉树的最小深度(简单)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    // null节点不参与比较
    if (root.left == null && root.right != null) {
        return 1 + minDepth(root.right);
    }
    // null节点不参与比较
    if (root.right == null && root.left != null) {
        return 1 + minDepth(root.left);
    }
    return 1 + Math.min(minDepth(root.left), minDepth(root.right));
    }
}

二叉树的序列化与反序列化(困难)

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
public class Codec {
    public String rserialize(TreeNode root, String str) {
        if (root == null) {
            str += "None,";
        } else {
            str += str.valueOf(root.val) + ",";
            str = rserialize(root.left, str);
            str = rserialize(root.right, str);
        }
        return str;
    }
    //序列化
    public String serialize(TreeNode root) {
        return rserialize(root, "");
    }
    //
    public TreeNode rdeserialize(List<String> l) {
        if (l.get(0).equals("None")) {
            l.remove(0);
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(l.get(0)));
        l.remove(0);
        root.left = rdeserialize(l);
        root.right = rdeserialize(l);
        return root;
    }
    //反序列化
    public TreeNode deserialize(String data) {
        String[] data_array = data.split(",");
        List<String> data_list = new LinkedList<String>(Arrays.asList(data_array));
        return rdeserialize(data_list);
    }
}

扫雷游戏(中等)

  • 当前点击的是「未挖出的地雷」，我们将其值改为 \text{X}X 即可。
  • 当前点击的是「未挖出的空方块」，我们需要统计它周围相邻的方块里地雷的数量 \textit{cnt}cnt（即 \text{M}M 的数量）。如果 \textit{cnt}cnt 为零，即执行规则 22，此时需要将其改为 \text{B}B，且递归地处理周围的八个未挖出的方块，递归终止条件即为规则 44，没有更多方块可被揭露的时候。否则执行规则 33，将其修改为数字即可。
    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
    class Solution {
        int[] dirX = {0, 1, 0, -1, 1, 1, -1, -1};
        int[] dirY = {1, 0, -1, 0, 1, -1, 1, -1};

        public char[][] updateBoard(char[][] board, int[] click) {
            int x = click[0], y = click[1];
            if (board[x][y] == 'M') {
                // 规则 1
                board[x][y] = 'X';
            } else{
                dfs(board, x, y);
            }
            return board;
        }

        public void dfs(char[][] board, int x, int y) {
            int cnt = 0;
            for (int i = 0; i < 8; ++i) {
                int tx = x + dirX[i];
                int ty = y + dirY[i];
                if (tx < 0 || tx >= board.length || ty < 0 || ty >= board[0].length) {
                    continue;
                }
                // 不用判断 M，因为如果有 M 的话游戏已经结束了
                if (board[tx][ty] == 'M') {
                    ++cnt;
                }
            }
            if (cnt > 0) {
                // 规则 3
                board[x][y] = (char) (cnt + '0');
            } else {
                // 规则 2
                board[x][y] = 'B';
                for (int i = 0; i < 8; ++i) {
                    int tx = x + dirX[i];
                    int ty = y + dirY[i];
                    // 这里不需要在存在 B 的时候继续扩展，因为 B 之前被点击的时候已经被扩展过了
                    if (tx < 0 || tx >= board.length || ty < 0 || ty >= board[0].length || board[tx][ty] != 'E') {
                        continue;
                    }
                    dfs(board, tx, ty);
                }
            }
        }
    }

单词接龙(困难)

图的广度优先遍历

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
class Solution {
    Map<String, Integer> wordId = new HashMap<String, Integer>();
    List<List<Integer>> edge = new ArrayList<List<Integer>>();
    int nodeNum = 0;

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        for (String word : wordList) {
            addEdge(word);
        }
        addEdge(beginWord);
        if (!wordId.containsKey(endWord)) {
            return 0;
        }
        int[] dis = new int[nodeNum];
        Arrays.fill(dis, Integer.MAX_VALUE);
        int beginId = wordId.get(beginWord), endId = wordId.get(endWord);
        dis[beginId] = 0;

        Queue<Integer> que = new LinkedList<Integer>();
        que.offer(beginId);
        while (!que.isEmpty()) {
            int x = que.poll();
            if (x == endId) {
                return dis[endId] / 2 + 1;
            }
            for (int it : edge.get(x)) {
                if (dis[it] == Integer.MAX_VALUE) {
                    dis[it] = dis[x] + 1;
                    que.offer(it);
                }
            }
        }
        return 0;
    }

    public void addEdge(String word) {
        addWord(word);
        int id1 = wordId.get(word);
        char[] array = word.toCharArray();
        int length = array.length;
        for (int i = 0; i < length; ++i) {
            char tmp = array[i];
            array[i] = '*';
            String newWord = new String(array);
            addWord(newWord);
            int id2 = wordId.get(newWord);
            edge.get(id1).add(id2);
            edge.get(id2).add(id1);
            array[i] = tmp;
        }
    }

    public void addWord(String word) {
        if (!wordId.containsKey(word)) {
            wordId.put(word, nodeNum++);
            edge.add(new ArrayList<Integer>());
        }
    }
}

圆圈中最后剩下的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
		//数学
    public int lastRemaining(int n, int m) {
        int f = 0;
        for (int i = 2; i != n + 1; ++i) {
            f = (m + f) % i;
        }
        return f;
    }
    //模拟
    public int lastRemaining(int n, int m) {
        int index = 0;
        List<Integer> list = new ArrayList<>(n);
        for(int i=0;i<n;i++)list.add(i);
        while(n>1){
            index = (m+index-1) % n ;
            list.remove(index);
            n--;
        }
        return list.get(0);
    }
}

矩阵中的最长递增路径（hard）

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
class Solution {
		//记忆化DFS
    private int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    private int m,n;
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix==null||matrix.length==0||matrix[0].length==0)return 0;
        m = matrix.length;
        n = matrix[0].length;
        int[][] memo = new int[m][n];
        int max = 0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                max = Math.max(dfs(matrix,i,j,memo),max);
            }
        }
        return max;
    }
    public int dfs(int[][] matrix,int x,int y,int[][] memo){   
        if(memo[x][y]!=0)return memo[x][y];
        ++memo[x][y];
        for(int[] dir:dirs){
            int newX = x+dir[0],newY = y + dir[1];
            if(newX>=0&&newX<m&&newY>=0&&newY<n&&matrix[x][y]<matrix[newX][newY]){
                memo[x][y] = Math.max(dfs(matrix,newX,newY,memo)+1,memo[x][y]);
            }
        }
        return memo[x][y];
    }
}

飞地的数量

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
class Solution {
    //思路：dfs查询当前陆地，如果x==0||y==0||x==m-1||y==n-1节点即为可跨越
    int[][] dirs = {{-1,0},{1,0},{0,1},{0,-1}};
    int cloums,rows;
    Boolean valid;
    Integer count = 0;
    public int numEnclaves(int[][] grid) {
        rows = grid.length;
        cloums = grid[0].length;
        int ret = 0;
        for(int i=0;i<rows;i++){
            for(int j=0;j<cloums;j++){
                if(grid[i][j]==1){
                    dfs(grid,i,j);
                    if(!valid)ret+=count;
                    valid = false;
                    count = 0;
                }
            }
        }
        return ret;
    }
    public int dfs(int[][] grid,int x,int y){
        grid[x][y] = 0;
        count++;
        if(x==0||y==0||x==rows-1||y==cloums-1){
            valid = true;
        }
        for(int[] dir:dirs){
            int newX = x+dir[0],newY = y+dir[1];
            if(newX>=0&&newX<rows&&newY>=0&&newY<cloums&&grid[newX][newY]==1){
                dfs(grid,newX,newY);
            }
        }
        return count;
    }
}

386. 字典序排数（mid）

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
public List<Integer> lexicalOrder(int n) {
        List<Integer> ret = new ArrayList<>();
        int num = 1;
        for (int i = 0; i < n; i++) {//总共需要轮询n轮
            ret.add(num);
            if (num * 10 <= n) num *= 10;//如果当前num*10小于n说明还可以到树的下一层
            else {//否则需要回到树的上一层
                while (num % 10 == 9 || num + 1 > n)num /= 10;//判断是否到达这一层的最后一个数
                num++;//下一个数
            }
        }
        return ret;
    }

    public List<Integer> lexicalOrderDFS(int n) {
        List<Integer> ret = new ArrayList<>();
        dfs(ret, 0, n);
        return ret;
    }

    public void dfs(List<Integer> ret, int start, int max) {
        if (start > max) return;
        for (int i = 0; i < 10; i++) {
            int num = start * 10 + i;
            if (num == 0) continue;
            if (num > max) break;
            ret.add(num);
            dfs(ret, num, max);
        }
    }

433. 最小基因变化（mid）

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
class Solution {
    //bfs:每次变化一位知道匹配end再记录变化次数取最小值
    int ret = 11;
    int[] visited;
    public int minMutation(String start, String end, String[] bank) {
        Set<String> set = new HashSet<>();
        for(String s:bank)set.add(s);
        if(!set.contains(end))return -1;
        int n = bank.length;
        visited = new int[n];
        for(int i=0;i<n;i++){
            if(visited[i]==0&&diff(start,bank[i])==1){
                visited[i] = 1;
                bfs(bank[i],end,bank,1);
                visited[i] = 0;
            }
        }
        return ret == 11 ? -1 : ret;
    }
    public void bfs(String start, String end, String[] bank,int step){
        if(start.equals(end)){
            ret = Math.min(step,ret);
            return;
        }
        for(int i=0;i<bank.length;i++){
            if(visited[i]==0&&diff(start,bank[i])==1){
                visited[i] = 1;
                bfs(bank[i],end,bank,step+1);
                visited[i] = 0;
            }
        }
    }
    public int diff(String s1,String s2){
        int diff = 0;
        for(int i=0;i<s1.length();i++){
            if(s1.charAt(i)!=s2.charAt(i))diff++;
        }
        return diff;
    }
}

464. 我能赢吗（mid）

相关资料

基础算法 > 刷题记录
算法笔记-递归/DFS/BFS类型
https://mikeygithub.github.io/2020/07/25/yuque/算法笔记-递归!DFS!BFS类型/
作者
Mikey
发布于
2020年7月25日
许可协议