算法知識總結

本部分主要是筆者在學習算法知識和一些相關面試題所做的筆記，如果出現錯誤，希望大家指出！

目錄

• 常用算法和數據結構總結
  • 排序
    • 冒泡排序
    • 選擇排序
    • 插入排序
    • 希爾排序
    • 歸并排序
    • 快速排序
    • 堆排序
    • 基數排序
    • 快速排序相對于其他排序效率更高的原因
    • 系統自帶排序實現
    • 穩定性
    • 排序面試題目總結
  • 樹
    • 二叉樹相關性質
    • 滿二叉樹
    • 完全二叉樹
    • 平衡二叉查找樹（AVL）
    • B-樹
    • B 樹
    • 數據庫索引
    • 紅黑樹
    • Huffman 樹
    • 二叉查找樹
    • 求解二叉樹中兩個節點的最近公共祖先節點
  • 鏈表
    • 反轉單向鏈表
  • 動態規劃
    • 爬樓梯問題
    • 遞歸方法分析
    • 備忘錄方法
    • 迭代法
  • 經典筆試題
    • 1. js 實現一個函數，完成超過范圍的兩個大整數相加功能
    • 2. js 如何實現數組扁平化？
    • 3. js 如何實現數組去重？
    • 4. 如何求數組的最大值和最小值？
    • 5. 如何求兩個數的最大公約數？
    • 6. 如何求兩個數的最小公倍數？
    • 7. 實現 IndexOf 方法？
    • 8. 判斷一個字符串是否為回文字符串？
    • 9. 實現一個累加函數的功能比如 sum(1,2,3)(2).valueOf()
    • 10. 使用 reduce 方法實現 forEach、map、filter
    • 11. 設計一個簡單的任務隊列，要求分別在 1,3,4 秒后打印出 “1”, “2”, “3”
    • 12. 如何查找一篇英文文章中出現頻率最高的單詞？
• 常見面試智力題總結
  • 1. 時針與分針夾角度數問題？
  • 2. 用3升，5升杯子怎么量出4升水？
  • 3. 渾濁藥罐問題
  • 4. 卡片證明問題
  • 5. 賽馬問題，25 匹馬，5 個賽道，最少幾次能選出最快的三匹馬？
  • 6. 五隊夫婦參加聚會握手問題
  • 7. 你只能帶行走 60 公里的油，只能在起始點加油，如何穿過 80 公里的沙漠？
  • 8. 燒一根不均勻的繩要用一個小時，如何用它來判斷一個小時十五分鐘？
  • 9. 有7克、2克砝碼各一個，天平一只，如何只用這些物品三次將140克的鹽分成50、90克各一份？
  • 10. 火車相對而行，小鳥飛行距離問題
  • 11. 彈球拾取幾率問題
  • 12. 8個球使用天平稱重問題
  • 13. 三盞燈區分開關問題
  • 14. 盲人黑白襪子問題
  • 15. 水果標簽問題
  • 16. 一個班級60%喜歡足球，70%喜歡籃球，80%喜歡排球，問即三種球都喜歡占比有多少？
  • 17. 五只雞五天能下五個蛋，一百天下一百個蛋需要多少只雞？
• 劍指 offer 思路總結
  • 題目
    • 1. 二維數組中的查找
    • 2. 替換空格
    • 3. 從尾到頭打印鏈表
    • 4. 重建二叉樹
    • 5. 用兩個棧實現隊列
    • 6. 旋轉數組的最小數字
    • 7. 斐波那契數列
    • 8. 跳臺階
    • 9. 變態跳臺階
    • 10. 矩形覆蓋
    • 11. 二進制中1的個數
    • 12. 數值的整數次方
    • 13. 調整數組順序使奇數位于偶數前面
    • 14. 鏈表中倒數第 k 個節點
    • 15. 反轉鏈表
    • 16. 合并兩個排序的鏈表
    • 17. 樹的子結構
    • 18. 二叉樹的鏡像
    • 19. 順時針打印矩陣
    • 20. 定義一個棧，實現 min 函數
    • 21. 棧的壓入彈出
    • 22. 從上往下打印二叉樹
    • 23. 二叉搜索樹的后序遍歷
    • 24. 二叉樹中和為某一值路徑
    • 25. 復雜鏈表的復制
    • 26. 二叉搜索樹與雙向鏈表
    • 27. 字符串的排列
    • 28. 數組中出現次數超過一半的數字
    • 29. 最小的 K 個數
    • 30. 連續子數組的最大和
    • 31. 整數中1出現的次數（待深入理解）
    • 32. 把數組排成最小的數
    • 33. 丑數（待深入理解）
    • 34. 第一個只出現一次的字符
    • 35. 數組中的逆序對
    • 36. 兩個鏈表的第一個公共結點
    • 37. 數字在排序數組中出現的次數
    • 38. 二叉樹的深度
    • 39. 平衡二叉樹
    • 40. 數組中只出現一次的數字
    • 41. 和為 S 的連續正數序列
    • 42. 和為 S 的兩個數字
    • 43. 左旋轉字符串
    • 44. 翻轉單詞順序列
    • 45. 撲克牌的順子
    • 46. 圓圈中最后剩下的數字（約瑟夫環問題）
    • 47. 1 2 3 … n
    • 48. 不用加減乘除做加法
    • 49. 把字符串轉換成整數。
    • 50. 數組中重復的數字
    • 51. 構建乘積數組
    • 52. 正則表達式的匹配
    • 53. 表示數值的字符串
    • 54. 字符流中第一個不重復的字符
    • 55. 鏈表中環的入口結點
    • 56. 刪除鏈表中重復的結點
    • 57. 二叉樹的下一個結點
    • 58. 對稱二叉樹
    • 59. 按之字形順序打印二叉樹（待深入理解）
    • 60. 從上到下按層打印二叉樹，同一層結點從左至右輸出。每一層輸出一行。
    • 61. 序列化二叉樹（待深入理解）
    • 62. 二叉搜索樹的第 K 個節點
    • 63. 數據流中的中位數（待深入理解）
    • 64. 滑動窗口中的最大值（待深入理解）
    • 65. 矩陣中的路徑（待深入理解）
    • 66. 機器人的運動范圍（待深入理解）
  • 相關算法題
    • 1. 明星問題
    • 2. 正負數組求和

常用算法和數據結構總結

排序

冒泡排序

冒泡排序的基本思想是，對相鄰的元素進行兩兩比較，順序相反則進行交換，這樣，每一趟會將最小或最大的元素“浮”到頂端，
最終達到完全有序。

代碼實現：

