前言

提及算法，可能會有很多前端同學覺得這是一個距離自己日常工作較遠的領域，認為算法並沒有那麼重要。事實上，這種看法是片面的，算法不僅僅是計算機科學中的一個重要概念，在前端開發中也有着廣泛的應用和巨大的價值。

一個精心設計的算法可以大幅度提高應用的性能和效率，例如：如何在大量數據中快速找到指定信息、如何高效地處理用户輸入、如何在動畫效果中保持流暢的用户體驗、如何讓頁面加載更快、響應更靈敏等等場景，這些都依賴於對算法的理解和應用。掌握算法能夠讓我們在面對複雜問題時，具備更強的分析能力和解決策略。

本文是一篇對前端同學相對友好的入門算法文章，提供一條易於理解的學習路徑，從經典的排序、搜索等基礎算法開始，逐步深入，
再到一些高級算法設計思想，結合 LeetCode 真題實戰案例分析，幫助你理解算法背後的實現邏輯，以及如何將其靈活應用於實際的前端開發場景中。

學習算法，不僅能提高編程能力，對求職面試也有很大幫助，微軟、字節跳動、騰訊等公司就特別喜歡問算法。

排序

簡單來説，排序算法用於將一組亂序的元素按照升序或降序的順序重新排列。其性能通常通過時間複雜度、空間複雜度、穩定性等指標來衡量。

JavaScript 語言中的自帶的排序：數組的 sort 方法。

冒泡排序

冒泡排序（Bubble Sort）是一種簡單的比較排序算法。它重複地遍歷待排序數組，每次比較相鄰的兩個元素，如果順序相反則進行交換。這樣，每一輪遍歷都會將最大（或最小）的元素“冒泡”到頂端，直到整個數組都排序完成，最終達到完全有序。

步驟：

1. 遍歷數組：從頭到尾遍歷數組，比較相鄰的兩個元素。
2. 比較相鄰元素：每次比較相鄰的兩個元素，如果它們的順序不正確（比如，前一個元素大於後一個元素），則交換它們。
3. 重複遍歷：重複上述步驟，直到沒有任何一對元素需要交換，即數組已經完全排序。

代碼實現：

function bubbleSort(array) {
    // 檢查輸入是否為數組且長度大於 1，若不滿足條件，則直接返回原數組
    if (!Array.isArray(array) || array.length <= 1) return array

    // 初始化最後一個未排序元素的索引
    let lastIndex = array.length - 1

    // 當還有未排序的元素時，執行排序過程
    while (lastIndex > 0) {
        // 初始化交換標誌為 true，若本輪未發生交換，則排序完成
        let flag = true
        // 記錄最後一次交換元素的位置，初始設置為未排序部分的末尾
        const k = lastIndex

        // 遍歷未排序部分的元素
        for (let j = 0; j < k; j++) {
            // 若當前元素大於其後面的元素，則交換它們的位置
            if (array[j] > array[j + 1]) {
                flag = false // 發生了交換，將標誌設置為 false
                lastIndex = j // 記錄最後一次交換的位置
                ;[array[j], array[j + 1]] = [array[j + 1], array[j]] // 交換元素
            }
        }

        // 若本輪未發生交換，則數組已經有序，直接退出循環
        if (flag) break
    }

    // 返回排序後的數組
    return array
}

// 測試
console.log(bubbleSort([6,1,5,4,2,3])) // [1, 2, 3, 4, 5, 6]

冒泡排序有幾種可以優化的空間：

• 優化遍歷範圍：在每一輪排序中，可以觀察到最後一次交換髮生的位置之後的元素已經是有序的，因此可以將下一輪排序的範圍限定在上一輪最後一次交換的位置之前。這樣可以減少不必要的比較和交換操作。
• 添加標誌位：如果在一輪排序過程中沒有發生任何元素的交換，説明數組已經是有序的，可以提前結束排序過程。
• 針對部分有序數組的優化：如果數組在初始狀態下已經接近有序，可以記錄下每輪排序中最後一次交換的位置，然後下一輪排序時只需要遍歷到該位置即可，這樣可以大大減少排序的比較次數。
• 雞尾酒排序（雙向冒泡排序）：在一次排序過程中，既從左到右比較交換，又從右到左比較交換，可以在某些特定情況下提升效率。

時間複雜度：

• 最優時間複雜度：O(n)
  當輸入數據已經是有序時，冒泡排序可以通過設置一個標誌變量來檢測是否發生了交換操作，如果在某一趟排序中沒有交換操作發生，説明數組已經有序，因此可以提前結束排序過程。此時，最優時間複雜度為 O(n)。
• 最壞時間複雜度：O(n^2)
  在最壞情況下，輸入數據是逆序的，此時需要進行 n-1 趟排序，每一趟排序中需要進行的比較次數逐漸減少，總比較次數為 n(n-1)/2，因此最壞時間複雜度為 O(n^2)。
• 平均時間複雜度：O(n^2)
  在一般情況下，冒泡排序的比較和交換操作的次數與輸入數據的初始排列狀態有關，但總體而言其時間複雜度仍為 O(n^2)。

空間複雜度：

冒泡排序是一種原地排序算法，它在排序過程中只需要常數級的額外空間，即只使用了少量的輔助變量，因此其空間複雜度為 O(1)。

穩定性：

冒泡排序是一種穩定排序算法。在排序過程中，如果兩個相等的元素相互比較，它們不會交換位置，因此相等元素的相對位置不會改變。

冒泡排序由於其簡單易懂的特性，常用於教學和小規模數據集的排序，但由於其較低的效率，通常不適合大規模數據集的排序任務。

選擇排序

選擇排序（Selection Sort）是一種簡單的比較排序算法。它的基本思想是在未排序數組中找到最小（或最大）的元素，然後將其放置到數組的起始位置，接着在剩餘的未排序部分中繼續尋找最小（或最大）的元素，依次類推，直到所有元素都排序完成。

步驟：

1. 初始狀態： 將整個序列看作兩部分，一部分是未排序的，一部分是已排序的（初始時已排序部分為空）。
2. 遍歷未排序部分： 遍歷未排序部分，找到最小（或最大）的元素。
3. 交換元素： 將找到的最小（或最大）元素與未排序部分的第一個元素交換位置，使得找到的最小元素成為已排序部分的最後一個元素。
4. 擴大已排序部分： 將已排序部分的長度增加 1，未排序部分的長度減少 1。
5. 重複： 重複以上步驟，直到所有元素都已經排序完畢。

這個過程類似於每次從一堆未排序的卡片中選出最小（或最大）的卡片，然後放到已排序的卡片堆中。選擇排序的特點是每次遍歷都只進行一次交換操作，因此相對於其他排序算法，它的交換次數較少。

代碼實現：

function selectionSort(array) {
    // 獲取數組長度
    const { length } = array

    // 如果不是數組或者數組長度小於等於 1，直接返回，不需要排序
    if (!Array.isArray(array) || length <= 1) return array

    // 外層循環，遍歷整個數組，每次找到當前未排序部分的最小元素並放到已排序部分的末尾
    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
            }
        }

        // 交換最小元素到當前位置
        swap(array, i, minIndex)
    }

    return array
}

// 交換數組中兩個元素的位置
function swap(array, left, right) {
    const temp = array[left]
    array[left] = array[right]
    array[right] = temp
}

// 測試
console.log(selectionSort([6, 1, 5, 4, 2, 3]))  // [1, 2, 3, 4, 5, 6]

時間複雜度：

• 最優時間複雜度：O(n^2)
  無論輸入數據的初始排列狀態如何，選擇排序總是需要進行 n(n-1)/2 次比較，因此最優時間複雜度為 O(n^2)。
• 最壞時間複雜度：O(n^2)
  同樣地，在最壞情況下，選擇排序仍需要進行 n(n-1)/2 次比較，所以最壞時間複雜度為 O(n^2)。
• 平均時間複雜度：O(n^2)
  由於選擇排序每一趟排序所需的比較次數固定，因此其平均時間複雜度也為 O(n^2)。

空間複雜度：

選擇排序是一種原地排序算法，只需要常數級的輔助空間（通常是用於交換元素的臨時變量），因此其空間複雜度為 O(1)。

穩定性：

選擇排序通常不是穩定排序。在選擇排序過程中，每次從未排序部分選擇最小（或最大）元素並將其與未排序部分的第一個元素交換時，如果相等元素存在，原有的相對順序可能會被打破。例如：

• 初始數組：[3, 2, 2, 1]
• 第一次選擇：選擇最小元素 1，與第一個元素 3 交換，結果：[1, 2, 2, 3]
• 第二次選擇：選擇最小元素 2，與第二個元素 2 交換，結果：[1, 2, 2, 3]

雖然這個例子沒有改變相同元素的相對順序，但在某些情況下，如處理：[2, 3, 1, 2]，第二個“2”會被提前，與第一個“2”交換，導致順序改變。

選擇排序由於其簡單性和恆定的空間複雜度，適用於對內存空間要求較高但對時間效率要求不高的場景。然而，由於其 O(n^2) 的時間複雜度，選擇排序在處理大規模數據集時效率較低，通常不作為首選的排序算法。

插入排序

插入排序（Insertion Sort）是一種簡單的比較排序算法。它的基本思想是將待排序數組分成已排序和未排序兩部分，初始時已排序部分只有一個元素（即數組的第一個元素），然後從未排序部分依次取出元素，將其插入到已排序部分的正確位置，直到所有元素都被插入完成。

插入排序類似撲克牌思想，想象在打撲克牌，拿起來第一張，放哪裏無所謂，再拿起來一張，比第一張小，放左邊，繼續拿，可能是中間數，就插在中間，依次把牌拿完。

步驟：

1. 初始已排序部分：初始時，將待排序數組的第一個元素視為已排序部分，其餘元素視為未排序部分。
2. 遍歷未排序部分：從第二個元素開始，依次遍歷未排序部分的元素。
3. 插入到已排序部分：對於每個未排序部分的元素，將其與已排序部分的元素逐個比較，找到正確的插入位置。
4. 重複插入：將元素插入到已排序部分的正確位置後，已排序部分的長度增加 1，未排序部分的長度減少 1，繼續重複上述步驟，直到所有元素都被插入完成。

代碼實現：

