算法与数据结构 #

面试必备算法知识，涵盖排序、搜索、动态规划、树、图等

---

📋 目录 #

• 排序算法
• 搜索算法
• 动态规划
• 树与图
• 常见题型

---

排序算法 #

面试必问 ⭐⭐⭐⭐⭐

快速排序 #

public class QuickSort {
    public void sort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            sort(arr, low, pivotIndex - 1);
            sort(arr, pivotIndex + 1, high);
        }
    }
    
    private int partition(int[] arr, int low, int high) {
        int pivot = arr[high];  // 选择最后一个元素作为基准
        int i = low - 1;
        
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }
    
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

时间复杂度: O(n log n) 平均，O(n²) 最坏

---

归并排序 #

public class MergeSort {
    public void sort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            
            sort(arr, left, mid);
            sort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
    
    private void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        
        int[] L = new int[n1];
        int[] R = new int[n2];
        
        for (int i = 0; i < n1; i++)
            L[i] = arr[left + i];
        for (int j = 0; j < n2; j++)
            R[j] = arr[mid + 1 + j];
        
        int i = 0, j = 0, k = left;
        
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k++] = L[i++];
            } else {
                arr[k++] = R[j++];
            }
        }
        
        while (i < n1)
            arr[k++] = L[i++];
        while (j < n2)
            arr[k++] = R[j++];
    }
}

时间复杂度: O(n log n) 稳定

---

Java内置排序 #

Arrays.sort(arr);           // 基础类型：双轴快排 O(n log n)
Arrays.sort(arr, comparator); // 对象：TimSort 稳定排序

List<Integer> list = Arrays.asList(arr);
Collections.sort(list);   // TimSort

排序算法对比 #

算法	平均	最坏	稳定性	空间	适用场景
冒泡	O(n²)	O(n²)	✅	O(1)	简单、小数据量
选择	O(n²)	O(n²)	❌	O(1)	简单
插入	O(n²)	O(n²)	✅	O(1)	小数据、基本有序
快速	O(n log n)	O(n²)	❌	O(log n)	通用排序
归并	O(n log n)	O(n log n)	✅	O(n)	外部排序、稳定
堆	O(n log n)	O(n log n)	❌	O(1)	Top K 问题

---

搜索算法 #

二分查找 #

面试高频 ⭐⭐⭐⭐⭐

public class BinarySearch {
    // 递归实现
    public int search(int[] nums, int target) {
        return binarySearch(nums, 0, nums.length - 1, target);
    }
    
    private int binarySearch(int[] nums, int left, int right, int target) {
        if (left > right) {
            return -1;
        }
        
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            return binarySearch(nums, left, mid - 1, target);
        } else {
            return binarySearch(nums, mid + 1, right, target);
        }
    }
    
    // 迭代实现
    public int searchIterative(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;
    }
}

时间复杂度: O(log n)

前提条件: 数组必须有序

---

动态规划 #

面试高频 ⭐⭐⭐⭐⭐

斐波那契数列 #

public class Fibonacci {
    // 递归（不推荐）: O(2^n)
    public int fibRecursive(int n) {
        if (n <= 1) return n;
        return fibRecursive(n - 1) + fibRecursive(n - 2);
    }
    
    // 记忆化搜索: O(n)
    public int fibMemo(int n) {
        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return fibHelper(n, memo);
    }
    
    private int fibHelper(int n, int[] memo) {
        if (n <= 1) return n;
        if (memo[n] != -1) return memo[n];
        
        memo[n] = fibHelper(n - 1, memo) + fibHelper(n - 2, memo);
        return memo[n];
    }
    
    // 动态规划: O(n)
    public int fibDP(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];
    }
    
    // 空间优化: O(1)
    public int fibOptimized(int n) {
        if (n <= 1) return n;
        
        int a = 0, b = 1, c;
        for (int i = 2; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        
        return b;
    }
}

爬楼梯问题 #

public class ClimbStairs {
    // 动态规划
    public int climbStairs(int n) {
        if (n <= 2) return n;
        
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        return dp[n];
    }
    
    // 空间优化
    public int climbStairsOptimized(int n) {
        if (n <= 2) return n;
        
        int a = 1, b = 2, c = 0;
        for (int i = 3; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        
        return c;
    }
}

时间复杂度: O(n) 空间复杂度: O(1)

---

树与图 #

二叉树遍历 #

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int val) {
        this.val = val;
    }
}

