16 种基本问题解决模式

数据结构和算法 (DSA) 对于高效解决问题至关重要。以下 16 种关键模式，以及用例和示例，旨在帮助您解决实际问题。本指南包含简洁的 Java 示例，用于演示每种模式的实际应用。

1.滑动窗口模式

用于跟踪随时间变化的数据子集，通常为数组或字符串。

用例：子数组的最大和。
示例：大小为 K 的子数组的最大和。

public int maxSubArraySum(int[] arr, int k) {
    int maxSum = 0, windowSum = 0;
    for (int i = 0; i < arr.length; i++) {
        windowSum += arr[i];
        if (i >= k - 1) {
            maxSum = Math.max(maxSum, windowSum);
            windowSum -= arr[i - (k - 1)];
        }
    }
    return maxSum;
}

2.双指针模式

两个指针从数组的不同端汇聚，从而找到解决方案。

用例：在排序数组中查找对。
示例：找到两个总和等于目标的数字。

public int[] twoSum(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) return new int[]{left, right};
        else if (sum < target) left++;
        else right--;
    }
    return new int[]{};
}

3.快慢指针模式

两个指针以不同的速度移动来检测序列中的循环。

用例：检测链接列表中的循环。
示例：检查链表是否有循环。

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;
}

4.合并间隔模式

此模式合并了重叠的间隔。

用例：安排会议。
示例：合并重叠间隔。

public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    List<int[]> merged = new ArrayList<>();
    for (int[] interval : intervals) {
        if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
            merged.add(interval);
        } else {
            merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);
        }
    }
    return merged.toArray(new int[merged.size()][]);
}

5.循环排序模式

当元素属于某个范围时对数字进行排序。

用例：查找缺失的数字。
例如：从 1 到 N 中找出缺失的数字。

public int findMissingNumber(int[] nums) {
    int i = 0;
    while (i < nums.length) {
        if (nums[i] != i && nums[i] < nums.length) {
            int temp = nums[nums[i]];
            nums[nums[i]] = nums[i];
            nums[i] = temp;
        } else {
            i++;
        }
    }
    for (i = 0; i < nums.length; i++) {
        if (nums[i] != i) return i;
    }
    return nums.length;
}

6.链表模式的就地反转

就地反转链接列表。

用例：反转链接列表的子列表。
示例：反转链接列表。

public ListNode reverseList(ListNode head) {
    ListNode prev = null, current = head;
    while (current != null) {
        ListNode next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

7.树状广度优先搜索（BFS）模式

逐级探索树中的节点。

用例：层次遍历。
示例：逐级遍历二叉树。

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

8.深度优先搜索（DFS）模式

在回溯之前，沿着分支尽可能深入地探索。

用例：在树或图中搜索。
示例：查找所有从根到叶的路径。

public void dfs(TreeNode node, List<Integer> path, List<List<Integer>> result) {
    if (node == null) return;
    path.add(node.val);
    if (node.left == null && node.right == null) result.add(new ArrayList<>(path));
    dfs(node.left, path, result);
    dfs(node.right, path, result);
    path.remove(path.size() - 1);
}

9.双堆模式

使用两个堆来维护动态数据集。

用例：查找数据流中的中位数。
示例：找出数字流的中位数。

class MedianFinder {
    private PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder());
    private PriorityQueue<Integer> high = new PriorityQueue<>();

    public void addNum(int num) {
        low.offer(num);
        high.offer(low.poll());
        if (low.size() < high.size()) low.offer(high.poll());
    }

    public double findMedian() {
        return low.size() > high.size() ? low.peek() : (low.peek() + high.peek()) / 2.0;
    }
}

10.子集模式

生成所有可能的子集。

用例：组合和排列问题。
示例：查找集合的所有子集。

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    result.add(new ArrayList<>());
    for (int num : nums) {
        int size = result.size();
        for (int i = 0; i < size; i++) {
            List<Integer> subset = new ArrayList<>(result.get(i));
            subset.add(num);
            result.add(subset);
        }
    }
    return result;
}

11.修改后的二分搜索模式

在旋转或部分排序的数组中搜索。

用例：在旋转数组中查找元素。
示例：在旋转排序数组中搜索目标。

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;
        if (nums[left] <= nums[mid]) {
            if (target >= nums[left] && target < nums[mid]) right = mid - 1;
            else left = mid + 1;
        } else {
            if (target > nums[mid] && target <= nums[right]) left = mid + 1;
            else right = mid - 1;
        }
    }
    return -1;
}

12.按位异或模式

使用 XOR 解决涉及对的问题。

用例：查找唯一数字。
示例：查找数组中的单个数字。

public int singleNumber(int[] nums) {
    int result = 0;
    for (int num : nums) result ^= num;
    return result;
}

13.顶部“K”元素模式

使用堆来查找数据集中的前 K 个元素。

用例：查找前 K 个频繁元素。
示例：找出最常见的 K 个数字。

public List<Integer> topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> countMap = new HashMap<>();
    for (int num : nums) countMap.put(num, countMap.getOrDefault(num, 0) + 1);
    PriorityQueue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));
    for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
        heap.offer(entry);
        if (heap.size() > k) heap.poll();
    }
    return heap.stream().map(Map.Entry::getKey).collect(Collectors.toList());
}

K-Way 合并模式有效地合并多个排序数组。

用例：合并 K 个排序列表。
示例：合并 K 个排序链表。

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
    ListNode dummy = new ListNode(0), tail = dummy;
    for (ListNode list : lists) if (list != null) heap.offer(list);
    while (!heap.isEmpty()) {
        tail.next = heap.poll();
        tail = tail.next;
        if (tail.next != null) heap.offer(tail.next);
    }
    return dummy.next;
}

15. 0/1背包动态规划模式

在约束条件下优化选择。

用例：资源分配。
例子：解决0/1背包问题。

public int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= capacity; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    return dp[n][capacity];
}

16.拓扑排序图模式

在有向无环图（DAG）中查找有效的任务顺序。

用例：课程安排。
例如：找出课程的正确顺序。

public int[] findOrder(int numCourses, int[][] prerequisites) {
    List<Integer>[] graph = new ArrayList[numCourses];
    int[] inDegree = new int[numCourses];
    for (int i = 0; i < numCourses; i++) graph[i] = new ArrayList<>();
    for (int[] pre : prerequisites) {
        graph[pre[1]].add(pre[0]);
        inDegree[pre[0]]++;
    }
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) if (inDegree[i] == 0) queue.add(i);
    int[] result = new int[numCourses];
    int idx = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll();
        result[idx++] = course;
        for (int next : graph[course]) {
            inDegree[next]--;
            if (inDegree[next] == 0) queue.add(next);
        }
    }
    return idx == numCourses ? result : new int[0];
}

这 16 种解题模式对于掌握 DSA 至关重要。每种模式都可以应用于各种实际问题，提供一条通往最优解决方案的有效途径。

文章来源：https://dev.to/saurabhkurve/16-essential-problem-solving-patterns-31p2