算法与数据结构核心思想与解题蓝图

目录

  1. 哈希(Hash)
  2. 双指针(Two Pointers)
  3. 滑动窗口(Sliding Window)
  4. 子串(Substring)
  5. 普通数组(Array)
  6. 矩阵(Matrix)
  7. 链表(Linked List)
  8. 二叉树(Binary Tree)
  9. 图论(Graph Theory)
  10. 回溯(Backtracking)
  11. 二分查找(Binary Search)
  12. 栈(Stack)
  13. 贪心算法(Greedy)
  14. 动态规划(DP)
  15. 多维动态规划(Multi-dimensional DP)
  16. 技巧(Tricks)

接下来我将简单介绍以上16种算法思想及其使用场景

哈希：快速查找和存储数据
双指针：有序数组/链表问题
滑动窗口：子数组/子串问题
子串：字符串匹配问题
普通数组：数组遍历、查找
矩阵：二维数组遍历
链表：遍历、反转
二叉树：遍历、搜索
图论：图的遍历
回溯：组合、排列
二分查找：有序数组查找
栈：逆序遍历
贪心算法：局部最优解
动态规划：最优解
多维动态规划：多维数组问题
技巧：位运算、前缀和

哈希(Hash)

核心思想：利用哈希表(O(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
// 哈希表基本操作
Map<Integer, Integer> map = new HashMap<>();
map.put(key, value);       // 存储
int val = map.get(key);     // 获取
boolean exists = map.containsKey(key); // 检查存在

// 典型问题：两数之和
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[0];
}

// 哈希集合去重
Set<Integer> set = new HashSet<>();
for (int num : nums) {
    if (set.contains(num)) {
        // 发现重复
    }
    set.add(num);
}

双指针(Two Pointers)

核心思想：使用两个指针协同遍历数据结构
适用场景：有序数组/链表问题，如归并数组、判断回文

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
// 左右指针模板（如反转数组）
public void reverse(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int temp = nums[left];
        nums[left++] = nums[right];
        nums[right--] = temp;
    }
}

// 快慢指针模板（如链表环检测）
public 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;
}

// 三数之和问题
public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        int left = i+1, right = nums.length-1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                while (left < right && nums[left] == nums[left+1]) left++;
                while (left < right && nums[right] == nums[right-1]) right--;
                left++; right--;
            } else if (sum < 0) left++;
            else right--;
        }
    }
    return res;
}

滑动窗口(Sliding Window)

核心思想：维护一个可变大小的窗口在数据结构上滑动
适用场景：子数组/子串问题，如最小覆盖子串、最长无重复子串

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
// 滑动窗口模板
public int slidingWindowTemplate(String s) {
    Map<Character, Integer> window = new HashMap<>();
    int left = 0, right = 0;
    int maxLen = 0;
    
    while (right < s.length()) {
        char c = s.charAt(right++);
        window.put(c, window.getOrDefault(c, 0) + 1);
        
        while (/* 窗口需要收缩的条件 */) {
            char d = s.charAt(left++);
            window.put(d, window.get(d) - 1);
            if (window.get(d) == 0) window.remove(d);
        }
        
        maxLen = Math.max(maxLen, right - left);
    }
    return maxLen;
}

// 最长无重复字符子串
public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> window = new HashMap<>();
    int left = 0, right = 0;
    int maxLen = 0;
    
    while (right < s.length()) {
        char c = s.charAt(right++);
        window.put(c, window.getOrDefault(c, 0) + 1);
        
        while (window.get(c) > 1) {
            char d = s.charAt(left++);
            window.put(d, window.get(d) - 1);
        }
        
        maxLen = Math.max(maxLen, right - left);
    }
    return maxLen;
}

子串(Substring)

核心思想：处理字符串中的连续字符序列问题
适用场景：字符串匹配、子串查找、回文子串等

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
// 最长回文子串（中心扩展法）
public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);    // 奇数长度
        int len2 = expandAroundCenter(s, i, i + 1); // 偶数长度
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

private int expandAroundCenter(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 1;
}

// KMP算法（字符串匹配）
public int strStr(String haystack, String needle) {
    if (needle.isEmpty()) return 0;
    int[] lps = computeLPSArray(needle);
    int i = 0, j = 0;
    while (i < haystack.length()) {
        if (haystack.charAt(i) == needle.charAt(j)) {
            i++; j++;
            if (j == needle.length()) return i - j;
        } else {
            if (j != 0) j = lps[j-1];
            else i++;
        }
    }
    return -1;
}

private int[] computeLPSArray(String pattern) {
    int[] lps = new int[pattern.length()];
    int len = 0, i = 1;
    while (i < pattern.length()) {
        if (pattern.charAt(i) == pattern.charAt(len)) {
            lps[i++] = ++len;
        } else {
            if (len != 0) len = lps[len-1];
            else lps[i++] = 0;
        }
    }
    return lps;
}