public class BinaryTreeTraversal {
    // 前序遍历: 根→左→右
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        preorderHelper(root, result);
        return result;
    }
    
    private void preorderHelper(TreeNode node, List<Integer> result) {
        if (node == null) return;
        
        result.add(node.val);        // 访问根
        preorderHelper(node.left, result);  // 左子树
        preorderHelper(node.right, result); // 右子树
    }
    
    // 中序遍历: 左→根→右
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorderHelper(root, result);
        return result;
    }
    
    private void inorderHelper(TreeNode node, List<Integer> result) {
        if (node == null) return;
        
        inorderHelper(node.left, result);  // 左子树
        result.add(node.val);        // 访问根
        inorderHelper(node.right, result); // 右子树
    }
    
    // 后序遍历: 左→右→根
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        postorderHelper(root, result);
        return result;
    }
    
    private void postorderHelper(TreeNode node, List<Integer> result) {
        if (node == null) return;
        
        postorderHelper(node.left, result);  // 左子树
        postorderHelper(node.right, result); // 右子树
        result.add(node.val);        // 访问根
    }
    
    // 层序遍历 (BFS)
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            
            result.add(level);
        }
        
        return result;
    }
}

二叉树的最大深度 #

public class MaxDepth {
    // 递归
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        
        return Math.max(leftDepth, rightDepth) + 1;
    }
    
    // 层序遍历
    public int maxDepthBFS(TreeNode root) {
        if (root == null) return 0;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            depth++;
            
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        
        return depth;
    }
}

---

常见题型 #

两数之和 #

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            
            map.put(nums[i], i);
        }
        
        return new int[] {};
    }
}

时间复杂度: O(n) 空间复杂度: O(n)

---

反转链表 #

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

class Solution {
    // 迭代
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        
        return prev;
    }
    
    // 递归
    public ListNode reverseListRecursive(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode newHead = reverseListRecursive(head.next);
        head.next.next = head;
        head.next = null;
        
        return newHead;
    }
}

时间复杂度: O(n) 空间复杂度: O(1)

---

合并两个有序链表 #

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                curr.next = list1;
                list1 = list1.next;
            } else {
                curr.next = list2;
                list2 = list2.next;
            }
            curr = curr.next;
        }
        
        curr.next = list1 != null ? list1 : list2;
        
        return dummy.next;
    }
}

时间复杂度: O(n + m)

---

数据结构 #

HashMap (哈希表) #

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);

// 查找
if (map.containsKey("apple")) {
    int value = map.get("apple");
}

// 遍历
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

时间复杂度: 平均 O(1) for get/put

---

Stack (栈) #

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);

int top = stack.pop();      // 移除并返回栈顶: 3
int peek = stack.peek();    // 仅查看栈顶: 2
boolean empty = stack.isEmpty();  // false

应用场景: 括号匹配、表达式求值、函数调用栈

---

Queue (队列) #

Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);

int front = queue.poll();  // 移除并返回队首: 1
int peek = queue.peek();   // 仅查看队首: 2
boolean empty = queue.isEmpty();  // false

// 优先队列
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
pq.offer(3);
int min = pq.poll();      // 返回最小值: 1

---

堆 #

// 大顶堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
maxHeap.offer(5);
maxHeap.offer(1);
maxHeap.offer(3);
System.out.println(maxHeap.poll());  // 5

// 小顶堆（默认）
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(1);
minHeap.offer(3);
System.out.println(minHeap.poll());  // 1

应用场景: Top K 问题、优先队列

---

算法复杂度分析 #

时间复杂度 #

复杂度	名称	示例
O(1)	常数	数组索引访问
O(log n)	对数	二分查找、平衡树操作
O(n)	线性	遍历数组/链表
O(n log n)	线性对数	归并排序、快速排序
O(n²)	平方	冒泡排序、嵌套循环
O(2ⁿ)	指数	递归斐波那契、子集枚举
O(n!)	阶乘	全排列

空间复杂度 #

复杂度	说明	示例
O(1)	常数额外空间	变量、指针
O(n)	线性额外空间	数组、链表
O(n²)	平方额外空间	二维数组
O(log n)	对数	递归调用栈

---

LeetCode 刷题建议 #

题型分类 #

类型	推荐题目	重要性
数组	两数之和、三数之和、最大子数组和	⭐⭐⭐⭐⭐
链表	反转链表、合并链表、环形链表	⭐⭐⭐⭐⭐
树	二叉树遍历、二叉树的最大深度	⭐⭐⭐⭐⭐
动态规划	爬楼梯、最长递增子序列	⭐⭐⭐⭐⭐
排序	快速排序、归并排序	⭐⭐⭐⭐
哈希表	两数之和、字母异位词	⭐⭐⭐⭐⭐
贪心	跳跃游戏、买卖股票	⭐⭐⭐⭐
滑动窗口	无重复字符的最长子串	⭐⭐⭐⭐