function insertSort(array) {
    const { length } = array

    // 如果不是數組或者數組長度小於等於 1，直接返回，不需要排序
    if (!Array.isArray(array) || length <= 1) return array

    // 循環從 1 開始，0 位置為默認的已排序的序列
    for (let i = 1; i < length; i++) {
        const 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
}

insertSort([6,1,5,4,2,3]) // [1, 2, 3, 4, 5, 6]

時間複雜度：

• 最優時間複雜度：O(n)
  當輸入數據已經有序時，插入排序每次只需要比較一次即可確定元素的位置，無需進行交換操作。此時，最優時間複雜度為 O(n)。
• 最壞時間複雜度：O(n^2)
  在最壞情況下，輸入數據是逆序的。此時，插入排序需要進行大量的比較和移動操作，每次插入元素時都需要將其與已經排序的部分進行比較並移動其他元素。因此最壞時間複雜度為 O(n^2)。
• 平均時間複雜度：O(n^2)
  在一般情況下，插入排序的比較和移動操作次數與輸入數據的初始排列狀態有關，但總體而言，其平均時間複雜度為 O(n^2)。

空間複雜度：

插入排序是一種原地排序算法，它在排序過程中只需要常數級的額外空間（用於存儲待插入的元素的臨時變量），因此其空間複雜度為 O(1)。

穩定性：

插入排序是一種穩定排序算法。在插入過程中，如果待插入的元素與已排序部分的某個元素相等，插入排序會將待插入的元素放在相等元素的後面，從而保持相等元素的相對順序不變。

插入排序由於其簡單性和對小規模數據集的高效性，常用於對小型數組進行排序或在其他更復雜的排序算法（如快速排序、歸併排序）的過程中處理小數據塊。然而，由於其 O(n^2) 的時間複雜度，插入排序在處理大規模數據集時效率較低。

希爾排序

希爾排序（Shell Sort）是一種改進的插入排序算法，也被稱為“縮小增量排序”。它的基本思想是通過定義一個間隔序列（稱為增量序列），將待排序數組分成若干個子序列，對每個子序列進行插入排序。隨着排序的進行，增量序列逐漸縮小，直到增量為 1，最後對整個數組進行插入排序。

步驟：

1. 選擇增量序列：定義一個增量序列，確定每個增量值（間隔），通常以遞減的方式選擇。
2. 分組排序：將待排序數組根據當前增量值分成若干個子序列，對每個子序列進行插入排序。
3. 逐步縮小增量：重複上述步驟，逐步縮小增量值，直到增量為 1。
4. 最終排序：當增量為 1 時，對整個數組進行一次插入排序，完成排序過程。

代碼實現：

function hillSort(array) {
  const { length } = array

  // 如果輸入不是數組或者數組長度小於等於 1，直接返回原數組，不需要排序
  if (!Array.isArray(array) || length <= 1) return array

  // 第一層循環：確定增量的大小，每次增量的大小減半
  for (let gap = parseInt(length >> 1); gap >= 1; gap = parseInt(gap >> 1)) {
    // 對每個分組使用插入排序，相當於將插入排序的 1 換成了 gap
    for (let i = gap; i < length; i++) {
      const temp = array[i] // 保存當前元素
      let j = i

      // 第二層循環：對當前分組進行插入排序
      // 如果 j - gap >= 0 並且前一個元素大於當前元素，則進行交換
      while (j - gap >= 0 && array[j - gap] > temp) {
        array[j] = array[j - gap] // 將前一個元素後移
        j -= gap // 繼續比較下一個分組內的元素
      }
      array[j] = temp // 插入元素到正確的位置
    }
  }

  return array // 返回排序後的數組
}

hillSort([6,1,5,4,2,3]) // [1, 2, 3, 4, 5, 6]

時間複雜度：

希爾排序的時間複雜度較為複雜，與所選的增量序列（gap sequence）有很大關係。常見的增量序列有希爾增量序列、Hibbard 增量序列、Sedgewick 增量序列等。以下是幾種常見增量序列的時間複雜度分析：

• 希爾增量序列（gap = n/2, n/4, ..., 1）：最壞時間複雜度：O(n^2)
• Hibbard 增量序列（gap = 2^k - 1）：最壞時間複雜度：O(n^(3/2))
• Sedgewick 增量序列（一種較為複雜的序列）：最壞時間複雜度：O(n^(4/3))
• 更優的增量序列：有些優化過的增量序列可以達到 O(n log^2 n) 的最壞時間複雜度。

由於增量序列的選擇對希爾排序的時間複雜度有很大的影響，所以具體的時間複雜度因實現而異，但通常在 O(n^2) 和 O(n log^2 n) 之間。

空間複雜度：

希爾排序是一種原地排序算法，其空間複雜度為 O(1)，只需要常數級的額外空間。

穩定性：

希爾排序不是穩定排序。在排序過程中，元素可能會跨越多個位置進行交換，因此相同元素的相對順序可能會被打亂。

希爾排序由於其高效性和相對簡單的實現，在實際應用中有一定的優勢，特別是在數據規模較大時。它通過對插入排序的改進，大大減少了數據移動的次數，從而提高了排序的效率。

歸併排序

歸併排序（Merge Sort）是一種基於分治法的高效排序算法。其基本思想是將數組分成更小的子數組，分別對這些子數組進行排序，然後再將它們合併起來，以得到一個有序的數組。

步驟：

1. 分割（Divide）：將數組從中間分成兩個子數組（遞歸地分割直到子數組的長度為 1）。
2. 排序（Conquer）：對每個子數組進行排序。因為子數組的長度為 1，所以它們是有序的。
3. 合併（Combine）：將兩個有序的子數組合併成一個有序的數組。重複這個過程，直到所有的子數組被合併成一個完整的有序數組。

代碼實現：

function mergeSort(array) {
  const { length } = array

  // 如果不是數組或者數組長度小於等於 0，直接返回，不需要排序
  if (!Array.isArray(array) || length <= 1) return array

  const mid = parseInt(length >> 1) // 找到中間索引值
  const left = array.slice(0, mid) // 截取左半部分
  const right = array.slice(mid, length) // 截取右半部分

  return merge(mergeSort(left), mergeSort(right)) // 遞歸分解後，進行排序合併
}

function merge(leftArray, rightArray) {
  const result = []
  const leftLength = leftArray.length
  const rightLength = rightArray.length
  let il = 0
  let 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
}

mergeSort([6,1,5,4,2,3]) // [1, 2, 3, 4, 5, 6]

基本過程：

1. 分割：將待排序數組分成兩半。
2. 遞歸排序：對每一半分別進行遞歸排序。
3. 合併：合併兩個有序子數組以形成一個有序的整體。

時間複雜度：

1. 最優時間複雜度：O(n log n)
2. 最壞時間複雜度：O(n log n)
3. 平均時間複雜度：O(n log n)

歸併排序在最優、最壞和平均情況下的時間複雜度都是 O(n log n)，因為它始終將數組分成兩半，然後對每一半進行排序，再合併結果。

空間複雜度：

歸併排序的空間複雜度為 O(n)，這是因為歸併排序在合併過程中需要一個額外的數組來暫存數據。對於遞歸實現，還需要考慮遞歸調用的棧空間，但總的額外空間仍然是 O(n)。

穩定性：

歸併排序是一種穩定排序算法。在合併兩個有序子數組的過程中，如果兩個元素相等，先將前一個數組的元素放入結果數組中，從而保持相等元素的相對順序不變。

歸併排序由於其穩定性和 O(n log n) 的時間複雜度，常用於處理大規模數據集，尤其是在需要穩定排序的情況下。雖然歸併排序的空間複雜度較高，但其分治策略使其在許多應用中表現出色。

快速排序

快速排序（Quick Sort）是一種高效的排序算法，基於分治法。它通過選擇一個"基準"（pivot）元素，並將數組分成兩部分，其中一部分的所有元素都小於基準，另一部分的所有元素都大於基準。然後遞歸地對這兩部分進行排序。

步驟：

1. 選擇基準：從數組中選擇一個元素作為基準（pivot）。
2. 分區：重新排列數組，使得所有小於基準的元素在基準的左邊，所有大於基準的元素在基準的右邊（相等的元素可以放在任一側）。此時基準元素處於其正確的位置。
3. 遞歸排序：遞歸地對基準左邊的子數組和右邊的子數組進行排序。

代碼實現：

function quickSort(array) {
  // 如果不是數組或者數組長度小於等於 0，直接返回，不需要排序
  if (!Array.isArray(array) || array.length <= 1) return array

  // 選擇基準
  const pivot = array[array.length - 1]
  // 使用兩個數組 left 和 right 來存儲小於和大於基準的元素
  const left = []
  const right = []

  // 分區過程
  for (let i = 0; i < array.length - 1; i++) {
    if (array[i] < pivot) {
      left.push(array[i])
    } else {
      right.push(array[i])
    }
  }

  // 遞歸地排序左右子數組併合並
  return [...quickSort(left), pivot, ...quickSort(right)]
}

quickSort([6, 1, 5, 4, 2, 3]) // [1, 2, 3, 4, 5, 6]

時間複雜度：

• 最優時間複雜度：O(n log n)
  當每次劃分的子數組都比較均勻時，遞歸樹的高度為 log n，每層的操作複雜度為 O(n)，所以最優時間複雜度為 O(n log n)。
• 最壞時間複雜度：O(n^2)
  在最壞情況下，每次劃分的子數組高度不均勻，例如每次選擇的基準（pivot）是最大或最小元素，這會導致遞歸樹退化為鏈表形式，時間複雜度為 O(n^2)。
• 平均時間複雜度：O(n log n)
  在實際應用中，快速排序的平均性能通常很好，期望時間複雜度為 O(n log n)，因為隨機選擇基準或使用“三數取中”等方法可以有效避免最壞情況。

空間複雜度：

快速排序的空間複雜度主要取決於遞歸調用棧的深度：

• 平均空間複雜度：O(log n)
  在理想情況下，遞歸調用棧的深度為 log n，因此空間複雜度為 O(log n)。
• 最壞空間複雜度：O(n)
  在最壞情況下，遞歸調用棧的深度為 n，因此空間複雜度為 O(n)。

穩定性：

快速排序不是穩定排序。在排序過程中，元素的相對順序可能會被改變，因為基準元素的交換可能會使得相等的元素順序顛倒。

快速排序因其高效性和較好的平均性能，廣泛應用於各種排序任務。通過隨機選擇基準或“三數取中”等方法，可以有效地改善其性能，避免最壞情況的發生。

堆排序

堆排序（Heap Sort）是一種基於二叉堆數據結構的比較排序算法。堆排序可以分為兩個階段：構建初始堆和在堆上進行排序操作。

步驟：

1. 構建最大堆：將無序數組構建成一個最大堆（max heap），最大堆是一個完全二叉樹，其中每個節點的值都大於或等於其子節點的值。
2. 排序：交換堆頂元素（最大值）和堆的最後一個元素，並將堆的大小減少 1。然後對堆的根節點進行調整，使其重新成為最大堆。
   重複上述步驟，直到堆中剩餘元素只剩一個，即完成排序。

function heapSort(array) {
  // 如果不是數組或者數組長度小於等於 1，直接返回，不需要排序
  if (!Array.isArray(array) || array.length <= 1) return array

  const n = array.length

  // 構建最大堆
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(array, n, i)
  }

  // 逐一從堆中取出元素，並對剩餘元素重新堆化
  for (let i = n - 1; i > 0; i--) {
    // 將堆頂（最大值）和堆的最後一個元素交換
    ;[array[0], array[i]] = [array[i], array[0]]

    // 對堆的剩餘部分重新堆化
    heapify(array, i, 0)
  }

  return array
}