普通数组(Array)

核心思想：利用数组索引和元素关系解决问题
适用场景：元素操作、排序、搜索等基础问题

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
// 数组反转
public void reverseArray(int[] nums) {
    for (int i = 0; i < nums.length / 2; i++) {
        int temp = nums[i];
        nums[i] = nums[nums.length - 1 - i];
        nums[nums.length - 1 - i] = temp;
    }
}

// 荷兰国旗问题（三向切分）
public void sortColors(int[] nums) {
    int low = 0, high = nums.length - 1;
    int i = 0;
    while (i <= high) {
        if (nums[i] == 0) {
            swap(nums, low++, i++);
        } else if (nums[i] == 2) {
            swap(nums, i, high--);
        } else {
            i++;
        }
    }
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

// 前缀和数组
class PrefixSum {
    private int[] prefix;
    
    public PrefixSum(int[] nums) {
        prefix = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }
    
    public int sumRange(int left, int right) {
        return prefix[right + 1] - prefix[left];
    }
}

矩阵(Matrix)

核心思想：二维数组的特殊遍历和操作技巧
适用场景：图像处理、矩阵运算、二维搜索等

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
// 螺旋矩阵遍历
public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> res = new ArrayList<>();
    if (matrix == null || matrix.length == 0) return res;
    int top = 0, bottom = matrix.length - 1;
    int left = 0, right = matrix[0].length - 1;
    
    while (true) {
        // 从左到右
        for (int i = left; i <= right; i++) res.add(matrix[top][i]);
        if (++top > bottom) break;
        
        // 从上到下
        for (int i = top; i <= bottom; i++) res.add(matrix[i][right]);
        if (--right < left) break;
        
        // 从右到左
        for (int i = right; i >= left; i--) res.add(matrix[bottom][i]);
        if (--bottom < top) break;
        
        // 从下到上
        for (int i = bottom; i >= top; i--) res.add(matrix[i][left]);
        if (++left > right) break;
    }
    return res;
}

// 旋转图像（原地旋转90度）
public void rotate(int[][] matrix) {
    int n = matrix.length;
    // 先转置矩阵
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
    // 再翻转每一行
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n / 2; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[i][n - 1 - j];
            matrix[i][n - 1 - j] = temp;
        }
    }
}

// 岛屿数量（DFS）
public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    int count = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                dfs(grid, i, j);
                count++;
            }
        }
    }
    return count;
}

private void dfs(char[][] grid, int i, int j) {
    if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != '1') return;
    grid[i][j] = '0'; // 标记为已访问
    dfs(grid, i + 1, j);
    dfs(grid, i - 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);
}

链表(Linked List)

核心思想：指针操作和虚拟头节点技巧
适用场景：链表反转、环检测、节点操作等

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
// 链表节点定义
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

// 反转链表（迭代）
public ListNode reverseList(ListNode head) {
    ListNode prev = null, 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 p = reverseListRecursive(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

// 合并两个有序链表
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    curr.next = l1 != null ? l1 : l2;
    return dummy.next;
}

// 检测链表环并找到入口
public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            ListNode ptr = head;
            while (ptr != slow) {
                ptr = ptr.next;
                slow = slow.next;
            }
            return ptr;
        }
    }
    return null;
}

二叉树(Binary Tree)

核心思想：递归和迭代遍历，分治思想
适用场景：树结构相关问题，如遍历、构造、属性判断等

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
// 二叉树节点定义
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

// 前序遍历（递归）
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    preorder(root, res);
    return res;
}

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

// 中序遍历（迭代）
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        res.add(curr.val);
        curr = curr.right;
    }
    return res;
}

// 层次遍历（BFS）
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < levelSize; 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);
        }
        res.add(level);
    }
    return res;
}

// 二叉树的最大深度
public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

图论(Graph Theory)

核心思想：DFS/BFS遍历，并查集，最短路径算法
适用场景：网络结构、路径查找、连通性问题

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
// 图的邻接表表示
List<List<Integer>> graph = new ArrayList<>();

// DFS遍历
public void dfs(int node, boolean[] visited, List<List<Integer>> graph) {
    visited[node] = true;
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited, graph);
        }
    }
}

// BFS遍历
public void bfs(int start, List<List<Integer>> graph) {
    boolean[] visited = new boolean[graph.size()];
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    visited[start] = true;
    while (!queue.isEmpty()) {
        int node = queue.poll();
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.offer(neighbor);
            }
        }
    }
}

// Dijkstra算法（最短路径）
public int[] dijkstra(List<List<int[]>> graph, int start) {
    int n = graph.size();
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    pq.offer(new int[]{start, 0});
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int u = curr[0], d = curr[1];
        if (d > dist[u]) continue;
        for (int[] edge : graph.get(u)) {
            int v = edge[0], w = edge[1];
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.offer(new int[]{v, dist[v]});
            }
        }
    }
    return dist;
}

