编码模式：一种更智能的面试准备编码方法

准备编码面试可能是一个真正的挑战，因为开发人员经常花费几周的时间来审查和学习新材料。

事实是，大多数开发人员从未为他们的编码面试做好充分准备。开发人员花费数周时间在 LeetCode 上解决问题却仍感到毫无准备的情况并不罕见。显然，这种方法存在问题。

让我们仔细看看与传统编码面试准备相关的一些问题。

传统面试准备的陷阱

传统面试准备中最常见的陷阱之一是“磨练”的做法。这种方法涉及在没有明确计划或策略的情况下解决尽可能多的LeetCode问题。虽然这看起来是一个富有成效的策略，但它有几个缺点。

当您在没有结构化方法的情况下解决问题时，您可能无法认识到自己的弱点。你的学习没有刻意的计划；目标只是解决尽可能多的问题。因此，您可能会觉得自己学到了很多东西，但您的知识可能存在很大差距。

此外，问题在于它本质上是围绕着记忆众多问题的解决方案而展开的。当面试官提出的问题与你以前遇到过的问题略有不同时，尝试记住一百种不同编码问题的解决方案是无效的。这可能会让您感觉没有准备好处理问题的变化。

我对这个策略的最后一个问题是，从长远来看，它会带来更多的压力和头痛。如果你每次想换工作时都必须经历同样的长达数周的临时抱佛脚课程，那么你每次都会很挣扎。您将花费数周的时间重新学习知识并解决与以前相同的问题。

考虑到这些挑战，必须有更好的方法。

更好的方法：拥抱编码模式

那么，是否有更有效和可持续的面试准备方法？答案在于理解和利用编码模式。

当我准备编码面试时，我会优先考虑掌握问题的根本模式。这些模式包括双指针、滑动窗口、修改二分搜索、拓扑排序等技术，为解决各种编码问题提供了一个通用且强大的框架。重点从记住解决方案转向经过验证的解决问题的技巧。

通过关注编码模式，您可以显着简化面试准备工作，从而提高效率。

请记住，准备得更聪明，而不是更努力。

期待什么？

在这篇文章中，我整理了前 15 名编码模式您需要知道才能回答任何编码问题。我将详细介绍每种模式是什么以及它是如何工作的。分享关键指标来帮助您识别模式，最后提供带有模板代码的详细图形来帮助您巩固理解。

虽然我在本文中介绍了很多内容，但如果您想要更深入的培训、解释和编码实践，您可以在 Techinterviews.io 上查看我们的综合编码面试准备课程。我们还涵盖数据结构、行为面试、甚至薪资谈判等重要主题。

现在让我们深入研究这些编码模式。

1. 链表反转

链表反转涉及更改链表中指针的方向以反转元素的顺序。这是数据结构中的基本操作，通常需要仔细操作节点引用。

这在处理链表并且约束是就地反转它时很有用。

就地反转链表的过程如下：

1. 首先定义三个变量： current 、 previous和next 。将current设置为链表的头，并将previous和next初始化为None。

2. 当当前变量不是None时，请按以下步骤操作：

   1. 将下一个节点存储在临时变量中。
   2. 反转当前节点的指针以指向前一个节点。
   3. 将previous更新为当前节点，将current 更新为下一个节点。

3. 最后，将反转列表的头设置为最后到达的节点，该节点存储在previous变量中。

关键指标：

• 您需要反转链表中元素的顺序。
• 问题涉及检查链表中的回文。
• 您想要反转列表中特定子列表中元素的顺序。

模板代码：

Python

 def reverse_linked_list(head): curr = head prev = None while curr: next_node = curr.next curr.next = prev prev = curr curr = next_node return prev

JS

 function reverseLinkedList(head) { let curr = head; let prev = null; while (curr) { const nextNode = curr.next; curr.next = prev; prev = curr; curr = nextNode; } return prev; }

爪哇

public ListNode reverseLinkedList(ListNode head) { ListNode curr = head; ListNode prev = null; while (curr != null) { ListNode nextNode = curr.next; curr.next = prev; prev = curr; curr = nextNode; } return prev; }

2. 改进的二分查找

改进的二分搜索采用经典的二分搜索算法来解决各种问题。变体包括查找元素的第一次/最后一次出现或在旋转数组中搜索。它需要仔细处理中点和条件。

如果您曾经给定一个排序数组、链表或矩阵，请考虑使用修改后的二分搜索。

以下是如何将此模式应用于排序数据结构的详细说明：

1. 首先确定开始位置和结束位置之间的中点。为了避免潜在的整数溢出，按如下方式计算中间值更安全： middle = start + (end - start) / 2 。
2. 检查键是否与中间索引处的元素匹配。如果是，则返回中间索引作为结果。
3. 如果键与中间索引处的元素不匹配，请继续执行后续步骤。
4. 评估键是否小于索引middle处的元素。如果是，请通过将end更新为middle - 1来缩小搜索范围。
5. 相反，如果键大于索引middle处的元素，则通过将start更新为middle + 1来调整搜索范围。

关键指标：

• 您正在使用排序的数据结构。
• 您需要有效地找到特定元素、边界或枢轴点。
• 问题涉及在旋转排序数组中进行搜索。

模板代码：

Python

 def binary_search(arr: List[int], target: int) -> int: left, right = 0, len(arr) - 1 first_true_index = -1 # Perform binary search until left and right pointers meet while left <= right: mid = (left + right) // 2 if feasible(mid): # If the condition is true at mid index, update first_true_index first_true_index = mid right = mid - 1 else: # If the condition is false at mid index, narrow down the search space left = mid + 1 return first_true_index