// 堆化函數，維護堆的性質
function heapify(array, n, i) {
  let largest = i // 假設當前節點是最大值
  const left = 2 * i + 1 // 左子節點
  const right = 2 * i + 2 // 右子節點

  // 如果左子節點大於當前節點，則更新最大值
  if (left < n && array[left] > array[largest]) {
    largest = left
  }

  // 如果右子節點大於當前節點，則更新最大值
  if (right < n && array[right] > array[largest]) {
    largest = right
  }

  // 如果最大值不是當前節點，則交換並繼續堆化
  if (largest !== i) {
    ;[array[i], array[largest]] = [array[largest], array[i]]
    heapify(array, n, largest)
  }
}

heapSort([6, 1, 5, 4, 2, 3]) // [1, 2, 3, 4, 5, 6]

時間複雜度：

• 最優時間複雜度：O(n log n)
  在最優情況下，堆排序的時間複雜度為 O(n log n)，因為構建最大堆和進行堆排序的時間複雜度都是 O(n log n)。
• 最壞時間複雜度：O(n log n)
  在最壞情況下，堆排序的時間複雜度也是 O(n log n)。無論輸入數據的順序如何，都需要將數據構建成最大堆，然後進行排序。
• 平均時間複雜度：O(n log n)

空間複雜度：

堆排序是一種原地排序算法，它只需要常數級別的額外空間來存儲堆的數據結構，因此其空間複雜度為 O(1)。

穩定性：

堆排序不是穩定排序算法。在堆排序中，可能會破壞相同元素的相對順序，因此它不是穩定的排序算法。

堆排序由於其高效性和原地排序的特性，常用於需要穩定且較高性能的排序任務。雖然堆排序的實現相對複雜，但它的時間複雜度穩定在 O(n log n)，在實踐中具有較好的性能表現。

基數排序

基數排序（Radix Sort）是一種非比較性的排序算法，它根據關鍵字的每個位的值來排序。基數排序適用於元素都是整數的數組，其中每個元素都有相同的位數或範圍。基本思想是將待排序的元素按照位數進行分組，然後按照每一位的順序依次排序。

步驟：

1. 按照最低有效位進行排序：從最低位（個位）開始，將元素按照該位的值進行分組（例如 0 到 9），並按照順序重新排列。
2. 依次對更高位進行排序：對每一位重複上述排序過程，直到按照最高位排序完成。
3. 合併分組：每次按照位數排序後，將所有分組合併為一個數組，形成新的待排序數組。
4. 重複步驟 1~3，直到所有位都被處理完畢。

示例：

假設我們有一個無序數組 [170, 45, 75, 90, 802, 24, 2, 66]，使用基數排序對其進行排序：

1. 按照個位進行排序：
   將數字按照個位的值進行分組：[170, 90, 802, 2], [24], [45, 75], [66]，並按照順序重新排列：[170, 90, 802, 2, 24, 45, 75, 66]。
2. 按照十位進行排序：
   將數字按照十位的值進行分組：[802, 2], [24], [45, 66], [75], [170, 90]，並按照順序重新排列：[802, 2, 24, 45, 66, 75, 170, 90]。
3. 按照百位進行排序（如果有的話）。
4. 排序完成，得到有序數組 [2, 24, 45, 66, 75, 90, 170, 802]。

代碼實現：

// 獲取數字的指定位數上的數字
function getDigit(num, place) {
  return Math.floor(Math.abs(num) / 10 ** place) % 10
}

// 獲取數字的位數（最大位數）
function digitCount(num) {
  if (num === 0) return 1
  return Math.floor(Math.log10(Math.abs(num))) + 1
}

// 獲取數組中最大數字的位數
function mostDigits(nums) {
  let maxDigits = 0
  for (let i = 0; i < nums.length; i++) {
    maxDigits = Math.max(maxDigits, digitCount(nums[i]))
  }
  return maxDigits
}

function radixSort(nums) {
  const maxDigitCount = mostDigits(nums)

  for (let k = 0; k < maxDigitCount; k++) {
    // 創建 10 個桶（0 到 9）
    const digitBuckets = Array.from({ length: 10 }, () => [])

    // 將數字放入相應的桶中
    for (let i = 0; i < nums.length; i++) {
      const digit = getDigit(nums[i], k)
      digitBuckets[digit].push(nums[i])
    }

    // 合併所有桶中的數字成為新的待排序數組
    nums = [].concat(...digitBuckets)
  }

  return nums
}

radixSort([6, 1, 5, 4, 2, 3]) // [1, 2, 3, 4, 5, 6]

時間複雜度：

• 最優時間複雜度：O(n * k)
  最優情況下，每個關鍵字的位數相同，基數排序的時間複雜度為 O(n * k)，其中 n 是元素個數，k 是關鍵字的位數。
• 最壞時間複雜度：O(n * k)
  最壞情況下，基數排序的時間複雜度仍然為 O(n * k)。
• 平均時間複雜度：O(n * k)
  基數排序的平均時間複雜度也為 O(n * k)，其中 k 通常為常數。

基數排序的時間複雜度主要取決於關鍵字的位數和元素個數，與元素的大小範圍無關。

空間複雜度：

基數排序的空間複雜度取決於輔助存儲空間的使用，通常需要一個額外的數組來存儲中間結果。因此，其空間複雜度為 O(n + k)，其中 n 是元素個數，k 是關鍵字的範圍（通常是 10）。

穩定性：

基數排序是一種穩定排序算法。在基數排序過程中，相同位數的元素根據其原始順序進行排序，不會改變相等元素的相對位置，因此是穩定的。

基數排序適用於處理整數或字符串等具有固定位數的元素集合。它的時間複雜度相對較低，並且是穩定排序算法，因此在一些特定的排序場景中具有一定的優勢。

計數排序

計數排序（Counting Sort）是一種非比較性的排序算法，適用於待排序元素都屬於一個有限範圍的整數。計數排序的基本思想是通過統計待排序數組中每個元素出現的次數，然後根據統計信息將元素放置到正確的位置上。

步驟：

1. 統計元素出現次數：遍歷待排序數組，統計每個元素出現的次數，存儲在一個輔助數組中。
2. 累加統計次數：對統計數組進行累加，使得每個位置存儲的值表示小於等於該值的元素的個數。
3. 根據統計信息排序：遍歷待排序數組，根據統計數組中的信息，將元素放置到正確的位置上。

示例：

假設我們有一個無序數組 [4, 2, 2, 8, 3, 3, 1]，使用計數排序對其進行排序：

1. 統計元素出現次數：統計數組中每個元素的出現次數：[1:1, 2:2, 3:2, 4:1, 8:1]。
2. 累加統計次數：將統計數組中的值進行累加：[1:1, 2:3, 3:5, 4:6, 8:7]，表示小於等於每個元素的個數。
3. 根據統計信息排序：根據累加統計次數，將待排序數組中的元素放置到正確的位置上，得到有序數組 [1, 2, 2, 3, 3, 4, 8]。

代碼實現：

function countingSort(array) {
  // 找到待排序數組中的最大值和最小值
  let min = array[0]
  let max = array[0]
  for (let i = 1; i < array.length; i++) {
    if (array[i] < min) min = array[i]
    if (array[i] > max) max = array[i]
  }

  // 創建統計數組，長度為 max - min + 1
  const countArray = new Array(max - min + 1).fill(0)

  // 統計每個元素出現的次數
  for (let i = 0; i < array.length; i++) {
    countArray[array[i] - min]++
  }

  // 根據統計信息對元素進行排序
  let sortedIndex = 0
  for (let i = 0; i < countArray.length; i++) {
    while (countArray[i] > 0) {
      array[sortedIndex] = i + min
      sortedIndex++
      countArray[i]--
    }
  }

  return array
}

countingSort([6, 1, 5, 4, 2, 3]) // [1, 2, 3, 4, 5, 6]

時間複雜度：

• 最優時間複雜度：O(n + k)
  最優情況下，計數排序的時間複雜度為 O(n + k)，其中 n 是元素個數，k 是元素的範圍。
• 最壞時間複雜度：O(n + k)
  最壞情況下，計數排序的時間複雜度仍然為 O(n + k)。
• 平均時間複雜度：O(n + k)
  計數排序的平均時間複雜度也為 O(n + k)。

計數排序的時間複雜度主要取決於元素的範圍，而與元素的個數無關。

空間複雜度：

計數排序的空間複雜度取決於額外的計數數組和輸出數組。因此，其空間複雜度為 O(n + k)，其中 n 是元素個數，k 是元素的範圍。

穩定性：

計數排序是一種穩定排序算法。在計數排序中，相同元素的相對順序不會改變，因此是穩定的。

計數排序適用於對一定範圍內的整數進行排序，並且適合於元素範圍不是很大的情況下。由於其時間複雜度和空間複雜度均為線性，因此在一些特定的排序場景中具有較好的性能表現。

搜索

搜索算法簡單來説就是用於找出數組中某個元素的下標。

JavaScript 語言中的自帶的搜索：數組的 indexOf 方法。

順序搜索

順序搜索（Sequential Search）算法是一種簡單的搜索算法，它按順序檢查列表中的每個元素，直到找到目標元素或遍歷完整個列表。

代碼實現：

function sequentialSearch(array, target) {
    // 遍歷數組中的每個元素
    for (let i = 0; i < array.length; i++) {
        // 如果當前元素等於目標元素，則返回當前元素的索引
        if (array[i] === target) {
            return i
        }
    }
    // 如果未找到目標元素，則返回 -1
    return -1
}

// 測試
console.log(sequentialSearch([1, 2, 3, 4, 5], 0)) // -1
console.log(sequentialSearch([1, 2, 3, 4, 5], 3)) // 2

順序搜索的時間複雜度為 O(n)，其中 n 是列表的長度。

二分搜索

二分搜索（Binary Search）是一種高效的搜索算法，適用於有序數組。該算法通過重複將搜索範圍縮小為一半來找到目標值。

function binarySearch(arr, target) {
  let low = 0 // 搜索範圍的最低索引
  let high = arr.length - 1 // 搜索範圍的最高索引

  while (low <= high) {
    const mid = Math.floor((low + high) / 2) // 中間索引

    if (arr[mid] === target) {
      return mid // 找到目標元素，返回索引
    }
    if (arr[mid] < target) {
      low = mid + 1 // 目標元素在右半部分，調整搜索範圍的最低索引
    } else {
      high = mid - 1 // 目標元素在左半部分，調整搜索範圍的最高索引
    }
  }

  return -1 // 目標元素未找到
}

