数据结构与算法（DSA）中的16个关键模式

数据结构与算法（DSA）对于高效解决问题至关重要。以下是16个关键模式，每个模式都附有使用案例和示例，帮助您解决现实世界中的问题。本指南包括简洁的Java示例，以演示每个模式的应用。

1. 滑动窗口模式（Sliding Window Pattern）

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

使用案例：子数组的最大和。示例：大小为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. 双指针模式（Two Pointer Pattern）

两个指针从数组的不同端向中间收敛，以找到解决方案。

使用案例：在已排序数组中查找对。示例：查找两个和为目标值的数字。

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. 快慢指针模式（Fast & Slow Pointers Pattern）

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

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

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. 合并区间模式（Merge Intervals Pattern）

合并重叠的区间。

使用案例：安排会议。示例：合并重叠的区间。

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. 循环排序模式（Cyclic Sort Pattern）

当元素落在一定范围内时，对数字进行排序。

使用案例：查找缺失的数字。示例：查找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. 链表原地反转模式（In-Place Reversal of Linked List Pattern）

在原地反转链表。

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

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）模式（Tree Breadth-First Search (BFS) Pattern）

逐层探索树中的节点。

使用案例：层序遍历。示例：逐层遍历二叉树。

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）模式（Depth-First Search (DFS) Pattern）

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

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

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. 双堆模式（Two Heap Pattern）

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

使用案例：在数据流中查找中位数。示例：查找数据流的中位数。

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. 子集模式（Subsets Pattern）

生成所有可能的子集。

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

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. 修改的二分搜索模式（Modified Binary Search Pattern）

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

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

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. 位运算异或模式（Bitwise XOR Pattern）

使用异或解决涉及对的问题。

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

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

13. 前K个元素模式（Top ‘K’ Elements Pattern）

使用堆查找数据集中的前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());
}

14. K路合并模式（K-Way Merge Pattern）

高效合并多个已排序的数组。

使用案例：合并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 Knapsack Dynamic Programming Pattern）

在约束条件下优化选择。

使用案例：资源分配。示例：解决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. 拓扑排序图模式（Topological Sort Graph Pattern）

在有向无环图（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个问题解决模式对于掌握数据结构与算法至关重要。每个模式都可以应用于广泛的现实世界问题，提供了一条通向最优解决方案的高效路径。

DevDailyNews

数据结构与算法（DSA）中的16个关键模式