刷题推荐顺序 #

阶段一: 基础 (Hot 100)
  - 数组: 1, 15, 217, 49
  - 字符串: 3, 5, 20, 125
  - 链表: 21, 206, 141
  
阶段二: 进阶 (Top 100)
  - 树: 94, 102, 104, 110
  - 动态规划: 70, 198, 322
  - 回溯: 39, 46, 51, 78
  
阶段三: 高级
  - 图: 200, 207, 210, 332
  - 并查集: 200, 1284
  - 高级DP: 42, 72, 152

---

面试题汇总 #

排序篇 #

1. 快速排序的实现原理？
2. 归并排序的过程？
3. 稳定排序 vs 不稳定排序？
4. Java Arrays.sort() 使用什么算法？

搜索篇 #

1. 二分查找的实现？
2. 时间复杂度分析？
3. 搜索应用场景？

树篇 #

1. 二叉树的前中后序遍历？
2. 求二叉树的最大深度？
3. 平衡二叉树（AVL/红黑树）？

动态规划篇 #

1. 动态规划的核心思想？
2. 斐波那契数列的解法？
3. 爬楼梯问题的解法？

---

面试题答案详解 #

排序篇 #

1. 快速排序的实现原理？

答案：

核心思想： 分治

步骤：

1. 选择基准：选一个元素作为pivot（通常选最后一个）
2. 分区：将数组分为两部分，小于pivot的放左边，大于等于pivot的放右边
3. 递归排序：对左右两部分递归执行快速排序

实现：

public void sort(int[] arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        sort(arr, low, pivotIndex - 1);
        sort(arr, pivotIndex + 1, high);
    }
}

private int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr, i + 1, high);
    return i + 1;
}

时间复杂度： 平均O(n log n)，最坏O(n²)（数组已排序） 稳定性： 不稳定

---

2. 归并排序的过程？

答案：

核心思想： 分治 + 合并

步骤：

1. 分解：将数组分成两半
2. 递归排序：分别对左右两半排序
3. 合并：将两个有序数组合并成一个

实现：

public void sort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        sort(arr, left, mid);
        sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

private void merge(int[] arr, int left, int mid, int right) {
    int[] L = new int[mid - left + 1];
    int[] R = new int[right - mid];
    
    for (int i = 0; i < L.length; i++) L[i] = arr[left + i];
    for (int j = 0; j < R.length; j++) R[j] = arr[mid + 1 + j];
    
    int i = 0, j = 0, k = left;
    while (i < L.length && j < R.length) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    
    while (i < L.length) arr[k++] = L[i++];
    while (j < R.length) arr[k++] = R[j++];
}

时间复杂度： O(n log n) 空间复杂度： O(n) 稳定性： 稳定

---

3. 稳定排序 vs 不稳定排序？

答案：

稳定排序： 相同元素的相对顺序不变

• 冒泡排序
• 插入排序
• 归并排序
• 计数排序、桶排序、基数排序

不稳定排序： 相同元素的相对顺序可能改变

• 快速排序
• 选择排序
• 堆排序
• Hill排序

重要性：

• 排序字段相同时，保留原顺序
• 多字段排序时，稳定排序更可靠

---

4. Java Arrays.sort() 使用什么算法？

答案：

基础类型（int、double等）：

• 双轴快速排序（Dual-Pivot Quicksort）
• 性能好，O(n log n)
• 不需要稳定性

对象类型：

• TimSort（归并排序 + 插入排序）
• 稳定排序
• 性能好，O(n log n)

Collections.sort()： 内部调用Arrays.sort()，同样使用TimSort

---

搜索篇 #

1. 二分查找的实现？

答案：

迭代实现（推荐）：

public int search(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;
}

递归实现：

public int searchRecursive(int[] nums, int target) {
    return binarySearch(nums, 0, nums.length - 1, target);
}

private int binarySearch(int[] nums, int left, int right, int target) {
    if (left > right) return -1;
    
    int mid = left + (right - left) / 2;
    
    if (nums[mid] == target) return mid;
    else if (nums[mid] < target) return binarySearch(nums, mid + 1, right, target);
    else return binarySearch(nums, left, mid - 1, target);
}

关键点：

• mid = left + (right - left)/2 防止溢出
• left <= right，不是 <
• 前提：数组必须有序

---

2. 时间复杂度分析？

答案：

二分查找： O(log n)

• 每次搜索范围减半
• 层数 ≈ log₂n

