跳到主要内容

递归与动态规划

递归与动态规划是面试中的核心考点，主要考察问题的分解、状态转移方程的设计以及记忆化搜索技巧。

面试题 08.01. 三步问题​

题目描述​

三步问题。有个小孩正在上楼梯，楼梯有 n 阶台阶，小孩一次可以上 1 阶、2 阶或 3 阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模 1000000007。

示例 1：

输入：n = 3 
输出：4
说明: 有四种走法

示例 2：

输入：n = 5
输出：13

解题思路​

动态规划。设 dp[i] 表示上 i 阶台阶的方法数。状态转移方程：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。

Java 代码实现​

class Solution {
    public int waysToStep(int n) {
        if (n <= 2) return n;
        if (n == 3) return 4;
        long[] dp = new long[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for (int i = 4; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 1000000007;
        }
        return (int) dp[n];
    }
}

面试题 08.02. 迷路的机器人​

题目描述​

设想有个机器人坐在一个网格的左上角，网格 r 行 c 列。机器人只能向下或向右移动，但不能走到一些被禁止的网格（有障碍物）。设计一种算法，寻找机器人从左上角移动到右下角的路径。

示例 1：

输入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出: [[0,0],[0,1],[0,2],[1,2],[2,2]]

解题思路​

使用 DFS 或 BFS 从起点搜索到终点的路径。需要记录已访问的位置避免重复搜索。

Java 代码实现​

class Solution {
    private List<List<Integer>> path;
    private int r, c;
    
    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        path = new ArrayList<>();
        r = obstacleGrid.length;
        c = obstacleGrid[0].length;
        if (obstacleGrid[0][0] == 1 || obstacleGrid[r - 1][c - 1] == 1) {
            return path;
        }
        boolean[][] visited = new boolean[r][c];
        dfs(obstacleGrid, 0, 0, visited);
        return path;
    }
    
    private boolean dfs(int[][] grid, int i, int j, boolean[][] visited) {
        if (i >= r || j >= c || grid[i][j] == 1 || visited[i][j]) {
            return false;
        }
        path.add(Arrays.asList(i, j));
        if (i == r - 1 && j == c - 1) {
            return true;
        }
        visited[i][j] = true;
        if (dfs(grid, i + 1, j, visited) || dfs(grid, i, j + 1, visited)) {
            return true;
        }
        path.remove(path.size() - 1);
        return false;
    }
}

面试题 08.03. 魔术索引​

题目描述​

魔术索引。在数组 A[0...n-1] 中，有所谓的魔术索引，满足条件 A[i] = i。给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组 A 中找出一个魔术索引，如果没有，则返回 -1。若有多个魔术索引，返回索引值最小的一个。

示例 1：

输入：nums = [0, 2, 3, 4, 5]
输出：0

示例 2：

输入：nums = [1, 1, 1]
输出：1

解题思路​

方法一：线性扫描

直接遍历数组查找满足条件的索引。

方法二：二分剪枝（针对有序数组）

利用数组有序的性质进行剪枝优化。

Java 代码实现​

线性扫描：

class Solution {
    public int findMagicIndex(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == i) {
                return i;
            }
        }
        return -1;
    }
}

二分剪枝：

class Solution {
    public int findMagicIndex(int[] nums) {
        return find(nums, 0, nums.length - 1);
    }
    
    private int find(int[] nums, int left, int right) {
        if (left > right) return -1;
        int mid = left + (right - left) / 2;
        int leftResult = find(nums, left, mid - 1);
        if (leftResult != -1) return leftResult;
        if (nums[mid] == mid) return mid;
        return find(nums, mid + 1, right);
    }
}

面试题 08.04. 幂集​

题目描述​

幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。

示例：

输入： nums = [1,2,3]
输出：
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

解题思路​

方法一：回溯

使用回溯法，每个元素可以选择加入或不加入。

方法二：位运算

使用位掩码枚举所有可能的子集。

Java 代码实现​

回溯法：

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }
    
    private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
        result.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrack(nums, i + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
}

面试题 08.05. 递归乘法​

题目描述​

递归乘法。写一个递归函数，不使用 * 运算符，实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。

示例 1：

输入：A = 1, B = 10
输出：10

示例 2：

输入：A = 3, B = 4
输出：12

解题思路​

使用递归和位移运算。A * B 可以转化为 (A/2) * (B*2) 或 (A/2) * (B*2) + B（当 A 为奇数时）。

Java 代码实现​

class Solution {
    public int multiply(int A, int B) {
        if (A == 0 || B == 0) return 0;
        if (A == 1) return B;
        if (B == 1) return A;
        int half = multiply(A >> 1, B);
        if ((A & 1) == 1) {
            return (half << 1) + B;
        }
        return half << 1;
    }
}

面试题 08.06. 汉诺塔问题​

题目描述​

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上（即每一个盘子只能放在更大的盘子上面）。移动圆盘时受到以下限制：

  1. 每次只能移动一个盘子
  2. 盘子只能从柱子顶端滑出移出，并滑入下一根柱子
  3. 盘子只能叠在比它大的盘子上

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。