// 測試
console.log(binarySearch([1, 2, 3, 4, 5], 0)) // -1
console.log(binarySearch([1, 2, 3, 4, 5], 3)) // 2

二分搜索的時間複雜度為 O(log n)，其中 n 是數組的長度。

算法設計思想

分而治之

分而治之（分治法）是一種常見的算法設計思想，其核心是將一個大問題分解成小的子問題，分別解決這些子問題，然後將子問題的解合併起來得到原問題的解。這種思想在很多算法中都有廣泛的應用，特別是在解決遞歸問題時很常見。

基本步驟

1. 分解（Divide）：將原問題劃分成若干個規模較小的子問題。
2. 解決（Conquer）：遞歸地解決這些子問題，如果子問題規模足夠小，則直接求解。
3. 合併（Combine）：將子問題的解合併成原問題的解。

使用場景

• 排序算法：如歸併排序和快速排序。
• 搜索算法：如二分搜索。
• 數據壓縮：如哈夫曼編碼。
• 分佈式計算：如 MapReduce 等。

分而治之的應用

多數元素

題目來源：LeetCode #169 簡單

給定一個大小為 n 的數組 nums，返回其中的多數元素。多數元素是指在數組中出現次數大於 ⌊ n/2 ⌋ 的元素。

你可以假設數組是非空的，並且給定的數組總是存在多數元素。

示例 1：

輸入：nums = [3, 2, 3]
輸出：3

示例 2：

輸入：nums = [2, 2, 1, 1, 1, 2, 2]
輸出：2

提示：

• n == nums.length
• 1 <= n <= 5 * 104
• -10^9 <= nums[i] <= 10^9

解題步驟：

1. 分解：將數組分成左右兩部分。
2. 解決子問題：遞歸地在左右兩部分中分別找出多數元素。

3. 合併：

   • 如果左右部分的多數元素相同，則該元素即為整個數組的多數元素。
   • 如果左右部分的多數元素不同，則需要統計這兩個元素在整個數組中的出現次數，出現次數較多的元素即為多數元素。

代碼實現：

function majorityElement(nums) {
   // 輔助函數：統計元素在給定區間內的出現次數
   function countInRange(nums, num, left, right) {
      let count = 0
      for (let i = left; i <= right; i++) {
         if (nums[i] === num) {
            count++
         }
      }
      return count
   }

   // 分治算法主函數
   function majorityElementRec(nums, left, right) {
      // 基本情況：只有一個元素時
      if (left === right) {
         return nums[left]
      }

      // 將數組分成左右兩部分
      const mid = Math.floor((left + right) / 2)
      const leftMajority = majorityElementRec(nums, left, mid)
      const rightMajority = majorityElementRec(nums, mid + 1, right)

      // 如果左右部分的多數元素相同，則返回該元素
      if (leftMajority === rightMajority) {
         return leftMajority
      }

      // 否則統計左右多數元素在整個區間內的出現次數
      const leftCount = countInRange(nums, leftMajority, left, right)
      const rightCount = countInRange(nums, rightMajority, left, right)

      // 返回出現次數較多的元素
      return leftCount > rightCount ? leftMajority : rightMajority
   }

   // 調用遞歸函數，從整個數組開始
   return majorityElementRec(nums, 0, nums.length - 1)
}

// 測試用例
console.log(majorityElement([3, 2, 3])) // 輸出：3
console.log(majorityElement([2, 2, 1, 1, 1, 2, 2])) // 輸出：2
console.log(majorityElement([1])) // 輸出：1
console.log(majorityElement([1, 1, 2, 2, 2, 1, 1, 1])) // 輸出：1

• 時間複雜度：O(n log n)，每次遞歸將數組分為兩部分，類似於歸併排序，每層的合併操作需要線性時間，遞歸深度為 log n，因此總時間複雜度為 O(n log n)。
• 空間複雜度：O(log n)，遞歸調用棧的深度為 log n，因此空間複雜度為 O(log n)（不包括輸入和輸出所佔用的空間）。

排序數組

題目來源：LeetCode #912 中等

給你一個整數數組 nums，請你將該數組升序排列。

示例 1：

輸入：nums = [5, 2, 3, 1]
輸出：[1, 2, 3, 5]

示例 2：

輸入：nums = [5, 1, 1, 2, 0, 0]
輸出：[0, 0, 1, 1, 2, 5]

要將一個整數數組進行排序，我們可以使用分而治之的思想，這裏我們選擇歸併排序作為實現方法，歸併排序是一種穩定的排序算法。

解題步驟：

1. 遞歸終止條件：當數組長度小於等於 1 時，返回數組本身，因為它已經是有序的。
2. 分解數組：找到數組的中點，將數組分成左右兩部分。
3. 遞歸排序：遞歸地對左右兩部分進行排序。
4. 合併：合併兩個有序的子數組成一個有序的數組。

代碼實現：

function sortArray(nums) {
   // 主函數，調用歸併排序函數
   return mergeSort(nums)
}

function mergeSort(nums) {
   // 基本情況：如果數組長度小於等於 1，直接返回
   if (nums.length <= 1) {
      return nums
   }

   // 計算中點
   const mid = Math.floor(nums.length / 2)

   // 分別對左右兩部分進行排序
   const left = mergeSort(nums.slice(0, mid))
   const right = mergeSort(nums.slice(mid))

   // 合併排序好的左右兩部分
   return merge(left, right)
}

function merge(left, right) {
   const sortedArray = []
   let i = 0
   let j = 0

   // 合併兩個有序數組
   while (i < left.length && j < right.length) {
      if (left[i] < right[j]) {
         sortedArray.push(left[i])
         i++
      } else {
         sortedArray.push(right[j])
         j++
      }
   }

   // 將剩餘的元素添加到結果數組
   while (i < left.length) {
      sortedArray.push(left[i])
      i++
   }
   while (j < right.length) {
      sortedArray.push(right[j])
      j++
   }

   return sortedArray
}

// 示例測試
console.log(sortArray([5, 2, 3, 1])) // 輸出：[1, 2, 3, 5]
console.log(sortArray([5, 1, 1, 2, 0, 0])) // 輸出：[0, 0, 1, 1, 2, 5]

• 時間複雜度：O(N log N)，因為數組每次都被分成兩部分，並且每次合併操作的時間複雜度為 O(N)。
• 空間複雜度：O(N)，因為歸併排序需要額外的空間來存儲合併後的數組。

最大子數組和

題目來源：LeetCode #53 中等

給你一個整數數組 nums，請你找出一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。

子數組是數組中的一個連續部分。

示例 1：

輸入：nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
輸出：6
解釋：連續子數組 [4, -1, 2, 1] 的和最大，為 6。

示例 2：

輸入：nums = [1]
輸出：1

示例 3：

輸入：nums = [5, 4, -1, 7, 8]
輸出：23

解決最大子數組和問題，分而治之的思想是一種有效的方法。分而治之的基本思想是將問題分解成子問題，分別解決這些子問題，然後合併這些子問題的解來得到原問題的解。在這個問題中，我們將數組分成兩個部分，然後遞歸地求解左右兩部分的最大子數組和，併合並兩部分的結果。

解題步驟：

1. 遞歸終止條件：當數組長度為 1 時，返回數組的唯一元素。
2. 分解數組：找到數組的中點，將數組分成左右兩部分。
3. 遞歸求解：遞歸地計算左半部分和右半部分的最大子數組和。

4. 合併：計算跨越中間的最大子數組和，包括：

   • 從中點向左掃描的最大子數組和。
   • 從中點向右掃描的最大子數組和。
   • 跨越中點的最大子數組和等於左半部分的最大和加上右半部分的最大和。

代碼實現：

function maxSubArray(nums) {
    // 分治法求解最大子數組和
    return divideAndConquer(nums, 0, nums.length - 1)
}

function divideAndConquer(nums, left, right) {
    // 基本情況：如果只有一個元素，返回該元素
    if (left === right) {
        return nums[left]
    }

    // 計算中間點
    const mid = Math.floor((left + right) / 2)

    // 遞歸求解左半部分和右半部分的最大子數組和
    const leftMax = divideAndConquer(nums, left, mid)
    const rightMax = divideAndConquer(nums, mid + 1, right)

    // 計算跨越中間點的最大子數組和
    const crossMax = maxCrossingSubArray(nums, left, mid, right)

    // 返回三個部分中最大的值
    return Math.max(leftMax, rightMax, crossMax)
}

function maxCrossingSubArray(nums, left, mid, right) {
    // 計算左半部分的最大子數組和
    let leftSum = -Infinity
    let sum = 0
    for (let i = mid; i >= left; i--) {
        sum += nums[i]
        if (sum > leftSum) {
            leftSum = sum
        }
    }

    // 計算右半部分的最大子數組和
    let rightSum = -Infinity
    sum = 0
    for (let i = mid + 1; i <= right; i++) {
        sum += nums[i]
        if (sum > rightSum) {
            rightSum = sum
        }
    }

    // 返回跨越中間點的最大子數組和
    return leftSum + rightSum
}

// 示例測試
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])) // 輸出：6
console.log(maxSubArray([1])) // 輸出：1
console.log(maxSubArray([5, 4, -1, 7, 8])) // 輸出：23

• 時間複雜度：O(n log n)：每次分治將問題分成兩個子問題，類似於歸併排序，每次合併時需要線性的時間來計算跨越中間的最大子數組和。
• 空間複雜度：O(log n)：遞歸調用的深度為 log n，因此空間複雜度為 O(log n)（不包括輸入和輸出所佔用的空間）。

數組中的第 K 個最大元素

題目來源：LeetCode #215 中等

給定整數數組 nums 和整數 k，請返回數組中第 k 個最大的元素。

請注意，你需要找的是數組排序後的第 k 個最大的元素，而不是第 k 個不同的元素。

你必須設計並實現時間複雜度為 O(n) 的算法解決此問題。

示例 1:

輸入: [3, 2, 1, 5, 6, 4], k = 2
輸出：5

示例 2:

