【数据结构和算法】爆肝三万字你必须知道的20个解决问题的技巧

在本文中，我将深入探讨 20 种解决问题的技巧，您必须知道这些技巧才能在学习、面试、工作中脱颖而出。

我将这些技术归为一组：

基于指针

基于递归

排序和搜索

扩展基本数据结构

杂项

我将解释它们中的每一个，展示如何将它们应用于编码问题，并为您留下一些练习，以便您可以自己练习。

基于指针的技术

1. 两个指针

这种技术对于排序数组和我们想要对其元素进行分组的数组非常有用。

这个想法是使用两个（或多个指针）根据某些条件将数组拆分为不同的区域或组：

小于、等于和大于某个值的元素

总和过小或过大的元素

等等

下面的例子将帮助你理解这个原理。

二和

给定一个已经按升序排序的整数数组，找到两个数字，使它们相加为特定的目标数字。函数 twoSum 应该返回两个数字的索引，使它们相加为目标，其中 index1 必须小于 index2。

笔记：

您返回的答案（index1 和 index2）不是从零开始的。

您可以假设每个输入都只有一个解决方案，并且您不能两次使用相同的元素。

例子：

输入：数字 = [2,7,11,15]，目标 = 9

输出：[1,2]

解释：2 和 7 的和是 9。因此 index1 = 1，index2 = 2。

解决方案

由于数组a已排序，我们知道：

最大的总和等于最后 2 个元素的总和

最小的总和等于前 2 个元素的总和

对于[0, a.size() - 1) => a[i + 1] >= a[i] 中的任何索引i

有了这个，我们可以设计以下算法：

我们保留了 2 个指针：l，从数组的第一个元素开始，而r从数组的最后一个元素开始。

如果 a[l] + a[r] 的总和小于我们的目标，我们将 l 加一（将加法中的最小操作数更改为另一个等于或大于l+1的操作数）；如果它大于目标，我们将 r 减一（将我 们的最大操作数更改为另一个等于或小于r-1 的操作数）。

我们这样做直到 a[l] + a[r] 等于我们的目标，或者 l 和 r

指向同一个元素（因为我们不能两次使用同一个元素）或者已经交叉，表明没有解决方案。

这是一个简单的 C++ 实现：

vector twoSum(const vector& a, int target) { int l = 0, r = a.size() - 1; vector sol; while(l < r) { const int sum = a[l] + a[r]; if(target == sum){ sol.push_back(l + 1); sol.push_back(r + 1); break; } else if (target > sum) { ++l; } else { --r; } } return sol; }

时间复杂度是 O(N)，因为我们可能需要遍历数组的 N 个元素才能找到解。

空间复杂度是 O(1)，因为我们只需要两个指针，而不管数组包含多少个元素。

还有其他方法可以解决这个问题（例如，使用哈希表），但我使用它只是作为两个指针技术的说明。

挑战

以下是此练习的两种变体：三和和四和。可以通过将它们简化为相同的问题来类似地解决它们。

这是一种非常常见的技术：将您不知道其解决方案的问题转化为您可以解决的问题。

从数组中删除重复项

给定一个排序数组 nums，就地删除重复项，使每个元素只出现一次并返回新长度。

不要为另一个数组分配额外的空间，您必须通过使用 O(1) 额外内存就地修改输入数组来实现。

示例 1：

给定 nums = [1,1,2]，

输出 = 2

示例 2：

给定 nums = [0,0,1,1,1,2,2,3,3,4],

输出 = 5

在返回的长度之外设置什么值并不重要。

解决方案

数组已排序，我们希望将重复项移动到数组的末尾，这听起来很像基于某些条件分组。你将如何使用两个指针解决这个问题？

您将需要一个指针来遍历数组i。

还有第二个指针n，用于定义不包含重复项的区域：[0,n]。

逻辑如下。如果索引i（i = 0除外）和i-1处元素的值为：

同样，我们什么都不做——这个副本将被a 中的下一个唯一元素覆盖。

不同：我们将a[i]添加到不包含重复项的数组部分 - 由n分隔，并将 n 递增 1。

int removeDuplicates(vector& nums) { if(nums.empty()) return 0; int n = 0; for(int i = 0; i < nums.size(); ++i){ if(i == 0 || nums[i] != nums[i - 1]){ nums[n++] = nums[i]; } } return n; }

此问题具有线性时间复杂度和恒定空间复杂度（使用此技术解决的问题通常是这种情况）。

排序颜色

给定一个包含 n 个颜色为红色、白色或蓝色的对象的数组，将它们就地排序，以便相同颜色的对象相邻，颜色的顺序为红色、白色和蓝色。在这里，我们将使用整数 0、1 和 2 分别表示红色、白色和蓝色。

注意：您不应该对这个问题使用库的排序功能。

例子：

输入：[2,0,2,1,1,0]

输出：[0,0,1,1,2,2]

