算法面试指南

# 算法面试指南

本指南收集了常见的算法面试题目和解题思路，帮助你系统性地准备算法面试。

# 学习路径

# 🎯 基础阶段（1-2个月）

数据结构基础 - 数组、链表、栈、队列、哈希表
基础算法 - 排序、查找、双指针
刷题量 - 50-100 题（Easy 为主）

# 🚀 进阶阶段（2-3个月）

树和图 - 二叉树遍历、DFS、BFS
动态规划 - 背包问题、子序列问题
刷题量 - 100-200 题（Easy + Medium）

# 💡 高级阶段（3-6个月）

高级算法 - 贪心、回溯、分治
复杂数据结构 - 并查集、线段树、字典树
刷题量 - 200-300 题（Medium + Hard）

# 算法复杂度速查

复杂度	名称	示例	n=100 的操作数
O(1)	常数	哈希表查找	1
O(log n)	对数	二分查找	7
O(n)	线性	遍历数组	100
O(n log n)	线性对数	快速排序	700
O(n²)	平方	冒泡排序	10,000
O(2ⁿ)	指数	递归斐波那契	1.27×10³⁰

# 常用算法模板

掌握这些模板，可以快速解决大部分算法题。

# 二分查找模板

// 标准二分查找
int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

// 查找左边界
int leftBound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    // left 是大于等于 target 的最小索引
    if (left >= nums.length || nums[left] != target) {
        return -1;
    }
    return left;
}

// 查找右边界
int rightBound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    // right 是小于等于 target 的最大索引
    if (right < 0 || nums[right] != target) {
        return -1;
    }
    return 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
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

关键点：

使用 left + (right - left) / 2 防止整数溢出
搜索区间统一用 [left, right]
注意边界检查

# 滑动窗口模板