线性查找： O(n)

• 最坏情况遍历全部

二分查找前提： 有序数组

---

3. 搜索应用场景？

答案：

二分查找：

• 有序数组查找
• 旋转有序数组
• 找左右边界
• 搜索二维矩阵

哈希表查找：

• 两数之和
• 快速查找
• 去重

搜索树：

• BST/AVL/红黑树
• 范围查找

---

树篇 #

1. 二叉树的前中后序遍历？

答案：

前序遍历： 根→左→右

public List<Integer> preorder(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    preorderHelper(root, result);
    return result;
}

private void preorderHelper(TreeNode node, List<Integer> result) {
    if (node == null) return;
    result.add(node.val);
    preorderHelper(node.left, result);
    preorderHelper(node.right, result);
}

中序遍历： 左→根→右

public List<Integer> inorder(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    inorderHelper(root, result);
    return result;
}

private void inorderHelper(TreeNode node, List<Integer> result) {
    if (node == null) return;
    inorderHelper(node.left, result);
    result.add(node.val);
    inorderHelper(node.right, result);
}

后序遍历： 左→右→根

public List<Integer> postorder(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    postorderHelper(root, result);
    return result;
}

private void postorderHelper(TreeNode node, List<Integer> result) {
    if (node == null) return;
    postorderHelper(node.left, result);
    postorderHelper(node.right, result);
    result.add(node.val);
}

层序遍历（BFS）：

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        
        result.add(level);
    }
    
    return result;
}

---

2. 求二叉树的最大深度？

答案：

递归实现（DFS）：

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    
    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);
    
    return Math.max(leftDepth, rightDepth) + 1;
}

层序遍历（BFS）：

public int maxDepthBFS(TreeNode root) {
    if (root == null) return 0;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int depth = 0;
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        depth++;
        
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
    
    return depth;
}

---

3. 平衡二叉树（AVL/红黑树）？

答案：

AVL树：

• 严格平衡：左右子树高度差 ≤ 1
• 查找：O(log n)
• 插入/删除：需要旋转，复杂
• 适合：读多写少

红黑树：

• 近似平衡：黑色高度相同
• 查找：O(log n)
• 插入/删除：较少旋转，效率高
• 适合：读多写少，但比AVL实用

Java中的应用：

• TreeMap：红黑树
• TreeSet：红黑树
• HashMap：红黑树（链表长度>8时）

---

动态规划篇 #

1. 动态规划的核心思想？

答案：

核心：

• 将问题分解为重叠子问题
• 记录子问题的解，避免重复计算
• 从简单子问题推出复杂问题

步骤：

1. 状态定义：dp[i]表示什么
2. 状态转移方程：dp[i] = f(dp[i-1], dp[i-2], ...)
3. 初始条件：dp[0], dp[1] = ?
4. 返回结果：dp[n]

优化方向：

• 空间优化：只保留需要的状态，不是整个数组
• 迭代代替递归，避免栈溢出

---

2. 斐波那契数列的解法？

答案：

方法1：递归（不推荐，O(2ⁿ)）

public int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

方法2：记忆化搜索（O(n)）

public int fibMemo(int n) {
    int[] memo = new int[n + 1];
    Arrays.fill(memo, -1);
    return fibHelper(n, memo);
}

private int fibHelper(int n, int[] memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fibHelper(n - 1, memo) + fibHelper(n - 2, memo);
    return memo[n];
}

方法3：动态规划（O(n)）

public int fibDP(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];
}

方法4：空间优化（O(1)）

public int fibOptimized(int n) {
    if (n <= 1) return n;
    
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    
    return b;
}

---

3. 爬楼梯问题的解法？

答案：

题目： 每次爬1或2层，到n层有多少种方法？

动态规划：

public int climbStairs(int n) {
    if (n <= 2) return n;
    
    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

空间优化：

public int climbStairsOptimized(int n) {
    if (n <= 2) return n;
    
    int a = 1, b = 2, c = 0;
    for (int i = 3; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    
    return c;
}

关键：

• 状态转移：dp[i] = dp[i-1] + dp[i-2]
• 初始条件：dp[1]=1, dp[2]=2
• 本质：斐波那契数列

---

🔗 相关资源 #

在线练习 #

• LeetCode - 力扣中文版
• 牛客网 - 中国版力扣
• LintCode - 算法练习

参考书籍 #

• 《算法导论》
• 《剑指Offer》
• 《编程珠玑》
• 《算法（第4版）》

---

🔗 相关笔记 #

• 集合框架
• Java

---

最后更新: 2026-04-29