// 并查集实现
class UnionFind {
    private int[] parent;
    public UnionFind(int size) {
        parent = new int[size];
        for (int i = 0; i < size; i++) parent[i] = i;
    }
    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    public void union(int x, int y) {
        parent[find(x)] = find(y);
    }
}

回溯(Backtracking)

核心思想：尝试-回溯-剪枝，系统性地搜索解空间
适用场景：排列组合、子集、棋盘类问题

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
// 回溯模板
public List<List<Integer>> backtrack(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrackHelper(res, new ArrayList<>(), nums, 0);
    return res;
}

private void backtrackHelper(List<List<Integer>> res, List<Integer> temp, int[] nums, int start) {
    // 满足条件时加入结果
    if (/* 终止条件 */) {
        res.add(new ArrayList<>(temp));
        return;
    }
    for (int i = start; i < nums.length; i++) {
        // 剪枝条件
        if (/* 剪枝 */) continue;
        temp.add(nums[i]); // 做选择
        backtrackHelper(res, temp, nums, i + 1); // 递归
        temp.remove(temp.size() - 1); // 撤销选择
    }
}

// 全排列
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, new ArrayList<>(), res);
    return res;
}

private void backtrack(int[] nums, List<Integer> temp, List<List<Integer>> res) {
    if (temp.size() == nums.length) {
        res.add(new ArrayList<>(temp));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (temp.contains(nums[i])) continue; // 剪枝
        temp.add(nums[i]);
        backtrack(nums, temp, res);
        temp.remove(temp.size() - 1);
    }
}

// N皇后问题
public List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<>();
    char[][] board = new char[n][n];
    for (char[] row : board) Arrays.fill(row, '.');
    backtrack(res, board, 0);
    return res;
}

private void backtrack(List<List<String>> res, char[][] board, int row) {
    if (row == board.length) {
        res.add(construct(board));
        return;
    }
    for (int col = 0; col < board.length; col++) {
        if (isValid(board, row, col)) {
            board[row][col] = 'Q';
            backtrack(res, board, row + 1);
            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> res = new ArrayList<>();
    for (char[] row : board) {
        res.add(new String(row));
    }
    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
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
// 标准二分查找
public 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;
}

// 查找左边界
public int leftBound(int[] nums, int target) {
    int left = 0, right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) right = mid;
        else left = mid + 1;
    }
    return left < nums.length && nums[left] == target ? left : -1;
}

// 查找右边界
public int rightBound(int[] nums, int target) {
    int left = 0, right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) left = mid + 1;
        else right = mid;
    }
    return left > 0 && nums[left-1] == target ? left-1 : -1;
}

// 旋转数组查找
public int searchInRotatedArray(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;
        // 左半部分有序
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) right = mid - 1;
            else left = mid + 1;
        } 
        // 右半部分有序
        else {
            if (nums[mid] < target && target <= nums[right]) left = mid + 1;
            else right = mid - 1;
        }
    }
    return -1;
}

栈(Stack)

核心思想：LIFO特性，用于处理对称、嵌套类问题
适用场景：括号匹配、表达式求值、单调栈问题

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
// 括号匹配
public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '(') stack.push(')');
        else if (c == '[') stack.push(']');
        else if (c == '{') stack.push('}');
        else if (stack.isEmpty() || stack.pop() != c) return false;
    }
    return stack.isEmpty();
}

// 单调栈模板（下一个更大元素）
public int[] nextGreaterElement(int[] nums) {
    int[] res = new int[nums.length];
    Stack<Integer> stack = new Stack<>();
    for (int i = nums.length - 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;
}

// 计算器（表达式求值）
public int calculate(String s) {
    Stack<Integer> stack = new Stack<>();
    int num = 0, res = 0, sign = 1;
    for (char c : s.toCharArray()) {
        if (Character.isDigit(c)) {
            num = num * 10 + (c - '0');
        } else if (c == '+') {
            res += sign * num;
            num = 0;
            sign = 1;
        } else if (c == '-') {
            res += sign * num;
            num = 0;
            sign = -1;
        } else if (c == '(') {
            stack.push(res);
            stack.push(sign);
            res = 0;
            sign = 1;
        } else if (c == ')') {
            res += sign * num;
            num = 0;
            res *= stack.pop(); // sign
            res += stack.pop(); // previous res
        }
    }
    if (num != 0) res += sign * num;
    return res;
}

贪心算法(Greedy)

核心思想：局部最优选择希望导致全局最优
适用场景：区间调度、分配问题、跳跃游戏等

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
// 区间调度问题（最多不重叠区间）
public int intervalSchedule(int[][] intervals) {
    if (intervals.length == 0) return 0;
    // 按结束时间排序
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
    int count = 1;
    int end = intervals[0][1];
    for (int[] interval : intervals) {
        int start = interval[0];
        if (start >= end) {
            count++;
            end = interval[1];
        }
    }
    return count;
}

// 跳跃游戏
public boolean canJump(int[] nums) {
    int farthest = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > farthest) return false;
        farthest = Math.max(farthest, i + nums[i]);
        if (farthest >= nums.length - 1) return true;
    }
    return false;
}