void slidingWindow(String s) {
    Map<Character, Integer> window = new HashMap<>();
    int left = 0, right = 0;
    
    while (right < s.length()) {
        // 1. 扩大窗口
        char c = s.charAt(right);
        right++;
        window.put(c, window.getOrDefault(c, 0) + 1);
        
        // 2. 判断是否需要收缩
        while (收缩条件) {
            // 3. 缩小窗口
            char d = s.charAt(left);
            left++;
            window.put(d, window.get(d) - 1);
        }
        
        // 4. 更新答案
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

三个核心问题：

何时扩大窗口？→ right 指针不断右移
何时缩小窗口？→ 求最大时：不满足条件；求最小时：满足条件
何时更新答案？→ 求最大：扩大后；求最小：缩小时

应用：

无重复字符的最长子串: 找出 "abcabcbb" 中无重复字符的最长子串

# 回溯算法模板

void backtrack(路径, 选择列表) {
    if (满足结束条件) {
        result.add(路径);
        return;
    }
    
    for (选择 : 选择列表) {
        // 做选择
        路径.add(选择);
        选择列表.remove(选择);
        
        // 递归
        backtrack(路径, 选择列表);
        
        // 撤销选择
        路径.remove(选择);
        选择列表.add(选择);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

核心：做选择 → 递归 → 撤销选择

# 动态规划模板

// 自顶向下（递归 + 备忘录）
int dp(状态1, 状态2, ...) {
    // base case
    if (终止条件) return 结果;
    
    // 查备忘录
    if (memo[状态] != -1) return memo[状态];
    
    // 状态转移
    int result = 最优解(选择1, 选择2, ...);
    
    // 记入备忘录
    memo[状态] = result;
    return result;
}

// 自底向上（迭代）
int dp(int n) {
    int[] dp = new int[n + 1];
    dp[0] = base_case;
    
    for (int i = 1; i <= n; i++) {
        dp[i] = 状态转移方程;
    }
    
    return dp[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

解题思路：

确定状态（变化的量）
确定选择（导致状态变化的行为）
明确 dp 定义
确定 base case

# BFS 模板

BFS 的重点在于队列

int BFS(Node start, Node target) {
    Queue<Node> queue = new LinkedList<>();
    Set<Node> visited = new HashSet<>();
    
    queue.offer(start);
    visited.add(start);
    int step = 0;
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        
        // 遍历当前层的所有节点
        for (int i = 0; i < size; i++) {
            Node cur = queue.poll();
            
            if (cur == target) {
                return step;
            }
            
            // 将相邻节点加入队列
            for (Node next : cur.neighbors()) {
                if (!visited.contains(next)) {
                    queue.offer(next);
                    visited.add(next);
                }
            }
        }
        
        step++;
    }
    
    return -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

应用：层序遍历、最短路径

# DFS 模板

DFS 的重点在于递归

void DFS(Node root) {
    if (root == null) return;
    
    // 访问当前节点
    visited.add(root);
    
    // 递归访问相邻节点
    for (Node next : root.neighbors()) {
        if (!visited.contains(next)) {
            DFS(next);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

应用：树的遍历、图的遍历、连通性问题

# 双指针模板

// 对撞指针（Two Pointers）
int twoPointers(int[] nums) {
    int left = 0, right = nums.length - 1;
    
    while (left < right) {
        if (条件) {
            left++;
        } else {
            right--;
        }
    }
    
    return result;
}

// 快慢指针（Fast & Slow）
int fastSlowPointers(int[] nums) {
    int slow = 0, fast = 0;
    
    while (fast < nums.length) {
        if (条件) {
            slow++;
        }
        fast++;
    }
    
    return slow;
}

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

应用：

对撞指针：两数之和、接雨水
快慢指针：链表环检测、删除重复元素

# 1. 二叉树算法

参考：labuladong 二叉树总结 (opens new window)

# 1.1 二叉树遍历框架

void traverse(TreeNode root) {
    if (root == null) return;
    
    // 前序位置
    traverse(root.left);
    // 中序位置
    traverse(root.right);
    // 后序位置
}

1
2
3
4
5
6
7
8
9

# 1.2 二叉树的最大深度 (opens new window)

题目：给定一个二叉树 root，返回其最大深度。

class Solution {
    int depth = 0;
    int res = 0;

    public int maxDepth(TreeNode root) {
        traverse(root);
        return res;
    }

    void traverse(TreeNode root) {
        if (root == null) {
            return;
        }

        // 前序位置：进入节点时增加深度
        depth++;
        res = Math.max(res, depth);
        
        traverse(root.left);
        traverse(root.right);
        
        // 后序位置：离开节点时减少深度
        depth--;
    }
}

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

class Solution {
    // 定义：返回以该节点为根的二叉树的最大深度
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftMax = maxDepth(root.left);
        int rightMax = maxDepth(root.right);
        // 根据左右子树的最大深度推出原二叉树的最大深度
        return 1 + Math.max(leftMax, rightMax);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12

// Make sure to add code blocks to your code group

复杂度：时间 O(n)，空间 O(h)，h 为树的高度

# 1.3 二叉树的直径 (opens new window)

题目：返回二叉树的直径（任意两个节点之间最长路径的长度）。

核心思想：二叉树的直径 = 左右子树的最大深度之和

class Solution {
    int maxDiameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return maxDiameter;
    }

    // 计算以某个节点为根的子树深度
    int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftMax = maxDepth(root.left);
        int rightMax = maxDepth(root.right);
        
        // 后序位置：计算最大直径
        maxDiameter = Math.max(maxDiameter, leftMax + rightMax);
        
        return 1 + Math.max(leftMax, rightMax);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

复杂度：时间 O(n)，空间 O(h)

# 2. 动态规划典型题目

# 2.1 最长递增子序列 (opens new window)

题目：找到数组中最长严格递增子序列的长度。

思路：dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度

int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);  // base case
    
    for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            // 寻找比 nums[i] 小的元素
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    
    int res = 0;
    for (int i = 0; i < dp.length; i++) {
        res = Math.max(res, dp[i]);
    }
    return res;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

复杂度：时间 O(n²)，空间 O(n)

# 2.2 最大子数组和 (opens new window)

题目：找出一个具有最大和的连续子数组，返回其最大和。

方法1：动态规划

int maxSubArray(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    
    // dp[i] 表示以 nums[i] 结尾的最大子数组和
    int[] dp = new int[n];
    dp[0] = nums[0];
    
    for (int i = 1; i < n; i++) {
        dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
    }
    
    int res = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        res = Math.max(res, dp[i]);
    }
    return res;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

方法2：滑动窗口

int maxSubArray(int[] nums) {
    int left = 0, right = 0;
    int windowSum = 0, maxSum = Integer.MIN_VALUE;
    
    while (right < nums.length) {
        windowSum += nums[right];
        right++;
        
        maxSum = Math.max(maxSum, windowSum);
        
        // 当窗口和为负数时收缩
        while (windowSum < 0) {
            windowSum -= nums[left];
            left++;
        }
    }
    return maxSum;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

复杂度：时间 O(n)，空间 O(1)

# 2.3 零钱兑换 (opens new window)

题目：给定不同面额的硬币和一个总金额，计算凑成总金额所需的最少硬币个数。

class Solution {
    int[] memo;

    public int coinChange(int[] coins, int amount) {
        memo = new int[amount + 1];
        Arrays.fill(memo, -666);
        return dp(coins, amount);
    }

    // 定义：凑出金额 n 的最少硬币数
    int dp(int[] coins, int amount) {
        if (amount == 0) return 0;
        if (amount < 0) return -1;
        
        if (memo[amount] != -666)
            return memo[amount];

        int res = Integer.MAX_VALUE;
        for (int coin : coins) {
            int subProblem = dp(coins, amount - coin);
            if (subProblem == -1) continue;
            res = Math.min(res, subProblem + 1);
        }
        
        memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;
        return memo[amount];
    }
}

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

复杂度：时间 O(n × amount)，空间 O(amount)

# 2.4 编辑距离 (opens new window)

题目：计算将 word1 转换成 word2 所使用的最少操作数（插入、删除、替换）。

核心思路：用两个指针 i、j 分别指向两个字符串的末尾，逐步缩小问题规模。

class Solution {
    int[][] memo;

    public int minDistance(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        memo = new int[m][n];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dp(s1, m - 1, s2, n - 1);
    }

    // 定义：s1[0..i] 和 s2[0..j] 的最小编辑距离
    int dp(String s1, int i, String s2, int j) {
            // base case
        if (i == -1) return j + 1;
        if (j == -1) return i + 1;
        
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        
        if (s1.charAt(i) == s2.charAt(j)) {
            memo[i][j] = dp(s1, i - 1, s2, j - 1);
        } else {
            memo[i][j] = min(
                dp(s1, i, s2, j - 1) + 1,     // 插入
                dp(s1, i - 1, s2, j) + 1,     // 删除
                dp(s1, i - 1, s2, j - 1) + 1  // 替换
            );
        }
        return memo[i][j];
    }

    int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }
}

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

复杂度：时间 O(m × n)，空间 O(m × n)

# 3. 回溯算法典型题目

# 3.1 N皇后问题 (opens new window)

题目：在 N×N 棋盘上放置 N 个皇后，使它们不能互相攻击。

class Solution {
    private List<List<String>> result = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        List<String> chessboard = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                sb.append('.');
            }
            chessboard.add(sb.toString());
        }
        backtracking(n, 0, chessboard);
        return result;
    }

    private void backtracking(int n, int row, List<String> chessboard) {
        if (row == n) {
            result.add(new ArrayList<>(chessboard));
            return;
        }
        
        for (int col = 0; col < n; col++) {
            if (isValid(row, col, chessboard, n)) {
                // 做选择
                StringBuilder sb = new StringBuilder(chessboard.get(row));
                sb.setCharAt(col, 'Q');
                chessboard.set(row, sb.toString());
                
                // 递归
                backtracking(n, row + 1, chessboard);
                
                // 撤销选择
                sb.setCharAt(col, '.');
                chessboard.set(row, sb.toString());
            }
        }
    }

    private boolean isValid(int row, int col, List<String> chessboard, int n) {
        // 检查列
        for (int i = 0; i < row; i++) {
            if (chessboard.get(i).charAt(col) == 'Q') {
                return false;
            }
        }
        
        // 检查45度对角线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (chessboard.get(i).charAt(j) == 'Q') {
                return false;
            }
        }
        
        // 检查135度对角线
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (chessboard.get(i).charAt(j) == 'Q') {
                return false;
            }
        }
        
        return true;
    }
}

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
63
64

复杂度：时间 O(n!)，空间 O(n²)

# 4. 链表算法

参考：labuladong 链表技巧 (opens new window)

# 4.1 环形链表 (opens new window)

题目：判断链表中是否有环。

思路：快慢指针，快指针每次走两步，慢指针每次走一步，如果有环必定相遇。

boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        
        if (slow == fast) {
            return true;
        }
    }
    
    return false;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

复杂度：时间 O(n)，空间 O(1)

# 4.2 环形链表 II (opens new window)

题目：返回链表开始入环的第一个节点。

思路：当快慢指针相遇时，让一个指针回到头节点，两指针以相同速度前进，再次相遇点就是环的起点。

    public ListNode detectCycle(ListNode head) {
    ListNode fast = head, slow = head;
    
    // 判断是否有环
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
    
        if (fast == null || fast.next == null) {
            return null;
        }

    // 重新指向头节点
        slow = head;

    // 同步前进，相交点就是环起点
        while (slow != fast) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 4.3 反转链表 (opens new window)

// 定义：输入一个单链表头节点，返回反转后的头节点
ListNode reverse(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    
    ListNode last = reverse(head.next);
    head.next.next = head;
    head.next = null;
    
    return last;
}

1
2
3
4
5
6
7
8
9
10
11
12

ListNode reverseList(ListNode head) {
    ListNode cur = head, pre = null;
    
    while (cur != null) {
        ListNode tmp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = tmp;
    }
    
    return pre;
}

1
2
3
4
5
6
7
8
9
10
11
12

// Make sure to add code blocks to your code group

# 4.4 合并K个升序链表 (opens new window)

题目：合并 k 个升序链表为一个升序链表。

思路：使用优先队列（最小堆）每次取出最小的节点。

ListNode mergeKLists(ListNode[] lists) {
    if (lists.length == 0) return null;
    
    ListNode dummy = new ListNode(-1);
    ListNode p = dummy;
    
    // 优先队列，最小堆
    PriorityQueue<ListNode> pq = new PriorityQueue<>(
        lists.length, (a, b) -> (a.val - b.val));
    
    // 将 k 个链表的头节点加入最小堆
    for (ListNode head : lists) {
        if (head != null) {
            pq.add(head);
        }
    }

    while (!pq.isEmpty()) {
        ListNode node = pq.poll();
        p.next = node;
        if (node.next != null) {
            pq.add(node.next);
        }
        p = p.next;
    }
    
    return dummy.next;
}

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

复杂度：时间 O(N log k)，N 是所有节点总数，k 是链表条数

# 5. 滑动窗口典型题目

# 5.1 无重复字符的最长子串 (opens new window)

题目：找出字符串中不含重复字符的最长子串的长度。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0;
        int res = 0;
        
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            window.put(c, window.getOrDefault(c, 0) + 1);
            
            // 出现重复字符时，缩小窗口
            while (window.get(c) > 1) {
                char d = s.charAt(left);
                left++;
                window.put(d, window.get(d) - 1);
            }
            
            // 更新最大长度
            res = Math.max(res, right - left);
        }
        
        return res;
    }
}

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

