2026年軟件工程師面試算法題集1.數(shù)組與字符串（3題，每題10分）題目1（10分）：給定一個包含重復字符的字符串`s`，返回其中不重復的最長子字符串的長度。例如，輸入`s="abcabcbb"`，輸出`4`（最長不重復子串為"bcab"）。題目2（10分）：給定一個整數(shù)數(shù)組`arr`，其中元素的范圍在`1`到`n`（`n`為數(shù)組長度），且每個元素出現(xiàn)一次或兩次。找出所有出現(xiàn)兩次的元素。例如，輸入`arr=[4,3,2,7,8,2,3,1]`，輸出`[2,3]`。題目3（10分）：將一個字符串`s`中的所有`0`移動到末尾，保持其他字符的相對順序。例如，輸入`s="012"`，輸出`"210"`。2.鏈表（2題，每題15分）題目4（15分）：設(shè)計一個單鏈表，支持在`O(1)`時間復雜度內(nèi)刪除任意節(jié)點（假設(shè)節(jié)點值唯一）。例如，給定鏈表`1->2->3`，刪除節(jié)點`2`后變?yōu)閌1->3`。題目5（15分）：判斷一個鏈表是否為回文鏈表。例如，輸入`1->2->2->1`，返回`true`。3.棧與隊列（2題，每題15分）題目6（15分）：給定一個包含`'('`,`')'`,`''`的字符串`s`，判斷是否存在一種括號匹配方式，使得字符串有效。`''`可以視為`'('`或`')'`。例如，輸入`s="()"`，返回`true`。題目7（15分）：實現(xiàn)一個`MinStack`類，支持在`O(1)`時間復雜度內(nèi)獲取棧中最小值。例如，`MinStack`包含操作`push(5)`,`push(2)`,`min()`（返回`2`），`pop()`，`min()`（返回`5`）。4.樹與二叉搜索樹（2題，每題15分）題目8（15分）：給定一個二叉搜索樹，找出其中所有范圍在`[low,high]`的節(jié)點值之和。例如，輸入`root=[10,5,15,3,7,null,18]`，`low=7`，`high=15`，輸出`32`（節(jié)點`7`和`10`）。題目9（15分）：判斷兩棵二叉樹是否相同。例如，樹`A`為`[1,2,3]`，樹`B`為`[1,2,3]`，返回`true`；樹`A`為`[1,2]`，樹`B`為`[1,2,3]`，返回`false`。5.哈希表（2題，每題15分）題目10（15分）：設(shè)計一個`LRUCache`類，支持在`O(1)`時間復雜度內(nèi)實現(xiàn)`get`和`put`操作。緩存容量為`capacity`。例如，`LRUCache(2)`，`put(1,1)`,`put(2,2)`,`get(1)`（返回`1`），`put(3,3)`（驅(qū)逐`2`），`get(2)`（返回`-1`）。題目11（15分）：統(tǒng)計一個字符串`s`中所有不同字母的異或結(jié)果。例如，輸入`s="abc"`，異或結(jié)果為`a^b^c`。6.排序與搜索（2題，每題15分）題目12（15分）：在一個未排序的數(shù)組`arr`中，找到第三大的數(shù)。如果數(shù)組長度小于`3`，返回最大數(shù)。例如，輸入`arr=[1,2,-2147483648,9,9,2]`，輸出`2`。題目13（15分）：實現(xiàn)二分查找的變種：給定一個旋轉(zhuǎn)排序數(shù)組`nums`（如`[4,5,6,7,0,1,2]`），找到目標值`target`的索引。例如，輸入`nums=[4,5,6,7,0,1,2]`，`target=0`，輸出`4`。7.動態(tài)規(guī)劃（2題，每題15分）題目14（15分）：給定一個整數(shù)數(shù)組`nums`，返回其中最多有多少個連續(xù)的`1`。例如，輸入`nums=[1,1,0,1,1,1]`，輸出`3`。題目15（15分）：給定一個字符串`s`，判斷是否可以通過刪除一些字符將其轉(zhuǎn)換為回文串。例如，輸入`s="baab"`，返回`true`（刪除第一個`b`）。8.圖（2題，每題15分）題目16（15分）：給定一個無向圖，判斷其是否為二分圖（可以用兩種顏色染色，使得相鄰節(jié)點顏色不同）。例如，輸入鄰接矩陣`[[1,3],[0,2],[1,3],[0,2]]`，返回`true`。題目17（15分）：給定一個`mxn`的矩陣，找出從左上角到右下角的最短路徑（只能向下或向右移動）。例如，輸入`grid=[[0,0,0],[0,1,0],[0,0,0]]`，輸出`2`。9.數(shù)學與位運算（2題，每題15分）題目18（15分）：給定一個正整數(shù)`n`，計算其二進制表示中`1`的個數(shù)。例如，輸入`n=11`（二進制`1011`），輸出`3`。題目19（15分）：給定兩個正整數(shù)`a`和`b`，計算它們的二進制表示中不同位（異或）的個數(shù)。例如，輸入`a=1`（`01`），`b=2`（`10`），輸出`2`。答案與解析1.數(shù)組與字符串題目1：-答案：滑動窗口法。維護一個窗口`[left,right]`，使用哈希表記錄窗口內(nèi)字符出現(xiàn)次數(shù)。遍歷字符串，若字符在哈希表中且計數(shù)大于`1`，則移動`left`直到該字符計數(shù)為`1`。每次更新最大長度`max_len`。-解析：時間`O(n)`，空間`O(n)`。題目2：-答案：哈希表記錄元素出現(xiàn)次數(shù)，遍歷數(shù)組將出現(xiàn)兩次的元素加入結(jié)果列表。-解析：時間`O(n)`，空間`O(n)`。題目3：-答案：雙指針法。維護兩個指針`left`和`right`，分別指向字符串首尾。交換`left`非`0`字符和`right`字符，直到`left>=right`。-解析：時間`O(n)`，空間`O(1)`。2.鏈表題目4：-答案：直接復制前一個節(jié)點的值到當前節(jié)點，然后刪除前一個節(jié)點。-解析：時間`O(1)`，空間`O(1)`。題目5：-答案：快慢指針判斷回文。將前半部分反轉(zhuǎn)，比較反轉(zhuǎn)后與后半部分是否一致。-解析：時間`O(n)`，空間`O(1)`。3.棧與隊列題目6：-答案：使用棧和計數(shù)器處理`'('`,`')'`,`''`。遍歷字符串，遇到`''`時考慮兩種情況，并使用兩個計數(shù)器維護左括號和星號的數(shù)量。-解析：時間`O(n)`，空間`O(n)`。題目7：-答案：使用兩個棧，一個存儲常規(guī)值，另一個存儲當前最小值。`push`時將當前最小值也壓入最小值棧。`pop`時比較棧頂是否為最小值，是則同時彈出。-解析：時間`O(1)`，空間`O(n)`。4.樹與二叉搜索樹題目8：-答案：遞歸遍歷二叉搜索樹，累加`[low,high]`范圍內(nèi)的節(jié)點值。-解析：時間`O(n)`，空間`O(h)`。題目9：-答案：遞歸比較兩棵樹的根節(jié)點，以及左子樹和右子樹。-解析：時間`O(n)`，空間`O(h)`。5.哈希表題目10：-答案：使用雙向鏈表和哈希表實現(xiàn)。鏈表頭尾分別表示最近和最久未使用節(jié)點，哈希表記錄節(jié)點值和鏈表中的位置。-解析：時間`O(1)`，空間`O(capacity)`。題目11：-答案：遍歷字符串，使用哈希表記錄每個字母的出現(xiàn)次數(shù)，最后計算所有字母的異或。-解析：時間`O(n)`，空間`O(1)`（假設(shè)字母表固定）。6.排序與搜索題目12：-答案：排序后取第`n-2`個元素。若數(shù)組長度小于`3`，返回最大值。-解析：時間`O(nlogn)`，空間`O(1)`（原地排序）。題目13：-答案：找到旋轉(zhuǎn)點，將數(shù)組分成兩部分，分別在左半部分和右半部分進行二分查找。-解析：時間`O(logn)`，空間`O(1)`。7.動態(tài)規(guī)劃題目14：-答案：遍歷數(shù)組，記錄當前連續(xù)`1`的個數(shù)，遇到`0`時重置。-解析：時間`O(n)`，空間`O(1)`。題目15：-答案：轉(zhuǎn)化為最長公共子序列問題，動態(tài)規(guī)劃計算最長回文子序列。-解析：時間`O(n^2)`，空間`O(n^2)`。8.圖題目16：-答案：使用BFS或DFS進行深度優(yōu)先染色，判斷是否能完成二分染色。-解析：時間`O(V+E)`，空間`O(V)`。題目17：-答案：BFS從左上角開始，記錄已訪問節(jié)點，每次移動向下或向右。-解析：時間`O(mn)`，空間`O(mn