解决方案

这次的组别是：

小于 1

等于 1

大于 1

我们可以用 3 个指针实现什么。

这个实现有点棘手，所以一定要彻底测试它。

void sortColors(vector& nums) { int smaller = 0, eq = 0, larger = nums.size() - 1; while(eq <= larger){ if(nums[eq] == 0){ swap(nums[smaller], nums[eq]); ++smaller; ++eq; } else if (nums[eq] == 2) { swap(nums[larger], nums[eq]); --larger; } else { eq++; } } }

由于需要遍历数组进行排序，时间复杂度为O(N)。空间复杂度为 O(1)。

出于好奇，这是Dijkstra 描述的荷兰国旗问题的一个实例。

从链表的末尾删除第 n 个节点

给定一个链表和一个数字 n，编写一个函数，返回链表末尾第 n 个节点的值。

解决方案

这是双指针技术最常见的变体之一：引入偏移量，使一个指针达到特定条件，另一个指针位于您感兴趣的位置。

在这种情况下，如果我们将一个指针f移动n 次，然后同时开始将两个指针向前移动一个节点，当f到达列表末尾时，另一个指针s将指向之前的节点我们要删除的节点。

确保您定义了 n = 1 的含义（最后一个元素或最后一个元素之前的元素？），并避免逐一错误。

时间和空间复杂度与前面的问题相同。

2. 指针以不同的速度移动

现在，您将有两个以不同速度移动的指针：在每次迭代中，一个指针将推进一个节点，另一个指针将推进两个节点。我们可以使用这种变体来：

获取链表的中间元素

检测链表中的循环

等等

像往常一样，我会给出一些例子，让它变得容易理解。

找到未知大小的链表的中间节点

给定一个带有头节点 head 的非空单向链表，返回列表的中间节点。如果有两个中间节点，则返回第二个中间节点。

示例 1：

输入：[1,2,3,4,5]

输出：此列表中的节点 3

解决方案

分两次解决这个问题很容易：第一次我们计算列表的大小L，第二次我们只前进L/2 个节点来找到列表中间的元素。这种方法在时间上具有线性复杂性，在空间上具有恒定性。

我们如何使用 2 个指针在一次通过中找到中间元素？

如果其中一个指针f 的移动速度是另一个s 的两倍，那么当f到达末尾时，s将位于列表的中间。

这是我在 C++ 中的解决方案。确保在测试代码时考虑边缘情况（空列表、奇数和偶数大小的列表等）。

ListNode* middleNode(ListNode* head) { ListNode* slow = head; ListNode* fast = head; while (fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; } return slow; }

检测链表中的循环

给定一个链表，判断它是否有环。为了表示给定链表中的循环，我们使用一个整数 pos 表示链表中尾部连接的位置（0-indexed）。如果 pos 为 -1，则链表中没有环。

示例 1：

输入：head = [3,2,0,-4], pos = 1

输出：真

解释：链表中有一个循环，其尾部连接到第二个节点。

解决方案

最简单的解决方案是将所有节点添加到哈希集。当我们遍历链表时，如果到达一个已经加入集合中的节点，就会有一个循环。如果我们到达列表的末尾，则没有循环。

这具有 O(L) 的时间复杂度，L是列表的长度，空间复杂度为 O(L)，因为在最坏的情况下 - 没有循环 - 我们需要将列表的所有元素添加到哈希放。

时间复杂度无法提高。然而，空间复杂度可以降低到 O(1)。想一想如何通过两个以不同速度移动的指针来实现这一点。

让我们称这些指针为fast 和slow。对于每个节点的慢访问，快将向前移动两个节点。为什么？

如果 fast 到达列表的末尾，则列表不包含任何循环。

如果有一个循环，因为快的移动速度是慢的两倍，所以快节点抓住慢节点只是时间问题（迭代，更准确地说），指向同一个节点，这表明存在一个周期。

现在，让我们将这个解决方案翻译成代码：

bool hasCycle(ListNode *head) { ListNode* slow = head, *fast = head; while(fast){ slow = slow->next; fast = fast->next; if(!fast) break; fast = fast->next; if(slow == fast) return true; } return false; }

找到重复的号码

给定一个数组 nums，其中包含 n + 1 个整数，其中每个整数都在 1 和 n 之间（含），证明必须至少存在一个重复数字。假设只有一个重复的数字，找到重复的一个。

示例 1：

输入：[1,3,4,2,2]

输出：2

解决方案

这是与前面的问题相同的问题/解决方案，用于数组而不是链表。

int findDuplicate(const vector& nums) { int slow = nums[0], fast = slow; do { slow = nums[slow]; fast = nums[nums[fast]]; } while(slow != fast); slow = nums[0]; while(slow != fast){ slow = nums[slow]; fast = nums[fast]; } return slow; }

挑战

以下是使用此技术可以解决的更多问题：

检测两个链表是否有共同元素