复杂度：时间 O(n)，空间 O(k)，k 为字符集大小

# 5.2 最小覆盖子串 (opens new window)

题目：返回 s 中涵盖 t 所有字符的最小子串。

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        
        int left = 0, right = 0;
        int valid = 0;
        int start = 0, len = Integer.MAX_VALUE;
        
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }
            
            // 窗口包含所有字符时，开始收缩
            while (valid == need.size()) {
                // 更新最小覆盖子串
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                
                char d = s.charAt(left);
                left++;
                
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}

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

复杂度：时间 O(m + n)，空间 O(k)

# 6. 数组双指针典型题目

# 6.1 两数之和 II (opens new window)

题目：在有序数组中找到两个数，使其和等于 target。

public int[] twoSum(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    
    while (lo < hi) {
        int sum = nums[lo] + nums[hi];
        
        if (sum < target) {
            lo++;
        } else if (sum > target) {
            hi--;
        } else {
            return new int[]{lo + 1, hi + 1};
        }
    }
    
    return new int[]{};
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 6.2 删除有序数组中的重复项 (opens new window)

题目：原地删除有序数组中的重复元素，返回新长度。

思路：利用数组已排序的特性，相同的元素一定是连续的！。使用快慢指针，slow 走在后面，fast 走在前面探路。

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        
        int slow = 0, fast = 0;
        
        while (fast < nums.length) {
            if (nums[fast] != nums[slow]) {
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
        }
        
        return slow + 1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

复杂度：时间 O(n)，空间 O(1)

工作流程

fast 向前探索
发现新的不重复元素时，告诉 slow
slow 前进一步，接收新元素

# 7. 字符串算法

# 7.1 最长回文子串 (opens new window)

题目：找到 s 中最长的回文子串。

思路：从中间向两边扩散判断回文串。

class Solution {
    public String longestPalindrome(String s) {
        String res = "";
        
        for (int i = 0; i < s.length(); i++) {
            // 以 s[i] 为中心（奇数长度）
            String s1 = palindrome(s, i, i);
            // 以 s[i] 和 s[i+1] 为中心（偶数长度）
            String s2 = palindrome(s, i, i + 1);
            
            res = res.length() > s1.length() ? res : s1;
            res = res.length() > s2.length() ? res : s2;
        }
        
        return res;
    }

    String palindrome(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        return s.substring(l + 1, r);
    }
}

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

复杂度：时间 O(n²)，空间 O(1)

# 8. LRU 缓存实现

参考：手撸 LRU 算法 (opens new window)

核心：双向链表 + 哈希表

class LRUCache {
class Node {
        int key, val;
        Node next, prev;
        Node(int k, int v) {
            key = k;
            val = v;
        }
    }
    
    private Map<Integer, Node> map;
    private Node head, tail;
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);
        moveToHead(node);
        return node.val;
    }

    public void put(int key, int val) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.val = val;
            moveToHead(node);
        } else {
            Node node = new Node(key, val);
            map.put(key, node);
            addToHead(node);
            
            if (map.size() > capacity) {
                Node removed = removeTail();
                map.remove(removed.key);
            }
        }
    }
    
    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
    
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }
    
    private Node removeTail() {
        Node node = tail.prev;
        removeNode(node);
        return node;
    }
}

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
63
64
65
66
67
68
69
70
71
72