function bubbleSort(arr) {if (!Array.isArray(arr) || arr.length <= 1) return;let lastIndex = arr.length - 1;while (lastIndex > 0) { // 當最后一個交換的元素為第一個時，說明后面全部排序完畢let flag = true, k = lastIndex;for (let j = 0; j < k; j++) {if (arr[j] > arr[j + 1]) {flag = false;lastIndex = j; // 設置最后一次交換元素的位置[arr[j], arr[j+1]] = [arr[j+1], arr[j]];}}if (flag) break;} }

冒泡排序有兩種優化方式。

一種是外層循環的優化，我們可以記錄當前循環中是否發生了交換，如果沒有發生交換，則說明該序列已經為有序序列了。
因此我們不需要再執行之后的外層循環，此時可以直接結束。

一種是內層循環的優化，我們可以記錄當前循環中最后一次元素交換的位置，該位置以后的序列都是已排好的序列，因此下
一輪循環中無需再去比較。

優化后的冒泡排序，當排序序列為已排序序列時，為最好的時間復雜度為 O(n)。

冒泡排序的平均時間復雜度為 O(n2) ，最壞時間復雜度為 O(n2) ，空間復雜度為 O(1) ，是穩定排序。

詳細資料可以參考：
《圖解排序算法(一)》
《常見排序算法 - 雞尾酒排序 》
《前端筆試&面試爬坑系列—算法》
《前端面試之道》

選擇排序

選擇排序的基本思想為每一趟從待排序的數據元素中選擇最小（或最大）的一個元素作為首元素，直到所有元素排完為止。

在算法實現時，每一趟確定最小元素的時候會通過不斷地比較交換來使得首位置為當前最小，交換是個比較耗時的操作。其實
我們很容易發現，在還未完全確定當前最小元素之前，這些交換都是無意義的。我們可以通過設置一個變量 min，每一次比較
僅存儲較小元素的數組下標，當輪循環結束之后，那這個變量存儲的就是當前最小元素的下標，此時再執行交換操作即可。

代碼實現：

function selectSort(array) {let length = array.length;// 如果不是數組或者數組長度小于等于1，直接返回，不需要排序 if (!Array.isArray(array) || length <= 1) return;for (let i = 0; i < length - 1; i++) {let minIndex = i; // 設置當前循環最小元素索引for (let j = i + 1; j < length; j++) {// 如果當前元素比最小元素索引，則更新最小元素索引if (array[minIndex] > array[j]) {minIndex = j;}}// 交換最小元素到當前位置// [array[i], array[minIndex]] = [array[minIndex], array[i]];swap(array, i, minIndex);}return array; }// 交換數組中兩個元素的位置 function swap(array, left, right) {var temp = array[left];array[left] = array[right];array[right] = temp; }

選擇排序不管初始序列是否有序，時間復雜度都為 O(n2)。

選擇排序的平均時間復雜度為 O(n2) ，最壞時間復雜度為 O(n2) ，空間復雜度為 O(1) ，不是穩定排序。

詳細資料可以參考：
《圖解排序算法(一)》

插入排序

直接插入排序基本思想是每一步將一個待排序的記錄，插入到前面已經排好序的有序序列中去，直到插完所有元素為止。

插入排序核心–撲克牌思想： 就想著自己在打撲克牌，接起來一張，放哪里無所謂，再接起來一張，比第一張小，放左邊，
繼續接，可能是中間數，就插在中間…依次

代碼實現：

function insertSort(array) {let length = array.length;// 如果不是數組或者數組長度小于等于1，直接返回，不需要排序 if (!Array.isArray(array) || length <= 1) return;// 循環從 1 開始，0 位置為默認的已排序的序列for (let i = 1; i < length; i++) {let temp = array[i]; // 保存當前需要排序的元素let j = i;// 在當前已排序序列中比較，如果比需要排序的元素大，就依次往后移動位置while (j -1 >= 0 && array[j - 1] > temp) {array[j] = array[j - 1];j--;}// 將找到的位置插入元素array[j] = temp;}return array; }

當排序序列為已排序序列時，為最好的時間復雜度 O(n)。

插入排序的平均時間復雜度為 O(n2) ，最壞時間復雜度為 O(n2) ，空間復雜度為 O(1) ，是穩定排序。

詳細資料可以參考：
《圖解排序算法(一)》

希爾排序

希爾排序的基本思想是把數組按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的元
素越來越多，當增量減至1時，整個數組恰被分成一組，算法便終止。

代碼實現：

function hillSort(array) {let length = array.length;// 如果不是數組或者數組長度小于等于1，直接返回，不需要排序 if (!Array.isArray(array) || length <= 1) return;// 第一層確定增量的大小，每次增量的大小減半for (let gap = parseInt(length >> 1); gap >= 1; gap = parseInt(gap >> 1)) {// 對每個分組使用插入排序，相當于將插入排序的1換成了 nfor (let i = gap; i < length; i++) {let temp = array[i];let j = i;while (j - gap >= 0 && array[j - gap] > temp) {array[j] = array[j - gap];j -= gap;}array[j] = temp;}}return array; }

希爾排序是利用了插入排序對于已排序序列排序效果最好的特點，在一開始序列為無序序列時，將序列分為多個小的分組進行
基數排序，由于排序基數小，每次基數排序的效果較好，然后在逐步增大增量，將分組的大小增大，由于每一次都是基于上一
次排序后的結果，所以每一次都可以看做是一個基本排序的序列，所以能夠最大化插入排序的優點。

簡單來說就是，由于開始時每組只有很少整數，所以排序很快。之后每組含有的整數越來越多，但是由于這些數也越來越有序，
所以排序速度也很快。

希爾排序的時間復雜度根據選擇的增量序列不同而不同，但總的來說時間復雜度是小于 O(n^2) 的。

插入排序是一個穩定排序，但是在希爾排序中，由于相同的元素可能在不同的分組中，所以可能會造成相同元素位置的變化，
所以希爾排序是一個不穩定的排序。

希爾排序的平均時間復雜度為 O(nlogn) ，最壞時間復雜度為 O(n^s) ，空間復雜度為 O(1) ，不是穩定排序。

詳細資料可以參考：
《圖解排序算法(二)之希爾排序》
《數據結構基礎 希爾排序 之 算法復雜度淺析》

歸并排序

歸并排序是利用歸并的思想實現的排序方法，該算法采用經典的分治策略。遞歸的將數組兩兩分開直到只包含一個元素，然后
將數組排序合并，最終合并為排序好的數組。

代碼實現：

function mergeSort(array) {let length = array.length;// 如果不是數組或者數組長度小于等于0，直接返回，不需要排序 if (!Array.isArray(array) || length === 0) return;if (length === 1) {return array;}let mid = parseInt(length >> 1), // 找到中間索引值left = array.slice(0, mid), // 截取左半部分right = array.slice(mid, length); // 截取右半部分return merge(mergeSort(left), mergeSort(right)); // 遞歸分解后，進行排序合并 }function merge(leftArray, rightArray) {let result = [],leftLength = leftArray.length,rightLength = rightArray.length,il = 0,ir = 0;// 左右兩個數組的元素依次比較，將較小的元素加入結果數組中，直到其中一個數組的元素全部加入完則停止while (il < leftLength && ir < rightLength) {if (leftArray[il] < rightArray[ir]) {result.push(leftArray[il++]);} else {result.push(rightArray[ir++]);}}// 如果是左邊數組還有剩余，則把剩余的元素全部加入到結果數組中。while (il < leftLength) {result.push(leftArray[il++]);}// 如果是右邊數組還有剩余，則把剩余的元素全部加入到結果數組中。while (ir < rightLength) {result.push(rightArray[ir++]);}return result; }

歸并排序將整個排序序列看成一個二叉樹進行分解，首先將樹分解到每一個子節點，樹的每一層都是一個歸并排序的過程，每
一層歸并的時間復雜度為 O(n)，因為整個樹的高度為 lgn，所以歸并排序的時間復雜度不管在什么情況下都為O(nlogn)。

歸并排序的空間復雜度取決于遞歸的深度和用于歸并時的臨時數組，所以遞歸的深度為 logn，臨時數組的大小為 n，所以歸
并排序的空間復雜度為 O(n)。

歸并排序的平均時間復雜度為 O(nlogn) ，最壞時間復雜度為 O(nlogn) ，空間復雜度為 O(n) ，是穩定排序。

詳細資料可以參考：
《圖解排序算法(四)之歸并排序》
《歸并排序的空間復雜度？》

快速排序

快速排序的基本思想是通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據
都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

代碼實現：

function quickSort(array, start, end) {let length = array.length;// 如果不是數組或者數組長度小于等于1，直接返回，不需要排序 if (!Array.isArray(array) || length <= 1 || start >= end) return;let index = partition(array, start, end); // 將數組劃分為兩部分，并返回右部分的第一個元素的索引值quickSort(array, start, index - 1); // 遞歸排序左半部分quickSort(array, index + 1, end); // 遞歸排序右半部分 }function partition(array, start, end) {let pivot = array[start]; // 取第一個值為樞紐值，獲取樞紐值的大小// 當 start 等于 end 指針時結束循環while (start < end) {// 當 end 指針指向的值大等于樞紐值時，end 指針向前移動while (array[end] >= pivot && start < end) {end--;}// 將比樞紐值小的值交換到 start 位置array[start] = array[end];// 移動 start 值，當 start 指針指向的值小于樞紐值時，start 指針向后移動while (array[start] < pivot && start < end) {start++;}// 將比樞紐值大的值交換到 end 位置，進入下一次循環array[end] = array[start];}// 將樞紐值交換到中間點array[start] = pivot;// 返回中間索引值return start; }

這一種方法是填空法，首先將第一個位置的數作為樞紐值，然后 end 指針向前移動，當遇到比樞紐值小的值或者 end 值
等于 start 值的時候停止，然后將這個值填入 start 的位置，然后 start 指針向后移動，當遇到比樞紐值大的值或者
start 值等于 end 值的時候停止，然后將這個值填入 end 的位置。反復循環這個過程，直到 start 的值等于 end 的
值為止。將一開始保留的樞紐值填入這個位置，此時樞紐值左邊的值都比樞紐值小，樞紐值右邊的值都比樞紐值大。然后在遞
歸左右兩邊的的序列。

當每次換分的結果為含 ?n/2?和 ?n/2??1 個元素時，最好情況發生，此時遞歸的次數為 logn，然后每次劃分的時間復雜
度為 O(n)，所以最優的時間復雜度為 O(nlogn)。一般來說只要每次換分都是常比例的劃分，時間復雜度都為 O(nlogn)。

當每次換分的結果為 n-1 和 0 個元素時，最壞情況發生。劃分操作的時間復雜度為 O(n)，遞歸的次數為 n-1，所以最壞
的時間復雜度為 O(n2)。所以當排序序列有序的時候，快速排序有可能被轉換為冒泡排序。

快速排序的空間復雜度取決于遞歸的深度，所以最好的時候為 O(logn)，最壞的時候為 O(n)。

快速排序的平均時間復雜度為 O(nlogn) ，最壞時間復雜度為 O(n2) ，空間復雜度為 O(logn) ，不是穩定排序。

詳細資料可以參考：
《圖解排序算法(五)之快速排序——三數取中法》
《關于快速排序的四種寫法》
《快速排序的時間和空間復雜度》
《快速排序最好，最壞，平均復雜度分析》
《快速排序算法的遞歸深度》

堆排序

堆排序的基本思想是：將待排序序列構造成一個大頂堆，此時，整個序列的最大值就是堆頂的根節點。將其與末尾元素進行
交換，此時末尾就為最大值。然后將剩余 n-1 個元素重新構造成一個堆，這樣會得到 n 個元素的次小值。如此反復執行，
便能得到一個有序序列了。

function heapSort(array) {let length = array.length;// 如果不是數組或者數組長度小于等于1，直接返回，不需要排序 if (!Array.isArray(array) || length <= 1) return;buildMaxHeap(array); // 將傳入的數組建立為大頂堆// 每次循環，將最大的元素與末尾元素交換，然后剩下的元素重新構建為大頂堆for (let i = length - 1; i > 0; i--) {swap(array, 0, i);adjustMaxHeap(array, 0, i); // 將剩下的元素重新構建為大頂堆}return array; }function adjustMaxHeap(array, index, heapSize) {let iMax,iLeft,iRight;while (true) {iMax = index; // 保存最大值的索引iLeft = 2 * index + 1; // 獲取左子元素的索引iRight = 2 * index + 2; // 獲取右子元素的索引// 如果左子元素存在，且左子元素大于最大值，則更新最大值索引if (iLeft < heapSize && array[iMax] < array[iLeft]) {iMax = iLeft;}// 如果右子元素存在，且右子元素大于最大值，則更新最大值索引if (iRight < heapSize && array[iMax] < array[iRight]) {iMax = iRight;}// 如果最大元素被更新了，則交換位置，使父節點大于它的子節點，同時將索引值跟新為被替換的值，繼續檢查它的子樹if (iMax !== index) {swap(array, index, iMax);index = iMax;} else {// 如果未被更新，說明該子樹滿足大頂堆的要求，退出循環break;}} }// 構建大頂堆 function buildMaxHeap(array) {let length = array.length,iParent = parseInt(length >> 1) - 1; // 獲取最后一個非葉子點的元素for (let i = iParent; i >= 0; i--) {adjustMaxHeap(array, i, length); // 循環調整每一個子樹，使其滿足大頂堆的要求} }// 交換數組中兩個元素的位置 function swap(array, i, j) {let temp = array[i];array[i] = array[j];array[j] = temp; }

建立堆的時間復雜度為 O(n)，排序循環的次數為 n-1，每次調整堆的時間復雜度為 O(logn)，因此堆排序的時間復雜度在
不管什么情況下都是 O(nlogn)。

堆排序的平均時間復雜度為 O(nlogn) ，最壞時間復雜度為 O(nlogn) ，空間復雜度為 O(1) ，不是穩定排序。

詳細資料可以參考：
《圖解排序算法(三)之堆排序》
《常見排序算法 - 堆排序 (Heap Sort)》
《堆排序中建堆過程時間復雜度O(n)怎么來的？》
《排序算法之 堆排序 及其時間復雜度和空間復雜度》
《最小堆 構建、插入、刪除的過程圖解》

基數排序

基數排序是一種非比較型整數排序算法，其原理是將整數按位數切割成不同的數字，然后按每個位數分別比較。排序過程：將
所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然后，從最低位開始，依次進行一次排序。這樣
從最低位排序一直到最高位排序完成以后，數列就變成一個有序序列。

代碼實現：

function radixSort(array) {let length = array.length;// 如果不是數組或者數組長度小于等于1，直接返回，不需要排序 if (!Array.isArray(array) || length <= 1) return;let bucket = [],max = array[0],loop;// 確定排序數組中的最大值for (let i = 1; i < length; i++) {if (array[i] > max) {max = array[i];}}// 確定最大值的位數loop = (max + '').length;// 初始化桶for (let i = 0; i < 10; i++) {bucket[i] = [];}for (let i = 0; i < loop; i++) {for (let j = 0; j < length; j++) {let str = array[j] + '';if (str.length >= i + 1) {let k = parseInt(str[str.length - 1 - i]); // 獲取當前位的值，作為插入的索引bucket[k].push(array[j]);} else {// 處理位數不夠的情況，高位默認為 0bucket[0].push(array[j]);}}array.splice(0, length); // 清空舊的數組// 使用桶重新初始化數組for (let i = 0; i < 10; i++) {let t = bucket[i].length;for (let j = 0; j < t; j++) {array.push(bucket[i][j]);}bucket[i] = [];}}return array;}

基數排序的平均時間復雜度為 O(nk)，k 為最大元素的長度，最壞時間復雜度為 O(nk)，空間復雜度為 O(n) ，是穩定
排序。

詳細資料可以參考：
《常見排序算法 - 基數排序》
《排序算法之 基數排序 及其時間復雜度和空間復雜度》

算法總結可以參考：
《算法的時間復雜度和空間復雜度-總結》
《十大經典排序算法（動圖演示）》
《各類排序算法的對比及實現》

快速排序相對于其他排序效率更高的原因

上面一共提到了8種排序的方法，在實際使用中，應用最廣泛的是快速排序。快速排序相對于其他排序算法的優勢在于在相同
數據量的情況下，它的運算效率最高，并且它額外所需空間最小。

我們首先從時間復雜度來判斷，由于前面幾種方法的時間復雜度平均情況下基本趨向于 O(n2)，因此只從時間復雜度上來看
的話，顯然歸并排序、堆排序和快速排序的時間復雜度最小。但是既然這幾種方法的時間復雜度基本一致，并且快速排序在最
壞情況下時間的復雜度還會變為 O(n2)，那么為什么它的效率反而更高呢？

首先在對大數據量排序的時候，由于歸并排序的空間復雜度為 O(n)，因此歸并排序在這種情況下會需要過多的額外內存，因
此歸并排序首先就被排除掉了。

接下來就剩下了堆排序和快速排序的比較。我認為堆排序相對于快速排序的效率不高的原因有兩個方面。

第一個方面是對于比較操作的有效性來說。對于快速排序來說，每一次元素的比較都會確定該元素在數組中的位置，也就是在
樞紐值的左邊或者右邊，快速排序的每一次比較操作都是有意義的結果。而對于堆排序來說，在每一次重新調整堆的時候，我
們在迭代時，已經知道上層的節點值一定比下層的節點值大，因此當我們每次為了打亂堆結構而將最后一個元素與堆頂元素互
換時，互換后的元素一定是比下層元素小的，因此我們知道比較結果卻還要在堆結構調整時去進行再一次的比較，這樣的比較
是沒有意義的，以此在堆排序中會產生大量的沒有意義的比較操作。

第二個方面是對于緩存局部性原理的利用上來考慮的，我認為這應該是造成堆排序的效率不如快速排序的主要原因。在計算機
中利用了多級緩存的機制，來解決 cpu 計算速度與存儲器數據讀取速度間差距過大的問題。緩存的原理主要是基于局部性原
理，局部性原理簡單來說就是，當前被訪問過的數據，很有可能在一段時間內被再次訪問，這被稱為時間局部性。還有就是當
前訪問的數據，那么它相鄰的數據，也有可能在一段時間內被訪問到，這被稱為空間局部性。計算機緩存利用了局部性的原理
來對數據進行緩存，來盡可能少的減少磁盤的 I/O 次數，以此來提高執行效率。對于堆排序來說，它最大的問題就是它對于
空間局部性的違背，它在進行比較時，比較的并不是相鄰的元素，而是與自己相隔很遠的元素，這對于利用空間局部性來進行
數據緩存的計算機來說，它的很多緩存都是無效的。并且對于大數據量的排序來說，緩存的命中率就會變得很低，因此會明顯
提高磁盤的 I/O 次數，并且由于堆排序的大量的無效比較，因此這樣就造成了堆排序執行效率的低下。而相對來快速排序來
說，它的排序每一次都是在相鄰范圍內的比較，并且比較的范圍越來越小，它很好的利用了局部性原理，因此它的執行效率更
高。簡單來說就是在堆排序中獲取一個元素的值所花費的時間比在快速排序獲取一個元素的值所花費的時間要大。因此我們可
以看出，時間復雜度類似的算法，在計算機中實際執行可能會有很大的差別，因為決定算法執行效率的還有內存讀取這樣的其
他的因素。

相關資料可以參考：
《為什么在平均情況下快速排序比堆排序要優秀？》
《為什么說快速排序是性能最好的排序算法？》

系統自帶排序實現

每個語言的排序內部實現都是不同的。

對于 JS 來說，數組長度大于 10 會采用快排，否則使用插入排序。選擇插入排序是因為雖然時間復雜度很差，但是在數據
量很小的情況下和 O(N * logN) 相差無幾，然而插入排序需要的常數時間很小，所以相對別的排序來說更快。

穩定性

穩定性的意思就是對于相同值來說，相對順序不能改變。通俗的講有兩個相同的數 A 和 B，在排序之前 A 在 B 的前面，
而經過排序之后，B 跑到了 A 的前面，對于這種情況的發生，我們管他叫做排序的不穩定性。

穩定性有什么意義？個人理解對于前端來說，比如我們熟知框架中的虛擬 DOM 的比較，我們對一個<ul>列表進行渲染，
當數據改變后需要比較變化時，不穩定排序或操作將會使本身不需要變化的東西變化，導致重新渲染，帶來性能的損耗。

排序面試題目總結

快速排序在完全無序的情況下效果最好，時間復雜度為O(nlogn)，在有序情況下效果最差，時間復雜度為O(n^2)。

初始數據集的排列順序對算法的性能無影響的有堆排序，直接選擇排序，歸并排序，基數排序。

合并 m 個長度為 n 的已排序數組的時間復雜度為 O(nmlogm)。

外部排序常用的算法是歸并排序。

數組元素基本有序的情況下，插入排序效果最好，因為這樣只需要比較大小，不需要移動，時間復雜度趨近于O(n)。

如果只想得到1000個元素組成的序列中第5個最小元素之前的部分排序的序列，用堆排序方法最快。

插入排序和優化后的冒泡在最優情況（有序）都只用比較 n-1 次。

對長度為 n 的線性表作快速排序，在最壞情況下，比較次數為 n(n-1)/2。

下標從1開始，在含有 n 個關鍵字的小根堆（堆頂元素最小）中，關鍵字最大的記錄有可能存儲在 [n/2]+2 位置上。
因為小根堆中最大的數一定是放在葉子節點上，堆本身是個完全二叉樹，完全二叉樹的葉子節點的位置大于 [n/2]。

拓撲排序的算法，每次都選擇入度為0的結點從圖中刪去，并從圖中刪除該頂點和所有以它為起點的有向邊。

任何一個基于"比較"的內部排序的算法，若對 n 個元素進行排序，則在最壞情況下所需的比較次數 k 滿足 2^k > n!，
時間下界為 O(nlogn)

m 個元素 k 路歸并的歸并趟數 s=logk(m)，代入數據：logk(100)≦3

對 n 個記錄的線性表進行快速排序為減少算法的遞歸深度，每次分區后，先處理較短的部分。

在用鄰接表表示圖時，拓撲排序算法時間復雜度為 O(n+e)

樹

二叉樹相關性質

節點的度：一個節點含有的子樹的個數稱為該節點的度；

葉節點或終端節點：度為零的節點；

節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推。

樹的高度或深度：樹中節點的最大層次。

在非空二叉樹中，第 i 層的結點總數不超過 2^(i-1)，i>=1。

深度為 h 的二叉樹最多有 2^h-1個結點(h>=1)，最少有 h 個結點。

對于任意一棵二叉樹，如果其葉結點數為 N0，而度數為2的結點總數為 N2，則 N0 = N2+1；

給定 N 個節點，能構成 h(N) 種不同的二叉樹。h(N)為卡特蘭數的第 N 項。(2n)!/(n!(n+1)!)。

二叉樹的前序遍歷，首先訪問根結點，然后遍歷左子樹，最后遍歷右子樹。簡記根-左-右。

二叉樹的中序遍歷，首先遍歷左子樹，然后訪問根結點，最后遍歷右子樹。簡記左-根-右。

二叉樹的后序遍歷，首先遍歷左子樹，然后遍歷右子樹，最后訪問根結點。簡記左-右-根。

二叉樹是非線性數據結構，但是順序存儲結構和鏈式存儲結構都能存儲。

一個帶權的無向連通圖的最小生成樹的權值之和是唯一的。

只有一個結點的二叉樹的度為 0 。

二叉樹的度是以節點的最大的度數定義的。

樹的后序遍歷序列等同于該樹對應的二叉樹的中序序列。

樹的先序遍歷序列等同于該樹對應的二叉樹的先序序列。

線索二叉樹的線索實際上指向的是相應遍歷序列特定結點的前驅結點和后繼結點，所以先寫出二叉樹的中序遍歷序列：
debxac，中序遍歷中在x左邊和右邊的字符，就是它在中序線索化的左、右線索，即 b、a 。

遞歸式的先序遍歷一個 n 節點，深度為 d 的二叉樹，需要棧空間的大小為 O（d），因為二叉樹并不一定是平衡的，
也就是深度d！=logn，有可能d>>logn。所以棧大小應該是O（d）

一棵具有 N 個結點的二叉樹的前序序列和后序序列正好相反 ，則該二叉樹一定滿足該二叉樹只有左子樹或只有右子樹，
即該二叉樹一定是一條鏈（二叉樹的高度為N，高度等于結點數）。

引入二叉線索樹的目的是加快查找結點的前驅或后繼的速度。

二叉樹線索化后，先序線索化與后序線索化最多有1個空指針域，而中序線索化最多有2個空指針域。

不管是幾叉樹，節點數等于=分叉數+1

任何一棵二叉樹的葉子結點在先序、中序和后序遍歷中的相對次序不發生改變。

詳細資料可以參考：
《n 個節點的二叉樹有多少種形態》
《數據結構二叉樹知識點總結》
《還原二叉樹–已知先序中序或者后序中序》
《樹、森林與二叉樹的轉換》

滿二叉樹

對于一棵二叉樹，如果每一個非葉子節點都存在左右子樹，并且二叉樹中所有的葉子節點都在同一層中，這樣的二叉樹稱為滿
二叉樹。

完全二叉樹

對于一棵具有 n 個節點的二叉樹按照層次編號，同時，左右子樹按照先左后右編號，如果編號為 i 的節點與同樣深度的滿
二叉樹中編號為i的節點在滿二叉樹中的位置完全相同，則這棵二叉樹稱為完全二叉樹。

性質：

具有 n 個結點的完全二叉樹的深度為 K =[log2n」+1(取下整數)

有 N 個結點的完全二叉樹各結點如果用順序方式存儲，則結點之間有如下關系： 若 I 為結點編號（從1開始編號）則
如果 I>1，則其父結點的編號為 I/2；

完全二叉樹，如果 2 * I <= N，則其左兒子（即左子樹的根結點）的編號為2 * I；若2 * I > N，則無左兒子；如
果 2 * I + 1 <= N，則其右兒子的結點編號為 2 * I + 1；若 2 * I + 1 > N，則無右兒子。

平衡二叉查找樹（AVL）

平衡二叉查找樹具有如下幾個性質：

可以是空樹。

假如不是空樹，任何一個結點的左子樹與右子樹都是平衡二叉樹，并且高度之差的絕對值不超過1。

平衡二叉樹是為了解決二叉查找樹中出現鏈式結構（只有左子樹或只有右子樹）的情況，這樣的情況出現后對我們的查找沒有
一點幫幫助，反而增加了維護的成本。

平衡因子使用兩個字母來表示。第一個字母表示最小不平衡子樹根結點的平衡因子，第二個字母表示最小不平衡子樹較高子樹
的根結點的平衡因子。根據不同的情況使用不同的方法來調整失衡的子樹。

詳細資料可以參考：
《平衡二叉樹，AVL樹之圖解篇》

B-樹

B-樹主要用于文件系統以及部分數據庫索引，如 MongoDB。使用 B-樹來作為數據庫的索引主要是為了減少查找是磁盤的 I/O
次數。試想，如果我們使用二叉查找樹來作為索引，那么查找次數的最壞情況等于二叉查找樹的高度，由于索引存儲在磁盤中，
我們每次都只能加載對應索引的磁盤頁進入內存中比較，那么磁盤的 I/O 次數就等于索引樹的高度。所以采用一種辦法來減少
索引樹的高度是提高索引效率的關鍵。

B-樹是一種多路平衡查找樹，它的每一個節點最多包含 K 個子節點，K 被稱為 B-樹的階，K 的大小取決于磁盤頁的大小。每
個節點中的元素從小到大排列，節點當中 k-1 個元素正好是 k 個孩子包含的元素的值域分劃。簡單來說就是以前一個磁盤頁
只存儲一個索引的值，但 B-樹中一個磁盤頁中存儲了多個索引的值，因此在相同的比較范圍內，B-樹相對于一般的二叉查找樹
的高度更小。其實它的主要目的就是每次盡可能多的將索引值加載入內存中進行比較，以此來減少磁盤的 I/O 次數，其實就查
找次數而言，和二叉查找樹比較差不了多少，只是說這個比較過程是在內存中完成的，速度更快而已。

詳細資料可以參考：
《漫畫：什么是 B- 樹？》

B+樹

B+ 樹相對于 B-樹有著更好的查找性能，根據 B-樹我們可以知道，要想加快索引速度的方法就是盡量減少磁盤 I/O 的次數。
B+ 樹相對于 B-的主要變化是，每個中間節點中不再包含衛星數據，只有葉子節點包含衛星數據，每個父節點都出現在子節點
中，葉子節點依次相連，形成一個順序鏈表。中間節點不包含衛星數據，只用來作為索引使用，這意味著每一個磁盤頁中能夠
包含更多的索引值。因此 B+ 樹的高度相對于 B-來說更低，所以磁盤的 I/O 次數更少。由于葉子節點依次相連，并且包含
了父節點，所以可以通過葉子節點來找到對應的值。同時 B+ 樹所有查詢都要查找到葉子節點，查詢性能比 B-樹穩定。

詳細資料可以參考：
《漫畫：什么是 B+ 樹？》

數據庫索引

數據庫以 B 樹或者 B+ 樹格式來儲存的數據的，一張表是根據主鍵來構建的樹的結構。因此如果想查找其他字段，就需要建
立索引，我對于索引的理解是它就是以某個字段為關鍵字的 B 樹文件，通過這個 B 樹文件就能夠提高數據查找的效率。但是
由于我們需要維護的是平衡樹的結構，因此對于數據的寫入、修改、刪除就會變慢，因為這有可能會涉及到樹的平衡調整。

相關資料可以參考：
《深入淺出數據庫索引原理》
《數據庫的最簡單實現》

紅黑樹

紅黑樹是一種自平衡的二叉查找樹，它主要是為了解決不平衡的二叉查找樹的查找效率不高的缺點。紅黑樹保證了從根到葉子
節點的最長路徑不會超過最短路徑的兩倍。

紅黑樹的有具體的規則：

1.節點是紅色或黑色。

2.根節點是黑色。

3.每個葉子節點都是黑色的空節點（NIL節點）。

4 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)

5.從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。

當紅黑樹發生刪除和插入導致紅黑樹不滿足這些規則時，需要通過處理，使其重新滿足這些規則。

詳細資料可以參考：
《漫畫：什么是紅黑樹？》
《漫畫算法等精選文章目錄》

Huffman 樹

給定 n 權值作為 n 個葉子節點，構造一棵二叉樹，若這棵二叉樹的帶權路徑長度達到最小，則稱這樣的二叉樹為最優二叉
樹，也稱為 Huffman 樹。

利用 Huffman 樹對每一個字符編碼，該編碼又稱為 Huffman 編碼，Huffman 編碼是一種前綴編碼，即一個字符的編碼
不是另一個字符編碼的前綴。

性質：

對應一組權重構造出來的 Huffman 樹一般不是唯一的

Huffman 樹具有最小的帶權路徑長度

Huffman 樹中沒有度為1的結點

哈夫曼樹是帶權路徑長度最短的樹，路徑上權值較大的結點離根較近

Huffman 樹的帶權路徑長度 WPL 等于各葉子結點的帶權路徑長度之和

詳細資料可以參考：

《數據結構和算法—— Huffman 樹和 Huffman 編碼》
《詳細圖解哈夫曼 Huffman 編碼樹》

二叉查找樹

二叉查找樹是一種特殊的二叉樹，相對較小的值保存在左節點中，較大的值保存在右節點中，這一特性使得查找的效率很高，
對于數值型和非數值型數據，比如字母和字符串，都是如此。

實現樹節點類：

// 節點類，樹的節點 class Node {constructor(value) {this.value = value;this.left = null;this.right = null;}show() {console.log(this.value);} }

實現二叉查找樹類：

class BinarySearchTree {constructor() {this.root = null}}

實現樹的節點插入方法

節點插入的基本思想是將插入節點和當前節點做比較，如果比當前節點值小，并且沒有左子樹，那么將節點作為左葉子節點，
否則繼續和左子樹進行比較。如果比當前節點值大，并且沒有右子樹，則將節點作為右葉子節點，否則繼續和右子樹進行比較。
循環這個過程直到找到合適的插入位置。

insert(value) {let newNode = new Node(value);// 判斷根節點是否為空，如果不為空則遞歸插入到樹中if (this.root === null) {this.root = newNode;} else {this.insertNode(this.root, newNode);}}insertNode(node, newNode) {// 將插入節點的值與當前節點的進行比較，如果比當前節點小，則遞歸判斷左子樹，如果比當前節點大，則遞歸判斷右子樹。if (newNode.value < node.value) {if (node.left === null) {node.left = newNode;} else {this.insertNode(node.left, newNode);}} else {if (node.right === null) {node.right = newNode;} else {this.insertNode(node.right, newNode);}}}

通過遞歸實現樹的先序、中序、后序遍歷

// 先序遍歷通過遞歸實現// 先序遍歷則先打印當前節點，再遞歸打印左子節點和右子節點。preOrderTraverse() {this.preOrderTraverseNode(this.root);}preOrderTraverseNode(node) {if (node !== null) {node.show();this.preOrderTraverseNode(node.left);this.preOrderTraverseNode(node.right);}}// 中序遍歷通過遞歸實現// 中序遍歷則先遞歸打印左子節點，再打印當前節點，最后再遞歸打印右子節點。inOrderTraverse() {this.inOrderTraverseNode(this.root);}inOrderTraverseNode(node) {if (node !== null) {this.inOrderTraverseNode(node.left);node.show();this.inOrderTraverseNode(node.right);}}// 后序遍歷通過遞歸實現// 后序遍歷則先遞歸打印左子節點和右子節點，最后再打印當前節點。postOrderTraverse() {this.postOrderTraverseNode(this.root);}postOrderTraverseNode(node) {if (node !== null) {this.postOrderTraverseNode(node.left);this.postOrderTraverseNode(node.right);node.show();}}

通過循環實現樹的先序、中序、后序遍歷

// 先序遍歷通過循環實現// 通過棧來實現循環先序遍歷，首先將根節點入棧。然后進入循環，每次循環開始，當前節點出棧，打印當前節點，然后將// 右子節點入棧，再將左子節點入棧，然后進入下一循環，直到棧為空結束循環。preOrderTraverseByStack() {let stack = [];// 現將根節點入棧，開始遍歷stack.push(this.root);while (stack.length > 0) {// 從棧中獲取當前節點let node = stack.pop();// 執行節點操作node.show();// 判斷節點是否還有左右子節點，如果存在則加入棧中，注意，由于中序遍歷先序遍歷是先訪問根// 再訪問左和右子節點，因此左右子節點的入棧順序應該是反過來的if (node.right) {stack.push(node.right);}if (node.left) {stack.push(node.left);}}}// 中序遍歷通過循環實現// 中序遍歷先將所有的左子節點入棧，如果左子節點為 null 時，打印棧頂元素，然后判斷該元素是否有右子樹，如果有// 則將右子樹作為起點重復上面的過程，一直循環直到棧為空并且節點為空時。inOrderTraverseByStack() {let stack = [],node = this.root;// 中序遍歷是先左再根最后右// 所以首先應該先把最左邊節點遍歷到底依次 push 進棧// 當左邊沒有節點時，就打印棧頂元素，然后尋找右節點while (stack.length > 0 || node) {if (node) {stack.push(node);node = node.left;} else {node = stack.pop();node.show();node = node.right;}}}// 后序遍歷通過循環來實現// 使用兩個棧來是實現，先將根節點放入棧1中，然后進入循環，每次循環將棧頂元素加入棧2，再依次將左節點和右節點依次// 加入棧1中，然后進入下一次循環，直到棧1的長度為0。最后再循環打印棧2的值。postOrderTraverseByStack() {let stack1 = [],stack2 = [],node = null;// 后序遍歷是先左再右最后根// 所以對于一個棧來說，應該先 push 根節點// 然后 push 右節點，最后 push 左節點stack1.push(this.root);while (stack1.length > 0) {node = stack1.pop();stack2.push(node); if (node.left) {stack1.push(node.left);}if (node.right) {stack1.push(node.right);}}while (stack2.length > 0) {node = stack2.pop();node.show();}}

實現尋找最大最小節點值

// 尋找最小值，在最左邊的葉子節點上findMinNode(root) {let node = root;while (node && node.left) {node = node.left;}return node;}// 尋找最大值，在最右邊的葉子節點上findMaxNode(root) {let node = root;while (node && node.right) {node = node.right;}return node;}

實現尋找特定大小節點值

// 尋找特定值find(value) {return this.findNode(this.root, value);}findNode(node, value) {if (node === null) {return node;}if (value < node.value) {return this.findNode(node.left, value);} else if (value > node.value) {return this.findNode(node.right, value);} else {return node;}}

實現移除節點值

移除節點的基本思想是，首先找到需要移除的節點的位置，然后判斷該節點是否有葉節點。如果沒有葉節點，則直接刪除，如
果有一個葉子節點，則用這個葉子節點替換當前的位置。如果有兩個葉子節點，則去右子樹中找到最小的節點來替換當前節點。

// 移除指定值節點remove(value) {this.removeNode(this.root, value);}removeNode(node, value) {if (node === null) {return node;}// 尋找指定節點if (value < node.value) {node.left = this.removeNode(node.left, value);return node;} else if (value > node.value) {node.right = this.removeNode(node.right, value);return node;} else { // 找到節點// 第一種情況——沒有葉節點if (node.left === null && node.right === null) {node = null;return node;}// 第二種情況——一個只有一個子節點的節點，將節點替換為節點的子節點if (node.left === null) {node = node.right;return node;} else if (node.right === null) {node = node.left;}// 第三種情況——一個有兩個子節點的節點，去右子樹中找到最小的節點，用它的值來替換當前節點// 的值，保持樹的特性，然后將替換的節點去掉let aux = this.findMinNode(node.right);node.value = aux.value;node.right = this.removeNode(node.right, aux);return node;}}

求解二叉樹中兩個節點的最近公共祖先節點

求解二叉樹中的兩個節點的最近公共祖先節點可以分為三種情況來考慮（1）該二叉樹為搜索二叉樹 解決辦法，首先從根節點開始遍歷。如果根節點的值比兩個節點的值都大的情況下，則說明兩個節點的共同祖先存在于根節點的左子樹中，因此遞歸遍歷左子樹。反之，則遍歷右子樹。當當前節點的值比其中一個節點的值大，比其中一個節點的值小時，該節點則為兩個節點的最近公共祖先節點。（2）該二叉樹為普通二叉樹，但是每個節點含有指向父節點的指針。通過指向父節點的指針，我們可以通過節點得到它的所有父節點，該父節點列表可以看做是一個鏈表，因此求兩個節點的最近公共祖先節點就可以看做是求兩個鏈表的最近公共節點，以此來找到兩個節點的最近公共祖先節點。（3）該二叉樹為普通二叉樹，節點不含有指向父節點的指針。這種情況下，我們可以從根節點出發，分別得到根節點到兩個節點的路徑。然后遍歷兩條路徑，直到遇到第一個不相同的節點為止，這個時候該節點前面的那個節點則為兩個節點的最近公共祖先節點。

詳細資料可以參考：
《二叉樹中兩個節點的最近公共祖先節點》

鏈表

反轉單向鏈表

需要將一個單向鏈表反轉。思路很簡單，使用三個變量分別表示當前節點和當前節點的前后節點，雖然這題很簡單，但是卻是
一道面試常考題。

思路是從頭節點往后遍歷，先獲取下一個節點，然后將當前節點的 next 設置為前一個節點，然后再繼續循環。

var reverseList = function(head) {// 判斷下變量邊界問題if (!head || !head.next) return head;// 初始設置為空，因為第一個節點反轉后就是尾部，尾部節點指向 nulllet pre = null;let current = head;let next;// 判斷當前節點是否為空// 不為空就先獲取當前節點的下一節點// 然后把當前節點的 next 設為上一個節點// 然后把 current 設為下一個節點，pre 設為當前節點while(current) {next = current.next;current.next = pre;pre = current;current = next;}return pre; };

動態規劃

爬樓梯問題

有一座高度是10級臺階的樓梯，從下往上走，每跨一步只能向上1級或者2級臺階。要求用程序來求出一共有多少種走法？

遞歸方法分析

由分析可知，假設我們只差最后一步就能走上第10級階梯，這個時候一共有兩種情況，因為每一步只允許走1級或2級階梯，
因此分別為從8級階梯和從9九級階梯走上去的情況。因此從0到10級階梯的走法數量就等于從0到9級階梯的走法數量加上
從0到8級階梯的走法數量。依次類推，我們可以得到一個遞歸關系，遞歸結束的標志為從0到1級階梯的走法數量和從0到
2級階梯的走法數量。

代碼實現

function getClimbingWays(n) {if (n < 1) {return 0;}if (n === 1) {return 1;}if (n === 2) {return 2;}return getClimbingWays(n - 1) + getClimbingWays(n - 2); }

使用這種方法時整個的遞歸過程是一個二叉樹的結構，因此該方法的時間復雜度可以近似的看為 O(2^n)，空間復雜度
為遞歸的深度 O(logn)。

備忘錄方法

分析遞歸的方法我們可以發現，其實有很多的計算過程其實是重復的，因此我們可以使用一個數組，將已經計算出的值給
保存下來，每次計算時，先判斷計算結果是否已經存在，如果已經存在就直接使用。

代碼實現

let map = new Map();function getClimbingWays(n) {if (n < 1) {return 0;}if (n === 1) {return 1;}if (n === 2) {return 2;}if (map.has(n)) {return map.get(n);} else {let value = getClimbingWays(n - 1) + getClimbingWays(n - 2);map.set(n, value);return value;} }

通過這種方式，我們將算法的時間復雜度降低為 O(n)，但是增加空間復雜度為 O(n)

迭代法

通過觀察，我們可以發現每一個值其實都等于它的前面兩個值的和，因此我們可以使用自底向上的方式來實現。

代碼實現

function getClimbingWays(n) {if (n < 1) {return 0;}if (n === 1) {return 1;}if (n === 2) {return 2;}let a = 1,b = 2,temp = 0;for (let i = 3; i <= n; i++) {temp = a + b;a = b;b = temp;}return temp; }

通過這種方式我們可以將算法的時間復雜度降低為 O(n)，并且將算法的空間復雜度降低為 O(1)。

詳細資料可以參考：
《漫畫：什么是動態規劃？（整合版）》

經典筆試題

1. js 實現一個函數，完成超過范圍的兩個大整數相加功能

主要思路是通過將數字轉換為字符串，然后每個字符串在按位相加。function bigNumberAdd(number1, number2) {let result = "", // 保存最后結果carry = false; // 保留進位結果// 將字符串轉換為數組number1 = number1.split("");number2 = number2.split("");// 當數組的長度都變為0，并且最終不再進位時，結束循環while (number1.length || number2.length || carry) {// 每次將最后的數字進行相加，使用~~的好處是，即使返回值為 undefined 也能轉換為 0carry += ~~number1.pop() + ~~number2.pop();// 取加法結果的個位加入最終結果result = carry % 10 + result;// 判斷是否需要進位，true 和 false 的值在加法中會被轉換為 1 和 0carry = carry > 9;}// 返回最終結果return result; }

詳細資料可以參考：
《JavaScript實現超范圍的數相加》
《js 實現大整數加法》

2. js 如何實現數組扁平化？

// 這一種方法通過遞歸來實現，當元素為數組時遞歸調用，兼容性好 function flattenArray(array) {if (!Array.isArray(array)) return;let result = [];result = array.reduce(function (pre, item) {// 判斷元素是否為數組，如果為數組則遞歸調用，如果不是則加入結果數組中return pre.concat(Array.isArray(item) ? flattenArray(item) : item);}, []);return result; }// 這一種方法是利用了 toString 方法，它的一個缺點是改變了元素的類型，只適合于數組中元素都是整數的情況 function flattenArray(array) {return array.toString().split(",").map(function (item) {return +item;}) }

詳細資料可以參考：
《JavaScript專題之數組扁平化》

3. js 如何實現數組去重？

function unique(array) {if (!Array.isArray(array) || array.length <= 1) return;var result = [];array.forEach(function (item) {if (result.indexOf(item) === -1) {result.push(item);}})return result; }function unique(array) {if (!Array.isArray(array) || array.length <= 1) return;return [...new Set(array)]; }

詳細資料可以參考：
《JavaScript專題之數組去重》

4. 如何求數組的最大值和最小值？

var arr = [6, 4, 1, 8, 2, 11, 23]; console.log(Math.max.apply(null, arr))

詳細資料可以參考：
《JavaScript專題之如何求數組的最大值和最小值》

5. 如何求兩個數的最大公約數？

基本思想是采用輾轉相除的方法，用大的數去除以小的那個數，然后再用小的數去除以的得到的余數，一直這樣遞歸下去， 直到余數為0時，最后的被除數就是兩個數的最大公約數。function getMaxCommonDivisor(a, b) {if (b === 0) return a;return getMaxCommonDivisor(b, a % b); }

6. 如何求兩個數的最小公倍數？

基本思想是采用將兩個數相乘，然后除以它們的最大公約數function getMinCommonMultiple(a, b){return a * b / getMaxCommonDivisor(a, b); }

詳細資料可以參考：
《百度 web 前端面試題之求兩個數的最大公約數和最小公倍數》

7. 實現 IndexOf 方法？

function indexFun(array, val) {if (!Array.isArray(array)) return;let length = array.length;for (let i = 0; i < length; i++) {if (array[i] === val) {return i;}}return -1; }

8. 判斷一個字符串是否為回文字符串？

function isPalindrome(str) {let reg = /[\W_]/g, // 匹配所有非單詞的字符以及下劃線newStr = str.replace(reg, "").toLowerCase(), // 替換為空字符并將大寫字母轉換為小寫reverseStr = newStr.split("").reverse().join(""); // 將字符串反轉return reverseStr === newStr; }

9. 實現一個累加函數的功能比如 sum(1,2,3)(2).valueOf()

function sum(...args) {let result = 0;result = args.reduce(function (pre, item) {return pre + item; }, 0);let add = function (...args) {result = args.reduce(function (pre, item) {return pre + item;}, result);return add; };add.valueOf = function () {console.log(result); }return add; }

10. 使用 reduce 方法實現 forEach、map、filter

// forEachfunction forEachUseReduce(array, handler) {array.reduce(function (pre, item, index) {handler(item, index);});}// mapfunction mapUseReduce(array, handler) {let result = [];array.reduce(function (pre, item, index) {let mapItem = handler(item, index);result.push(mapItem);});return result;}// filterfunction filterUseReduce(array, handler) {let result = [];array.reduce(function (pre, item, index) {if (handler(item, index)) {result.push(item);}});return result;}

11. 設計一個簡單的任務隊列，要求分別在 1,3,4 秒后打印出 “1”, “2”, “3”

class Queue {constructor() {this.queue = [];this.time = 0;}addTask(task, t) {this.time += t;this.queue.push([task, this.time]);return this;}start() {this.queue.forEach(item => {setTimeout(() => {item[0]();}, item[1]);})}}

12. 如何查找一篇英文文章中出現頻率最高的單詞？

function findMostWord(article) {// 合法性判斷if (!article) return;// 參數處理article = article.trim().toLowerCase();let wordList = article.match(/[a-z]+/g),visited = [],maxNum = 0,maxWord = "";article = " " + wordList.join(" ") + " ";// 遍歷判斷單詞出現次數wordList.forEach(function (item) {if (visited.indexOf(item) < 0) {let word = new RegExp(" " + item + " ", "g"),num = article.match(word).length;if (num > maxNum) {maxNum = num;maxWord = item;}}});return maxWord + " " + maxNum;}

常見面試智力題總結

1. 時針與分針夾角度數問題？

分析：

當時間為 m 點 n 分時，其時針與分針夾角的度數為多少？我們可以這樣考慮，分針每走一格為 6 度，分針每走一格對應的時針會走 0.5 度。時針每走一格為 30 度。因此，時針走過的度數為 m * 30 + n * 0.5，分針走過的度數為 n * 6。因此時針與分針的夾角度數為 |m * 30 + n * 0.5 - n * 6|;

答案：

因此時針與分針的夾角度數為 |m * 30 + n * 0.5 - n * 6|;

詳細資料參考：
《面試智力題 — 時針與分針夾角度數問題》

2. 用3升，5升杯子怎么量出4升水？

（1）將 5 升杯子裝滿水，然后倒入 3 升杯子中，之后 5 升杯子還剩 2 升水。（2）將 3 升杯子的水倒出，然后將 5 升杯子中的 2 升水倒入 3 升杯子中。（3）將 5 升杯子裝滿水，然后向 3 升杯子中倒水，直到 3 升杯子裝滿為止，此時 5 升杯子中就還剩 4 升水。

3. 四個藥罐中有一個渾濁的藥罐，渾濁的每片藥片都比其他三個干凈的藥罐多一克，如何只用一次天平找出渾濁的藥罐？

由于渾濁的每片藥片比正常藥片都多出了一克，因此我認為可以通過控制藥片的數量來實現判斷。（1）首先將每個藥罐進行編號，分別標記為 1、2、3、4 號藥罐。（2）然后從 1 號藥罐中取出 1 片藥片，從 2 號藥罐中取出 2 片藥片，從 3 號藥罐中取出 3 片藥片，從 4 號藥罐中取出 4片藥片。（3）將 10 片藥片使用天平稱重，藥片的重量比正常重量多出幾克，就是哪一號藥罐的問題。

4. 四張卡片，卡片正面是數字，反面是字母。現在桌上四張卡片，狀態為 a 1 b 2 現在我想要證明 a 的反面必然是 1 ，我只能翻兩張牌，我翻哪兩張？

我認為證明 a 的反面一定是 1 的充要條件為 a 的反面為 1，并且 2 的反面不能為 a，因此應該翻 a 和 2 兩張牌。

5. 賽馬問題，25 匹馬，5 個賽道，最少幾次能選出最快的三匹馬？

我認為一共至少需要 7 次才能選出最快的三匹馬。（1）首先，我們將 25 匹馬分為 5 組，每組進行比賽，選出每組最快的三匹馬，其余的馬由于已經不可能成為前三了，因此可以直接淘汰掉，那么我們現在還剩下了 15 匹馬。（2）然后我們將 5 組中的第一名來進行一輪比賽，最終的結果能夠確定最快的馬一定是第一名，四五名的馬以及它們對應組的其余馬就可以淘汰掉了，因為它們已經沒有進入前三的機會了。并且第二名那一組的第三名和第三組的第二第三名都可以淘汰掉了，它們也沒有進入前三的機會了。因此我們最終剩下了第一名那一組的二三名和第二名那一組的一二名，以及第三名一共 5 匹馬，它們都有競爭最快第二第三的機會。（3）最后一次對最后的 5 匹馬進行比賽，選擇最快的一二名作為最終結果的二三名，因此就能夠通過 7 次比較，選擇出最快的馬。

6. 五隊夫婦參加聚會，每個人不能和自己的配偶握手，只能最多和他人握手一次。A問了其他人，發現每個人的握手次數都不同，那么A的配偶握手了幾次？

（1）由于每個人不能和自己的配偶握手，并且最多只能和他人握手一次，因此一個人最多能握 8 次手。（2）因為 A 問了除自己配偶的其他人，每個人的握手次數都不同。因此一共有九種握手的情況，由于一個人最多只能握 8 次手，因此握手的情況分別為 0、1、2、3、4、5、6、7、8 這九種情況。（3）我們首先分析握了 8 次手的人，由于他和除了自己配偶的每一個人都握了一次手，因此其他人的握手次數都不為 0，因此只有他的配偶握手次數為0，由此我們可以知道握手次數為 8 的人和握手次數為 0 的人是配偶。（4）我們再來分析握了 7 次手的人，他和除了握了 0 次手以外的人都握了一次手，由于握了 8 次手的人和其余人也都握了一次手，因此其他人的握手次數至少為 2 ，因此只有他的配偶的握手次數才能為 1。由此我們可以知道握手次數為 7 的人和握手次數為 1 的人是配偶。（5）依次可以類推，握手次數為 6 的人和握手次數為 2 的人為配偶，握手次數為 5 的人和握手次數為 3 的人為配偶。（6）最終剩下了握手次數為 4 的人，按照規律我們可以得知他的配偶的握手次數也為4。（7）由于 A 和其他人的握手次數都不同，因此我們可以得知握手次數為 4 的人就是 A。因此他的配偶的握手次數為 4 。

7. 你只能帶行走 60 公里的油，只能在起始點加油，如何穿過 80 公里的沙漠？

（1）先走到離起點 20 公里的地方，然后放下 20 公里的油在這，然后返回起點加油。（2）當第二次到達這時，車還剩 40 公里的油，加上上一次放在這的 20 公里的油，一共就有 60 公里的油，能夠走完剩下的路程。

8. 燒一根不均勻的繩要用一個小時，如何用它來判斷一個小時十五分鐘？

一共需要三根繩子，假設分別為 1、2、3 號繩子，每個繩子一共有 A、B 兩端。（1）首先點燃 1 號繩子的 A、B 兩端，然后點燃 2 號繩子的 A 端。（2）當 1 號繩子燃盡時，此時過去了半小時，然后同時點燃 2 號繩子的 B 端。（3）當 2 號繩子燃盡時，此時又過去了 15 分鐘，然后同時點燃 3 號繩子的 A、B 兩端。（4）當 3 號繩子燃盡時，又過去了半小時，以此一共加起來過去了一個小時十五分鐘。

9. 有7克、2克砝碼各一個，天平一只，如何只用這些物品三次將140克的鹽分成50、90克各一份？

（1） 第一次用 7 克砝碼和 2 克砝碼稱取 9 克鹽。（2） 第二次再用第一次稱取的鹽和砝碼稱取 16 克鹽。（3） 第三次再用前兩次稱取的鹽和砝碼稱取 25 克鹽，這樣就總共稱取了 50 克鹽，剩下的就是 90 克。

10. 有一輛火車以每小時15公里的速度離開洛杉磯直奔紐約，另一輛火車以第?小時20公里的速度從紐約開往洛杉磯。如果有一只鳥，以外30公里每小時的速度和?兩輛火車現時啟動，從洛杉磯出發，碰到另輛車后返回，依次在兩輛火車來回的飛行，直道兩面輛火車相遇，請問，這只小鳥飛行了多長距離？

由于小鳥一直都在飛，直到兩車相遇時才停下來。因此小鳥飛行的時間為兩車相遇的時間，由于兩車是相向而行，因此兩車相遇的時間為總路程除以兩車的速度之和，然后再用飛行的時間去乘以小鳥的速度，就能夠得出小鳥飛行的距離。

11. 你有兩個罐子，50個紅色彈球，50個藍色彈球，隨機選出一個罐子，隨機選取出一個彈球放入罐子，怎么給紅色彈球最大的選中機會？在你的計劃中，得到紅球的準確幾率是多少？

第一個罐子里放一個紅球，第二個罐子里放剩余的球，這樣概率接近75%，這是概率最大的方法

12. 假設你有8個球，其中一個略微重一些，但是找出這個球的惟一方法是將兩個球放在天平上對比。最少要稱多少次才能找出這個較重的球？

最少兩次可以稱出。首先將 8 個球分為 3 組，其中兩組為 3 個球，一組為 2 個球。第一次將兩組三個的球進行比較，如果兩邊相等，則說明重的球在最后一組里。第二次將最后一組的球進行比較即可。如果兩邊不等，則說明重的球在較重的一邊，第二次只需從這一組中隨機取兩球出來比較即可判斷。

13. 在房里有三盞燈，房外有三個開關，在房外看不見房內的情況，你只能進門一次，你用什么方法來區分那個開關控制那一盞燈？

（1）首先打開一盞燈 10 分鐘，然后打開第二盞。（2）進入房間，看看那盞燈亮，摸摸那盞燈熱，熱的是第一個開關打開的，亮的是第二個開關打開的，而剩下的就是第三個開關打開的。

14. 他們都各自買了兩對黑襪和兩對白襪，八對襪子的布質、大小完全相同，而每對襪子都有一張商標紙連著。兩位盲人不小心將八對襪子混在一起。他們每人怎樣才能取回黑襪和白襪各兩對呢？

將每一對襪子分開，一人拿一只襪子，因為襪子不分左右腳的，因此最后每個人都能取回白襪和黑襪兩對。

15. 有三筐水果，一筐裝的全是蘋果，第二筐裝的全是橘子，第三筐是橘子與蘋果混在一起。筐上的標簽都是騙人的，（就是說筐上的標簽都是錯的）你的任務是拿出其中一筐，從里面只拿一只水果，然后正確寫出三筐水果的標簽。

從混合標簽里取出一個水果，取出的是什么水果，就寫上相應的標簽。對應水果標簽的筐的標簽改為另一種水果。另一種水果標簽的框改為混合。

16. 一個班級60%喜歡足球，70%喜歡籃球，80%喜歡排球，問即三種球都喜歡占比有多少？

（1）首先確定最多的一種情況，就是 60% 喜歡足球的人同時也喜歡籃球和排球，此時為三種球都喜歡的人的最大比例。（2）然后確定最小的一種情況，根據題目可以知道有 40%的人不喜歡足球，30%的人不喜歡籃球，20%的人不喜歡排球，因此有最多90% 的人三種球中有一種球不喜歡，因此三種球都喜歡的人的最小比例為 10%。因此三種球都喜歡的人占比為 10%-60%

17. 五只雞五天能下五個蛋，一百天下一百個蛋需要多少只雞？

五只雞五天能下五個蛋，平均下來五只雞每天能下一個蛋，因此五只雞一百天就能夠下一百個蛋。

更多的智力題可以參考：
《經典面試智力題200+題和解答》

劍指 offer 思路總結

本部分主要是筆者在練習劍指 offer 時所做的筆記，如果出現錯誤，希望大家指出！

題目

1. 二維數組中的查找

題目： 在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的 一個二維數組和一個整數，判斷數組中是否含有該整數。思路：（1）第一種方式是使用兩層循環依次遍歷，判斷是否含有該整數。這一種方式最壞情況下的時間復雜度為 O(n^2)。（2）第二種方式是利用遞增序列的特點，我們可以從二維數組的右上角開始遍歷。如果當前數值比所求的數要小，則將位置向下移動，再進行判斷。如果當前數值比所求的數要大，則將位置向左移動，再進行判斷。這一種方式最壞情況下的時間復雜度為 O(n)。

2. 替換空格

題目：請實現一個函數，將一個字符串中的空格替換成“%20”。例如，當字符串為 We Are Happy.則經過替換之后的字符串為 We%20 Are%20Happy思路：使用正則表達式，結合字符串的 replace 方法將空格替換為 “%20”str.replace(/\s/g,"%20")

3. 從尾到頭打印鏈表

題目：輸入一個鏈表，從尾到頭打印鏈表每個節點的值。思路：利用棧來實現，首先根據頭結點以此遍歷鏈表節點，將節點加入到棧中。當遍歷完成后，再將棧中元素彈出并打印，以此來實現。棧的 實現可以利用 Array 的 push 和 pop 方法來模擬。

4. 重建二叉樹

題目：輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字。例如輸 入前序遍歷序列 {1,2,4,7,3,5,6,8} 和中序遍歷序列 {4,7,2,1,5,3,8,6}，則重建二叉樹并返回。思路：利用遞歸的思想來求解，首先先序序列中的第一個元素一定是根元素。然后我們去中序遍歷中尋找到該元素的位置，找到后該元素的左 邊部分就是根節點的左子樹，右邊部分就是根節點的右子樹。因此我們可以分別截取對應的部分進行子樹的遞歸構建。使用這種方式的 時間復雜度為 O(n)，空間復雜度為 O(logn)。

5. 用兩個棧實現隊列

題目：用兩個棧來實現一個隊列，完成隊列的 Push 和 Pop 操作。思路：隊列的一個基本特點是，元素先進先出。通過兩個棧來模擬時，首先我們將兩個棧分為棧1和棧2。當執行隊列的 push 操作時，直接 將元素 push 進棧1中。當隊列執行 pop 操作時，首先判斷棧2是否為空，如果不為空則直接 pop 元素。如果棧2為空，則將棧1中 的所有元素 pop 然后 push 到棧2中，然后再執行棧2的 pop 操作。擴展：當使用兩個長度不同的棧來模擬隊列時，隊列的最大長度為較短棧的長度的兩倍。

6. 旋轉數組的最小數字

題目：把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。 輸入一個非遞減排序的數組的一個旋轉，輸出旋轉數組的 最小元素。 例如數組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該數組的最小值為1。 NOTE：給出的所有元素都大于0，若數組大 小為0，請返回0。思路：（1）我們輸入的是一個非遞減排序的數組的一個旋轉，因此原始數組的值遞增或者有重復。旋轉之后原始數組的值一定和一個值相鄰，并且不滿足遞增關系。因此我們就可以進行遍歷，找到不滿足遞增關系的一對值，后一個值就是旋轉數組的最小數字。（2）二分法

相關資料可以參考：
《旋轉數組的最小數字》

7. 斐波那契數列

題目：大家都知道斐波那契數列，現在要求輸入一個整數 n，請你輸出斐波那契數列的第 n 項。 n<=39思路：斐波那契數列的規律是，第一項為0，第二項為1，第三項以后的值都等于前面兩項的和，因此我們可以通過循環的方式，不斷通過疊 加來實現第 n 項值的構建。通過循環而不是遞歸的方式來實現，時間復雜度降為了 O(n)，空間復雜度為 O(1)。

8. 跳臺階

題目：一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個 n 級的臺階總共有多少種跳法。思路：跳臺階的問題是一個動態規劃的問題，由于一次只能夠跳1級或者2級，因此跳上 n 級臺階一共有兩種方案，一種是從 n-1 跳上，一 種是從 n-2 級跳上，因此 f(n) = f(n-1) + f(n-2)。和斐波那契數列類似，不過初始兩項的值變為了 1 和 2，后面每項的值等于前面兩項的和。

9. 變態跳臺階

題目：一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上 n 級。求該青蛙跳上一個 n 級的臺階總共有多少種跳法。思路：變態跳臺階的問題同上一個問題的思考方案是一樣的，我們可以得到一個結論是，每一項的值都等于前面所有項的值的和。f(1) = 1 f(2) = f(2-1) + f(2-2) //f(2-2) 表示2階一次跳2階的次數。 f(3) = f(3-1) + f(3-2) + f(3-3) ... f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n) 再次總結可得| 1 ,(n=0 ) f(n) = | 1 ,(n=1 )| 2*f(n-1),(n>=2)

10. 矩形覆蓋

題目：我們可以用 2*1 的小矩形橫著或者豎著去覆蓋更大的矩形。請問用 n 個 2*1 的小矩形無重疊地覆蓋一個 2*n 的大矩形，總共有多少種方法？思路：依舊是斐波那契數列的應用

11. 二進制中1的個數

題目：輸入一個整數，輸出該數二進制表示中1的個數。其中負數用補碼表示。思路：一個不為 0 的整數的二進制表示，一定會有一位為1。我們找到最右邊的一位1，當我們將整數減去1時，最右邊的一位1變為0，它后面的所有位都取反，因此將減一后的值與原值相與，我們就會能夠消除最右邊的一位1。因此判斷一個二進制中1的個數，我們可以判斷這個數可以經歷多少次這樣的過程。如：1100&1011=1000

12. 數值的整數次方

題目：給定一個 double 類型的浮點數 base 和 int 類型的整數 exponent。求 base 的 exponent 次方。思路：首先我們需要判斷 exponent 正負和零取值三種情況，根據不同的情況通過遞歸來實現。

13. 調整數組順序使奇數位于偶數前面

題目：輸入一個整數數組，實現一個函數來調整該數組中數字的順序，使得所有的奇數位于數組的前半部分，所有的偶數位于位于數組的后半部分，并保證奇數和奇數，偶數和偶數之間的相對位置不變。思路：由于需要考慮到調整之后的穩定性，因此我們可以使用輔助數組的方式。首先對數組中的元素進行遍歷，每遇到一個奇數就將它加入到奇數輔助數組中，每遇到一個偶數，就將它將入到偶數輔助數組中。最后再將兩個數組合并。這一種方法的時間復雜度為 O(n)，空間復雜度為 O(n)。

14. 鏈表中倒數第 k 個節點

題目：輸入一個鏈表，輸出該鏈表中倒數第 k 個結點。思路：使用兩個指針，先讓第一個和第二個指針都指向頭結點，然后再讓第二個指針走 k-1 步，到達第 k 個節點。然后兩個指針同時向后移動，當第二個指針到達末尾時，第一個指針指向的就是倒數第 k 個節點了。

15. 反轉鏈表

題目：輸入一個鏈表，反轉鏈表后，輸出鏈表的所有元素。思路：通過設置三個變量 pre、current 和 next，分別用來保存前繼節點、當前節點和后繼結點。從第一個節點開始向后遍歷，首先將當前節點的后繼節點保存到 next 中，然后將當前節點的后繼節點設置為 pre，然后再將 pre 設置為當前節點，current 設置為 next 節點，實現下一次循環。

16. 合并兩個排序的鏈表

題目：輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規則。思路：通過遞歸的方式，依次將兩個鏈表的元素遞歸進行對比。

17. 樹的子結構

題目：輸入兩棵二叉樹A、B，判斷 B 是不是 A 的子結構。（ps：我們約定空樹不是任意一個樹的子結構）思路：通過遞歸的思想來解決第一步首先從樹 A 的根節點開始遍歷，在左右子樹中找到和樹 B 根結點的值一樣的結點 R 。第二步兩棵樹同時從 R 節點和根節點以相同的遍歷方式進行遍歷，依次比較對應的值是否相同，當樹 B 遍歷結束時，結束比較。

18. 二叉樹的鏡像

題目：操作給定的二叉樹，將其變換為源二叉樹的鏡像。 思路：從根節點開始遍歷，首先通過臨時變量保存左子樹的引用，然后將根節點的左右子樹的引用交換。然后再遞歸左右節點的子樹交換。

19. 順時針打印矩陣

題目：輸入一個矩陣，按照從外向里以順時針的順序依次打印出每一個數字，例如，如果輸入如下矩陣： 1 2 3 45 6 7 8 9 10 11 12 13 14 15 16 則依次打印出數字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10思路：（1）根據左上角和右下角可以定位出一次要旋轉打印的數據。一次旋轉打印結束后，往對角分別前進和后退一個單位，可以確定下一次需要打印的數據范圍。（2）使用模擬魔方逆時針解法，每打印一行，則將矩陣逆時針旋轉 90 度，打印下一行，依次重復。

20. 定義一個棧，實現 min 函數

題目：定義棧的數據結構，請在該類型中實現一個能夠得到棧最小元素的 min 函數。思路：使用一個輔助棧，每次將數據壓入數據棧時，就把當前棧里面最小的值壓入輔助棧當中。這樣輔助棧的棧頂數據一直是數據棧中最小的值。

21. 棧的壓入彈出

題目：輸入兩個整數序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序。假設壓入棧的所有數字均不相等。例如序列 1,2,3,4,5 是某棧的壓入順序，序列 4,5,3,2,1 是該壓棧序列對應的一個彈出序列，但 4,3,5,1,2 就不可能是該壓棧序列的彈出序列。（注意：這兩個序列的長度是相等的）思路：我們可以使用一個輔助棧的方式來實現，首先遍歷壓棧順序，依次將元素壓入輔助棧中，每次壓入元素后我們首先判斷該元素是否與出棧順序中的此刻位置的元素相等，如果不相等，則將元素繼續壓棧，如果相等，則將輔助棧中的棧頂元素出棧，出棧后，將出棧順序中的位置后移一位繼續比較。當壓棧順序遍歷完成后，如果輔助棧不為空，則說明該出棧順序不正確。

22. 從上往下打印二叉樹

題目：從上往下打印出二叉樹的每個節點，同層節點從左至右打印。思路：本質上是二叉樹的層序遍歷，可以通過隊列來實現。首先將根節點入隊。然后對隊列進行出隊操作，每次出隊時，將出隊元素的左右子節點依次加入到隊列中，直到隊列長度變為 0 時，結束遍歷。

23. 二叉搜索樹的后序遍歷

題目：輸入一個整數數組，判斷該數組是不是某二叉搜索樹的后序遍歷的結果。如果是則輸出 Yes，否則輸出 No。假設輸入的數組的任意兩個數字都互不相同。思路：對于一個合法而二叉樹的后序遍歷來說，最末尾的元素為根元素。該元素前面的元素可以劃分為兩個部分，一部分為該元素的左子樹，所有元素的值比根元素小，一部分為該元素的右子樹，所有的元素的值比該根元素大。并且每一部分都是一個合法的后序序列，因此我們可以利用這些特點來遞歸判斷。

24. 二叉樹中和為某一值路徑

題目：輸入一顆二叉樹和一個整數，打印出二叉樹中結點值的和為輸入整數的所有路徑。路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。思路：通過對樹進行深度優先遍歷，遍歷時保存當前節點的值并判斷是否和期望值相等，如果遍歷到葉節點不符合要求則回退處理。

25. 復雜鏈表的復制

題目：輸入一個復雜鏈表（每個節點中有節點值，以及兩個指針，一個指向下一個節點，另一個特殊指針指向任意一個節點），返回結果為復制后復雜鏈表的 head。（注意，輸出結果中請不要返回參數中的節點引用，否則判題程序會直接返回空）思路：（1）第一種方式，首先對原有鏈表每個節點進行復制，通過 next 連接起來。然后當鏈表復制完成之后，再來設置每個節點的 random 指針，這個時候每個節點的 random 的設置都需要從頭結點開始遍歷，因此時間的復雜度為 O(n^2)。（2）第二種方式，首先對原有鏈表每個節點進行復制，并且使用 Map 以鍵值對的方式將原有節點和復制節點保存下來。當鏈表復制完成之后，再來設置每個節點的 random 指針，這個時候我們通過 Map 中的鍵值關系就可以獲取到對應的復制節點，因此不必再從頭結點遍歷，將時間的復雜度降低為了 O(n)，但是空間復雜度變為了 O(n)。這是一種以空間換時間的做法。（3）第三種方式，首先對原有鏈表的每個節點進行復制，并將復制后的節點加入到原有節點的后面。當鏈表復制完成之后，再進行random 指針的設置，由于每個節點后面都跟著自己的復制節點，因此我們可以很容易的獲取到 random 指向對應的復制節點。最后再將鏈表分離，通過這種方法我們也能夠將時間復雜度降低為 O(n)。

26. 二叉搜索樹與雙向鏈表

題目：輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只能調整樹中結點指針的指向。思路：需要生成一個排序的雙向列表，那么我們應該通過中序遍歷的方式來調整樹結構，因為只有中序遍歷，返回才是一個從小到大的排序序列。基本的思路是我們首先從根節點開始遍歷，先將左子樹調整為一個雙向鏈表，并將左子樹雙向鏈表的末尾元素的指針指向根節點，并將根節點的左節點指向末尾節點。再將右子樹調整為一個雙向鏈表，并將右子樹雙向鏈表的首部元素的指針指向根元素，再將根節點的右節點指向首部節點。通過對左右子樹遞歸調整，因此來實現排序的雙向鏈表的構建。

27. 字符串的排列

題目：輸入一個字符串，按字典序打印出該字符串中字符的所有排列。例如輸入字符串 abc，則打印出由字符 a,b,c 所能排列出來的所有字符串 abc,acb,bac,bca,cab 和 cba。輸入描述：輸入一個字符串，長度不超過9（可能有字符重復），字符只包括大小寫字母。思路：我們可以把一個字符串看做是兩個部分，第一部分為它的第一個字符，第二部分是它后面的所有字符。求整個字符串的一個全排列，可以看做兩步，第一步是求所有可能出現在第一個位置的字符，即把第一個字符和后面的所有字符交換。第二步就是求后面所有字符的一個全排列。因此通過這種方式，我們可以以遞歸的思路來求出當前字符串的全排列。

詳細資料可以參考：
《字符串的排列》

28. 數組中出現次數超過一半的數字

題目：數組中有一個數字出現的次數超過數組長度的一半。請找出這個數字。例如輸入一個長度為9的數組{1,2,3,2,2,2,5,4,2}。由于數字2在數組中出現了5次，超過數組長度的一半，因此輸出2。如果不存在則輸出0。思路：（1）對數組進行排序，排序后的中位數就是所求數字。這種方法的時間復雜度取決于我們采用的排序方法的時間復雜度，因此最快為O(nlogn)。（2）由于所求數字的數量超過了數組長度的一半，因此排序后的中位數就是所求數字。因此我們可以將問題簡化為求一個數組的中位數問題。其實數組并不需要全排序，只需要部分排序。我們通過利用快排中的 partition 函數來實現，我們現在數組中隨機選取一個數字，而后通過 partition 函數返回該數字在數組中的索引 index，如果 index 剛好等于 n/2，則這個數字便是數組的中位數，也即是要求的數，如果 index 大于 n/2，則中位數肯定在 index的左邊，在左邊繼續尋找即可，反之在右邊尋找。這樣可以只在 index 的一邊尋找，而不用兩邊都排序，減少了一半排序時間，這種方法的時間復雜度為 O(n)。（3）由于該數字的出現次數比所有其他數字出現次數的和還要多，因此可以考慮在遍歷數組時保存兩個值：一個是數組中的一個數字，一個是次數。當遍歷到下一個數字時，如果下一個數字與之前保存的數字相同，則次數加1，如果不同，則次數減1，如果次數為0，則需要保存下一個數字，并把次數設定為1。由于我們要找的數字出現的次數比其他所有數字的出現次數之和還要大，則要找的數字肯定是最后一次把次數設為1時對應的數字。該方法的時間復雜度為O(n)，空間復雜度為 O(1)。

詳細資料可以參考：
《出現次數超過一半的數字》

29. 最小的 K 個數

題目：輸入 n 個整數，找出其中最小的 K 個數。例如輸入 4,5,1,6,2,7,3,8 這8個數字，則最小的4個數字是 1,2,3,4 。思路：（1）第一種思路是首先將數組排序，排序后再取最小的 k 個數。這一種方法的時間復雜度取決于我們選擇的排序算法的時間復雜度，最好的情況下為 O(nlogn)。（2）第二種思路是由于我們只需要獲得最小的 k 個數，這 k 個數不一定是按序排序的。因此我們可以使用快速排序中的 partition函數來實現。每一次選擇一個樞紐值，將數組分為比樞紐值大和比樞紐值小的兩個部分，判斷樞紐值的位置，如果該樞紐值的位置為 k-1 的話，那么樞紐值和它前面的所有數字就是最小的 k 個數。如果樞紐值的位置小于 k-1 的話，假設樞紐值的位置為 n-1，那么我們已經找到了前 n 小的數字了，我們就還需要到后半部分去尋找后半部分 k-n 小的值，進行劃分。當該樞紐值的位置比 k-1大時，說明最小的 k 個值還在左半部分，我們需要繼續對左半部分進行劃分。這一種方法的平均時間復雜度為 O(n)。（3）第三種方法是維護一個容量為 k 的最大堆。對數組進行遍歷時，如果堆的容量還沒有達到 k ，則直接將元素加入到堆中，這就相當于我們假設前 k 個數就是最小的 k 個數。對 k 以后的元素遍歷時，我們將該元素與堆的最大值進行比較，如果比最大值小，那么我們則將最大值與其交換，然后調整堆。如果大于等于堆的最大值，則繼續向后遍歷，直到數組遍歷完成。這一種方法的平均時間復雜度為 O(nlogk)。

詳細資料可以參考：
《尋找最小的 k 個數》

30. 連續子數組的最大和

題目：HZ 偶爾會拿些專業問題來忽悠那些非計算機專業的同學。今天測試組開完會后，他又發話了:在古老的一維模式識別中，常常需要計算連續子向量的最大和,當向量全為正數的時候，問題很好解決。但是，如果向量中包含負數，是否應該包含某個負數，并期望旁邊的正數會彌補它呢？例如：{6,-3,-2,7,-15,1,2,2}，連續子向量的最大和為8（從第0個開始，到第3個為止）。你會不會被他忽悠住？（子向量的長度至少是1）思路：（1）第一種思路是直接暴力求解的方式，先以第一個數字為首往后開始疊加，疊加的過程中保存最大的值。然后再以第二個數字為首往后開始疊加，并與先前保存的最大的值進行比較。這一種方法的時間復雜度為 O(n^2)。（2）第二種思路是，首先我們觀察一個最大和的連續數組的規律，我們可以發現，子數組一定是以正數開頭的，中間包含了正負數。因此我們可以從第一個數開始向后疊加，每次保存最大的值。疊加的值如果為負數，則將疊加值初始化為0，因為后面的數加上負數只會更小，因此需要尋找下一個正數開始下一個子數組的判斷。一直往后判斷，直到這個數組遍歷完成為止，得到最大的值。使用這一種方法的時間復雜度為 O(n)。

詳細資料可以參考：
《連續子數組的最大和》

31. 整數中1出現的次數（待深入理解）

題目：求出1~13的整數中1出現的次數，并算出100~1300的整數中1出現的次數？為此他特別數了一下1~13中包含1的數字有1、10、11、12、13因此共出現6次，但是對于后面問題他就沒轍了。ACMer希望你們幫幫他，并把問題更加普遍化，可以很快的求出任意非負整數區間中1出現的次數。思路：（1）第一種思路是直接遍歷每個數，然后將判斷每個數中 1 的個數，一直疊加。（2）第二種思路是求出1出現在每位上的次數，然后進行疊加。

詳細資料可以參考：
《從1到n整數中1出現的次數：O(logn)算法》

32. 把數組排成最小的數

題目：輸入一個正整數數組，把數組里所有數字拼接起來排成一個數，打印能拼接出的所有數字中最小的一個。例如輸入數組{3，32，321}，則打印出這三個數字能排成的最小數字為321323。思路：（1）求出數組的全排列，然后對每個排列結果進行比較。（2）利用排序算法實現，但是比較時，比較的并不是兩個元素的大小，而是兩個元素正序拼接和逆序拼接的大小，如果逆序拼接的結果更小，則交換兩個元素的位置。排序結束后，數組的順序則為最小數的排列組合順序。

詳細資料可以參考：
《把數組排成最小的數》

33. 丑數（待深入理解）

題目：把只包含質因子2、3和5的數稱作丑數。例如6、8都是丑數，但14不是，因為它包含因子7。 習慣上我們把1當做是第一個丑數。求按從小到大的順序的第 N 個丑數。思路：（1）判斷一個數是否為丑數，可以判斷該數不斷除以2，最后余數是否為1。判斷該數不斷除以3，最后余數是否為1。判斷不斷除以5，最后余數是否為1。在不考慮時間復雜度的情況下，可以依次遍歷找到第 N 個丑數。（2）使用一個數組來保存已排序好的丑數，后面的丑數由前面生成。

34. 第一個只出現一次的字符

題目：在一個字符串（1<=字符串長度<=10000，全部由大寫字母組成）中找到第一個只出現一次的字符，并返回它的位置。思路：（1）第一種思路是，從前往后遍歷每一個字符。每遍歷一個字符，則將字符與后邊的所有字符依次比較，判斷是否含有相同字符。這一種方法的時間復雜度為 O(n^2)。（2）第二種思路是，首先對字符串進行一次遍歷，將字符和字符出現的次數以鍵值對的形式存儲在 Map 結構中。然后第二次遍歷時，去 Map 中獲取對應字符出現的次數，找到第一個只出現一次的字符。這一種方法的時間復雜度為 O(n)。

35. 數組中的逆序對

題目：在數組中的兩個數字，如果前面一個數字大于后面的數字，則這兩個數字組成一個逆序對。輸入一個數組，求出這個數組中的逆序對的總數 P。思路：（1）第一種思路是直接求解的方式，順序掃描整個數組。每掃描到一個數字的時候，逐個比較該數字和它后面的數字的大小。如果后面的數字比它小，則這兩個數字就組成了一個逆序對。假設數組中含有 n 個數字。由于每個數字都要和 O(n）個數字作比較，因此這個算法的時間復雜度是 O(n^2)。（2）第二種方式是使用歸并排序的方式，通過利用歸并排序分解后進行合并排序時，來進行逆序對的統計，這一種方法的時間復雜度為 O(nlogn)。

詳細資料可以參考：
《數組中的逆序對》

36. 兩個鏈表的第一個公共結點

題目：輸入兩個鏈表，找出它們的第一個公共結點。思路：（1）第一種方法是在第一個鏈表上順序遍歷每個結點，每遍歷到一個結點的時候，在第二個鏈表上順序遍歷每個結點。如果在第二個鏈表上有一個結點和第一個鏈表上的結點一樣，說明兩個鏈表在這個結點上重合，于是就找到了它們的公共結點。如果第一個鏈表的長度為 m，第二個鏈表的長度為 n。這一種方法的時間復雜度是 O(mn）。（2）第二種方式是利用棧的方式，通過觀察我們可以發現兩個鏈表的公共節點，都位于鏈表的尾部，以此我們可以分別使用兩個棧，依次將鏈表元素入棧。然后在兩個棧同時將元素出棧，比較出棧的節點，最后一個相同的節點就是我們要找的公共節點。這一種方法的時間復雜度為 O(m+n)，空間復雜度為 O(m+n)。（3）第三種方式是，首先分別遍歷兩個鏈表，得到兩個鏈表的長度。然后得到較長的鏈表與較短的鏈表長度的差值。我們使用兩個指針來分別對兩個鏈表進行遍歷，首先將較長鏈表的指針移動 n 步，n 為兩個鏈表長度的差值，然后兩個指針再同時移動，判斷所指向節點是否為同一節點。這一種方法的時間復雜度為 O(m+n)，相同對于上一種方法不需要額外的空間。

詳細資料可以參考：
《兩個鏈表的第一個公共結點》

37. 數字在排序數組中出現的次數

題目：統計一個數字：在排序數組中出現的次數。例如輸入排序數組｛ 1, 2, 3, 3, 3, 3, 4, 5｝和數字 3 ，由于 3 在這個數組中出現了 4 次，因此輸出 4 。思路：（1）第一種方法是直接對數組順序遍歷的方式，通過這種方法來統計數字的出現次數。這種方法的時間復雜度為 O(n)。（2）第二種方法是使用二分查找的方法，由于數組是排序好的數組，因此相同數字是排列在一起的。統計數字出現的次數，我們需要去找到該段數字開始和結束的位置，以此來確定數字出現的次數。因此我們可以使用二分查找的方式來確定該數字的開始和結束位置。如果我們第一次我們數組的中間值為 k ，如果 k 值比所求值大的話，那么我們下一次只需要判斷前面一部分就行了，如果 k值比所求值小的話，那么我們下一次就只需要判斷后面一部分就行了。如果 k 值等于所求值的時候，我們則需要判斷該值是否為開始位置或者結束位置。如果是開始位置，那么我們下一次需要到后半部分去尋找結束位置。如果是結束位置，那么我們下一次需要到前半部分去尋找開始位置。如果既不是開始位置也不是結束位置，那么我們就分別到前后兩個部分去尋找開始和結束位置。這一種方法的平均時間復雜度為 O(logn)。

38. 二叉樹的深度

題目：輸入一棵二叉樹，求該樹的深度。從根結點到葉結點依次經過的結點（含根、葉結點）形成樹的一條路徑，最長路徑的長度為樹的深度。思路：根節點的深度等于左右深度較大值加一，因此可以通過遞歸遍歷來實現。

39. 平衡二叉樹

題目：輸入一棵二叉樹，判斷該二叉樹是否是平衡二叉樹。思路：（1）在遍歷樹的每個結點的時候，調用函數得到它的左右子樹的深度。如果每個結點的左右子樹的深度相差都不超過 1 ，那么它就是一棵平衡的二叉樹。使用這種方法時，節點會被多次遍歷，因此會造成效率不高的問題。（2）在求一個節點的深度時，同時判斷它是否平衡。如果不平衡則直接返回 -1，否則返回樹高度。如果一個節點的一個子樹的深度為-1，那么就直接向上返回 -1 ，該樹已經是不平衡的了。通過這種方式確保了節點只能夠被訪問一遍。

40. 數組中只出現一次的數字

題目：一個整型數組里除了兩個數字之外，其他的數字都出現了兩次。請寫程序找出這兩個只出現一次的數字。思路：（1）第一種方式是依次遍歷數組，記錄下數字出現的次數，從而找出兩個只出現一次的數字。（2）第二種方式，根據位運算的異或的性質，我們可以知道兩個相同的數字異或等于0，一個數和 0 異或還是它本身。由于數組中的其他數字都是成對出現的，因此我們可以將數組中的所有數依次進行異或運算。如果只有一個數出現一次的話，那么最后剩下的就是落單的數字。如果是兩個數只出現了一次的話，那么最后剩下的就是這兩個數異或的結果。這個結果中的1表示的是 A 和B 不同的位。我們取異或結果的第一個1所在的位數，假如是第3位，接著通過比較第三位來將數組分為兩組，相同數字一定會被分到同一組。分組完成后再按照依次異或的思路，求得剩余數字即為兩個只出現一次的數字。

41. 和為 S 的連續正數序列

題目：小明很喜歡數學，有一天他在做數學作業時，要求計算出9~16的和，他馬上就寫出了正確答案是100。但是他并不滿足于此，他在想究竟有多少種連續的正數序列的和為100（至少包括兩個數）。沒多久，他就得到另一組連續正數和為100的序列：18,19,20,21,22。現在把問題交給你，你能不能也很快的找出所有和為 S 的連續正數序列？Good Luck!輸出描述：輸出所有和為S的連續正數序列。序列內按照從小至大的順序，序列間按照開始數字從小到大的順序。思路：維護一個正數序列數組，數組中初始只含有值1和2，然后從3依次往后遍歷，每遍歷到一個元素則將這個元素加入到序列數組中，然后判斷此時序列數組的和。如果序列數組的和大于所求值，則將第一個元素（最小的元素彈出）。如果序列數組的和小于所求值，則繼續往后遍歷，將元素加入到序列中繼續判斷。當序列數組的和等于所求值時，打印出此時的正數序列，然后繼續往后遍歷，尋找下一個連續序列，直到數組遍歷完成終止。

詳細資料可以參考：
《和為 s 的連續正數序列》

42. 和為 S 的兩個數字

題目：輸入一個遞增排序的數組和一個數字 S，在數組中查找兩個數，是的他們的和正好是 S，如果有多對數字的和等于 S，輸出兩個數的乘積最小的。輸出描述：對應每個測試案例，輸出兩個數，小的先輸出。思路：首先我們通過規律可以發現，和相同的兩個數字，兩個數字的差值越大，乘積越小。因此我們只需要從數組的首尾開始找到第一對和為 s 的數字對進行了。因此我們可以使用雙指針的方式，左指針初始指向數組的第一個元素，右指針初始指向數組的最后一個元素。然后首先判斷兩個指針指向的數字的和是否為 s ，如果為 s ，兩個指針指向的數字就是我們需要尋找的數字對。如果兩數的和比 s 小，則將左指針向左移動一位后繼續判斷。如果兩數的和比 s 大，則將右指針向右移動一位后繼續判斷。

詳細資料可以參考：
《和為 S 的字符串》

43. 左旋轉字符串

題目：匯編語言中有一種移位指令叫做循環左移（ROL），現在有個簡單的任務，就是用字符串模擬這個指令的運算結果。對于一個給定的字符序列 S，請你把其循環左移 K 位后的序列輸出。例如，字符序列 S=”abcXYZdef”，要求輸出循環左移3位后的結果，即 “XYZdefabc”。是不是很簡單？OK，搞定它！思路：字符串裁剪后拼接

44. 翻轉單詞順序列

題目：牛客最近來了一個新員工 Fish，每天早晨總是會拿著一本英文雜志，寫些句子在本子上。同事 Cat 對 Fish 寫的內容頗感興趣，有一天他向 Fish 借來翻看，但卻讀不懂它的意思。例如，“student. a am I”。后來才意識到，這家伙原來把句子單詞的順序翻轉了，正確的句子應該是“I am a student.”。Cat 對一一的翻轉這些單詞順序可不在行，你能幫助他么？思路：通過空格將單詞分隔，然后將數組反序后，重新拼接為字符串。

45. 撲克牌的順子

題目：LL 今天心情特別好，因為他去買了一副撲克牌，發現里面居然有2個大王，2個小王（一副牌原本是54張^_^）...他隨機從中抽出了5張牌，想測測自己的手氣，看看能不能抽到順子，如果抽到的話，他決定去買體育彩票，嘿嘿！！“紅心 A，黑桃3，小王，大王，方片5”，“Oh My God!”不是順子..... LL 不高興了，他想了想，決定大\小王可以看成任何數字，并且 A 看作1，J 為11，Q 為12，K 為13。上面的5張牌就可以變成“1,2,3,4,5”（大小王分別看作2和4），“So Lucky!”。LL 決定去買體育彩票啦。現在，要求你使用這幅牌模擬上面的過程，然后告訴我們 LL 的運氣如何。為了方便起見，你可以認為大小王是0。思路：首先判斷5個數字是不是連續的，最直觀的方法是把數組排序。值得注意的是，由于 0 可以當成任意數字，我們可以用 0 去補滿數組中的空缺。如果排序之后的數組不是連續的，即相鄰的兩個數字相隔若干個數字，但只要我們有足夠的。可以補滿這兩個數字的空缺，這個數組實際上還是連續的。于是我們需要做 3 件事情：首先把數組排序，再統計數組中 0 的個數，最后統計排序之后的數組中相鄰數字之間的空缺總數。如果空缺的總數小于或者等于 0 的個數，那么這個數組就是連續的：反之則不連續。最后，我們還需要注意一點：如果數組中的非 0數字重復出現，則該數組不是連續的。換成撲克牌的描述方式就是如果一副牌里含有對子，則不可能是順子。

詳細資料可以參考：
《撲克牌的順子》

46. 圓圈中最后剩下的數字（約瑟夫環問題）

題目：0, 1, … , n-1 這 n 個數字排成一個圈圈，從數字 0 開始每次從圓圏里刪除第 m 個數字。求出這個圈圈里剩下的最后一個數字。思路：（1）使用環形鏈表進行模擬。（2）根據規律得出（待深入理解）

詳細資料可以參考：
《圓圈中最后剩下的數字》

47. 1+2+3+…+n

題目：求 1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case 等關鍵字及條件判斷語句（A?B:C）。思路：由于不能使用循環語句，因此我們可以通過遞歸來實現。并且由于不能夠使用條件判斷運算符，我們可以利用 && 操作符的短路特性來實現。

48. 不用加減乘除做加法

題目：寫一個函數，求兩個整數之和，要求在函數體內不得使用 ＋、－、×、÷ 四則運算符號。思路：通過位運算，遞歸來實現。

49. 把字符串轉換成整數。

題目：將一個字符串轉換成一個整數，要求不能使用字符串轉換整數的庫函數。數值為0或者字符串不是一個合法的數值則返回 0。輸入描述：輸入一個字符串，包括數字字母符號，可以為空。輸出描述：如果是合法的數值表達則返回該數字，否則返回0。思路：首先需要進行符號判斷，其次我們根據字符串的每位通過減0運算轉換為整數和，依次根據位數疊加。

50. 數組中重復的數字

題目：在一個長度為 n 的數組里的所有數字都在 0 到 n-1 的范圍內。數組中某些數字是重復的，但不知道有幾個數字重復了，也不知道每個數字重復了幾次。請找出數組中任意一個重復的數字。思路：（1）首先將數組排序，排序后再進行判斷。這一種方法的時間復雜度為 O(nlogn)。（2）使用 Map 結構的方式，依次記錄下每一個數字出現的次數，從而可以判斷是否出現重復數字。這一種方法的時間復雜度為 O(n)，空間復雜度為 O(n)。（3）從數組首部開始遍歷，每遍歷一個數字，則將該數字和它的下標相比較，如果數字和下標不等，則將該數字和它對應下標的值交換。如果對應的下標值上已經是正確的值了，那么說明當前元素是一個重復數字。這一種方法相對于上一種方法來說不需要額外的內存空間。

51. 構建乘積數組

題目：給定一個數組 A[0,1,...,n-1]，請構建一個數組 B[0,1,...,n-1]，其中 B 中的元素 B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。思路：（1） C[i]=A[0]×A[1]×...×A[i-1]=C[i-1]×A[i-1] D[i]=A[i+1]×...×A[n-1]=D[i+1]×A[i+1] B[i]=C[i]×D[i]將乘積分為前后兩個部分，分別循環求出后，再進行相乘。（2）上面的方法需要額外的內存空間，我們可以引入中間變量的方式，來降低空間復雜度。（待深入理解）

詳細資料可以參考：
《構建乘積數組》

52. 正則表達式的匹配

題目：請實現一個函數用來匹配包括'.'和'*'的正則表達式。模式中的字符'.'表示任意一個字符，而'*'表示它前面的字符可以出現任意次（包含0次）。 在本題中，匹配是指字符串的所有字符匹配整個模式。例如，字符串"aaa"與模式"a.a"和"ab*ac*a"匹配，但是與"aa.a"和"ab*a"均不匹配。思路：（1）狀態機思路（待深入理解）

詳細資料可以參考：
《正則表達式匹配》

53. 表示數值的字符串

題目：請實現一個函數用來判斷字符串是否表示數值（包括整數和小數）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示數值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。、思路：利用正則表達式實現

54. 字符流中第一個不重復的字符

題目：請實現一個函數用來找出字符流中第一個只出現一次的字符。例如，當從字符流中只讀出前兩個字符 "go" 時，第一個只出現一次的字符是 "g" 。當從該字符流中讀出前六個字符 "google" 時，第一個只出現一次的字符是 "l"。 輸出描述：如果當前字符流沒有存在出現一次的字符，返回#字符。思路：同第 34 題

55. 鏈表中環的入口結點

題目：一個鏈表中包含環，如何找出環的入口結點？思路：首先使用快慢指針的方式我們可以判斷鏈表中是否存在環，當快慢指針相遇時，說明鏈表中存在環。相遇點一定存在于環中，因此我們可以從使用一個指針從這個點開始向前移動，每移動一個點，環的長度加一，當指針再次回到這個點的時候，指針走了一圈，因此通過這個方法我們可以得到鏈表中的環的長度，我們將它記為 n 。然后我們設置兩個指針，首先分別指向頭結點，然后將一個指針先移動 n 步，然后兩個指針再同時移動，當兩個指針相遇時，相遇點就是環的入口節點。

詳細資料可以參考：
《鏈表中環的入口結點》
《《劍指offer》——鏈表中環的入口結點》

56. 刪除鏈表中重復的結點

題目：在一個排序的鏈表中，存在重復的結點，請刪除該鏈表中重復的結點，重復的結點不保留，返回鏈表頭指針。例如，鏈表1->2->3->3->4->4->5 處理后為 1->2->5思路：解決這個問題的第一步是確定刪除的參數。當然這個函數需要輸入待刪除鏈表的頭結點。頭結點可能與后面的結點重復，也就是說頭結點也可能被刪除，所以在鏈表頭額外添加一個結點。接下來我們從頭遍歷整個鏈表。如果當前結點的值與下一個結點的值相同，那么它們就是重復的結點，都可以被刪除。為了保證刪除之后的鏈表仍然是相連的而沒有中間斷開，我們要把當前的前一個結點和后面值比當前結點的值要大的結點相連。我們要確保 prev要始終與下一個沒有重復的結點連接在一起。

57. 二叉樹的下一個結點

題目：給定一棵二叉樹和其中的一個結點，如何找出中序遍歷順序的下一個結點？樹中的結點除了有兩個分別指向左右子結點的指針以外，還有一個指向父節點的指針。思路：這個問題我們可以分為三種情況來討論。第一種情況，當前節點含有右子樹，這種情況下，中序遍歷的下一個節點為該節點右子樹的最左子節點。因此我們只要從右子節點出發，一直沿著左子節點的指針，就能找到下一個節點。第二種情況是，當前節點不含有右子樹，并且當前節點為父節點的左子節點，這種情況下中序遍歷的下一個節點為當前節點的父節點。第三種情況是，當前節點不含有右子樹，并且當前節點為父節點的右子節點，這種情況下我們沿著父節點一直向上查找，直到找到一個節點，該節點為父節點的左子節點。這個左子節點的父節點就是中序遍歷的下一個節點。

58. 對稱二叉樹

題目：請實現一個函數來判斷一棵二叉樹是不是對稱的。如果一棵二叉樹和它的鏡像一樣，那么它是對稱的。思路：我們對一顆二叉樹進行前序遍歷的時候，是先訪問左子節點，然后再訪問右子節點。因此我們可以定義一種對稱的前序遍歷的方式，就是先訪問右子節點，然后再訪問左子節點。通過比較兩種遍歷方式最后的結果是否相同，以此來判斷該二叉樹是否為對稱二叉樹。

59. 按之字形順序打印二叉樹（待深入理解）

題目：請實現一個函數按照之字形順序打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右到左的順序打印，即第一行按照從左到右的順序打印，第二層按照從右到左順序打印，第三行再按照從左到右的順序打印，其他以此類推。思路：按之字形順序打印二叉樹需要兩個棧。我們在打印某一行結點時，把下一層的子結點保存到相應的棧里。如果當前打印的是奇數層，則先保存左子結點再保存右子結點到一個棧里；如果當前打印的是偶數層，則先保存右子結點再保存左子結點到第二個棧里。每一個棧遍歷完成后進入下一層循環。

詳細資料可以參考：
《按之字形順序打印二叉樹》

60. 從上到下按層打印二叉樹，同一層結點從左至右輸出。每一層輸出一行。

題目：從上到下按層打印二叉樹，同一層的結點按從左到右的順序打印，每一層打印一行。思路：用一個隊列來保存將要打印的結點。為了把二叉樹的每一行單獨打印到一行里，我們需要兩個變量：一個變量表示在當前的層中還沒有打印的結點數，另一個變量表示下一次結點的數目。

61. 序列化二叉樹（待深入理解）

題目：請實現兩個函數，分別用來序列化和反序列化二叉樹。思路：數組模擬

62. 二叉搜索樹的第 K 個節點

題目：給定一顆二叉搜索樹，請找出其中的第 k 小的結點。思路：對一顆樹首先進行中序遍歷，在遍歷的同時記錄已經遍歷的節點數，當遍歷到第 k 個節點時，這個節點即為第 k 大的節點。

63. 數據流中的中位數（待深入理解）

題目：如何得到一個數據流中的中位數？如果從數據流中讀出奇數個數值，那么中位數就是所有值排序之后位于中間的數值。如果數據流中讀出偶數個數值，那么中位數就是所有數值排序之后中間兩個數的平均值。

64. 滑動窗口中的最大值（待深入理解）

題目：給定一個數組和滑動窗口的大小，找出所有滑動窗口里數值的最大值。例如，如果輸入數組{2,3,4,2,6,2,5,1}及滑動窗口的大小3，那么一共存在6個滑動窗口，他們的最大值分別為{4,4,6,6,6,5}； 針對數組{2,3,4,2,6,2,5,1}的滑動窗口有以下6個： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。思路：使用隊列的方式模擬

65. 矩陣中的路徑（待深入理解）

題目：請設計一個函數，用來判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意一個格子開始，每一步可以在矩陣中向左，向右，向上，向下移動一個格子。如果一條路徑經過了矩陣中的某一個格子，則該路徑不能再進入該格子。例如 a b c e s f c s a d e e 矩陣中包含一條字符串"bcced"的路徑，但是矩陣中不包含"abcb"路徑，因為字符串的第一個字符 b 占據了矩陣中的第一行第二個格子之后，路徑不能再次進入該格子。

66. 機器人的運動范圍（待深入理解）

題目：地上有一個m行和n列的方格。一個機器人從坐標0,0的格子開始移動，每一次只能向左，右，上，下四個方向移動一格，但是不能進入行坐標和列坐標的數位之和大于k的格子。 例如，當k為18時，機器人能夠進入方格（35,37），因為3+5+3+7 = 18。但是，它不能進入方格（35,38），因為3+5+3+8 = 19。請問該機器人能夠達到多少個格子？

劍指 offer 相關資料可以參考：
《劍指 offer 題目練習及思路分析》
《JS 版劍指 offer》
《劍指 Offer 學習心得》

相關算法題

1. 明星問題

題目：有 n 個人，其中一個明星和 n-1 個群眾，群眾都認識明星，明星不認識任何群眾，群眾和群眾之間的認識關系不知道，現有一個 函數 foo(A, B)，若 A 認識 B 返回 true，若 A 不認識 B 返回 false，試設計一種算法找出明星，并給出時間復雜度。思路：（1）第一種方法我們可以直接使用雙層循環遍歷的方式，每一個人都和其他人進行判斷，如果一個人誰都不認識，那么他就是明星。這一種方法的時間復雜度為 O(n^2)。（2）上一種方法沒有充分利用題目所給的條件，其實我們每一次比較，都可以排除一個人的可能。比如如果 A 認識 B，那么說明A 就不會是明星，因此 A 就可以從數組中移除。如果 A 不認識 B，那么說明 B 不可能是明星，因此 B 就可以從數組中移除。因此每一次判斷都能夠減少一個可能性，我們只需要從數組從前往后進行遍歷，每次移除一個不可能的人，直到數組中只剩一人為止，那么這個人就是明星。這一種方法的時間復雜度為 O(n)。

詳細資料可以參考：
《一個明星和 n-1 個群眾》

2. 正負數組求和

題目：有兩個數組，一個數組里存放的是正整數，另一個數組里存放的是負整數，都是無序的，現在從兩個數組里各拿一個，使得它們的和 最接近零。思路：（1）首先我們可以對兩個數組分別進行排序，正數數組按從小到大排序，負數數組按從大到小排序。排序完成后我們使用兩個指針分別指向兩個數組的首部，判斷兩個指針的和。如果和大于0，則負數指針往后移動一個位置，如果和小于0，則正數指針往后移動一個位置，每一次記錄和的值，和當前保存下來的最小值進行比較。

的棧里。如果當前打印的是奇數層
，則先保存左子結點再保存右子結點到一個棧里；如果當前打印的是偶數層，則先保存右子結點再保存左子結點到第二個棧里。每
一個棧遍歷完成后進入下一層循環。

詳細資料可以參考： [《按之字形順序打印二叉樹》](https://www.cnblogs.com/wuguanglin/p/Print.html)#### 60. 從上到下按層打印二叉樹，同一層結點從左至右輸出。每一層輸出一行。 題目：從上到下按層打印二叉樹，同一層的結點按從左到右的順序打印，每一層打印一行。思路：用一個隊列來保存將要打印的結點。為了把二叉樹的每一行單獨打印到一行里，我們需要兩個變量：一個變量表示在當前的層中還 沒有打印的結點數，另一個變量表示下一次結點的數目。 #### 61. 序列化二叉樹（待深入理解） 題目：請實現兩個函數，分別用來序列化和反序列化二叉樹。思路：數組模擬 #### 62. 二叉搜索樹的第 K 個節點 題目：給定一顆二叉搜索樹，請找出其中的第 k 小的結點。思路：對一顆樹首先進行中序遍歷，在遍歷的同時記錄已經遍歷的節點數，當遍歷到第 k 個節點時，這個節點即為第 k 大的節點。 #### 63. 數據流中的中位數（待深入理解） 題目：如何得到一個數據流中的中位數？如果從數據流中讀出奇數個數值，那么中位數就是所有值排序之后位于中間的數值。如果數據 流中讀出偶數個數值，那么中位數就是所有數值排序之后中間兩個數的平均值。 #### 64. 滑動窗口中的最大值（待深入理解） 題目：給定一個數組和滑動窗口的大小，找出所有滑動窗口里數值的最大值。例如，如果輸入數組{2,3,4,2,6,2,5,1}及滑動窗口的 大小3，那么一共存在6個滑動窗口，他們的最大值分別為{4,4,6,6,6,5}； 針對數組{2,3,4,2,6,2,5,1}的滑動窗口有以下 6個： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2 ,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。思路：使用隊列的方式模擬 #### 65. 矩陣中的路徑（待深入理解） 題目：請設計一個函數，用來判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意一個格子開始，每 一步可以在矩陣中向左，向右，向上，向下移動一個格子。如果一條路徑經過了矩陣中的某一個格子，則該路徑不能再進入該格子 。例如 a b c e s f c s a d e e 矩陣中包含一條字符串"bcced"的路徑，但是矩陣中不包含"abcb"路徑，因為字符串的 第一個字符 b 占據了矩陣中的第一行第二個格子之后，路徑不能再次進入該格子。 #### 66. 機器人的運動范圍（待深入理解） 題目：地上有一個m行和n列的方格。一個機器人從坐標0,0的格子開始移動，每一次只能向左，右，上，下四個方向移動一格，但是不能 進入行坐標和列坐標的數位之和大于k的格子。 例如，當k為18時，機器人能夠進入方格（35,37），因為3+5+3+7 = 18。但是 ，它不能進入方格（35,38），因為3+5+3+8 = 19。請問該機器人能夠達到多少個格子？ 劍指 offer 相關資料可以參考： [《劍指 offer 題目練習及思路分析》](https://blog.csdn.net/zzl819954692/article/details/79648054) [《JS 版劍指 offer》](https://www.cnblogs.com/wuguanglin/p/code-interview.html) [《劍指 Offer 學習心得》](https://wiki.jikexueyuan.com/project/for-offer/)## 相關算法題 #### 1. 明星問題

題目：

有 n 個人，其中一個明星和 n-1 個群眾，群眾都認識明星，明星不認識任何群眾，群眾和群眾之間的認識關系不知道，現有一個
函數 foo(A, B)，若 A 認識 B 返回 true，若 A 不認識 B 返回 false，試設計一種算法找出明星，并給出時間復雜度。

思路：

（1）第一種方法我們可以直接使用雙層循環遍歷的方式，每一個人都和其他人進行判斷，如果一個人誰都不認識，那么他就是明星。
這一種方法的時間復雜度為 O(n^2)。

（2）上一種方法沒有充分利用題目所給的條件，其實我們每一次比較，都可以排除一個人的可能。比如如果 A 認識 B，那么說明
A 就不會是明星，因此 A 就可以從數組中移除。如果 A 不認識 B，那么說明 B 不可能是明星，因此 B 就可以從數組中移
除。因此每一次判斷都能夠減少一個可能性，我們只需要從數組從前往后進行遍歷，每次移除一個不可能的人，直到數組中只剩
一人為止，那么這個人就是明星。這一種方法的時間復雜度為 O(n)。

詳細資料可以參考： [《一個明星和 n-1 個群眾》](https://www.nowcoder.com/questionTerminal/fd3caff374c945fb9ea5f107016bcd4f)#### 2. 正負數組求和

題目：

有兩個數組，一個數組里存放的是正整數，另一個數組里存放的是負整數，都是無序的，現在從兩個數組里各拿一個，使得它們的和
最接近零。

思路：

（1）首先我們可以對兩個數組分別進行排序，正數數組按從小到大排序，負數數組按從大到小排序。排序完成后我們使用兩個指針分
別指向兩個數組的首部，判斷兩個指針的和。如果和大于0，則負數指針往后移動一個位置，如果和小于0，則正數指針往后移動
一個位置，每一次記錄和的值，和當前保存下來的最小值進行比較。

總結

以上是生活随笔為你收集整理的常用数据结构和算法总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。