快乐数字

3. 滑动窗口

滑动窗口技术简化了寻找满足特定条件的最佳连续数据块的任务：

最长的子阵列…

包含…的最短子串

等等

您可以将其视为双指针技术的另一种变体，其中根据特定条件分别更新指针。以下是此类问题的基本方法，以伪代码表示：

Create two pointers, l, and r Create variable to keep track of the result (res) Iterate until condition A is satisfied: Based on condition B: update l, r or both Update res Return res

无重复字符的最长子串

给定一个字符串，找出没有重复字符的最长子字符串的长度。

示例 1：

输入：“abcabcbb”

输出：3

解释：答案是“abc”，长度为3

解决方案

在不重复字符的情况下查找最长子字符串的长度听起来很像找到最佳的满足特定条件的连续数据块。

根据我上面描述的配方，您将需要：

两个指针l和r，用于定义我们的子字符串s。

一个变量sol，用于存储我们目前看到的最长子字符串的长度。

一种跟踪形成s的字符的方法：一个集合，seen，将是完美的。

在遍历字符串时：

如果当前字符在seen* 中，您必须增加 *l以开始从s的开头删除元素。

否则，将角色添加到seen，向前移动r并更新sol。

int lengthOfLongestSubstring(const string& s) { int sol = 0; int l = 0, r = 0; unordered_set seen; while(r < s.size()) { const auto find = seen.find(s[r]); if(find == seen.end()) { sol = max (sol, r - l + 1); seen.insert(s[r]); ++r; } else { seen.erase(s[l++]); } } return sol; }

挑战

如需更多练习，您可以尝试以下问题：

字符串的排列

最大连续数

可能有更简单的解决方案，但专注于使用这种技术来更好地掌握它。

基于递归的技术

4. 动态规划

后面我会写一篇关于这个主题的文章，填补这一部分。

5. 回溯

回溯背后的想法是以聪明的方式探索问题的所有潜在解决方案。它逐步构建候选解决方案，一旦确定候选解决方案不可行，它就会回溯到先前的状态并尝试下一个候选解决方案。

回溯问题为您提供了一系列选择：

你应该把这件作品放在这个位置吗？

您应该将此号码添加到集合中吗？

你接下来应该在这个位置尝试这个数字吗？

等等

在您选择了其中一个选项后，它会为您提供一个新的选择列表，直到您达到没有更多选择的状态：要么找到了解决方案，要么没有解决方案。

从视觉上看，您每次选择都从树的根部移动，直到到达一片叶子。回溯算法的基本高级配方（伪代码）如下：