輸入: [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
輸出：4

為了找到數組中的第 k 個最大元素，並且實現時間複雜度為 O(n) 的算法，我們可以使用快速選擇算法（Quickselect）。快速選擇算法是快速排序的變種，通過分而治之的方法來選擇特定的第 k 個元素。

解題步驟：

1. 選擇一個主元（pivot）：通常選擇數組的最後一個元素作為主元。
2. 分區：使用 Lomuto 分區方案，將數組重新排列，使得主元的位置是其最終位置，同時確保左邊的元素都小於等於主元，右邊的元素都大於主元。

3. 遞歸搜索：

   • 如果主元的位置正好是我們需要找的位置，直接返回主元。
   • 如果主元的位置大於目標位置，在左半部分繼續搜索。
   • 如果主元的位置小於目標位置，在右半部分繼續搜索。

代碼實現：

function findKthLargest(nums, k) {
    // 目標是找到第 k 大的元素，即排序後第 (n-k) 小的元素
    const targetIndex = nums.length - k;
    return quickSelect(nums, 0, nums.length - 1, targetIndex);
}

function quickSelect(nums, left, right, targetIndex) {
    if (left === right) {
        return nums[left];
    }

    // 分區操作
    const pivotIndex = partition(nums, left, right);

    if (pivotIndex === targetIndex) {
        return nums[pivotIndex];
    } else if (pivotIndex < targetIndex) {
        return quickSelect(nums, pivotIndex + 1, right, targetIndex);
    } else {
        return quickSelect(nums, left, pivotIndex - 1, targetIndex);
    }
}

function partition(nums, left, right) {
    const pivot = nums[right];
    let i = left;

    for (let j = left; j < right; j++) {
        if (nums[j] <= pivot) {
            [nums[i], nums[j]] = [nums[j], nums[i]];
            i++;
        }
    }

    [nums[i], nums[right]] = [nums[right], nums[i]];
    return i;
}

// 示例測試
console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2)); // 輸出：5
console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)); // 輸出：4

• 時間複雜度：平均情況為 O(n)，因為每次分區都會將數組分成兩部分。然而，在最壞情況下（例如數組已經有序時），時間複雜度可能達到 O(n^2)。
• 空間複雜度：O(1)，因為快速選擇是就地排序的算法，不需要額外的空間來存儲數組。遞歸調用的棧空間為 O(log n)。

動態規劃

動態規劃是一種解決複雜問題的方法，通過將問題分解成更小的子問題，並利用子問題的重疊性，避免重複計算，從而提高效率。動態規劃的核心思想是利用已計算的結果來構建解決方案，從而減少不必要的計算。

基本步驟

1. 定義子問題：將原問題分解為若干子問題，確定這些子問題的狀態和狀態之間的轉移關係。
2. 確定狀態轉移方程：根據子問題的定義，找出當前狀態與之前狀態的關係，即狀態轉移方程。
3. 初始化：確定初始狀態的值。
4. 填表計算：利用狀態轉移方程，從初始狀態出發，逐步計算每個子問題的值，通常使用一個表格（數組）來存儲子問題的解。
5. 返回結果：根據問題的要求，從表格中提取最終的結果。

使用場景

動態規劃主要用於解決以下幾類問題：

• 最優化問題：如最短路徑、最大子序列和等問題。
• 計數問題：如統計符合某些條件的方案數量。
• 序列問題：如最長遞增子序列、最長公共子序列等問題。
• 劃分問題：如揹包問題、劃分等問題。

動態規劃的應用

爬樓梯

題目來源：LeetCode #70 簡單

假設你正在爬樓梯。需要 n 階你才能到達樓頂。
每次你可以爬 1 或 2 個台階。你有多少種不同的方法可以爬到樓頂呢？

示例 1：

輸入：n = 2
輸出：2
解釋：有兩種方法可以爬到樓頂。

1. 1 階 + 1 階
2. 2 階

示例 2：

輸入：n = 3
輸出：3
解釋：有三種方法可以爬到樓頂。

1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階

解題步驟：

1. 定義狀態：定義一個數組 dp，其中 dp[i] 表示達到第 i 階的方法總數。
2. 初始條件：知道 dp[0] = 1（到達第 0 階的方法是站在原地）和 dp[1] = 1（到達第 1 階的方法只有一種）。
3. 狀態轉移方程：為了到達第 i 階，可以從第 i-1 階邁一步或者從第 i-2 階邁兩步，所以 dp[i] = dp[i-1] + dp[i-2]。
4. 最終結果：dp[n] 表示達到第 n 階的方法總數。

代碼實現：

function climbStairs(n) {
   // 如果樓梯階數為 0 或 1，直接返回 n
   if (n <= 1) return n

   // 創建一個 dp 數組來存儲每個台階的方法數
   const dp = new Array(n + 1).fill(0)

   // 初始條件
   dp[0] = 1
   dp[1] = 1

   // 計算每個台階的方法數
   for (let i = 2; i <= n; i++) {
      dp[i] = dp[i - 1] + dp[i - 2]
   }

   // 返回到達第 n 階的方法總數
   return dp[n]
}

// 示例測試
console.log(climbStairs(2)) // 輸出：2
console.log(climbStairs(3)) // 輸出：3
console.log(climbStairs(4)) // 輸出：5
console.log(climbStairs(5)) // 輸出：8

• 時間複雜度：O(n)，因為只需遍歷一次數組。
• 空間複雜度：O(n)，需要一個長度為 n+1 的數組來存儲每一階的方法數。

最長遞增子序列

題目來源：LeetCode #300 中等

給你一個整數數組 nums，找到其中最長嚴格遞增子序列的長度。

子序列是由數組派生而來的序列，刪除（或不刪除）數組中的元素而不改變其餘元素的順序。例如，[3, 6, 2, 7] 是數組 [0, 3, 1, 6, 2, 2, 7] 的子序列。

示例 1：

輸入：nums = [10, 9, 2, 5, 3, 7, 101, 18]
輸出：4
解釋：最長遞增子序列是 [2, 3, 7, 101]，因此長度為 4。

示例 2：

輸入：nums = [0, 1, 0, 3, 2, 3]
輸出：4

示例 3：

輸入：nums = [7, 7, 7, 7, 7, 7, 7]
輸出：1

解題步驟：

1. 定義狀態：定義一個數組 dp，其中 dp[i] 表示以 nums[i] 結尾的最長遞增子序列的長度。
2. 初始化：每個位置的初始值為 1，因為每個位置都至少可以是一個長度為 1 的子序列。
3. 狀態轉移方程：對於每個 nums[i]，遍歷其之前的元素 nums[j] (0 ≤ j < i)，如果 nums[i] > nums[j]，則更新 dp[i] = max(dp[i], dp[j] + 1)，表示在 nums[j] 的子序列上追加 nums[i]。
4. 最終結果：數組 dp 中的最大值即為最長遞增子序列的長度。

代碼實現：

function lengthOfLIS(nums) {
   if (nums.length === 0) return 0

   // dp 數組，每個位置初始化為 1
   const dp = new Array(nums.length).fill(1)

   // 計算每個位置的最長遞增子序列長度
   for (let i = 1; i < nums.length; i++) {
      for (let j = 0; j < i; j++) {
         if (nums[i] > nums[j]) {
            dp[i] = Math.max(dp[i], dp[j] + 1)
         }
      }
   }

   // 返回 dp 數組中的最大值
   return Math.max(...dp)
}

// 示例測試
console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])) // 輸出：4
console.log(lengthOfLIS([0, 1, 0, 3, 2, 3])) // 輸出：4
console.log(lengthOfLIS([7, 7, 7, 7, 7, 7, 7])) // 輸出：1

• 時間複雜度：O(n^2)，因為我們需要嵌套循環遍歷每個元素對。
• 空間複雜度：O(n)，需要一個長度為 n 的數組來存儲每個位置的最長子序列長度。

打家劫舍

題目來源：LeetCode #198 中等

你是一個專業的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。

給定一個代表每個房屋存放金額的非負整數數組，計算你不觸動警報裝置的情況下，一夜之內能夠偷竊到的最高金額。

示例 1：

輸入：[1, 2, 3, 1]
輸出：4
解釋：偷竊 1 號房屋 (金額 = 1) ，然後偷竊 3 號房屋 (金額 = 3)。
偷竊到的最高金額 = 1 + 3 = 4。

示例 2：

輸入：[2, 7, 9, 3, 1]
輸出：12
解釋：偷竊 1 號房屋 (金額 = 2), 偷竊 3 號房屋 (金額 = 9)，接着偷竊 5 號房屋 (金額 = 1)。
偷竊到的最高金額 = 2 + 9 + 1 = 12。

解題步驟：

1. 定義狀態：定義一個數組 dp，其中 dp[i] 表示到達第 i 個房子時可以偷竊到的最高金額。
2. 初始條件：如果只有一個房子，那麼可以偷竊的最高金額就是該房子的金額，即 dp[0] = nums[0]。如果有兩個房子，則可以偷竊的最高金額是這兩個房子中金額較大的那個，即 dp[1] = Math.max(nums[0], nums[1])。
3. 狀態轉移方程：對於每個房子 i，有兩種選擇：偷竊該房子（然後加上 i-2 房子的最高金額）或者不偷竊該房子（直接取 i-1 房子的最高金額）。狀態轉移方程為 dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])。
4. 最終結果：數組 dp 中的最後一個值即為可以偷竊到的最高金額。

代碼實現：

function rob(nums) {
   const n = nums.length
   if (n === 0) return 0
   if (n === 1) return nums[0]

   // dp 數組，每個位置初始化為 0
   const dp = new Array(n).fill(0)

   // 初始條件
   dp[0] = nums[0]
   dp[1] = Math.max(nums[0], nums[1])

   // 填充 dp 數組
   for (let i = 2; i < n; i++) {
      dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])
   }

   // 返回 dp 數組的最後一個值
   return dp[n - 1]
}

// 示例測試
console.log(rob([1, 2, 3, 1])) // 輸出：4
console.log(rob([2, 7, 9, 3, 1])) // 輸出：12

• 時間複雜度：O(n)，因為需要遍歷一次數組。
• 空間複雜度：O(n)，因為需要一個長度為 n 的數組來存儲每個位置的最高金額。

優化空間複雜度：

注意到我們在狀態轉移時，只需要前兩個狀態的值，所以可以將空間複雜度優化為 O(1)。

function rob(nums) {
   const n = nums.length
   if (n === 0) return 0
   if (n === 1) return nums[0]

   let prev1 = 0
   let prev2 = 0

   for (let i = 0; i < n; i++) {
      const current = Math.max(prev1, prev2 + nums[i])
      prev2 = prev1
      prev1 = current
   }

   return prev1
}

// 示例測試
console.log(rob([1, 2, 3, 1])) // 輸出：4
console.log(rob([2, 7, 9, 3, 1])) // 輸出：12

優化後的算法分析：

• 時間複雜度：O(n)，因為需要遍歷一次數組。
• 空間複雜度：O(1)，因為只需要常量空間來存儲前兩個狀態的值。

通過上述方法，我們可以有效地計算出不觸動警報裝置的情況下，可以偷竊到的最高金額。優化後的代碼在空間複雜度上更高效。

零錢兑換

題目來源：LeetCode #322 中等