示例 1：

输入：A = [2, 1, 0], B = [], C = []
输出：C = [2, 1, 0]

解题思路​

递归解决：

  1. 将 n-1 个盘子从 A 移到 B（借助 C）
  2. 将第 n 个盘子从 A 移到 C
  3. 将 n-1 个盘子从 B 移到 C（借助 A）

Java 代码实现​

class Solution {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        move(A.size(), A, B, C);
    }
    
    private void move(int n, List<Integer> A, List<Integer> B, List<Integer> C) {
        if (n == 1) {
            C.add(A.remove(A.size() - 1));
            return;
        }
        move(n - 1, A, C, B);
        C.add(A.remove(A.size() - 1));
        move(n - 1, B, A, C);
    }
}

面试题 08.07. 无重复字符串的排列组合​

题目描述​

无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。

示例 1：

输入：S = "qwe"
输出：["qwe", "qew", "wqe", "weq", "ewq", "eqw"]

解题思路​

使用回溯法，每次选择一个字符加入当前排列，然后递归处理剩余字符。

Java 代码实现​

class Solution {
    public String[] permutation(String S) {
        List<String> result = new ArrayList<>();
        char[] chars = S.toCharArray();
        boolean[] used = new boolean[chars.length];
        backtrack(chars, used, new StringBuilder(), result);
        return result.toArray(new String[0]);
    }
    
    private void backtrack(char[] chars, boolean[] used, StringBuilder sb, List<String> result) {
        if (sb.length() == chars.length) {
            result.add(sb.toString());
            return;
        }
        for (int i = 0; i < chars.length; i++) {
            if (!used[i]) {
                used[i] = true;
                sb.append(chars[i]);
                backtrack(chars, used, sb, result);
                sb.deleteCharAt(sb.length() - 1);
                used[i] = false;
            }
        }
    }
}

面试题 08.08. 有重复字符串的排列组合​

题目描述​

有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。

示例 1：

输入：S = "qqe"
输出：["eqq","qeq","qqe"]

解题思路​

使用回溯法，需要先排序，然后跳过重复元素。

Java 代码实现​

class Solution {
    public String[] permutation(String S) {
        List<String> result = new ArrayList<>();
        char[] chars = S.toCharArray();
        Arrays.sort(chars);
        boolean[] used = new boolean[chars.length];
        backtrack(chars, used, new StringBuilder(), result);
        return result.toArray(new String[0]);
    }
    
    private void backtrack(char[] chars, boolean[] used, StringBuilder sb, List<String> result) {
        if (sb.length() == chars.length) {
            result.add(sb.toString());
            return;
        }
        for (int i = 0; i < chars.length; i++) {
            if (used[i] || (i > 0 && chars[i] == chars[i - 1] && !used[i - 1])) {
                continue;
            }
            used[i] = true;
            sb.append(chars[i]);
            backtrack(chars, used, sb, result);
            sb.deleteCharAt(sb.length() - 1);
            used[i] = false;
        }
    }
}

面试题 08.09. 括号​

题目描述​

括号。设计一种算法，打印 n 对括号的所有合法的（例如，开闭一一对应）组合。

示例：

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

解题思路​

使用回溯法，维护左右括号的数量。可以添加左括号的条件是左括号数量小于 n，可以添加右括号的条件是右括号数量小于左括号数量。

Java 代码实现​

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(n, 0, 0, new StringBuilder(), result);
        return result;
    }
    
    private void backtrack(int n, int left, int right, StringBuilder sb, List<String> result) {
        if (sb.length() == 2 * n) {
            result.add(sb.toString());
            return;
        }
        if (left < n) {
            sb.append('(');
            backtrack(n, left + 1, right, sb, result);
            sb.deleteCharAt(sb.length() - 1);
        }
        if (right < left) {
            sb.append(')');
            backtrack(n, left, right + 1, sb, result);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

面试题 08.10. 颜色填充​

题目描述​

编写函数，实现许多图片编辑软件都支持的「颜色填充」功能。待填充的图像用二维数组 image 表示，元素为初始颜色值。初始坐标点的行坐标为 sr 列坐标为 sc。需要填充的新颜色为 newColor。「周围区域」是指颜色相同且在上、下、左、右四个方向上存在相连情况的若干元素。

示例：

输入：
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
输出：[[2,2,2],[2,2,0],[2,0,1]]

解题思路​

使用 DFS 或 BFS 从起始点开始，将所有相连的同色区域填充为新颜色。

Java 代码实现​

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int oldColor = image[sr][sc];
        if (oldColor == newColor) return image;
        dfs(image, sr, sc, oldColor, newColor);
        return image;
    }
    
    private void dfs(int[][] image, int i, int j, int oldColor, int newColor) {
        if (i < 0 || i >= image.length || j < 0 || j >= image[0].length || image[i][j] != oldColor) {
            return;
        }
        image[i][j] = newColor;
        dfs(image, i + 1, j, oldColor, newColor);
        dfs(image, i - 1, j, oldColor, newColor);
        dfs(image, i, j + 1, oldColor, newColor);
        dfs(image, i, j - 1, oldColor, newColor);
    }
}