JS

 function binarySearch(arr, target) { let left = 0; let right = arr.length - 1; let firstTrueIndex = -1; // Perform binary search until left and right pointers meet while (left <= right) { const mid = Math.floor((left + right) / 2); if (feasible(mid)) { // If the condition is true at mid index, update firstTrueIndex firstTrueIndex = mid; right = mid - 1; } else { // If the condition is false at mid index, narrow down the search space left = mid + 1; } } return firstTrueIndex; }

爪哇

public int binarySearch(int[] arr, int target) { int left = 0; int right = arr.length - 1; int firstTrueIndex = -1; // Perform binary search until left and right pointers meet while (left <= right) { int mid = left + (right - left) / 2; if (feasible(mid)) { // If the condition is true at mid index, update firstTrueIndex firstTrueIndex = mid; right = mid - 1; } else { // If the condition is false at mid index, narrow down the search space left = mid + 1; } } return firstTrueIndex; }

3. 两个指针

双指针技术涉及维护两个遍历数据结构的指针，通常是数组或链表，通常用于涉及对或子数组的问题。它针对需要在不同位置的元素之间进行比较的问题进行了优化。

这种技术的优点在于它的简单性和效率，特别是在处理线性数据结构（如数组或字符串）时，您最初可能只使用一个指针。通过使用两个指针，您可以避免冗余操作并显着提高运行时效率，有可能将其从O(n^2)降低到O(n) 。

“双指针”模式包含多种变体，每种变体都针对特定场景而定制。这些变化包括相同方向、相反方向以及一种称为“快与慢”的独特方法，通常称为“龟兔赛跑”技术，该技术涉及两个指针以不同的速度在数据结构中移动，特别适用于检测循环。

如果您使用多个指针来遍历数据结构，则可以将您的方法分类为遵循“双指针”模式。

关键指标：

• 您需要对不同位置的元素进行比较或操作。
• 问题需要在排序数组中搜索元素对。
• 您希望有效地从排序数组中删除重复项。
• 当处理线性数据结构（数组、字符串或链表）并面临二次时间复杂度（ O(n^2)强力解决方案）时，请考虑使用两个指针。

模板代码：

“相反方向”变化的模板

Python

 def two_pointers_opposite(arr): left = 0 right = len(arr) - 1 ans = 0 while left < right: # Perform logic using the left and right pointers if CONDITION: left += 1 else: right -= 1 return ans

JS

 function twoPointersOpposite(arr) { let left = 0; let right = arr.length - 1; let ans = 0; while (left < right) { // Perform logic using the left and right pointers if (CONDITION) { left++; } else { right--; } } return ans; }

爪哇

public int twoPointersOpposite(int[] arr) { int left = 0; int right = arr.length - 1; int ans = 0; while (left < right) { // Perform logic using the left and right pointers if (CONDITION) { left++; } else { right--; } } return ans; }

4. 滑动窗口

滑动窗口技术涉及在线性数据结构（例如数组、字符串或链接列表）上维护动态窗口。窗口的大小可以根据具体实现而变化，也可以设置为固定值。该窗口的主要目标是持续监视和捕获满足特定标准的数据，这使其对于有效解决子数组或子串问题特别有价值。

这种模式通常利用哈希图来促进窗口内单个数据的跟踪。然而，值得注意的是，这种方法可能会导致O(n)的时空复杂度。

关键指标：

• 您需要分析连续或不连续的子数组或子字符串。
• 问题涉及跟踪较大数据集中的可变长度序列。
• 您想要找到固定长度的最大和子数组。
• 问题输入是线性数据结构，例如数组、链表或字符串。

模板代码：

Python

 def slidingWindow(nums): # Initialize necessary variables left = 0 window = [] # Initialize the window ans = 0 # Initialize the answer variable for right in range(len(nums)): window.append(nums[right]) # Expand the window to the right while invalid(window): # Condition to shrink the window from the left until it is valid again window.pop(0) # Remove the left element from the window left += 1 ans = max(ans, len(window)) # Update the answer, can vary on your implementation return ans

JS

 function slidingWindow(nums) { let left = 0; const window = []; // Initialize the window let ans = 0; // Initialize the answer variable for (let right = 0; right < nums.length; right++) { window.push(nums[right]); // Expand the window to the right while (invalid(window)) { // Condition to shrink the window from the left until it is valid again window.shift(); // Remove the left element from the window left++; } ans = Math.max(ans, window.length); // Update the answer , can vary on your implementation } return ans; }

爪哇

public static int slidingWindow(int[] nums) { int left = 0; List<Integer> window = new ArrayList<>(); // Initialize the window int ans = 0; // Initialize the answer variable for (int right = 0; right < nums.length; right++) { window.add(nums[right]); // Expand the window to the right while (invalid(window)) { // Condition to shrink the window from the left until it is valid again window.remove(0); // Remove the left element from the window left++; } ans = Math.max(ans, window.size()); // Update the answer , can vary on your implementation } return ans; }

5. 前 K 个元素

此模式涉及查找集合中的 K 个最大或最小元素，通常使用堆或优先级队列等数据结构来实现。它对于根据值或频率选择元素子集很有用。

每当我们被要求在给定数据集中找到最频繁、最小或前“K”个元素时，我们都可以考虑使用此模式。

它的工作方式很简单：

1. 我们将“K”元素插入到最小或最大堆中（这取决于实现）。
2. 每当我们添加到堆中时，我们都必须进行调整，以便始终保持频繁/最小/顶部“K”元素。

这种方法的优点在于它的效率；您不需要诉诸任何排序算法，因为堆本身自然会为您维护所需的顺序。

关键指标：

• 您需要识别集合中的 K 个最大或最小元素。
• 问题需要根据某些标准对元素进行排名。
• 您想要找到数据集中前 K 个频繁元素。

模板代码：

Python

 import heapq def top_k_elements(arr, k): heap = [] for num in arr: # Define your own criteria and logic to push elements onto the heap # For example, if you want to find the top k largest elements, push (-num, num) onto the heap heapq.heappush(heap, (-CRITERIA, num)) if len(heap) > k: heapq.heappop(heap) return [num for _, num in heap]

JS

 function topKElements(arr, k) { const minHeap = []; for (const num of arr) { // Define your own criteria and logic to push elements onto the heap // For example, if you want to find the top k smallest elements, push num onto the heap minHeap.push(CRITERIA); if (minHeap.length > k) { minHeap.sort((a, b) => a - b).shift(); } } return minHeap.sort((a, b) => a - b); }

爪哇

import java.util.*; public List<Integer> topKElements(int[] arr, int k) { PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.comparingInt(a -> -CRITERIA)); for (int num : arr) { // Define your own criteria and logic to push elements onto the heap // For example, if you want to find the top k largest elements, push -num onto the heap heap.offer(-CRITERIA); if (heap.size() > k) { heap.poll(); } } List<Integer> topK = new ArrayList<>(); while (!heap.isEmpty()) { topK.add(-heap.poll()); } Collections.reverse(topK); return topK; }

6. 两堆

两个堆利用两个堆（最大堆和最小堆）来优化某些问题，例如查找数据集中的中值。这种模式对于维持平衡结构特别有用。

它的工作原理如下：

1. 使用两个堆：最大堆用于识别最大元素，最小堆用于查找最小元素。
2. 用前半部分数字填充最大堆，旨在找到其中最大的数字。
3. 用后半部分的数字填充最小堆，以确定这部分中最小的数字。
4. 通过检查两个堆的顶部元素，可以随时计算当前数字集的中位数。

关键指标：

• 您需要保持平衡的结构才能有效地查找中位数。
• 问题涉及使用动态中位数处理滑动窗口问题。
• 您希望根据集合中元素的值对元素进行优先级排序。

模板代码：

Python

 import heapq class TwoHeaps: def __init__(self): self.min_heap = [] # Right heap to store larger half self.max_heap = [] # Left heap to store smaller half def add_num(self, num): if not self.max_heap or num <= -self.max_heap[0]: heapq.heappush(self.max_heap, -num) else: heapq.heappush(self.min_heap, num) # Balance the heaps if necessary if len(self.max_heap) > len(self.min_heap) + 1: heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap)) elif len(self.min_heap) > len(self.max_heap): heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap)) def find_median(self): if len(self.max_heap) == len(self.min_heap): return (-self.max_heap[0] + self.min_heap[0]) / 2.0 else: return -self.max_heap[0] # Usage: two_heaps = TwoHeaps() two_heaps.add_num(1) two_heaps.add_num(2) median = two_heaps.find_median() print("Median:", median)

JS

 class TwoHeaps { constructor() { this.minHeap = []; // Right heap to store larger half this.maxHeap = []; // Left heap to store smaller half } addNumber(num) { if (this.maxHeap.length === 0 || num <= -this.maxHeap[0]) { this.maxHeap.push(-num); } else { this.minHeap.push(num); } // Balance the heaps if necessary if (this.maxHeap.length > this.minHeap.length + 1) { this.minHeap.push(-this.maxHeap.shift()); } else if (this.minHeap.length > this.maxHeap.length) { this.maxHeap.push(-this.minHeap.shift()); } } findMedian() { if (this.maxHeap.length === this.minHeap.length) { return (-this.maxHeap[0] + this.minHeap[0]) / 2; } else { return -this.maxHeap[0]; } } } // Usage: const twoHeaps = new TwoHeaps(); twoHeaps.addNumber(1); twoHeaps.addNumber(2); const median = twoHeaps.findMedian(); console.log("Median:", median);

爪哇

import java.util.*; class TwoHeaps { private PriorityQueue<Integer> minHeap; // Right heap to store larger half private PriorityQueue<Integer> maxHeap; // Left heap to store smaller half public TwoHeaps() { minHeap = new PriorityQueue<>(); maxHeap = new PriorityQueue<>(Collections.reverseOrder()); } public void addNumber(int num) { if (maxHeap.isEmpty() || num <= -maxHeap.peek()) { maxHeap.offer(-num); } else { minHeap.offer(num); } // Balance the heaps if necessary if (maxHeap.size() > minHeap.size() + 1) { minHeap.offer(-maxHeap.poll()); } else if (minHeap.size() > maxHeap.size()) { maxHeap.offer(-minHeap.poll()); } } public double findMedian() { if (maxHeap.size() == minHeap.size()) { return (-maxHeap.peek() + minHeap.peek()) / 2.0; } else { return -maxHeap.peek(); } } } // Usage: TwoHeaps twoHeaps = new TwoHeaps(); twoHeaps.addNumber(1); twoHeaps.addNumber(2); double median = twoHeaps.findMedian(); System.out.println("Median: " + median);

7. 单调堆栈

单调 - （函数或数量的）以永远不会减少或永远不会增加的方式变化。

单调堆栈以非递增或非递减的顺序维护元素堆栈，通常用于查找数组中最近的较小/较大元素。它是优化某些问题的强大工具。

顺序是严格的，每当我们遇到一个比堆栈顶部的元素更小（或更大）的元素时，我们必须从单调堆栈中弹出，直到我们要添加的元素是最小（或最大）的元素。他们。

关键指标：

• 您需要以非递增或非递减的顺序维护元素。
• 问题涉及找到最近的较小或较大元素。
• 您希望在保持顺序的同时优化基于堆栈的操作。

模板代码：

Python

 def monotonic_stack(items): stack = [] for item in items: # Adjust the condition for comparisons to suit your needs while stack and stack[-1] <= item: stack.pop() # Do something with the popped item here stack.append(item)

JS

 function monotonicStack(items) { const stack = []; for (const item of items) { // Adjust the condition for comparisons to suit your needs while (stack.length > 0 && stack[stack.length - 1] <= item) { stack.pop(); // Do something with the popped item here } stack.push(item); } return stack; }

爪哇

import java.util.*; public static int[] monotonicStack(int[] items) { Deque<Integer> stack = new ArrayDeque<>(); for (int item : items) { // Adjust the condition for comparisons to suit your needs while (!stack.isEmpty() && stack.peekLast() <= item) { stack.pollLast(); // Do something with the popped item here } stack.offerLast(item); } int[] result = new int[stack.size()]; int i = stack.size() - 1; while (!stack.isEmpty()) { result[i--] = stack.pollLast(); } return result; }

8. 深度优先搜索

DFS ，即深度优先搜索，是一种遍历方法，在回溯之前沿着分支尽可能深入地探索；它广泛应用于涉及树和图的问题，特别是遍历和搜索操作。

为了在树上执行 DFS，您需要从根开始。然后按照以下步骤操作：

1. 通过访问其子节点来探索当前节点，通常是从左到右。
2. 递归地将 DFS 过程应用于每个子节点，深入到树中。
3. 访问完所有子节点后，回溯到父节点。
4. 对当前节点的每个未访问的子节点重复步骤 1-3 ，直到访问了树中的所有节点。

与图上的 DFS 的区别：树 DFS 和图 DFS 之间的主要区别在于循环的存在。在树中，根据定义不存在循环，因此树DFS确保每个节点仅被访问一次，并且当遍历整棵树时它自然终止。相比之下，图 DFS 必须包含额外的措施来处理图中的循环结构。为了避免无限期地在一个循环中重新访问节点，图 DFS 需要诸如标记已访问节点和适当处理回溯之类的机制。这种区别使得图 DFS 比树 DFS 更复杂，因为存在循环时可能会出现无限循环。

关键指标：

• 您正在处理树结构并且需要探索特定的遍历顺序。
• 问题涉及寻找路径、计算深度或执行前序/中序/后序遍历。
• 您想要检查两个节点之间是否存在路径。

模板代码：

Python

 def dfs(root, target): if root is None: # Base case: Check if the current node is None return None if root.val == target: # Base case: Check if the current node value matches the target return root left = dfs(root.left, target) # Recursively search the left subtree if left is not None: # If the target is found in the left subtree, return the result return left return dfs(root.right, target) # Recursively search the right subtree

JS

 function dfs(root, target) { if (root === null) { // Base case: Check if the current node is null return null; } if (root.val === target) { // Base case: Check if the current node value matches the target return root; } let left = dfs(root.left, target); // Recursively search the left subtree if (left !== null) { // If the target is found in the left subtree, return the result return left; } return dfs(root.right, target); // Recursively search the right subtree }

爪哇

public TreeNode dfs(TreeNode root, int target) { if (root == null) { // Base case: Check if the current node is null return null; } if (root.val == target) { // Base case: Check if the current node value matches the target return root; } TreeNode left = dfs(root.left, target); // Recursively search the left subtree if (left != null) { // If the target is found in the left subtree, return the result return left; } return dfs(root.right, target); // Recursively search the right subtree }

9. 广度优先搜索

BFS 是一种树和图的遍历技术，它在移动到下一个级别之前探索当前深度的所有节点。

为了在树上执行 BFS，您需要从根开始。然后按照以下步骤操作：

1. 初始化一个空队列数据结构来跟踪要访问的节点。

2. 将根节点放入队列中。

3. 进入循环直到队列为空：

   1. 将队列前面的节点出队。
   2. 处理出队的节点（例如，访问它或对其执行某些操作）。
   3. 将节点的所有子节点（如果有）放入队列中。

4. 重复步骤 3a-3c ，直到队列变空。

5. 当树中的所有节点都从左到右以级别方式访问完时，BFS 遍历就完成了。

本质上，树上的 BFS逐层探索节点，从根开始，移动到子节点，然后再进入下一层。这确保了在移动到下一个级别之前访问每个级别的节点，这使得它对于在未加权的树中查找最短路径或逐级探索树等任务特别有用。

与图上 BFS 的区别：与 DFS 类似，图 BFS 适应节点之间存在环路和多条路径。它采用标记访问节点和专门终止条件等机制来有效地导航图中复杂的关系网络。

关键指标：

• 您需要逐层遍历树。
• 问题涉及在未加权图中找到最短路径。
• 您希望以广度优先的方式探索树或图。

模板代码：

Python

 from collections import deque def bfs(root): # Create a queue and initialize it with the root node queue = deque([root]) # Perform breadth-first search until the queue is empty while len(queue) > 0: # Dequeue the front node from the queue node = queue.popleft() # Process the current node for child in node.children: if is_goal(child): # If the goal condition is satisfied, return the child node return FOUND(child) # Enqueue the child node to explore it in the next iterations queue.append(child) # Return NOT_FOUND if the goal is not reached return NOT_FOUND

JS

 function bfs(root) { const queue = []; // Create a queue and initialize it with the root node queue.push(root); while (queue.length > 0) { // Perform breadth-first search until the queue is empty const node = queue.shift(); // Dequeue the front node from the queue for (const child of node.children) { // Process the current node if (isGoal(child)) { // If the goal condition is satisfied, return the child node return `FOUND ${child}`; } queue.push(child); // Enqueue the child node to explore it in the next iterations } } return 'NOT_FOUND'; // Return NOT_FOUND if the goal is not reached }

爪哇

import java.util.LinkedList; import java.util.Queue; public String bfs(Node root) { Queue<Node> queue = new LinkedList<>(); // Create a queue and initialize it with the root node queue.offer(root); while (!queue.isEmpty()) { // Perform breadth-first search until the queue is empty Node node = queue.poll(); // Dequeue the front node from the queue for (Node child : node.getChildren()) { // Process the current node if (isGoal(child)) { // If the goal condition is satisfied, return the child node return "FOUND(child)"; } queue.offer(child); // Enqueue the child node to explore it in the next iterations } } return "NOT_FOUND"; // Return NOT_FOUND if the goal is not reached }

10.并集查找（不相交集并集）

并查数据结构，也称为不相交集并集 (DSU) ，用于有效管理和解决涉及不相交集或连通分量的问题。它提供了合并集合（并集）和确定元素所属集合（查找）的操作。并查法通常用于克鲁斯卡尔最小生成树和图中的循环检测等算法。

Union Find的实现如下：

1. 初始化：从元素集合开始，每个元素被视为一个单独的不相交集。为每个集合分配一个唯一的代表（通常是元素本身）。
2. 并集运算：要合并两个集合，请执行并集运算。选择一组代表（通常基于某些标准，例如排名或大小），并将其设为另一组代表的父代。这有效地连接了两组。
3. 查找操作：当需要确定某个元素所属的集合时，可以使用查找操作。从有问题的元素开始，向上遍历树以找到其集合的根节点（代表）。这里可以应用路径压缩技术，通过使路径上的元素直接指向根来优化未来的查找操作。
4. 循环检测：并查找通常用于检测图中的循环。在执行并集操作时，如果两个元素属于同一集合（即它们具有相同的代表），则表明节点之间添加边将在图中创建环。
5. 优化：可以应用各种优化技术来提高并查操作的效率，例如按等级并集和路径压缩。

模板代码：

Python

 class UnionFind: def __init__(self): self.id = {} def find(self, x): y = self.id.get(x, x) if y != x: self.id[x] = y = self.find(y) return y def union(self, x, y): self.id[self.find(x)] = self.find(y)

JS

 class UnionFind { constructor() { this.id = {}; } /** * Find the root parent of an element in the set. * Implements path compression for better efficiency. * @param x The element to find the root parent for. * @returns The root parent of the element. */ find(x) { let y = this.id[x] || x; if (y !== x) { this.id[x] = y = this.find(y); } return y; } /** * Union two elements into the same set. * @param x The first element. * @param y The second element. */ union(x, y) { this.id[this.find(x)] = this.find(y); } }

爪哇

import java.util.*; class UnionFind { private Map<String, String> id; public UnionFind() { id = new HashMap<>(); } /** * Find the root parent of an element in the set. * Implements path compression for better efficiency. * @param x The element to find the root parent for. * @return The root parent of the element. */ public String find(String x) { String y = id.getOrDefault(x, x); if (!y.equals(x)) { id.put(x, find(y)); } return y; } /** * Union two elements into the same set. * @param x The first element. * @param y The second element. */ public void union(String x, String y) { id.put(find(x), find(y)); } }

11.拓扑排序

有向无环图（DAG）是没有有向环的有向图。

拓扑排序是一种按线性顺序排列有向无环图 ( DAG ) 节点的算法，其中每个节点出现在其后继节点之前。它对于调度依赖关系、编译代码和分析各种应用程序中任务的优先级等任务至关重要。

以下是拓扑排序的逐步分解：

1. 初始化：从表示具有依赖关系的任务或节点的有向无环图 ( DAG ) 开始。初始化一个队列来保存已排序的节点。

2. 入度计算：计算图中每个节点的入度（传入边的数量）。入度为0的节点没有依赖关系，适合作为拓扑排序的起点。

3. 初始队列填充：将所有入度为0的节点放入队列中。可以先处理这些节点。

4. 拓扑排序循环：当队列不为空时，执行以下步骤：

   1. 从队列前面取出一个节点。
   2. 处理节点（例如，将其添加到排序列表中）。
   3. 对于每个节点的邻居（它指向的节点），将它们的入度减 1。
   4. 如果邻居的入度因递减而变为 0，则将其放入队列中。

5. 完成：一旦拓扑排序循环完成，队列将为空，排序列表将包含有效拓扑顺序的所有节点。

6. 环路检测：在拓扑排序过程中的任意时刻，如果队列中没有剩余入度为0的节点，则表明图中存在环路，无法进行拓扑排序。

拓扑排序的结果是节点的线性排序，尊重其依赖性，使其适合调度任务或分析各种应用程序中的执行顺序。

关键指标：

• 该问题涉及对具有依赖性的任务进行调度或排序。
• 您正在使用有向无环图 (DAG)。
• 任务需要按特定顺序执行，同时遵守其依赖性。

模板代码：

Python

 from collections import deque def find_indegree(graph): # Calculate the indegree of each node in the graph indegree = {node: 0 for node in graph} for node in graph: for neighbor in graph[node]: indegree[neighbor] += 1 return indegree def topological_sort(graph): result = [] queue = deque() indegree = find_indegree(graph) # Add nodes with 0 indegree to the queue for node in indegree: if indegree[node] == 0: queue.append(node) while queue: node = queue.popleft() result.append(node) # Update the indegree of neighboring nodes for neighbor in graph[node]: indegree[neighbor] -= 1 if indegree[neighbor] == 0: queue.append(neighbor) # If all nodes are visited, return the result if len(graph) == len(result): return result else: return None

JS

 /** * Finds the indegree of each node in the graph. * @param {object} graph - The input graph. * @returns {object} - The indegree of each node. */ function findIndegree(graph) { const indegree = {}; for (const node in graph) { indegree[node] = 0; } for (const node in graph) { for (const neighbor of graph[node]) { indegree[neighbor]++; } } return indegree; } /** * Performs topological sorting on the given graph. * @param {object} graph - The input graph. * @returns {array|null} - The sorted nodes in topological order or null if a cycle is detected. */ function topologicalSort(graph) { const result = []; const queue = []; const indegree = findIndegree(graph); // Add nodes with no incoming edges to the queue for (const node in indegree) { if (indegree[node] === 0) { queue.push(node); } } while (queue.length > 0) { const node = queue.shift(); result.push(node); // Decrement the indegree of neighbors and enqueue if indegree becomes zero for (const neighbor of graph[node]) { indegree[neighbor]--; if (indegree[neighbor] === 0) { queue.push(neighbor); } } } // Check if all nodes have been visited (no cycles) if (Object.keys(graph).length === result.length) { return result; } else { return null; } }

爪哇

import java.util.*; /** * Finds the indegree of each node in the graph. * @param graph - The input graph. * @return The indegree of each node. */ public Map<String, Integer> findIndegree(Map<String, List<String>> graph) { Map<String, Integer> indegree = new HashMap<>(); for (String node : graph.keySet()) { indegree.put(node, 0); } for (String node : graph.keySet()) { for (String neighbor : graph.get(node)) { indegree.put(neighbor, indegree.getOrDefault(neighbor, 0) + 1); } } return indegree; } /** * Performs topological sorting on the given graph. * @param graph - The input graph. * @return The sorted nodes in topological order or null if a cycle is detected. */ public List<String> topologicalSort(Map<String, List<String>> graph) { List<String> result = new ArrayList<>(); Queue<String> queue = new LinkedList<>(); Map<String, Integer> indegree = findIndegree(graph); // Add nodes with no incoming edges to the queue for (String node : indegree.keySet()) { if (indegree.get(node) == 0) { queue.offer(node); } } while (!queue.isEmpty()) { String node = queue.poll(); result.add(node); // Decrement the indegree of neighbors and enqueue if indegree becomes zero for (String neighbor : graph.get(node)) { indegree.put(neighbor, indegree.get(neighbor) - 1); if (indegree.get(neighbor) == 0) { queue.offer(neighbor); } } } // Check if all nodes have been visited (no cycles) if (graph.size() == result.size()) { return result; } else { return null; } }

12.尝试（前缀树）

Trie是一种树状数据结构，用于高效的字符串匹配和单词存储。它擅长解决需要存储和搜索具有公共前缀的字符串的问题。

下面是如何实现 Trie：

1. 初始化：从一个空的 Trie 开始，它通常由一个没有关联字符的根节点组成。

2. 插入：要将一个单词插入到 Trie 中，请从根节点开始，沿着树向下遍历，一次一个字符。对于单词中的每个字符：

   1. 检查当前节点下是否存在具有该字符的子节点。
   2. 如果存在，则移动到子节点。
   3. 如果没有，则用该角色创建一个新的子节点并移动到它。

3. 单词完成：要检查单词是否存在于 Trie 中，请以类似于插入的方式遍历它。确保单词中的每个字符对应于当前节点的一个子节点。如果遍历到达单词的末尾并且在最后一个字符节点处存在有效的结束标记（例如，布尔标志），则该单词存在于Trie中。

4. 前缀搜索： Trie 在前缀搜索方面表现出色。要查找具有给定前缀的所有单词，请从根节点开始遍历，并沿着前缀的字符向下移动树。到达前缀的最后一个字符后，您可以从该节点执行深度优先搜索 (DFS)，以查找共享相同前缀的所有单词。

5. 删除：要从 Trie 中删除单词，请执行该单词的搜索。当到达单词末尾时，删除结束标记（如果存在）。如果该节点没有其他子节点，则可以安全地删除代表单词的 Trie 的整个分支。

尝试可能会占用大量内存，尤其是对于大词汇量。为了优化内存，可以应用压缩（例如，在每个节点中使用映射而不是字符数组）和修剪（删除没有后代的节点）等技术。

尝试对于高效的字符串匹配、自动完成建议、拼写检查器以及对具有公共前缀的单词进行索引特别有用。它们提供了一种快速且节省空间的方法来存储和搜索具有树状结构中共享前缀的单词或字符串。

关键指标：

• 您正在处理字符串并且需要有效的字符串匹配。
• 问题涉及自动完成建议、拼写检查器或搜索具有常见前缀的单词。
• 您想要高效地存储和搜索单词。

模板代码：

Python

 class TrieNode: def __init__(self, value): self.value = value self.children = {} def insert(self, s, idx): # idx: index of the current character in s if idx != len(s): self.children.setdefault(s[idx], TrieNode(s[idx])) self.children.get(s[idx]).insert(s, idx + 1)

JS

 class TrieNode { constructor(value) { this.value = value; this.children = {}; } insert(s, idx) { // idx: index of the current character in s if (idx !== s.length) { if (!this.children[s[idx]]) { this.children[s[idx]] = new TrieNode(s[idx]); } this.children[s[idx]].insert(s, idx + 1); } } }

爪哇

import java.util.*; class TrieNode { char value; Map<Character, TrieNode> children; TrieNode(char value) { this.value = value; this.children = new HashMap<>(); } void insert(String s, int idx) { // idx: index of the current character in s if (idx != s.length()) { char c = s.charAt(idx); if (!children.containsKey(c)) { children.put(c, new TrieNode(c)); } children.get(c).insert(s, idx + 1); } } }

13.动态规划

动态规划是计算机科学和数学中使用的一种强大的问题解决技术，可以有效地解决各种复杂问题。当一个问题可以分解为更简单的子问题，并且这些子问题的解决方案可以组合起来解决整个问题时，这是特别有价值的。

以下是其主要特征及其工作原理：

最优子结构：

• 该特性是指可以从较小子问题的最优解构造出较大问题的最优解的性质。
• 换句话说，DP 问题呈现出递归结构，其中问题的最优解依赖于其子问题的最优解。
• 例如，在寻找图中两点之间的最短路径时，任意两个中间点之间的最短路径也应该是最优的。

重叠子问题：

• 当计算过程中多次求解相同的子问题时，就会出现子问题重叠，从而导致冗余工作。
• 动态编程旨在通过将子问题的解决方案存储在数据结构（通常是表或记忆数组）中以避免重新计算来解决这个问题。
• 子问题解的存储和重用显着降低了算法的时间复杂度。

动态规划的工作原理：

1. 识别子问题：使用 DP 解决问题的第一步是识别子问题。将问题分解为较小的、可管理的子问题，这些子问题解决后有助于解决主要问题。
2. 递归解决方案：开发一个递归解决方案，用较小子问题的解决方案来表达较大问题的解决方案。该递归公式捕获了最佳子结构。
3. 记忆或制表：要解决重叠的子问题，您可以在两种常用技术之间进行选择：
   • 记忆化：在计算子问题时将结果存储在数据结构（通常是数组或哈希表）中。当再次遇到子问题时，从存储中检索其解，而不是重新计算。这也称为自上而下的方法。
   • 制表：创建一个表（通常是二维数组）以自下而上的方式存储子问题的解决方案。从解决最小的子问题开始，逐步解决主要问题。
4. 最优解：当所有子问题都得到解决后，根据问题的递归结构，将其子问题的解组合起来，就可以得到主问题的解。

动态规划适用于各种问题，包括在图中查找最短路径、优化资源分配、计算组合、解决背包问题等等。它通过将复杂问题分解为更简单的部分并避免冗余计算来优化解决方案的能力使其成为算法设计和优化的基本技术。

重要概念：自下而上的方法、自上而下的方法、记忆法、制表法

关键指标：

• 该问题可以分解为较小的重叠子问题。
• 需要通过存储和重用子问题的解决方案来进行优化。
• 您想要解决涉及优化或计数的问题。

模板代码：

自上而下记忆的模板是实现动态编程的多种方法之一。

Python

 def top_down_memo(arr): def dp(state): # Base case(s): Define your own base case(s) for the problem if base_case: return 0 # Check if the state has already been memoized if state in memo: return memo[state] # Calculate the result using recurrence relation and memoize it result = recurrence_relation(state) memo[state] = result return result memo = {} # Memoization table to store calculated results return dp(initial_state)

JS

 function topDownMemo(arr) { function dp(state) { // Base case(s): Define your own base case(s) for the problem if (baseCase) { return 0; } // Check if the state has already been memoized if (memo.has(state)) { return memo.get(state); } // Calculate the result using recurrence relation and memoize it const result = recurrenceRelation(state); memo.set(state, result); return result; } const memo = new Map(); // Memoization map to store calculated results return dp(initialState); }

爪哇

import java.util.HashMap; import java.util.Map; public int topDownMemo(int[] arr) { Map<StateType, Integer> memo = new HashMap<>(); // Memoization map to store calculated results return dp(initialState, memo); } private int dp(StateType state, Map<StateType, Integer> memo) { // Base case(s): Define your own base case(s) for the problem if (baseCase) { return 0; } // Check if the state has already been memoized if (memo.containsKey(state)) { return memo.get(state); } // Calculate the result using recurrence relation and memoize it int result = recurrenceRelation(state); memo.put(state, result); return result; }

14.回溯

回溯是一种通用算法技术，通过尝试不同的可能性并在无法找到解决方案时撤消它们来逐步解决问题。当需要彻底搜索时使用它。

下面深入了解回溯的工作原理：

1. 问题空间探索：回溯通过一次一点地增量构建解决方案来探索问题空间。每一步，它都会做出决定并继续前进。
2. 递归结构：回溯通常涉及递归。它从最初的部分解决方案开始，并探索扩展它的所有可能方法。此过程递归地继续，直到找到完整的解决方案或明显不存在有效的解决方案。
3. 决策点：在每个步骤中，都有决策点，算法必须从可用选项中进行选择。这些选择导致探索过程出现分支。
4. 解决方案验证：做出选择后，算法检查当前的部分解决方案是否有效。如果有效，算法将继续下一步。如果没有，它就会回溯，撤销之前的选择并探索其他选择。
5. 终止条件：回溯继续进行，直到满足两个条件之一：
   • 找到有效的解决方案，在这种情况下算法将停止并返回解决方案。
   • 确定不存在有效的解决方案，此时算法回溯到先前的决策点并探索不同的选项。
6. 修剪：为了优化搜索，回溯通常包括修剪策略。修剪涉及避免探索肯定会导致无效解决方案的路径，从而显着减少搜索空间。

回溯的应用：

回溯用于各种问题领域，包括：

• 解决数独和 N 皇后等谜题。
• 生成排列和组合。
• 在图形和树中搜索路径。
• 约束满足问题（例如，旅行商问题）。
• 游戏算法（例如，国际象棋人工智能）。

关键指标：

• 该问题涉及逐步探索多种可能性。
• 存在需要尝试不同选项的决策点或约束。
• 您需要通过穷举搜索找到所有可能的解决方案或满足特定条件。

模板代码：

Python

 def backtrack(curr, OTHER_ARGUMENTS...): if BASE_CASE: # Modify the answer according to the problem's requirements return ans = 0 for ITERATE_OVER_INPUT: # Modify the current state according to the problem's requirements ans += backtrack(curr, OTHER_ARGUMENTS...) # Undo the modification of the current state (backtrack) return ans

JS

 function backtrack(curr, ...OTHER_ARGUMENTS) { if (BASE_CASE) { // Modify the answer according to the problem's requirements return; } let ans = 0; for (let i = 0; i < ITERATE_OVER_INPUT.length; i++) { const item = ITERATE_OVER_INPUT[i]; // Modify the current state according to the problem's requirements ans += backtrack(curr, ...OTHER_ARGUMENTS); // Undo the modification of the current state (backtrack) } return ans; }

爪哇

public int backtrack(StateType curr, OtherArgumentType... OTHER_ARGUMENTS) { if (BASE_CASE) { // Modify the answer according to the problem's requirements return; } int ans = 0; for (int i = 0; i < ITERATE_OVER_INPUT.length; i++) { ItemType item = ITERATE_OVER_INPUT[i]; // Modify the current state according to the problem's requirements ans += backtrack(curr, OTHER_ARGUMENTS); // Undo the modification of the current state (backtrack) } return ans; }

15.合并区间

合并间隔涉及将重叠或相邻的间隔组合成一个统一的集合，通常用于涉及时间间隔或调度的问题。它简化了基于间隔的操作。

下面详细介绍了合并间隔的工作原理：

1. 间隔表示：间隔通常表示为起点和终点对（例如， [start, end] ）。
2. 排序：为了有效地合并间隔，首先根据它们的起点对它们进行排序。这确保了重叠或相邻间隔在排序列表中是相邻的。
3. 合并过程：初始化一个空列表来保存合并的间隔。然后，逐一迭代排序后的区间：
   • 如果当前间隔与前一个间隔不重叠，则将其添加到合并间隔列表中。
   • 如果存在重叠，则更新先前合并间隔的端点以包含当前间隔和先前间隔，从而有效地合并它们。
4. 完成：处理完所有区间后，合并区间列表将包含非重叠区间和合并区间。

合并区间的应用：

合并间隔常用于：

• 日程安排和时间管理应用程序。
• 日历系统中的重叠事件检测。
• 基于区间的数据分析，例如数据库查询。
• 解决与资源分配和会议安排相关的问题。

通过合并重叠间隔，该技术简化了基于间隔的操作并提高了各种应用程序的效率。

关键指标：

• 您正在处理间隔或基于时间的数据。
• 问题涉及合并重叠或相邻的间隔。
• 您想要简化基于间隔的操作或优化事件调度。

模板代码：

Python

 def merge_intervals(intervals): # 1. Sort the intervals based on their start values. intervals.sort(key=lambda x: x[0]) # 2. Initialize an empty list to store merged intervals. merged_intervals = [] # 3. Iterate through the sorted intervals. for interval in intervals: # 4. If the merged_intervals list is empty or the current interval does not overlap with the last merged interval: if not merged_intervals or interval[0] > merged_intervals[-1][1]: merged_intervals.append(interval) else: # 5. If the current interval overlaps with the last merged interval, merge them. merged_intervals[-1][1] = max(merged_intervals[-1][1], interval[1]) # 6. Return the merged_intervals list. return merged_intervals

JS

 function mergeIntervals(intervals) { // 1. Sort the intervals based on their start values. intervals.sort((a, b) => a[0] - b[0]); // 2. Initialize an empty array to store merged intervals. const mergedIntervals = []; // 3. Iterate through the sorted intervals. for (const interval of intervals) { // 4. If the mergedIntervals array is empty or the current interval does not overlap with the last merged interval: if (mergedIntervals.length === 0 || interval[0] > mergedIntervals[mergedIntervals.length - 1][1]) { mergedIntervals.push(interval); } else { // 5. If the current interval overlaps with the last merged interval, merge them. mergedIntervals[mergedIntervals.length - 1][1] = Math.max(mergedIntervals[mergedIntervals.length - 1][1], interval[1]); } } // 6. Return the mergedIntervals array. return mergedIntervals; }

爪哇

public class MergeIntervals { public int[][] merge(int[][] intervals) { // 1. Sort the intervals based on their start values. Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // 2. Create a list to store merged intervals. List<int[]> mergedIntervals = new ArrayList<>(); // 3. Iterate through the sorted intervals. for (int[] interval : intervals) { // 4. If the mergedIntervals list is empty or the current interval does not overlap with the last merged interval: if (mergedIntervals.isEmpty() || interval[0] > mergedIntervals.get(mergedIntervals.size() - 1)[1]) { mergedIntervals.add(interval); } else { // 5. If the current interval overlaps with the last merged interval, merge them. mergedIntervals.get(mergedIntervals.size() - 1)[1] = Math.max(mergedIntervals.get(mergedIntervals.size() - 1)[1], interval[1]); } } // 6. Convert the list to an array and return it. return mergedIntervals.toArray(new int[mergedIntervals.size()][]); } }

想了解更多吗？

如果您想了解有关这些模式的更多信息以及如何在下一次编码面试中更有效地实施它们，请立即查看techinterviews.io ！我们提供全面的课程，帮助您为下一次编码面试做好准备，涵盖数据结构、算法、行为面试，甚至薪资谈判等主题。我们甚至有一个内置的编码工作区供您练习。

立即使用我们的促销代码TECH30为您的编程面试准备提供 30 美元折扣！