給你一個整數數組 coins，表示不同面額的硬幣；以及一個整數 amount，表示總金額。

計算並返回可以湊成總金額所需的最少的硬幣個數。如果沒有任何一種硬幣組合能組成總金額，返回 -1。

你可以認為每種硬幣的數量是無限的。

示例 1：

輸入：coins = [1, 2, 5], amount = 11
輸出：3
解釋：11 = 5 + 5 + 1

示例 2：

輸入：coins = [2], amount = 3
輸出：-1

示例 3：

輸入：coins = [1], amount = 0
輸出：0

解題步驟：

1. 定義狀態：定義一個數組 dp，其中 dp[i] 表示湊成金額 i 所需的最少硬幣個數。
2. 初始化：dp[0] = 0，因為湊成金額 0 所需的硬幣數是 0。其他 dp[i] 初始化為一個較大的值（如 Infinity），表示還沒有計算出結果。
3. 狀態轉移方程：對於每個金額 i，嘗試使用每種硬幣 coin，更新 dp[i] = Math.min(dp[i], dp[i - coin] + 1)，表示從金額 i - coin 加上一個 coin 的硬幣數量。
4. 最終結果：如果 dp[amount] 仍然是初始值 Infinity，則表示無法湊成該金額，返回 -1，否則返回 dp[amount]。

代碼實現：

function coinChange(coins, amount) {
   // 創建一個 dp 數組，初始化為 Infinity
   const dp = new Array(amount + 1).fill(Infinity)
   dp[0] = 0 // 初始化金額為 0 時的最少硬幣數為 0

   // 填充 dp 數組
   for (let i = 1; i <= amount; i++) {
      for (const coin of coins) {
         if (i - coin >= 0) {
            dp[i] = Math.min(dp[i], dp[i - coin] + 1)
         }
      }
   }

   // 如果 dp[amount] 還是 Infinity，表示無法湊成該金額，返回 -1
   return dp[amount] === Infinity ? -1 : dp[amount]
}

// 示例測試
console.log(coinChange([1, 2, 5], 11)) // 輸出：3
console.log(coinChange([2], 3)) // 輸出：-1
console.log(coinChange([1], 0)) // 輸出：0
console.log(coinChange([1, 3, 4, 5], 7)) // 輸出：2 (3 + 4)
console.log(coinChange([2, 5, 10, 1], 27)) // 輸出：4 (10 + 10 + 5 + 2)

• 時間複雜度：O(n * m)，其中 n 是金額 amount，m 是硬幣種類數。
• 空間複雜度：O(n)，需要一個長度為 amount + 1 的數組來存儲每個金額的最少硬幣數。

貪心算法

貪心算法是一種在每一步選擇中都採取在當前狀態下最好或最優的選擇，從而希望導致結果是全局最優的算法。貪心算法的核心是貪心選擇性質，即每一步的局部最優選擇最終能夠導致全局最優解。

基本步驟

1. 建立數學模型：將問題抽象為數學模型，明確所需的解和約束條件。
2. 選擇貪心策略：根據問題的特性，選擇一個貪心策略，即在每一步選擇中，採取局部最優的選擇。
3. 證明貪心選擇的正確性：證明所選的貪心策略能夠得到問題的最優解，通常通過數學歸納法或反證法證明。
4. 實施貪心算法：從初始狀態開始，按照貪心策略逐步推進，直到達到問題的約束條件或無法繼續推進為止。
5. 構造解：根據選擇的步驟，構造出問題的解。

使用場景

貪心算法通常用於以下幾類問題：

• 最優化問題：如最小生成樹、最短路徑等問題。
• 活動選擇問題：如區間調度、任務安排等問題。
• 資源分配問題：如揹包問題的某些變種、最大子序列和等問題。
• 圖論問題：如 Dijkstra 算法求最短路徑，Kruskal 算法和 Prim 算法求最小生成樹。

貪心算法的應用

分發餅乾

題目來源：LeetCode #455 簡單

假設你是一位很棒的家長，想要給你的孩子們一些小餅乾。但是，每個孩子最多隻能給一塊餅乾。

對每個孩子 i，都有一個胃口值 g[i]，這是能讓孩子們滿足胃口的餅乾的最小尺寸；並且每塊餅乾 j，都有一個尺寸 s[j]。如果 s[j] >= g[i]，我們可以將這個餅乾 j 分配給孩子 i，這個孩子會得到滿足。你的目標是儘可能滿足越多數量的孩子，並輸出這個最大數值。

示例 1:

輸入: g = [1, 2, 3], s = [1, 1]
輸出：1
解釋：
你有三個孩子和兩塊小餅乾，3 個孩子的胃口值分別是：1, 2, 3。
雖然你有兩塊小餅乾，由於他們的尺寸都是 1，你只能讓胃口值是 1 的孩子滿足。
所以你應該輸出 1。

示例 2:

輸入: g = [1, 2], s = [1, 2, 3]
輸出：2
解釋：
你有兩個孩子和三塊小餅乾，2 個孩子的胃口值分別是 1, 2。
你擁有的餅乾數量和尺寸都足以讓所有孩子滿足。
所以你應該輸出 2。

先對孩子的滿足度和餅乾的大小排序，然後依次為每個孩子分配滿足其滿足度的最小餅乾。

解題步驟：

1. 排序：將孩子的胃口數組 g 和餅乾尺寸數組 s 分別進行排序。
2. 匹配：使用兩個指針，一個指向孩子的胃口數組，另一個指向餅乾尺寸數組。依次嘗試用當前最小的餅乾去滿足當前最小的胃口。
3. 更新指針：如果當前餅乾可以滿足當前孩子的胃口，兩個指針都移動到下一個。如果不能，則只移動餅乾的指針，嘗試用下一個較大的餅乾去滿足當前孩子的胃口。
4. 結束條件：當兩個指針都到達數組末尾時，匹配結束，返回滿足孩子的數量。

代碼實現：

function findContentChildren(g, s) {
   // 對孩子的胃口數組和餅乾尺寸數組進行排序
   g.sort((a, b) => a - b)
   s.sort((a, b) => a - b)

   let i = 0 // 孩子的指針
   let j = 0 // 餅乾的指針
   let count = 0 // 滿足的孩子數量

   // 當孩子和餅乾都沒有處理完時進行匹配
   while (i < g.length && j < s.length) {
      if (s[j] >= g[i]) {
         // 當前餅乾可以滿足當前孩子
         count++
         i++
      }
      // 無論是否滿足，都嘗試下一個餅乾
      j++
   }

   return count
}

// 示例測試
console.log(findContentChildren([1, 2, 3], [1, 1])) // 輸出：1
console.log(findContentChildren([1, 2], [1, 2, 3])) // 輸出：2
console.log(findContentChildren([1, 2, 3], [3])) // 輸出：1
console.log(findContentChildren([10, 9, 8, 7], [5, 6, 7, 8])) // 輸出：2

• 時間複雜度：O(n log n + m log m)，其中 n 是孩子數組的長度，m 是餅乾數組的長度。這是因為排序需要 O(n log n) 和 O(m log m)。
• 空間複雜度：O(1)，只需要常量級別的額外空間。

檸檬水找零

題目來源：LeetCode #860 簡單

在檸檬水攤上，每一杯檸檬水的售價為 5 美元。顧客排隊購買你的產品（按賬單 bills 支付的順序）一次購買一杯。

每位顧客只買一杯檸檬水，然後向你付 5 美元、10 美元或 20 美元。你必須給每個顧客正確找零，也就是説淨交易是每位顧客向你支付 5 美元。

注意，一開始你手頭沒有任何零錢。

給你一個整數數組 bills，其中 bills[i] 是第 i 位顧客付的賬。如果你能給每位顧客正確找零，返回 true，否則返回 false。

示例 1：

輸入：bills = [5, 5, 5, 10, 20]
輸出：true
解釋：
前 3 位顧客那裏，我們按順序收取 3 張 5 美元的鈔票。
第 4 位顧客那裏，我們收取一張 10 美元的鈔票，並返還 5 美元。
第 5 位顧客那裏，我們找還一張 10 美元的鈔票和一張 5 美元的鈔票。
由於所有客户都得到了正確的找零，所以我們輸出 true。

示例 2：

輸入：bills = [5, 5, 10, 10, 20]
輸出：false
解釋：
前 2 位顧客那裏，我們按順序收取 2 張 5 美元的鈔票。
對於接下來的 2 位顧客，我們收取一張 10 美元的鈔票，然後返還 5 美元。
對於最後一位顧客，我們無法退回 15 美元，因為我們現在只有兩張 10 美元的鈔票。
由於不是每位顧客都得到了正確的找零，所以答案是 false。

遍歷顧客給的錢，優先使用手中的大額鈔票找零，從而保留小額鈔票以應對後續的找零需求。

解題步驟：

1. 初始化錢箱：使用兩個變量 five 和 ten 來分別表示手中擁有的 5 美元和 10 美元的數量，初始值為 0。
2. 遍歷賬單：遍歷顧客付的每一張賬單。

3. 處理賬單：

   • 如果顧客付的是 5 美元，直接收下。
   • 如果顧客付的是 10 美元，需要找零，檢查是否有足夠的 5 美元找零，如果有則找零，否則無法找零，返回 false。
   • 如果顧客付的是 20 美元，需要找零，優先使用 10 美元找零，然後再用 5 美元找零，如果都無法找零，則返回 false。
4. 返回結果：遍歷結束後，如果能夠給每個顧客正確找零，則返回 true，否則返回 false。

代碼實現：

function lemonadeChange(bills) {
   let five = 0
   let ten = 0

   for (const bill of bills) {
      if (bill === 5) {
         // 顧客付 5 美元，直接收下
         five++
      } else if (bill === 10) {
         // 顧客付 10 美元，嘗試找零，優先使用 10 美元找零
         if (five === 0) {
            return false // 無法找零，返回 false
         }
         five--
         ten++
      } else {
         // 顧客付 20 美元，嘗試找零，優先使用 10 美元找零，再使用 5 美元找零
         if (ten > 0 && five > 0) {
            ten--
            five--
         } else if (five >= 3) {
            five -= 3
         } else {
            return false // 無法找零，返回 false
         }
      }
   }

   return true
}

// 示例測試
console.log(lemonadeChange([5, 5, 5, 10, 20])) // 輸出：true
console.log(lemonadeChange([5, 5, 10, 10, 20])) // 輸出：false

• 時間複雜度：O(n)，其中 n 是賬單的數量，我們需要遍歷一次賬單數組。
• 空間複雜度：O(1)，只需要常數級別的額外空間來存儲 5 美元和 10 美元的數量。

跳躍遊戲

題目來源：LeetCode #55 中等