// 分发饼干
public int findContentChildren(int[] g, int[] s) {
    Arrays.sort(g);
    Arrays.sort(s);
    int i = 0, j = 0;
    while (i < g.length && j < s.length) {
        if (s[j] >= g[i]) i++;
        j++;
    }
    return i;
}

动态规划(DP)

核心思想：将问题分解为子问题，存储中间结果避免重复计算
适用场景：最优化问题，如最长子序列、背包问题、路径问题

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
73
74
75
// 斐波那契数列（记忆化递归）
public int fib(int n) {
    int[] memo = new int[n + 1];
    return helper(n, memo);
}

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

// 斐波那契数列（迭代）
public int fibIterative(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

// 最长递增子序列
public int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);
    int max = 1;
    for (int i = 1; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        max = Math.max(max, dp[i]);
    }
    return max;
}

// 0-1背包问题
public int knapsack(int W, int[] wt, int[] val) {
    int n = wt.length;
    int[][] dp = new int[n + 1][W + 1];
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (wt[i - 1] <= w) {
                dp[i][w] = Math.max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    return dp[n][W];
}

// 编辑距离
public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], 
                    Math.min(dp[i][j - 1], dp[i - 1][j]));
            }
        }
    }
    return dp[m][n];
}

多维动态规划(Multi-dimensional DP)

核心思想：扩展DP状态到多个维度
适用场景：复杂约束条件的最优化问题

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
// 股票买卖问题（含冷冻期）
public int maxProfit(int[] prices) {
    if (prices == null || prices.length == 0) return 0;
    int n = prices.length;
    int[][] dp = new int[n][3];
    // dp[i][0]: 持有股票
    // dp[i][1]: 不持有股票，处于冷冻期
    // dp[i][2]: 不持有股票，不处于冷冻期
    dp[0][0] = -prices[0];
    for (int i = 1; i < n; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2] - prices[i]);
        dp[i][1] = dp[i - 1][0] + prices[i];
        dp[i][2] = Math.max(dp[i - 1][1], dp[i - 1][2]);
    }
    return Math.max(dp[n - 1][1], dp[n - 1][2]);
}

// 正则表达式匹配
public boolean isMatch(String s, String p) {
    int m = s.length(), n = p.length();
    boolean[][] dp = new boolean[m + 1][n + 1];
    dp[0][0] = true;
    for (int j = 1; j <= n; j++) {
        if (p.charAt(j - 1) == '*') {
            dp[0][j] = dp[0][j - 2];
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') {
                dp[i][j] = dp[i - 1][j - 1];
            } else if (p.charAt(j - 1) == '*') {
                if (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') {
                    dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i][j - 2];
                }
            }
        }
    }
    return dp[m][n];
}

// 最大正方形面积
public int maximalSquare(char[][] matrix) {
    if (matrix == null || matrix.length == 0) return 0;
    int m = matrix.length, n = matrix[0].length;
    int[][] dp = new int[m + 1][n + 1];
    int maxLen = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (matrix[i - 1][j - 1] == '1') {
                dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                maxLen = Math.max(maxLen, dp[i][j]);
            }
        }
    }
    return maxLen * maxLen;
}

技巧(Tricks)

核心思想：各种实用技巧和小算法
适用场景：位操作、数学技巧、随机化等

// 位操作技巧
public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1); // 清除最低位的1
        count++;
    }
    return count;
}

// 洗牌算法（Fisher-Yates）
public void shuffle(int[] nums) {
    Random rand = new Random();
    for (int i = nums.length - 1; i > 0; i--) {
        int j = rand.nextInt(i + 1);
        swap(nums, i, j);
    }
}

// 蓄水池抽样
public int getRandom(ListNode head) {
    Random rand = new Random();
    int res = 0, i = 1;
    ListNode curr = head;
    while (curr != null) {
        if (rand.nextInt(i) == 0) {
            res = curr.val;
        }
        i++;
        curr = curr.next;
    }
    return res;
}

// 摩尔投票法（多数元素）
public int majorityElement(int[] nums) {
    int count = 0, candidate = 0;
    for (int num : nums) {
        if (count == 0) candidate = num;
        count += (num == candidate) ? 1 : -1;
    }
    return candidate;
}

// 快速幂
public double myPow(double x, int n) {
    long N = n;
    if (N < 0) {
        x = 1 / x;
        N = -N;
    }
    double res = 1;