面试题 08.11. 硬币​

题目描述​

硬币。给定数量不限的硬币，币值为 25 分、10 分、5 分和 1 分，编写代码计算 n 分有几种表示法。

示例 1：

输入: n = 5
输出：2
解释: 有两种方式凑成总金额: 5=5, 5=1+1+1+1+1

示例 2：

输入: n = 10
输出：4
解释: 有四种方式凑成总金额: 10=10, 10=5+5, 10=5+1+1+1+1+1, 10=1+1+1+1+1+1+1+1+1+1

解题思路​

完全背包问题。使用动态规划，dp[i] 表示金额 i 的组合数。

Java 代码实现​

class Solution {
    public int waysToChange(int n) {
        int[] coins = {1, 5, 10, 25};
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= n; i++) {
                dp[i] = (dp[i] + dp[i - coin]) % 1000000007;
            }
        }
        return dp[n];
    }
}

面试题 08.12. 八皇后​

题目描述​

设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的"对角线"指的是所有的对角线，不只是平分整个棋盘的那两条对角线。

示例：

输入：4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

解题思路​

使用回溯法，逐行放置皇后，检查是否与已放置的皇后冲突。

Java 代码实现​

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(board[i], '.');
        }
        backtrack(board, 0, result);
        return result;
    }
    
    private void backtrack(char[][] board, int row, List<List<String>> result) {
        if (row == board.length) {
            result.add(construct(board));
            return;
        }
        for (int col = 0; col < board.length; col++) {
            if (isValid(board, row, col)) {
                board[row][col] = 'Q';
                backtrack(board, row + 1, result);
                board[row][col] = '.';
            }
        }
    }
    
    private boolean isValid(char[][] board, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }
        for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }
        return true;
    }
    
    private List<String> construct(char[][] board) {
        List<String> list = new ArrayList<>();
        for (char[] row : board) {
            list.add(new String(row));
        }
        return list;
    }
}

面试题 08.13. 堆箱子​

题目描述​

堆箱子。给你一堆 n 个箱子，箱子宽 wi、深 di、高 hi。箱子不能翻转，将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法，搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。

示例：

输入：box = [[1, 1, 1], [2, 2, 2], [3, 3, 3]]
输出：6

解题思路​

动态规划。先按宽度、深度、高度排序，然后使用类似最长递增子序列的方法求解。

Java 代码实现​

class Solution {
    public int pileBox(int[][] box) {
        Arrays.sort(box, (a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0];
            if (a[1] != b[1]) return a[1] - b[1];
            return a[2] - b[2];
        });
        int n = box.length;
        int[] dp = new int[n];
        int maxHeight = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = box[i][2];
            for (int j = 0; j < i; j++) {
                if (box[j][0] < box[i][0] && box[j][1] < box[i][1] && box[j][2] < box[i][2]) {
                    dp[i] = Math.max(dp[i], dp[j] + box[i][2]);
                }
            }
            maxHeight = Math.max(maxHeight, dp[i]);
        }
        return maxHeight;
    }
}

面试题 08.14. 布尔运算​

题目描述​

给定一个布尔表达式和一个期望的布尔结果 result，布尔表达式由 0 (false)、1 (true)、& (AND)、| (OR) 和 ^ (XOR) 符号组成。实现一个函数，算出有几种可使该表达式得出 result 值的括号方法。

示例 1：

输入: s = "1^0|0|1", result = 0
输出: 2

示例 2：

输入: s = "0&0&0&1^1|0", result = 1
输出: 10

解题思路​

使用区间 DP。dp[i][j][0/1] 表示子串 s[i...j] 计算结果为 0 或 1 的方法数。

Java 代码实现​

class Solution {
    public int countEval(String s, int result) {
        int n = s.length();
        int[][][] dp = new int[n][n][2];
        for (int i = 0; i < n; i += 2) {
            dp[i][i][s.charAt(i) - '0'] = 1;
        }
        for (int len = 3; len <= n; len += 2) {
            for (int i = 0; i + len <= n; i += 2) {
                int j = i + len - 1;
                for (int k = i + 1; k < j; k += 2) {
                    char op = s.charAt(k);
                    for (int left = 0; left <= 1; left++) {
                        for (int right = 0; right <= 1; right++) {
                            int val = compute(left, right, op);
                            dp[i][j][val] += dp[i][k - 1][left] * dp[k + 1][j][right];
                        }
                    }
                }
            }
        }
        return dp[0][n - 1][result];
    }
    
    private int compute(int left, int right, char op) {
        switch (op) {
            case '&': return left & right;
            case '|': return left | right;
            case '^': return left ^ right;
        }
        return 0;
    }
}