boolean backtracking(Node n){ if(isLeaf(n) { if(isSolution(candidate)){ sol.add(candidate); return true; } else { return false; } } //Explore all children for(child in n) { if(backtracking(child)) return true; } return false; }

这当然可以根据问题而改变：

如果您需要所有解决方案，辅助函数将不返回任何内容 (void) 以避免在我们找到第一个解决方案时停止。

要回溯，您可能必须先将程序恢复到以前的状态，然后才能继续

选择孩子后，需要检测候选解决方案是否可行：可行的定义取决于问题

等等

但核心思想是相同的：==以系统的方式检查所有路径，并在当前路径不再可行时立即回溯。==

N皇后

n-皇后拼图是将 n 个皇后放在 n×n 棋盘上的问题，使得没有两个皇后相互攻击

给定一个整数 n，返回 n-皇后拼图的所有不同解。

每个解决方案都包含 n-queens 布局的独特电路板配置，其中“Q”和“.” 两者分别表示皇后和空位。

例子：

输入：4

输出： [ [".Q…", // 解决方案 1 “…Q”, “Q…”, “…Q.”],

[" …Q .", // 解决方案 2

“Q…”,

“…Q”,

“.Q…”]

]

说明：如上所示，对于 4 皇后拼图，存在两种不同的解决方案。

解决方案

这是一个经典的回溯问题

我们需要这里的所有解决方案，这就是我在本节介绍中解释的递归函数不返回任何内容的原因。

现在不要太担心isViableSolution函数。试着看看我给你的食谱（略有修改）在行动。

class Solution { public: vector> solveNQueens(int n) { vector> solutions; /** This is usually solved with a vector of integers, where each integer represents the position of the queen in that column. This particular problem expects strings. Each string represents a column */ vector board(n, string(n, '.')); solveBoard(solutions, board, 0, n); return solutions; } void solveBoard(vector>& solutions, vector& board, int col, int n){ if(col == n){ solutions.push_back(board); return; } for(int row = 0; row < n; row++){ if(isViableSolution(board, row, col)){ board[row][col] = 'Q'; solveBoard(solutions, board, col + 1, n); //Backtracking - we bring our board to the previous state board[row][col] = '.'; } } } bool isViableSolution(vector& board, int row, int col){ int n = board.size(); for(int x = 1; x <= col; x++){ if(board[row][col-x] == 'Q') return false; } for(int x = 1; row - x >= 0 && col >= x; x++){ if(board[row-x][col-x] == 'Q') return false; } for(int x = 1; row + x < n && col >= x; x++){ if(board[row+x][col-x] == 'Q') return false; } return true; } };

字母组合

给定一个包含 2-9 数字的字符串，返回该数字可以表示的所有可能的字母组合（检查图表链接）。请注意，1 不映射到任何字母。

例子：

输入：“23”

输出：[“ad”、“ae”、“af”、“bd”、“be”、“bf”、“cd”、“ce”、“cf”]。

解决方案

对于输入中的每个数字，您都有几个字母可供选择。如果您可以绘制一棵树（这就是我所做的），其中分支是从您所做的不同选择中产生的，那么您很有可能可以应用回溯。

注意：在开始解决任何问题之前，请尝试不同的方法：动态规划、贪心算法、分而治之、算法和数据结构的组合等。编码是最后一步。

我的解决方案，在 C++ 中：

vector letterCombinations(const string &digits) { if(digits.empty()) return {}; const vector letters {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; vector sol; string candidate (digits.size(), ' '); h(sol, 0, candidate, letters, digits); return sol; } void h(vector &sol, int idx, string &candidate, const vector &letters, const string &digits){ if(idx == digits.size()){ sol.push_back(candidate); return; } for(const char &c : letters[digits[idx] - '0']) { candidate[idx] = c; h(sol, idx + 1, candidate, letters, digits); } }

由于我已经知道解决方案的大小，因此我candidate使用该大小初始化 my并仅修改了位置处的字符idx。如果大小未知，则可以这样做：

string candidate; //instead of string candidate (digits.size(), ' '); … for(const char &c : letters[digits[idx] - '0']) { candidate.push_back(c); h(sol, idx + 1, candidate, letters, digits); candidate.pop_back(); }

数独解算器

编写一个程序，通过填充空单元格来解决数独谜题。打开链接以获得更长的描述，包括拼图的图像。

解决方案

在面试中，除非你有足够的时间，否则你不需要实现isViableSolution，只是为了勾勒它。我认识一位朋友，他在现场遇到了这个问题。

尽管代码很长，但主要是因为isViableSolution。否则，它与其他回溯问题没有太大区别。

void solveSudoku(vector>& board){ helper(board); } bool helper(vector>& board, int row = 0, int col = 0) { if(col == size){ col = 0; ++row; if(row == size){ return true; } } if(board[row][col] != '.'){ return helper(board, row, col + 1); } for(char i = '1'; i <= '9'; ++i){ if(isViableSolution(board, row, col, i)){ board[row][col] = i; if (helper(board, row, col + 1)) return true; } } board[row][col] = '.'; return false; } bool isViableSolution(const vector>& board, int row, int col, char c){ for(const auto& n : board[row]){ if(n == c) return false; } for(int r = 0; r < size; ++r){ if(board[r][col] == c) return false; } const int br = row / nsize; const int bc = col / nsize; for(int i = 0; i < nsize ; ++i){ for(int j = 0; j < nsize; ++j){ if(c == board[3 * br + i][3 * bc + j]) return false; } } return true; }

挑战

N皇后II

生成括号

回文分区

字母瓷砖的可能性

6.子集

我为以下内容创建了一个通用的单独部分：

子集

组合

排列

等等

因为在概念上它们是相似的：获取容器的元素（数组、字符串等）并根据某些规则从中创建子集。

您会注意到其中大部分是回溯问题或非常相似。

子集

给定一组不同的整数 nums，返回所有可能的子集（幂集）。

注意：解决方案集不得包含重复的子集。

例子：

输入：nums = [1,2,3]

输出： [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

解决方案

对于每个索引i，您需要生成两个解决方案：

一个包含 a[i]

一个不包含 a[i]

直到到达数组的末尾。

这是我们讨论过的内容的简单实现。

vector> subsets(const vector& nums) { vector> sol; vector partial; h(sol, partial, nums); return sol; } void h(vector>& sol, vector& partial, const vector& nums, int idx = 0){ sol.push_back(partial); if(idx == nums.size()){ return; } for(int i = idx; i < nums.size(); ++i){ partial.push_back(nums[i]); h(sol, partial, nums, i + 1); partial.pop_back(); } }

子集 - 包含重复项

这是上一个问题的变体。尝试使用我的代码，看看是否可以更改它以满足新要求。您必须更改少于 5 行。

解决方案

vector> subsetsWithDup(vector nums) { vector> sol; vector partial; sort(nums.begin(), nums.end()); h(sol, partial, nums); return sol; } void h(vector>& sol, vector& partial, const vector& nums, int idx = 0){ sol.push_back(partial); if(idx == nums.size()){ return; } for(int i = idx; i < nums.size(); ++i){ if(i != idx && nums[i] == nums[i - 1]) continue; partial.push_back(nums[i]); h(sol, partial, nums, i + 1); partial.pop_back(); } }

排列

给定一组不同的整数，返回所有可能的排列。

例子：

输入：[1,2,3]

输出：[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

解决方案

与之前的问题非常相似，但这次我们需要考虑候选数组中的所有元素。我们移动它们的方式是交换不同位置的元素。

vector> permute(const vector& nums) { vector> sol; vector p (nums); h(nums, sol, p); return sol; } void h(const vector &nums, vector> &sol, vector &p, int idx = 0){ if(idx == nums.size()){ sol.push_back(p); return; } for(int i = idx; i < nums.size(); ++i){ swap(p[idx], p[i]); h(nums, sol, p, idx + 1); swap(p[idx], p[i]); } }

重复排列

给定一组可能包含重复项的数字，返回所有可能的唯一排列。

例子：

输入：[1,1,2]

输出： [[1,1,2], [1,2,1], [2,1,1] ]

解决方案

我们可以在这里应用与以前相同的技巧进行组合。如果你想不出这个“技巧”，你总是可以使用一个集合来存储解决方案，然后从这个集合中创建和返回一个数组。

void helper(vector>& res, int pos, vector& nums) { if(pos == nums.size()) { res.push_back(nums); return; } for(int i = pos; i < nums.size(); ++i) { if(i != pos && nums[i] == nums[pos]) continue; swap(nums[i], nums[pos]); helper(res, pos + 1, nums); } rotate(nums.begin() + pos, nums.begin() + pos + 1, nums.end()); } vector> permuteUnique(vector& nums) { if(nums.empty()) return {}; sort(nums.begin(), nums.end()); vector> sol; helper(sol, 0, nums); return sol; }

如您所见，无需学习文献中的每一种数据结构和算法来解决大量问题。有价值且可以训练的是系统思考问题的能力和将您的想法转化为代码的技能。

挑战

额外练习：

组合和

组合和II

组合和III

排序和搜索

7. 排序

排序并不是一种解决问题的技术，但正如您在前几节中看到的那样，我们已经能够通过对输入进行排序或假设它已排序然后应用其他技术之一来解决许多问题。

当你面临一个新问题时，问问自己：

我可以对输入进行排序吗？ 例如，有时您必须返回索引，因此排序不是一种选择

如果元素被排序，这个问题会如何改变？

排序如何影响整体复杂性？最好的排序算法的复杂度为 O(n log n) - 排序整数可以在 O(n) 中完成

例如，我们的第一个问题（二和）可以用双指针技术在线性时间内解决，因为输入是排序的。但是，如果我们必须排序，则复杂度变为 O(n log n)。

这里有几个问题可以在对输入进行排序后轻松解决。

其他解决方案以时间换取空间，因此在开始编写任何代码之前值得考虑它们。

有效字谜

给定两个字符串 s 和 t，编写一个函数来确定 t 是否是 s 的变位词。

示例 1：

输入：s = “anagram”, t = “nagaram”

输出：真

示例 2：

输入：s = “rat”, t = “car”

输出：假

解决方案

根据定义，如果两个字符串以不同的顺序包含相同的字符，则它们是变位词。因此，我们可以简单地对两个字符串进行排序并进行比较。总时间复杂度为 O(n log n)。

bool isAnagram(string s, string t) { if(s.size() != t.size()) return false; sort(s.begin(), s.end()); sort(t.begin(), t.end()); return s == t; }

两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。

示例 1：

输入：nums1 = [1,2,2,1]，nums2 = [2,2]

输出：[2,2]

解决方案

您可以通过对两个数组进行排序并使用基于双指针的方法来解决此问题。在阅读我的解决方案之前尝试一下。

假设我们有以下数组：

A = [1,2,4,5]

B = [2,3,5,7,9,11]

还有两个指针，l代表 A，r代表 B，从每个数组的索引 0 开始。

A[l] = 1

B[r] = 2

我们需要增加l以查看 A 是否有 2: B 不能在r的右侧包含 1 ，因为它已排序。

简而言之，我们比较两个元素：

如果它们相同，我们将它们包含到表示两个数组交集的数组中，并推进两个指针

如果它们不同，我们将指针移动到两个元素中最小的一个。

vector intersect(vector& nums1, vector& nums2) { sort(nums1.begin(), nums1.end()); sort(nums2.begin(), nums2.end()); vector sol; int i = 0, j = 0; while( i < nums1.size() && j < nums2.size()) { if(nums1[i] == nums2[j]) { sol.push_back(nums1[i]); ++i; ++j; } else if(nums1[i] > nums2[j]) { ++j; } else { ++i; } } return sol; }

这种方法的时间复杂度是 O(n log n) - 即使两个指针部分是线性的 - 而空间复杂度是 O(1) - 当然，不包括存储交集所需的空间，在这种情况下我们可以说它是 O(min(length(A), length(B))。

挑战

离原点最近的 K 个点。在另一部分中，我将提出一个不同的解决方案，速度略快。

最大数

8. 间隔

我见过的大多数与间隔相关的问题都归结为：

将区间建模为两个元素的数组、一对/元组或自定义类（这是最干净的选项）

排序输入

遍历已排序的数组并根据间隔的开始/结束决定要执行的操作

您可以将其视为在对输入进行排序后可以简化的另一种类型的问题，这就是我将其包含在本节中的原因。

根据我刚刚描述的内容，我将在这里留下我对两个练习的解决方案。在阅读我的解决方案之前尝试它们。

合并间隔

给定一组区间，合并所有重叠的区间。

示例 1：

输入：区间 = [[1,3],[2,6],[8,10],[15,18]]

输出：[[1,6],[8,10],[15,18]]

解释：由于区间 [1,3] 和 [2,6] 重叠，将它们合并为 [1,6]。

解决方案

vector> merge(vector>& intervals) { sort(intervals.begin(), intervals.end(), [](const auto& i1, const auto& i2){ return i1[0] < i2[0]; }); int i = 0; vector> sol; vector curr(2); while(i < intervals.size()){ curr = intervals[i++]; while(i < intervals.size() && intervals[i][0] <= curr[1]){ curr[1] = max(curr[1], intervals[i][1]); ++i; } sol.push_back(curr); } return sol; }

区间列表交点

给定两个闭区间列表，每个区间列表都是成对不相交的，并且按顺序排列。返回这两个区间列表的交集。

解决方案

vector> intervalIntersection(const vector>& A, vector>& B) { vector> sol; int i = 0, j = 0; while(i < A.size() && j < B.size()){ const int lo = max(A[i][0], B[j][0]); const int hi = min(A[i][1], B[j][1]); if(lo <= hi){ sol.push_back({lo, hi}); } if(A[i][1] < B[j][1]) ++i; else ++j; } return sol; }

9. 二分查找的变化

二分搜索是一种搜索算法，可应用于时间复杂度为 O(log n) 和空间复杂度为 O(1) 的排序数据结构（如数组或二叉搜索树）。

您可能不知道的是其实现中最常见的错误。假设我们在范围从 [l,r] 的元素中执行二分搜索，中间的元素通常计算为：

const int m = (l + r) / 2;

你能发现这里的问题吗？

该行可能会溢出。计算这个中间元素的安全方法是：

const int m = l + (r - l) / 2;

这是使用 C++ 模板的二进制搜索的基本实现。如果您了解它的工作原理以及如何正确实现它，您就可以解决许多问题，这些问题只是对需求稍作调整，或者是变相的二分搜索问题。

template int binary_search(const vector& v, int k) { int l = 0, r = v.size() - 1; while(l<=r) { const int m = l + (r - l) / 2; if(k == v[m]) { return m; } else if (k > v[m]) { l = m + 1; } else { r = m - 1; } } return -1; }

整数平方根

计算并返回 x 的平方根，其中 x 保证为非负整数。

由于返回类型是整数，所以小数位被截断，只返回结果的整数部分。

示例 1：

输入：4

输出：2

解决方案

我们需要在 [0, x] 范围内找到一个数字，并对其进行排序。这听起来很像一个二分搜索问题。

知道这一点并不重要，但我们可以稍微优化一下：

如果x为 0 或 1，则其平方根为x。这让我们从 2 开始测试数字。

范围的上限可以减少到 x/2，因为 (x/2)^2 = x^2/4 >= x => x >= 4，这对于范围 [2, …]

有了这个，我们可以在 [2, x/2] 中搜索并加快速度。

int mySqrt(int x) { if(x == 0 || x == 1) return x; int sol = 1; int l = 2, r = x / 2; while(l <= r){ const long m = l + (r - l) / 2; if(m * m == x) return m; else if(m * m > x){ r = m - 1; } else { sol = m; l = m + 1; } } return sol; }

挑战

搜索插入位置

带重量的随机选择

旋转排序数组中的最小值

旋转排序数组中的最小值 2

10.广度优先搜索

这是您在探索树和图形时需要了解的技术之一。由于许多问题都可以建模为图形，因此您必须了解这种技术。为了实现它，我们只需要使用一个队列q并将我们从q处理的节点的子节点添加到这个相同的队列中。

在迭代中的任何给定点，BFS 访问距离原点相同距离的所有节点。在其中一些示例之后，这将变得更加清楚。

字梯

给定两个单词（beginWord 和 endWord）和字典的单词列表，找到从 beginWord 到 endWord 的最短转换序列的长度，使得：

一次只能更改一个字母。

每个转换后的词都必须存在于词表中。

笔记：

如果没有这样的转换序列，则返回 0。

所有单词的长度相同。

所有单词仅包含小写字母字符。

您可以假设单词列表中没有重复项。

您可以假设 beginWord 和 endWord 非空且不相同。

示例 1：

输入：

beginWord = “hit”,

endWord = “cog”,

wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]

输出：5

解释：由于最短的转换是“hit”->“hot”->“dot”->“dog”->“cog”，返回其长度5。

解决方案

亚马逊的现场面试中问过这个问题。这个想法是使用图来模拟这个问题：

节点代表单词

边连接仅相差一个字母的单词

有了这个设置，这个问题就相当于在图中寻找两个节点之间的路径，BFS 可以解决这个问题。由于所有边都具有相同的权重 (1)，因此我们不需要 Dijkstra 或任何其他更高级的算法。

int ladderLength(const string &beginWord, const string &endWord, const vector& wordList) { if(beginWord == endWord) return 1; unordered_set dict(wordList.begin(), wordList.end()); queue todo; todo.push(beginWord); dict.erase(beginWord); int ladder = 1; while (!todo.empty()) { ladder++; int n = todo.size(); for (int i = 0; i < n; i++) { string word = todo.front(); todo.pop(); for (int j = 0; j < word.size(); j++) { char c = word[j]; for (int k = 0; k < 26; k++) { word[j] = 'a' + k; if (dict.find(word) != dict.end()) { if (word == endWord) { return ladder; } todo.push(word); dict.erase(word); } } word[j] = c; } } } return 0; }

在您访问 DFS 部分后：

如果我们改用 DFS 会发生什么？你看到任何好处/缺点吗？

订单级树遍历

给定一棵二叉树，返回其节点值的层序遍历。（即从左到右，逐级）。

打开链接以获取问题的图形描述。

解决方案

您只需要在此处对标准 BFS 算法进行一些调整：您需要知道每个级别需要处理队列中的多少元素。

这是一种可以应用于许多其他问题的方法。

vector> levelOrder(TreeNode* root) { if(!root) return {}; vector> sol; queue q; q.push(root); vector partial; while(!q.empty()){ int size = q.size(); while(size-->0){ auto n = q.front(); partial.push_back({n->val}); q.pop(); if(n->left) q.push({n->left}); if(n->right) q.push({n->right}); } sol.push_back(partial); partial.clear(); } return sol; }

挑战

让我提出一种不同的挑战：构建一些东西，而不是解决抽象的问题。我觉得它更有趣，你可以将它们添加到你的 Github 个人资料中。这里仅举两个例子：

网络爬虫使用 BFS 来探索网站上的所有链接。

扫雷舰

11.深度优先搜索

类似于 BFS 的目的：探索树和图。DFS 不保证找到两点之间的最短路径，但它会找到任何现有路径。

它的实现时间通常比 BFS 短。有些人觉得这更容易。其他的，因为递归调用，没有那么多。它是由你决定。如果堆栈的大小开始变大，请确保您考虑潜在的堆栈溢出问题。

有些问题用DFS/递归更容易解决，值得练习。

岛屿数量

给定一个由“1”（陆地）和“0”（水）组成的二维网格图，计算岛屿的数量。岛被水包围，由水平或垂直连接相邻的陆地而形成。您可以假设网格的所有四个边都被水包围。

例子：

输入：grid = [ [“1”,“1”,“1”,“1”,“0”], [“1”,“1”,“0”,“1”,“0”], [“1”,“1”,“0”,“0”,“0”], [“0”,“0”,“0”,“0”,“0”]]

输出：1

解决方案

一看到矩阵，就想到图。这个问题（及其变体）非常简单：

遍历矩阵

每找到 1 个，增加计数器并沉没岛屿

要下沉该岛，需要访问矩阵中所有周围的1，这相当于访问了该节点及其所有邻居的所有邻居，这听起来很像一个递归问题。

你也可以尝试使用 BFS 来解决这个问题，但 DFS 要短得多。

int numIslands(vector>& grid) { int numIslands = 0; for(int r = 0; r < grid.size(); ++r){ for(int c = 0; c < grid[0].size(); ++c){ if(grid[r][c] == '1'){ ++numIslands; sinkIslands(grid, r, c); } } } return numIslands; } const vector> dirs {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; void sinkIslands(vector> &m, int r, int c){ m[r][c] = '0'; for(const auto &d : dirs){ const int nr = r + d[0]; const int nc = c + d[1]; if(isValid(m, nr, nc)){ sinkIslands(m, nr, nc); } } } bool isValid(vector> &m, int r, int c){ return r >= 0 && r < m.size() && c >= 0 && c < m[0].size() && m[r][c] == '1'; }

对称树

给定一棵二叉树，检查它是否是自身的镜像（即围绕其中心对称）。

解决方案

许多与树相关的问题都有相对简单的递归解决方案。这个问题可以使用 BFS 解决，但 DFS 让它变得更容易。

我将把这个留在这里作为你的练习。如果您遇到困难，请使用我的解决方案。

bool isSymmetric(TreeNode* root) { if(!root) return true; return helper(root->left, root->right); } bool helper(TreeNode* p, TreeNode* q){ if(!p && !q) return true; if(!p || !q) return false; return p->val == q->val && iS(p->left, q->right) && iS(p->right, q->left); }

挑战

接受我为 BFS 提供的相同挑战和练习，并尝试使用 DFS 来实现它们。另外，为了更多练习，请尝试以下练习：

路径和

路径和 2

验证 BST

12.拓扑排序

您可以将此算法视为 DFS 的应用。它的实现只需要对常规 DFS 做一个小改动：处理完一个节点的所有子节点后，将此节点添加到堆栈中。

就是这么简单。

直观理解该算法实现的效果的最佳方法是想象一堆任务，其中一些任务依赖于其他任务（任务 1 在任务 2 完成之前无法开始）。拓扑排序将列出所有这些保留这种依赖关系结构的任务。

让我们用这个算法解决一个问题。

课程表二

你总共需要学习 n 门课程，从 0 到 n-1 标记。有些课程可能有先决条件，例如，要参加课程 0，您必须先参加课程 1，这表示为一对：[0,1]

给定课程总数和先决条件对列表，返回完成所有课程所需的课程顺序。可能有多个正确的订单，您只需要返回其中一个。如果不可能完成所有课程，则返回一个空数组。

示例 1：

输入：2, [[1,0]]

输出：[0,1]

说明：总共有 2 门课程要参加。要参加课程 1，您应该完成课程 0。因此正确的课程顺序是 [0,1]。

示例 2：

输入：4, [[1,0],[2,0],[3,1],[3,2]]

输出：[0,1,2,3] 或 [0,2,1,3]

说明：共有 4 门课程。要参加课程 3，您应该完成课程 1 和课程 2。课程 1 和课程 2 都应该在您完成课程 0之后进行。因此，正确的课程顺序是 [0,1,2,3]。另一个正确的顺序是 [0,2,1,3]。

解决方案

这是经典的拓扑排序问题。有很多课程要参加，有些取决于其他课程。这可以建模为有向图。拓扑排序将返回完成所有课程所需的课程顺序。

应用拓扑排序的先决条件是图是有向无环的。从问题描述中，我们可以看出该图是有向的。我们可以检测它是否包含任何循环并在同一遍中计算拓扑排序。

一种更间接但仍然有效的方法是首先检查它是否有环，只有在没有环的情况下，才计算拓扑排序。

vector findOrder(int numCourses, vector>& prerequisites) { vector> adj(numCourses, vector(0)); for(const auto &p : prerequisites){ int u = p[0]; int v = p[1]; adj[u].push_back(v); } vector white(numCourses, true), grey(numCourses), black(numCourses); vector sol (0); for(int i = 0; i < numCourses; ++i){ if(white[i] && hasCycle(adj, i, white, grey, black, sol)){ return {}; } } return sol; } bool hasCycle(const vector>& adj, int i, vector &white, vector &grey, vector &black, vector& sol){ //We have started exploring this node white[i] = false; grey[i] = true; for(const auto & n : adj[i]){ if(black[i]) continue; if(grey[n] || hasCycle(adj, n, white, grey, black, sol)) return true; } grey[i] = false; black[i] = true; sol.push_back(i); return false; }

扩展基本数据结构

13.出队

我已经看到数据结构主要用作实现您在本文前面阅读的滑动窗口技术的另一种方法。与标准 FIFO 队列的唯一区别是您可以在队列的两端进行操作（插入和删除元素）。

就是这样。简单的。

让我们看看这样一个微小的改变是如何简化这些问题的。

滑动窗口最大值

给定一个数组 nums，有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。您只能在窗口中看到 k 个数字。每次滑动窗口向右移动一个位置。返回最大滑动窗口。

例子：

输入：nums = [1,3,-1,-3,5,3,6,7]，k = 3

输出：[3,3,5,5,6,7]

解决方案

我们将使用出队来存储索引，而不是值。我们需要知道哪些元素仍然是滑动窗口的一部分。对于每次迭代，有四件事要做。

1.移除出列中当前滑动窗口之外的元素（每次迭代一个）

2.删除出列中所有小于我们所在的当前元素的元素，因为它们不能代表该滑动窗口的最大值

3.将当前元素添加到双端队列

4.一旦我们完成了第一个滑动窗口，我们就可以开始向我们的解决方案添加元素。按照设计，我们出队最前面的元素将包含滑动窗口的最大值，这是我们感兴趣的。

此技术可用于查找数组中连续数据块的最小值或其他属性。

vector maxSlidingWindow(const vector& nums, int k) { vector sol; deque dq; for (int i=0; i= k-1) sol.push_back(nums[dq.front()]); } return sol; }

挑战

设计自己的循环出队，全面掌握这个数据结构的内部结构。

数据结构

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。