給你一個非負整數數組 nums，你最初位於數組的第一個下標。數組中的每個元素代表你在該位置可以跳躍的最大長度。

判斷你是否能夠到達最後一個下標，如果可以，返回 true；否則，返回 false。

示例 1：

輸入：nums = [2, 3, 1, 1, 4]
輸出：true
解釋：可以先跳 1 步，從下標 0 到達下標 1, 然後再從下標 1 跳 3 步到達最後一個下標。

示例 2：

輸入：nums = [3, 2, 1, 0, 4]
輸出：false
解釋：無論怎樣，總會到達下標為 3 的位置。但該下標的最大跳躍長度是 0，所以永遠不可能到達最後一個下標。

從前往後遍歷數組，維護當前能夠到達的最遠位置，如果在某一步能夠到達或超過數組的最後一個位置，則返回 true。

解題步驟：

1. 初始化：定義一個變量 maxReach，表示當前能夠到達的最遠位置，初始值為 0。
2. 遍歷數組：從頭到尾遍歷數組的每個位置，檢查當前位置是否能夠到達。如果當前位置大於 maxReach，説明不能到達當前位置，返回 false。
3. 更新最遠可達位置：如果當前位置在可達範圍內，更新 maxReach 為 max(maxReach, i + nums[i])。
4. 檢查是否可達：如果在遍歷過程中，maxReach 大於或等於數組的最後一個下標，返回 true。

代碼實現：

function canJump(nums) {
   let maxReach = 0

   for (let i = 0; i < nums.length; i++) {
      // 如果當前下標超過了能到達的最遠位置
      if (i > maxReach) {
         return false
      }
      // 更新能到達的最遠位置
      maxReach = Math.max(maxReach, i + nums[i])
      // 如果能到達或超過最後一個下標
      if (maxReach >= nums.length - 1) {
         return true
      }
   }

   return false
}

// 示例測試
console.log(canJump([2, 3, 1, 1, 4])) // 輸出：true
console.log(canJump([3, 2, 1, 0, 4])) // 輸出：false
console.log(canJump([0])) // 輸出：true (只有一個元素，已經在最後一個下標)
console.log(canJump([2, 0])) // 輸出：true (可以直接到達最後一個下標)
console.log(canJump([1, 2, 3, 4, 5])) // 輸出：true (每步都能跳到最後)

1. canJump 函數：主函數，判斷是否能夠到達最後一個下標。
2. 初始化 maxReach：定義變量 maxReach 表示當前能夠到達的最遠位置，初始值為 0。

3. 遍歷數組：

   • 對於每個位置 i，檢查是否超過了 maxReach。如果是，返回 false，表示不能到達該位置。
   • 否則，更新 maxReach 為 max(maxReach, i + nums[i])，表示當前能夠到達的最遠位置。
4. 檢查終止條件：如果 maxReach 已經大於或等於數組的最後一個下標，返回 true。
5. 返回結果：遍歷結束後，如果沒有返回 true，則返回 false。

• 時間複雜度：O(n)，因為我們需要遍歷一次數組。
• 空間複雜度：O(1)，只需要常量級別的額外空間。

無重疊區間

題目來源：LeetCode #435 中等

給定一個區間的集合 intervals，其中 intervals[i] = [starti, endi] 。返回需要移除區間的最小數量，使剩餘區間互不重疊。

示例 1:

輸入: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
輸出：1
解釋: 移除 [1, 3] 後，剩下的區間沒有重疊。

示例 2:

輸入: intervals = [[1, 2], [1,2], [1,2]]
輸出：2
解釋: 你需要移除兩個 [1, 2] 來使剩下的區間沒有重疊。

示例 3:

輸入: intervals = [[1, 2], [2, 3]]
輸出：0
解釋：你不需要移除任何區間，因為它們已經是無重疊的了。

先按照區間的結束時間排序，然後依次選擇結束時間最早且不與前一個選擇的區間重疊的區間。對於這個問題，我們要儘可能多地保留區間，從而使得需要移除的區間數量最小。

解題步驟：

1. 排序：首先將區間按照結束時間 end 進行排序。這樣可以保證每次選擇的區間結束時間儘可能早，以便留出更多的空間給後面的區間。
2. 貪心選擇：使用一個變量 end 來記錄上一個選擇的區間的結束時間。初始化 end 為負無窮大。
3. 遍歷區間：依次遍歷排序後的區間，如果當前區間的起始時間 start 大於等於 end，説明這個區間可以保留，同時更新 end 為當前區間的結束時間 end。否則，這個區間需要移除。
4. 統計結果：遍歷結束後，計算需要移除的區間數量。

代碼實現：

function eraseOverlapIntervals(intervals) {
   if (intervals.length === 0) return 0

   // 按區間的結束時間進行排序
   intervals.sort((a, b) => a[1] - b[1])

   let count = 0
   let end = -Infinity

   for (const [start, finish] of intervals) {
      if (start >= end) {
         // 當前區間可以保留，更新結束時間
         end = finish
      } else {
         // 當前區間與上一個區間重疊，需要移除
         count++
      }
   }

   return count
}

// 示例測試
console.log(eraseOverlapIntervals([[1, 2], [2, 3], [3, 4], [1, 3]])) // 輸出：1
console.log(eraseOverlapIntervals([[1, 2], [1, 2], [1, 2]])) // 輸出：2
console.log(eraseOverlapIntervals([[1, 2], [2, 3]])) // 輸出：0
console.log(eraseOverlapIntervals([[1, 2], [1, 3], [2, 4], [3, 5]])) // 輸出：1
console.log(eraseOverlapIntervals([[0, 2], [1, 3], [2, 4], [3, 5], [4, 6]])) // 輸出：2

1. eraseOverlapIntervals 函數：主函數，計算需要移除的區間數量。
2. 排序：將區間按照結束時間進行排序，使得每次選擇的區間結束時間儘可能早。
3. 初始化變量：count 用於記錄需要移除的區間數量，end 初始化為負無窮大。

4. 遍歷區間：

   • 如果當前區間的起始時間 start 大於等於 end，説明這個區間可以保留，並更新 end 為當前區間的結束時間 finish。
   • 否則，這個區間與上一個區間重疊，需要移除，增加 count 計數器。
5. 返回結果：遍歷結束後，返回需要移除的區間數量 count。

• 時間複雜度：O(n log n)，因為我們需要對區間進行排序。
• 空間複雜度：O(1)，不需要額外的空間，除了用於存儲輸入的區間列表。

分發糖果

題目來源：LeetCode #135 困難

n 個孩子站成一排。給你一個整數數組 ratings 表示每個孩子的評分。

你需要按照以下要求，給這些孩子分發糖果：

• 每個孩子至少分配到 1 個糖果。
• 相鄰兩個孩子評分更高的孩子會獲得更多的糖果。

請你給每個孩子分發糖果，計算並返回需要準備的最少糖果數目。

示例 1：

輸入：ratings = [1, 0, 2]
輸出：5
解釋：你可以分別給第一個、第二個、第三個孩子分發 2、1、2 顆糖果。

示例 2：

輸入：ratings = [1, 2, 2]
輸出：4
解釋：你可以分別給第一個、第二個、第三個孩子分發 1、2、1 顆糖果。
第三個孩子只得到 1 顆糖果，這滿足題面中的兩個條件。

先從左到右掃描數組，確保右邊的評分更高的孩子獲得更多糖果；再從右到左掃描數組，確保左邊的評分更高的孩子獲得更多糖果。

解題步驟：

1. 初始化：創建一個數組 candies，初始化每個孩子的糖果數為 1，表示每個孩子至少有一個糖果。
2. 從左到右遍歷：檢查每個孩子與前一個孩子的評分，如果當前孩子的評分比前一個孩子高，則更新當前孩子的糖果數為 candies[i-1] + 1。
3. 從右到左遍歷：檢查每個孩子與後一個孩子的評分，如果當前孩子的評分比後一個孩子高且糖果數不大於後一個孩子，則更新當前孩子的糖果數為 candies[i+1] + 1。
4. 計算總糖果數：遍歷 candies 數組，求和得到最少需要的糖果數。

代碼實現：

function candy(ratings) {
   const n = ratings.length
   const candies = new Array(n).fill(1)

   // 從左到右遍歷，保證右邊孩子評分高的糖果更多
   for (let i = 1; i < n; i++) {
      if (ratings[i] > ratings[i - 1]) {
         candies[i] = candies[i - 1] + 1
      }
   }

   // 從右到左遍歷，保證左邊孩子評分高的糖果更多
   for (let i = n - 2; i >= 0; i--) {
      if (ratings[i] > ratings[i + 1]) {
         candies[i] = Math.max(candies[i], candies[i + 1] + 1)
      }
   }

   // 計算總糖果數
   return candies.reduce((sum, candy) => sum + candy, 0)
}

// 示例測試
console.log(candy([1, 0, 2])) // 輸出：5
console.log(candy([1, 2, 2])) // 輸出：4
console.log(candy([1, 3, 2, 2, 1])) // 輸出：7
console.log(candy([1, 2, 3, 4, 5])) // 輸出：15
console.log(candy([5, 4, 3, 2, 1])) // 輸出：15

1. candy 函數：主函數，計算最少需要的糖果數。
2. 初始化 candies 數組：每個孩子至少分配 1 個糖果。

3. 從左到右遍歷：

   • 如果當前孩子的評分高於前一個孩子，則當前孩子的糖果數等於前一個孩子的糖果數加 1。

4. 從右到左遍歷：

   • 如果當前孩子的評分高於後一個孩子且糖果數不大於後一個孩子，則更新當前孩子的糖果數為 candies[i + 1] + 1。
5. 計算總糖果數：通過遍歷 candies 數組求和得到最少需要的糖果數。

• 時間複雜度：O(n)，因為我們需要遍歷兩次數組，每次遍歷的時間複雜度都是 O(n)。
• 空間複雜度：O(n)，因為我們需要額外的數組 candies 來存儲每個孩子的糖果數。

回溯算法

回溯算法是一種通過逐步構建解決方案的方法，當遇到某一步無法繼續前進時，回溯算法會回退到上一步，嘗試其他的選擇，直到找到問題的解決方案或確定無解。回溯算法通常通過深度優先搜索的方式實現。

基本步驟

1. 選擇決策樹：將問題抽象成一個決策樹，每個節點代表一個決策點。
2. 深度優先搜索：從根節點開始，採用深度優先搜索的方式探索決策樹的所有分支。
3. 做出選擇：在每個節點處，根據問題的限制條件，做出一個選擇。
4. 檢查約束條件：檢查當前選擇是否滿足問題的約束條件，如果滿足則繼續探索，否則回溯到上一步。
5. 標記路徑：在探索過程中，記錄已經探索過的路徑，避免重複探索。
6. 撤銷選擇：在回溯時，撤銷當前節點的選擇，回到上一層繼續探索其他分支。
7. 判斷終止條件：當到達葉子節點或者無法繼續探索時，判斷是否找到了問題的解決方案。

