【數據結構和算法】爆肝三萬字你必須知道的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小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。