复杂度：get 和 put 都是 O(1)

# 9. 常见数据结构实现

# 9.1 单调栈

应用：寻找下一个更大/更小元素

// 下一个更大元素
int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Stack<Integer> stack = new Stack<>();
    
    // 倒着遍历
    for (int i = n - 1; i >= 0; i--) {
        // 弹出小于等于当前元素的值
        while (!stack.isEmpty() && stack.peek() <= nums[i]) {
            stack.pop();
        }
        res[i] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(nums[i]);
    }
    
    return res;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 9.2 单调队列

应用：滑动窗口最大值

class MonotonicQueue {
    private LinkedList<Integer> queue = new LinkedList<>();
    
    public void push(int n) {
        // 保持队列单调递减
        while (!queue.isEmpty() && queue.getLast() < n) {
            queue.pollLast();
        }
        queue.addLast(n);
    }
    
    public int max() {
        return queue.getFirst();
    }
    
    public void pop(int n) {
        if (n == queue.getFirst()) {
            queue.pollFirst();
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 10. 面试技巧

# 10.1 解题步骤

理解题意 - 确认输入输出，边界条件
分析示例 - 手动模拟测试用例
确定思路 - 选择算法和数据结构
编写代码 - 先框架后细节
测试验证 - 考虑边界和特殊情况
复杂度分析 - 分析时间和空间复杂度

# 10.2 常见陷阱

// 1. 整数溢出
int mid = (left + right) / 2;           // ❌ 可能溢出
int mid = left + (right - left) / 2;    // ✅

// 2. 数组越界
if (i < nums.length && nums[i] == target)  // ✅ 先检查边界

// 3. 空指针
if (node != null && node.val == target)    // ✅ 先检查 null

// 4. 死循环
while (left < right) {
    int mid = left + (right - left) / 2;
    if (check(mid)) {
        right = mid;      // ✅ 不是 mid - 1
    } else {
        left = mid + 1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 10.3 刷题建议

分类	推荐题数	难度	重要程度
数组/字符串	30-50	Easy/Medium	⭐⭐⭐⭐⭐
链表	20-30	Easy/Medium	⭐⭐⭐⭐
树	30-40	Medium	⭐⭐⭐⭐⭐
动态规划	40-60	Medium/Hard	⭐⭐⭐⭐⭐
回溯	20-30	Medium	⭐⭐⭐⭐
二分查找	15-20	Medium	⭐⭐⭐⭐
滑动窗口	15-20	Medium	⭐⭐⭐⭐

刷题策略：

按专题刷，集中攻克
由易到难，循序渐进
重要题目刷 2-3 遍
总结模板和套路
定期复习保持手感

# 11. 必刷题目清单

# 数组

# 链表

# 树

# 动态规划

# 滑动窗口

# 概念辨析

面试中经常遇到概念混淆，这里统一解释易混淆的算法概念。

# Q1: 回溯 vs DFS 有什么区别？

回答：回溯算法使用了 DFS 的遍历方式，是带撤销操作的 DFS。

维度	回溯算法	DFS
本质	算法思想	遍历方式
目标	找到所有解	遍历所有节点
核心操作	做选择 → 递归 → 撤销选择	访问 → 递归
是否撤销	✅ 必须撤销	❌ 不需要撤销
典型题目	全排列、N皇后、组合总和	树遍历、图遍历、岛屿数量

代码对比：

// 纯 DFS（遍历）
void DFS(TreeNode root) {
    if (root == null) return;
    System.out.println(root.val);
    DFS(root.left);
    DFS(root.right);
    // ❌ 没有撤销
}

// 回溯（枚举所有解）
void backtrack(List<Integer> path) {
    if (满足条件) {
        result.add(new ArrayList<>(path));
            return;
        }
    for (选择 : 选择列表) {
        path.add(选择);        // 做选择
        backtrack(path);       // 递归
        path.remove(选择);     // ✅ 撤销选择
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

记忆：回溯 = DFS + 撤销操作

# Q2: 滑动窗口 vs 双指针有什么区别？

维度	滑动窗口	双指针
指针移动	都向右移动	可能相向或同向移动
窗口概念	维护一个可变窗口	不一定维护窗口
适用问题	连续子数组/子串	数组查找、链表操作
典型关键词	"最长"、"最短"、"包含"	"两数之和"、"反转"
典型题目	最长无重复子串	两数之和、反转链表

关系：滑动窗口是双指针的一种特殊应用。

// 滑动窗口（同向，维护窗口）
int left = 0, right = 0;
while (right < n) {
    right++;        // 都向右
    while (条件) {
        left++;     // 都向右
    }
}

// 双指针（对撞）
int left = 0, right = n - 1;
while (left < right) {
    if (条件) left++;      // 相向移动
    else right--;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# Q3: 递归 vs 迭代 vs 动态规划有什么关系？

概念	本质	关系
递归	函数调用自己	一种实现方式
迭代	使用循环	一种实现方式
动态规划	算法思想	可用递归或迭代实现

示例：斐波那契数列

// 递归实现（简单但效率低）
int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);  // 重复计算
}

// 递归 + 备忘录（动态规划的递归实现）
int fib(int n) {
    if (memo[n] != 0) return memo[n];
    if (n <= 1) return n;
    memo[n] = fib(n-1) + fib(n-2);
    return memo[n];
}

// 迭代（动态规划的迭代实现）
int fib(int n) {
    if (n <= 1) return n;
    int dp[] = new int[n+1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[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

结论：动态规划是思想，递归和迭代是实现方式。

# Q4: BFS vs DFS 如何选择？

场景	推荐算法	原因
找最短路径	BFS ⭐	层序遍历，第一次找到就是最短
找所有路径	DFS ⭐	需要遍历所有可能
判断连通性	DFS/BFS 都可	看个人习惯
层序遍历	BFS ⭐	天然的层序结构
空间受限	DFS ⭐	空间复杂度O(h)，BFS是O(w)

// BFS：逐层扩散，找到就是最短路径
1
├─ 2 (第1层)
│  ├─ 4 (第2层)
│  └─ 5
└─ 3
   ├─ 6
   └─ 7

// DFS：深入到底，可能绕远路
1 → 2 → 4 → 5 → 3 → 6 → 7

1
2
3
4
5
6
7
8
9
10
11

# Q5: 贪心 vs 动态规划有什么区别？

维度	贪心算法	动态规划
决策方式	每步做局部最优选择	考虑所有可能，选全局最优
是否回退	❌ 不能回退	✅ 可以通过状态转移"回退"
子问题关系	无后效性	有重叠子问题
适用条件	局部最优 = 全局最优	最优子结构 + 重叠子问题
难度	找到贪心策略较难	找到状态转移方程较难

示例：找零钱问题

// 贪心（只对特定币值有效，如 [1, 5, 10, 25]）。 对于特殊币种 ([1, 5, 11]) 则失效
int coinChangeGreedy(int[] coins, int amount) {
    Arrays.sort(coins);
    int count = 0;
    for (int i = coins.length - 1; i >= 0; i--) {
        while (amount >= coins[i]) {
            amount -= coins[i];
            count++;
        }
    }
    return amount == 0 ? count : -1;
}

// 动态规划（适用所有情况）
int coinChangeDP(int[] coins, int amount) {
    // 1️⃣ 创建 dp 数组
    int[] dp = new int[amount + 1];
    
    // 2️⃣ 初始化为一个"不可能"的大值
    Arrays.fill(dp, amount + 1);
    
    // 3️⃣ base case：凑出金额 0 需要 0 个硬币
    dp[0] = 0;
    
    // 4️⃣ 外层循环：遍历所有金额（从小到大）
    for (int i = 1; i <= amount; i++) {
        
        // 5️⃣ 内层循环：尝试每一种硬币
        for (int coin : coins) {
            
            // 6️⃣ 只有当前金额 >= 硬币面额时才能选
            if (i >= coin) {
                
                // 7️⃣ 状态转移方程（核心）
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    
    // 8️⃣ 返回结果（检查是否无解）
    return dp[amount] > amount ? -1 : dp[amount];
}

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

# Q6: 子序列 vs 子串 vs 子数组的区别？

概念	是否连续	是否保持顺序	示例
子序列	❌ 不要求连续	✅ 保持相对顺序	"ace" 是 "abcde" 的子序列
子串	✅ 必须连续	✅ 保持顺序	"bcd" 是 "abcde" 的子串
子数组	✅ 必须连续	✅ 保持顺序	子串的数组版本

对应算法：

// 子序列问题 → 动态规划
最长递增子序列、最长公共子序列

// 子串/子数组问题 → 滑动窗口 or 动态规划
最长无重复子串（滑动窗口）
最大子数组和（DP或滑动窗口）

1
2
3
4
5
6

# Q7: 快慢指针的核心思想是什么？

核心：用两个速度不同的指针解决问题。

应用场景：

// 1. 链表找中点（slow走1步，fast走2步）
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;        // 走1步
    fast = fast.next.next;   // 走2步
}
// slow 就是中点

// 2. 链表检测环
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) return true;  // 相遇说明有环
}

// 3. 数组去重（slow慢，fast快）
int slow = 0, fast = 0;
while (fast < nums.length) {
    if (nums[fast] != nums[slow]) {
        slow++;                    // slow维护不重复区域
        nums[slow] = nums[fast];
    }
    fast++;
}
return slow + 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

关键思想：

slow：维护"有效区域"或"慢速探索"
fast：快速探索或检测特殊情况
相对速度差：是解决问题的关键

# Q8: 时间复杂度 O(n) 和 O(2n) 有区别吗？

回答：在大O表示法中，没有区别！

O(2n) = O(n)
O(n + 100) = O(n)
O(3n²) = O(n²)

1
2
3

原因：大O只关注增长趋势，忽略常数系数。

// 这两个算法的时间复杂度都是 O(n)
void algorithm1(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // O(n)
    }
}

void algorithm2(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // 第一遍
    }
    for (int i = 0; i < nums.length; i++) {
        // 第二遍
    }
    // O(n) + O(n) = O(2n) = O(n)
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

但在实际中：

O(n) 的算法通常比 O(2n) 快
面试时可以说"优化了常数因子"

# Q9: 空间复杂度 O(1) 是什么意思？

回答：使用的额外空间是常数级别，不随输入规模增长。

// ✅ 空间 O(1) - 只用了几个变量
int findMax(int[] nums) {
    int max = nums[0];
    for (int num : nums) {
        max = Math.max(max, num);
    }
    return max;
}

// ❌ 空间 O(n) - 创建了新数组
int[] copy(int[] nums) {
    return Arrays.copyOf(nums, nums.length);
}

// ⚠️ 注意：递归的调用栈也算空间
int sum(int[] nums, int i) {
    if (i == nums.length) return 0;
    return nums[i] + sum(nums, i + 1);
    // 空间 O(n)，因为递归深度是 n
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

常见误区：

// 这个的空间复杂度是多少？
int[] dp = new int[n];  // O(n)

// 优化版本
int prev = 0, curr = 1;  // O(1)
// 用两个变量代替数组

1
2
3
4
5
6

# Q10: 什么时候用递归，什么时候用迭代？

选择标准：

场景	推荐方式	原因
树的遍历	递归 ⭐	代码简洁，符合树的结构
深度很大	迭代 ⭐	避免栈溢出
需要优化空间	迭代 ⭐	递归有调用栈开销
动态规划	两者都可	递归+备忘录 or 迭代+dp数组
回溯问题	递归 ⭐	自然适合递归表达

// 递归：简洁但可能栈溢出
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

// 迭代：代码略长但更安全
int factorial(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

建议：

🎯 优先考虑代码的可读性
⚡ 性能要求高时选迭代
🌳 树相关问题优先递归
📊 大规模数据优先迭代

# 总结

算法面试的核心是：

掌握基础 - 数据结构和基本算法
理解思想 - 动态规划、贪心、回溯等
熟练模板 - 掌握常见算法模板
大量练习 - 刷题是基础
总结归纳 - 形成解题套路
辨析概念 - 理解算法之间的区别和联系

记住：

算法能力需要长期积累
理解比记忆更重要
多思考、多总结、多复习
面试时注意沟通思路
概念清晰能加分

# 参考资源

LeetCode (opens new window) - 刷题平台
labuladong 的算法小抄 (opens new window) - 算法思维
代码随想录 (opens new window) - 系统教程
Hello 算法 (opens new window) - 动画图解
visualgo (opens new window) - 算法可视化

#算法 #面试 #LeetCode #数据结构

上次更新: 2025/10/14, 17:25:25

← algo float的存储→

算法面试指南

# 算法面试指南

# 学习路径

# 🎯 基础阶段（1-2个月）

# 🚀 进阶阶段（2-3个月）

# 💡 高级阶段（3-6个月）

# 算法复杂度速查

# 常用算法模板

# 二分查找模板

# 滑动窗口模板

# 回溯算法模板

# 动态规划模板

# BFS 模板

# DFS 模板

# 双指针模板

# 1. 二叉树算法

# 1.1 二叉树遍历框架

# 1.2 二叉树的最大深度 (opens new window)

# 1.3 二叉树的直径 (opens new window)

# 2. 动态规划典型题目

# 2.1 最长递增子序列 (opens new window)

# 2.2 最大子数组和 (opens new window)

# 2.3 零钱兑换 (opens new window)

# 2.4 编辑距离 (opens new window)

# 3. 回溯算法典型题目

# 3.1 N皇后问题 (opens new window)

# 4. 链表算法

# 4.1 环形链表 (opens new window)

# 4.2 环形链表 II (opens new window)

# 4.3 反转链表 (opens new window)

# 4.4 合并K个升序链表 (opens new window)

# 5. 滑动窗口典型题目

# 5.1 无重复字符的最长子串 (opens new window)

# 5.2 最小覆盖子串 (opens new window)

# 6. 数组双指针典型题目

# 6.1 两数之和 II (opens new window)

# 6.2 删除有序数组中的重复项 (opens new window)

# 7. 字符串算法

# 7.1 最长回文子串 (opens new window)

# 8. LRU 缓存实现

# 9. 常见数据结构实现

# 9.1 单调栈

# 9.2 单调队列

# 10. 面试技巧

# 10.1 解题步骤

# 10.2 常见陷阱

# 10.3 刷题建议

# 11. 必刷题目清单

# 数组

# 链表

# 树

# 动态规划

# 滑动窗口

# 概念辨析

# Q1: 回溯 vs DFS 有什么区别？

# Q2: 滑动窗口 vs 双指针 有什么区别？

# Q3: 递归 vs 迭代 vs 动态规划 有什么关系？

# Q4: BFS vs DFS 如何选择？

# Q5: 贪心 vs 动态规划 有什么区别？

# Q6: 子序列 vs 子串 vs 子数组 的区别？

# Q7: 快慢指针的核心思想是什么？

# Q8: 时间复杂度 O(n) 和 O(2n) 有区别吗？

# Q9: 空间复杂度 O(1) 是什么意思？

# Q10: 什么时候用递归，什么时候用迭代？

# 总结

# 参考资源

# Q2: 滑动窗口 vs 双指针有什么区别？

# Q3: 递归 vs 迭代 vs 动态规划有什么关系？

# Q5: 贪心 vs 动态规划有什么区别？

# Q6: 子序列 vs 子串 vs 子数组的区别？