使用場景

回溯算法通常用於以下幾類問題：

• 組合問題：如組合總和、組合總和 II 等問題。
• 排列問題：如全排列、字符串的全排列等問題。
• 搜索問題：如解數獨、N 皇后問題等。
• 子集問題：如子集、子集 II 等問題。

回溯算法的應用

全排列

題目來源：LeetCode #46 中等

給定一個不含重複數字的數組 nums，返回其所有可能的全排列。你可以按任意順序返回答案。

示例 1：

輸入：nums = [1, 2, 3]
輸出：[[1, 2, 3], [1, 3, 2], [2, 1 ,3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

示例 2：

輸入：nums = [0, 1]
輸出：[[0, 1], [1, 0]]

示例 3：

輸入：nums = [1]
輸出：[[1]]

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整數互不相同

解題步驟：

1. 初始化結果集：創建一個結果數組 result 來存儲所有的排列。
2. 回溯函數：定義一個回溯函數 backtrack，參數為當前路徑 path 和剩餘可選擇的數字 choices。
3. 終止條件：當路徑長度等於輸入數組長度時，表明我們找到了一種排列，將其加入結果集。
4. 選擇和探索：遍歷剩餘可選擇的數字，將每個數字加入當前路徑，並遞歸調用回溯函數，傳遞更新後的路徑和剩餘可選擇的數字。
5. 回溯：在遞歸調用結束後，撤銷上一步選擇，進行下一輪選擇和探索。

代碼實現：

function permute(nums) {
   const result = []

   function backtrack(path, choices) {
      if (path.length === nums.length) {
         result.push([...path])
         return
      }
      for (let i = 0; i < choices.length; i++) {
         path.push(choices[i])
         backtrack(path, choices.slice(0, i).concat(choices.slice(i + 1)))
         path.pop()
      }
   }

   backtrack([], nums)
   return result
}

// 示例測試
console.log(permute([1, 2, 3])) // 輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
console.log(permute([0, 1])) // 輸出：[[0,1],[1,0]]
console.log(permute([1])) // 輸出：[[1]]

1. permute 函數：主函數，接收輸入數組 nums，返回所有的排列。
2. 初始化結果集：創建一個空數組 result 來存儲所有的排列結果。
3. backtrack 函數：遞歸函數，構建排列。參數 path 表示當前路徑，choices 表示當前剩餘的可選擇數字。
4. 終止條件：當路徑長度等於輸入數組長度時，將當前路徑加入結果集。
5. 選擇和探索：遍歷剩餘可選擇的數字，將每個數字加入當前路徑，遞歸調用 backtrack 函數，並傳遞更新後的路徑和剩餘可選擇的數字。
6. 回溯：在遞歸調用結束後，撤銷上一步選擇，通過 path.pop() 將最後一個元素移除，進行下一輪選擇和探索。

• 時間複雜度：O(n * n!)，其中 n 是輸入數組的長度。總共有 n! 種排列，每種排列需要 O(n) 的時間來構建。
• 空間複雜度：O(n)，用於存儲遞歸調用棧和臨時路徑。

子集

題目來源：LeetCode 78 中等

給你一個整數數組 nums，數組中的元素互不相同。返回該數組所有可能的子集（冪集）。

解集不能包含重複的子集。你可以按任意順序返回解集。

示例 1：

輸入：nums = [1, 2, 3]
輸出：[[], [1], [2], [1,2], [3], [1, 3], [2, 3], [1, 2, 3]]

示例 2：

輸入：nums = [0]
輸出：[[], [0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素互不相同

解題步驟：

1. 初始化結果集：創建一個結果數組 result 來存儲所有的子集。
2. 回溯函數：定義一個回溯函數 backtrack，參數為當前路徑 path 和起始索引 start。
3. 添加當前路徑到結果集：將當前路徑 path 的拷貝加入結果集 result。
4. 選擇和探索：從起始索引開始遍歷 nums 數組，將每個數字加入當前路徑，並遞歸調用回溯函數，傳遞更新後的路徑和新的起始索引。
5. 回溯：在遞歸調用結束後，撤銷上一步選擇，進行下一輪選擇和探索。

代碼實現：

function subsets(nums) {
   const result = []

   function backtrack(path, start) {
      // 將當前路徑加入結果集
      result.push([...path])
      // 從當前索引開始遍歷 nums 數組
      for (let i = start; i < nums.length; i++) {
         // 將當前數字加入路徑
         path.push(nums[i])
         // 遞歸調用回溯函數，傳遞更新後的路徑和新的起始索引
         backtrack(path, i + 1)
         // 回溯，撤銷上一步選擇
         path.pop()
      }
   }

   // 初始化回溯
   backtrack([], 0)
   return result
}

// 示例測試
console.log(subsets([1, 2, 3])) // 輸出：[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
console.log(subsets([0])) // 輸出：[[], [0]]

1. subsets 函數：主函數，接收輸入數組 nums，返回所有的子集。
2. 初始化結果集：創建一個空數組 result 來存儲所有的子集結果。
3. backtrack 函數：遞歸函數，構建子集。參數 path 表示當前路徑，start 表示起始索引。
4. 添加當前路徑到結果集：將當前路徑 path 的拷貝加入結果集 result。
5. 選擇和探索：從起始索引開始遍歷 nums 數組，將每個數字加入當前路徑 path，遞歸調用 backtrack 函數，並傳遞更新後的路徑和新的起始索引 i + 1。
6. 回溯：在遞歸調用結束後，撤銷上一步選擇，通過 path.pop() 將最後一個元素移除，進行下一輪選擇和探索。

• 時間複雜度：O(n * 2^n)，其中 n 是輸入數組的長度。總共有 2^n 個子集，每個子集的平均長度為 n/2。
• 空間複雜度：O(n)，用於存儲遞歸調用棧和臨時路徑。

單詞拆分 II

題目來源：LeetCode #140 困難

給定一個字符串 s 和一個字符串字典 wordDict，在字符串 s 中增加空格來構建一個句子，使得句子中所有的單詞都在詞典中。以任意順序返回所有這些可能的句子。

注意：詞典中的同一個單詞可能在分段中被重複使用多次。

示例 1：

輸入：s = "catsanddog", wordDict = ["cat", "cats", "and", "sand", "dog"]
輸出：["cats and dog", "cat sand dog"]

示例 2：

輸入：s = "pineapplepenapple", wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
輸出：["pine apple pen apple", "pineapple pen apple", "pine applepen apple"]
解釋：注意你可以重複使用字典中的單詞。

示例 3：

輸入：s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
輸出：[]

提示：

• 1 <= s.length <= 20
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 10
• s 和 wordDict[i] 僅有小寫英文字母組成
• wordDict 中所有字符串都不同

要解決這個問題，我們可以使用回溯算法結合動態規劃進行優化。具體來説，我們需要遞歸地嘗試在字符串 s 中插入空格來構成單詞，同時使用緩存來存儲已經計算過的結果，避免重複計算。

解題步驟：

1. 定義緩存：使用一個對象 memo 來存儲已經計算過的子問題的結果。
2. 定義回溯函數：遞歸函數 backtrack，參數為當前子字符串 s。
3. 遞歸終止條件：如果當前子字符串 s 在緩存中，直接返回緩存中的結果；如果 s 為空字符串，返回包含一個空字符串的數組。
4. 遍歷匹配：遍歷詞典中的單詞，如果當前子字符串 s 以該單詞開頭，則遞歸處理剩餘部分的字符串，並將結果組合起來。
5. 更新緩存：將當前子字符串的結果存入緩存中，並返回該結果。

代碼實現：

function wordBreak(s, wordDict) {
   const wordSet = new Set(wordDict)
   const memo = {}

   function backtrack(s) {
      // 如果當前子字符串已經在緩存中，直接返回緩存的結果
      if (memo[s] !== undefined) {
         return memo[s]
      }
      // 如果子字符串為空，返回包含一個空字符串的數組
      if (s === '') {
         return ['']
      }

      const result = []

      // 遍歷詞典中的每個單詞
      for (const word of wordSet) {
         if (s.startsWith(word)) {
            const subResult = backtrack(s.slice(word.length))
            for (const sub of subResult) {
               result.push(word + (sub === '' ? '' : ' ') + sub)
            }
         }
      }

      // 將當前子字符串的結果存入緩存
      memo[s] = result
      return result
   }

   return backtrack(s)
}

// 示例測試
console.log(wordBreak('catsanddog', ['cat', 'cats', 'and', 'sand', 'dog']))
// 輸出：["cats and dog", "cat sand dog"]

console.log(wordBreak('pineapplepenapple', ['apple', 'pen', 'applepen', 'pine', 'pineapple']))
// 輸出：["pine apple pen apple", "pineapple pen apple", "pine applepen apple"]

console.log(wordBreak('catsandog', ['cats', 'dog', 'sand', 'and', 'cat']))
// 輸出：[]

1. wordBreak 函數：主函數，接收字符串 s 和詞典 wordDict，返回所有可能的句子。
2. 初始化：將詞典轉化為集合 wordSet，用於快速查找；定義緩存 memo。
3. backtrack 函數：遞歸函數，處理當前子字符串 s，返回其所有可能的句子組合。
4. 緩存查詢：如果當前子字符串 s 在緩存中，直接返回緩存中的結果。
5. 遞歸終止條件：如果子字符串 s 為空，返回包含一個空字符串的數組。
6. 遍歷詞典：對於每個單詞，如果當前子字符串 s 以該單詞開頭，則遞歸處理剩餘部分的字符串 s.slice(word.length)。
7. 組合結果：將當前單詞和遞歸結果組合成新的句子，並添加到結果集中。
8. 更新緩存：將當前子字符串 s 的結果存入緩存 memo，避免重複計算。
9. 返回結果：主函數調用 backtrack 函數，返回最終結果。

• 時間複雜度：最壞情況下為 O(n^2 * k)，其中 n 是字符串 s 的長度，k 是詞典 wordDict 的大小。每個子字符串的計算會涉及到對詞典的遍歷，並且需要組合結果。
• 空間複雜度：O(n^2)，用於緩存子字符串的結果和存儲遞歸棧。

最後

感謝大家看到最後，本文篇幅較長，難免會有錯誤，還望同學們多指正。看完本文後還沒能理解透算法實現原理的同學，也不用灰心，掌握算法不是一朝半夕的事，勤加練習才能突破。

另外，作者組建了氛圍特別好的前端交流羣 & 自由程序猿交流羣，歡迎同學們一起來交流吐槽。由於羣人數較多，需要添加作者才能邀請進羣。