花了十幾天，把《算法》看了一遍然后重新 AC 了一遍 LeetCode 的題，收獲頗豐。這次好好記錄下心得。
我把所有做題的代碼都放在 github 上以供參考。
項(xiàng)目地址：https://github.com/violetjack/LeetCodeACByJS
題目地址：https://leetcode.com/problemset/top-interview-questions/

說(shuō)來(lái)慚愧，之前寫(xiě)的《LeetCode 邏輯題分享》其實(shí)自己動(dòng)手做的比較少，都是看解決方案。更加關(guān)鍵的是我沒(méi)有系統(tǒng)地去學(xué)習(xí)過(guò)算法（自學(xué)的編程）。所以導(dǎo)致以下幾個(gè)問(wèn)題：

• 看題不懂方法論，理解他人方案困難。
• 解題方法通過(guò)看別人的方案去歸納，照著抄。（其實(shí)都是有系統(tǒng)的算法寫(xiě)法的）
• 很多題目看了答案只是知其然而不知其所以然。
• 很多答案（討論區(qū)的方案）是有錯(cuò)誤的，卻把它當(dāng)正確答案來(lái)發(fā)。

之后，我看了《算法（第4版）》一書(shū)，重新去做并且試著去 AC 題目，問(wèn)題又是一堆堆的。所以這次比第一次刷題時(shí)間要久不少。

各類題的解決方案

話不多說(shuō)，系統(tǒng)整理下解題的一些算法和解決方案

二叉樹(shù)

二叉樹(shù)大多使用遞歸的方式左右兩個(gè)元素向下遞歸。比如：

計(jì)算二叉樹(shù)最大深度

var maxDepth = function (root) {
    if (root == null) return 0
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right))
};

將二叉樹(shù)以二維數(shù)組形式表現(xiàn)

var levelOrder = function(root) {
    let ans = []
    helper(root, ans, 0)
    return ans
};

function helper(node, ans, i){
    if (node == null) return
    if (i == ans.length) ans.push([])
    ans[i].push(node.val)

    helper(node.left, ans, i + 1)
    helper(node.right, ans, i + 1)
}

都是通過(guò)遞歸方式逐層向下去查找二叉樹(shù)數(shù)據(jù)。

可能性問(wèn)題

這類題一般是告訴你一組數(shù)據(jù)，然后求出可能性、最小值或最大值。比如：

給定幾種面額的硬幣和一個(gè)總額，使用最少的硬幣湊成這個(gè)總額。

var coinChange = function (coins, amount) {
    let max = amount + 1
    let dp = new Array(amount + 1)
    dp.fill(max)
    dp[0] = 0

    for (let i = 1; i < max; i++) {
        for (let j = 0; j < coins.length; j++) {
            if (coins[j] <= i) {
                dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1)
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount]
};

使用了動(dòng)態(tài)規(guī)劃（DP），將從 0 到目標(biāo)額度所需的最小硬幣數(shù)都列出來(lái)。

求出從矩陣左上角走到右下角，且只能向右向下移動(dòng)，一共有多少種可能性。

var uniquePaths = function (m, n) {
    const pos = new Array(m)
    for (let i = 0; i < m; i++) {
        pos[i] = new Array(n)
    }
    for (let i = 0; i < n; i++) {
        pos[0][i] = 1
    }
    for (let i = 0; i < m; i++) {
        pos[i][0] = 1
    }
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            pos[i][j] = pos[i - 1][j] + pos[i][j - 1]
        }
    }
    return pos[m - 1][n - 1]
};

這題就是使用了動(dòng)態(tài)規(guī)劃逐步列出每一格的可能性，最后返回右下角的可能性。

獲取給定數(shù)組連續(xù)元素累加最大值

var maxSubArray = function (nums) {
    let count = nums[0], maxCount = nums[0]
    for (let i = 1; i < nums.length; i++) {
        count = Math.max(count + nums[i], nums[i])
        maxCount = Math.max(maxCount, count)    
    }
    return maxCount
};

上面這題通過(guò)不斷對(duì)比最大值來(lái)保留并返回最大值。

其實(shí)，可能性問(wèn)題使用動(dòng)態(tài)規(guī)劃要比使用 DFS、BFS 算法更加簡(jiǎn)單而容易理解。（我使用 DFS 經(jīng)常報(bào) TLE）

查找

一般遇到的查找問(wèn)題，如查找某個(gè)值一般會(huì)用到一下方法：

• 排序算法（排序便于查找）
• 二分查找
• 索引移動(dòng)查找（這個(gè)方法名自己想的，大概就這個(gè)意思~）

查找橫向和縱向都遞增的二維矩陣中的某個(gè)值

var searchMatrix = function (matrix, target) {
    if (matrix.length == 0) return false
    let row = 0, col = matrix[0].length - 1
    while (true) {
        if (matrix[row][col] > target && col > 0) {
            col--
        } else if (matrix[row][col] < target && row < matrix.length - 1) {
            row++
        } else if (matrix[row][col] == target) {
            return true
        } else {
            break
        }
    }
    return false
};

先將位置定位在右上角，通過(guò)改變位置坐標(biāo)來(lái)找到目標(biāo)值。使用了索引移動(dòng)查找法來(lái)找到結(jié)果。

找到數(shù)組中最左邊和最右邊的某個(gè)數(shù)字所在位置

var searchRange = function (nums, target) {
    let targetIndex = binarySearch(nums, target, 0, nums.length - 1)
    if (targetIndex == -1) return [-1, -1]
    let l = targetIndex, r = targetIndex
    while(l > 0 && nums[l - 1] == target){
        l--
    }
    while(r < nums.length - 1 && nums[r + 1] == target){
        r++
    }
    return [l, r]
};

function binarySearch(arr, val, lo, hi) {
    if (hi < lo) return -1
    let mid = lo + parseInt((hi - lo) / 2)

    if (val < arr[mid]) {
        return binarySearch(arr, val, lo, mid - 1)
    } else if (val > arr[mid]) {
        return binarySearch(arr, val, mid + 1, hi)
    } else {
        return mid
    }
}

這題使用二分法來(lái)查找到某個(gè)目標(biāo)數(shù)字的索引值，然后索引移動(dòng)法分別向左和向右查找字符。獲取左右兩側(cè)的索引值返回。

回文

所謂回文，就是正著讀反著讀是一樣的。使用索引兩邊向中間移動(dòng)的方式來(lái)判斷是否為回文。

找到給定字符串中某段最長(zhǎng)的回文

var longestPalindrome = function (s) {
    let maxLength = 0, left = 0, right = 0
    for (let i = 0; i < s.length; i++) {
        let singleCharLength = getPalLenByCenterChar(s, i, i)
        let doubleCharLength = getPalLenByCenterChar(s, i, i + 1)
        let max = Math.max(singleCharLength, doubleCharLength)
        if (max > maxLength) {
            maxLength = max
            left = i - parseInt((max - 1) / 2)
            right = i + parseInt(max / 2)
        }
    }
    return s.slice(left, right + 1)
};

function getPalLenByCenterChar(s, left, right) {
    // 中間值為兩個(gè)字符，確保兩個(gè)字符相等
    if (s[left] != s[right]){
        return right - left
    }
    while (left > 0 && right < s.length - 1) {
        left--
        right++
        if (s[left] != s[right]){
            return right - left - 1
        }
    }
    return right - left + 1
}

路徑題

路徑題可以使用深度優(yōu)先（DFS）和廣度優(yōu)先（BFS）算法來(lái)做。我比較常用的是使用 DFS 來(lái)做。通過(guò)遞歸將走過(guò)的路徑進(jìn)行標(biāo)記來(lái)不斷往前找到目標(biāo)路徑。如：

通過(guò)給定單詞在二維字母數(shù)組中查找是否能使用鄰近字母組成這個(gè)單詞(212題)

let hasWord = false

var findWords = function (board, words) {
    var ans = []
    for (let word of words) {
        for (let j = 0; j < board.length; j++) {
            for (let i = 0; i < board[0].length; i++) {
                if (board[j][i] == word[0]) {
                    hasWord = false
                    DFS(word, board, 0, j, i, "")
                    if (hasWord) {
                        if (!ans.includes(word))
                            ans.push(word)
                    }
                }
            }
        }
    }
    return ans
};

function DFS(word, board, index, j, i, subStr) {
    if (word[index] == board[j][i]) {
        subStr += board[j][i]
        board[j][i] = "*"
        if (j < board.length - 1)
            DFS(word, board, index + 1, j + 1, i, subStr)
        if (j > 0)
            DFS(word, board, index + 1, j - 1, i, subStr)
        if (i < board[0].length - 1)
            DFS(word, board, index + 1, j, i + 1, subStr)
        if (i > 0)
            DFS(word, board, index + 1, j, i - 1, subStr)
        board[j][i] = word[index]
    }
    if (index >= word.length || subStr == word) {
        hasWord = true
    }
}

由于 DFS 是一條路走到黑，如果每個(gè)元素都去使用 DFS 來(lái)找會(huì)出現(xiàn)超時(shí)的情況。如果條件允許（如查找遞增數(shù)組）可以通過(guò)設(shè)置緩存來(lái)優(yōu)化 DFS 查找超時(shí)問(wèn)題。

獲取二維矩陣中最大相鄰遞增數(shù)組長(zhǎng)度。

const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]

var longestIncreasingPath = function (matrix) {
    if (matrix.length == 0) return 0
    const m = matrix.length, n = matrix[0].length
    let max = 1

    let cache = new Array(m)
    for (let i = 0; i < m; i++){
        let child = new Array(n)
        child.fill(0)
        cache[i] = child
    }

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            let len = dfs(matrix, i, j, m, n, cache)
            max = Math.max(max, len)
        }
    }
    return max
}

function dfs(matrix, i, j, m, n, cache){
    if (cache[i][j] != 0) return cache[i][j]
    let max = 1
    for (let dir of dirs){
        let x = i + dir[0], y = j + dir[1]
        if(x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= matrix[i][j]) continue;
        let len = 1 + dfs(matrix, x, y, m, n, cache)
        max = Math.max(max, len)
    }
    cache[i][j] = max
    return max
}

將已使用 DFS 查找過(guò)的長(zhǎng)度放入緩存，如果有其他元素走 DFS 走到當(dāng)前值，直接返回緩存最大值即可。

鏈表

鏈表從 JS 的角度來(lái)說(shuō)就是一串對(duì)象使用指針連接的數(shù)據(jù)結(jié)構(gòu)。合理使用 next 指針改變指向來(lái)完成對(duì)鏈表的一系列操作。如：

鏈表的排序：

var sortList = function (head) {
    if (head == null || head.next == null) return head

    let prev = null, slow = head, fast = head
    while (fast != null && fast.next != null) {
        prev = slow
        slow = slow.next
        fast = fast.next.next
    }

    prev.next = null;

    let l1 = sortList(head)
    let l2 = sortList(slow)

    return merge(l1, l2)
};

function merge(l1, l2) {
    let l = new ListNode(0), p = l;

    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            p.next = l1;
            l1 = l1.next;
        } else {
            p.next = l2;
            l2 = l2.next;
        }
        p = p.next;
    }

    if (l1 != null)
        p.next = l1;

    if (l2 != null)
        p.next = l2;

    return l.next;
}

使用了自上而下的歸并排序方法對(duì)鏈表進(jìn)行了排序。使用 slow.next 和 fast.next.next 兩種速度獲取鏈表節(jié)點(diǎn)，從而獲取中間值。

鏈表的倒序

var reverseList = function(head) {
    let ans = null,cur = head
    while (cur != null) {
        let nextTmp = cur.next
        cur.next = ans
        ans = cur
        cur = nextTmp
    }
    return ans
};

排序

排序和查找算是算法中最重要的問(wèn)題了。常用的排序算法有：

• 插入排序
• 選擇排序
• 快速排序
• 歸并排序
• 計(jì)數(shù)排序

更多排序算法的知識(shí)點(diǎn)可參考《JS家的排序算法》，文章作者圖文并茂的講解了各種排序算法，很容易理解。
舉幾個(gè)排序算法的栗子：

求數(shù)組中第K大的值

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
    for (let i = 0; i <= k; i++) {
        let max = i
        for (let j = i; j < nums.length; j++) {
            if (nums[j] > nums[max]) max = j
        }
        swap(nums, i, max)
    }
    return nums[k - 1]
};

function swap(arr, a, b) {
    let tmp = arr[a]
    arr[a] = arr[b]
    arr[b] = tmp
}

使用了選擇排序排列了前 K 個(gè)值得到結(jié)果。

對(duì)有重復(fù)值的數(shù)組 [2,0,2,1,1,0] 排序

var sortColors = function (nums) {
    sort(nums, 0, nums.length - 1)
};

function sort(arr, lo, hi) {
    if (hi <= lo) return
    let lt = lo, i = lo + 1, gt = hi;
    let v = arr[lo]
    while (i <= gt) {
        if (arr[i] < v) swap(arr, lt++, i++)
        else if (arr[i] > v) swap(arr, i, gt--)
        else i++
    }
    sort(arr, lo, lt - 1)
    sort(arr, gt + 1, hi)
}

function swap(arr, a, b) {
    let x = arr[a]
    arr[a] = arr[b]
    arr[b] = x
}

這種有重復(fù)值的使用三向切分的快速排序是非常好的解決方案。當(dāng)然，計(jì)數(shù)排序法可是不錯(cuò)的選擇。
還有之前提到的鏈表的排序使用的是歸并排序。

算術(shù)題

算術(shù)題看似簡(jiǎn)單，但是遇到最大的問(wèn)題就是：如果使用累加、累成這種常熟級(jí)別的增長(zhǎng)，遇到很大的數(shù)字會(huì)出現(xiàn) TLE （超出時(shí)間限制）。所以，我們要用指數(shù)級(jí)別的增長(zhǎng)來(lái)找到結(jié)果。如：

計(jì)算 x 的 n 次方

var myPow = function (x, n) {
    if (n == 0) return 1
    if (n < 0) {
        n = -n
        x = 1 / x
    }
    return (n % 2 == 0) ? myPow(x * x, parseInt(n / 2)) : x * myPow(x * x, parseInt(n / 2));
};

一開(kāi)始我使用了 x*x 這么乘上 n 次，但是遇到 n 太大就直接超時(shí)了。使用以上方案：2⁹ = 2 * 4⁴ = 2 * 8² = 2 * 64 = 128
直接從常熟級(jí)變化變?yōu)橹笖?shù)級(jí)變化，這一點(diǎn)在數(shù)學(xué)運(yùn)算中是需要注意的。

求 x 的平方根

var mySqrt = function (x) {
    let l = 0, r = x
    while (true) {
        let mid = parseInt(l + (r - l) / 2)
        if (mid * mid > x) {
            r = mid - 1
        } else if (mid * mid < x) {
            if ((mid + 1) * (mid + 1) > x) {
                return mid
            }
            l = mid + 1
        } else {
            return mid
        }
    }
};

這題使用二分法來(lái)找到結(jié)果。

二進(jìn)制問(wèn)題

二進(jìn)制問(wèn)題，一般使用按位運(yùn)算符和二進(jìn)制轉(zhuǎn)換 Number.parseInt() 和 Number.prototype.toString()來(lái)解決。

將一個(gè)32位數(shù)字的二進(jìn)制進(jìn)行倒序

var reverseBits = function(n) {
    var t = n.toString(2).split("");
    while(t.length < 32) t.unshift("0"); // 插入足夠的 0
    return parseInt(t.reverse().join(""), 2);
};

常用算法

講了這么多，其實(shí)除了常用的排序、搜索，其他最常用的就是 DP、DFS、BFS 這三個(gè)算法了?？梢赃@么說(shuō)：掌握了排序和這三個(gè)算法，可以 AC 大多數(shù)的算法問(wèn)題。這么牛逼的算法了解一下？

簡(jiǎn)單說(shuō)說(shuō)幾種排序和查找

• 冒泡排序：遍歷數(shù)組，對(duì)比元素和后面相鄰元素，如果當(dāng)前元素大于后面元素，調(diào)換位置。這樣從頭遍歷到尾，獲取最后一位排序玩的元素。然后在 1 到 n - 1 中再次重復(fù)以上步驟。直到最后第一和第二個(gè)元素對(duì)比大小。是一種從后往前的排序。
• 選擇排序：遍歷數(shù)組，找到最小的元素位置，與第一個(gè)元素調(diào)換位置，然后縮小范圍從第二個(gè)元素開(kāi)始遍歷，如此重復(fù)到最后一個(gè)元素?？梢詮暮笸耙部梢詮那巴笈判?。

function sort(arr) {
    const len = arr.length
    for (let i = 0; i < len; i++) {
        let min = i
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[min]) min = j
        }
        swap(arr, i, min)
        console.log(arr)
    }
    return arr
}

• 插入排序：遍歷數(shù)組，選中某一個(gè)元素，與前面相鄰元素對(duì)比，如果當(dāng)前元素小于之前元素，調(diào)換位置，繼續(xù)對(duì)比直到當(dāng)前元素前的元素小于當(dāng)前元素（或者到最前面），如此對(duì)所有元素排序一遍。是一種從前往后的排序。

function sort(arr) {
    const len = arr.length
    for (let i = 1; i < len; i++) {
        for (let j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
            swap(arr, j, j - 1)
            console.log(arr)
        }
    }
    return arr
}

• 希爾排序：類似于插入排序，選中一個(gè)元素與元素前 n 個(gè)元素進(jìn)行比大小和調(diào)換位置。之后再縮小 n 的值。這種方法可以減少插入排序中最小值在最后面，然后需要一個(gè)一個(gè)調(diào)換位置知道最前面這類問(wèn)題。減少調(diào)換次數(shù)。是一種從前往后的排序。
• 歸并排序：在《算法》中提到了兩種歸并排序：一種是自上而下的歸并排序。將數(shù)組不斷二分到最小單位（1到2個(gè)元素）將他們進(jìn)行排序，之后將前兩個(gè)和后兩個(gè)元素對(duì)比，如此往上最后完成整個(gè)數(shù)組的排序。還有一種自下而上的歸并排序是直接將數(shù)組分割為若干個(gè)子數(shù)組進(jìn)行排序然后合并。

let aux = new Array(arr.length)
function sort(arr, lo, hi) {
    if (hi <= lo) return
    let mid = lo + (parseInt((hi - lo) / 2))

    sort(arr, lo, mid)
    sort(arr, mid + 1, hi)
    merge(arr, lo, mid, hi)
}

function merge(arr, lo, mid, hi) {
    let i = lo, j = mid + 1
    for (let k = lo; k <= hi; k++) {
        aux[k] = arr[k]
    }
    for (let k = lo; k <= hi; k++) {
        if (i > mid) arr[k] = aux[j++]
        else if (j > hi) arr[k] = aux[i++]
        else if (aux[j] < aux[i]) arr[k] = aux[j++]
        else arr[k] = aux[i++]
    }
    console.log(arr)
}

• 快速排序：選定第一個(gè)值為中間值，然后將小于中間值的元素放在中間值的左側(cè)而大于中間值的元素放在中間值右側(cè)，然后對(duì)兩側(cè)的元素分別再次切割，直到最小單位。

function sort(arr, lo, hi) {
    if (hi <= lo + 1) return
    let mid = partition(arr, lo, hi) // 切分方法
    sort(arr, lo, mid)
    sort(arr, mid + 1, hi)
}

function partition(arr, lo, hi) {
    let i = lo, j = hi + 1
    let v = arr[lo]
    while(true) {
        while(arr[++i] < v) if (i == hi) break
        while(v < arr[--j]) if (j == lo) break
        if ((i >= j)) break
        swap(arr, i, j)
        console.log(arr)
    }
    swap(arr, lo, j)
    console.log(arr)
    return j
}

• 三向切分的快速排序：類似于快速排序，優(yōu)化點(diǎn)在于如果某個(gè)元素等于切分元素，元素位置不變。最后小于切分元素的到左邊，等于切分元素的根據(jù)數(shù)量放在中間，大于切分元素的放在右邊。適用于有大量相同大小元素的數(shù)組。

function sort(arr, lo, hi) {
    if (hi <= lo) return
    let lt = lo, i = lo + 1, gt = hi;
    let v = arr[lo]
    while (i <= gt) {
        if (arr[i] < v) swap(arr, lt++, i++)
        else if (arr[i] > v) swap(arr, i, gt--)
        else i++
        console.log(arr)
    }
    sort(arr, lo, lt - 1)
    sort(arr, gt + 1, hi)
}

• 堆排序：堆排序可以說(shuō)是一種利用堆的概念來(lái)排序的選擇排序。使用優(yōu)先隊(duì)列返回最大值的特性逐個(gè)返回當(dāng)前堆的最大值。
• 計(jì)數(shù)排序：就是將數(shù)組中所有元素的出現(xiàn)次數(shù)保存在一個(gè)數(shù)組中，然后按照從小到大返回排序后的數(shù)組。
• 桶排序：其實(shí)就是字符串排序的 LSD 和 MSD 排序。LSD 使用索引計(jì)數(shù)法從字符串右邊向左邊移動(dòng)，根據(jù)當(dāng)前值進(jìn)行排序。而 MSD 是從左到右使用索引計(jì)數(shù)法來(lái)排序，在字符串第一個(gè)字符后，將字符串?dāng)?shù)組分為若干個(gè)相同首字符串的數(shù)組各自進(jìn)行第二、第三次的 MSD 排序。
• 二分查找： 對(duì)有序數(shù)組去中間值與目標(biāo)值相比對(duì)。如果目標(biāo)值小于中間值，取前一半數(shù)組繼續(xù)二分。如果目標(biāo)值大于中間值，取后一半數(shù)組繼續(xù)二分。如果目標(biāo)值等于中間值，命中！

DP

關(guān)于動(dòng)態(tài)規(guī)劃，可以看下詳解動(dòng)態(tài)規(guī)劃——鄒博講動(dòng)態(tài)規(guī)劃一文，其中講了路徑、硬幣、最長(zhǎng)子序列。都是 LeetCode 中有的題目。
我的理解：動(dòng)態(tài)規(guī)劃就是下一狀態(tài)可以根據(jù)上一狀態(tài)，或之前幾個(gè)狀態(tài)獲取到的一種推理過(guò)程。

DFS

深度優(yōu)先搜索（DFS）就是選中某條從條件1到條件2的某條可能性進(jìn)行搜索，之后返回搜索其他一條可能性，如此一條條升入。舉個(gè)栗子，如果有5條路，那么 DFS 算法就是只排出一個(gè)斥候先走一條路走到底去偵察，如果走不通那么返回走下一條路徑。

DFS（頂點(diǎn)v）
{
  標(biāo)記v為已遍歷；
  for（對(duì)于每一個(gè)鄰接v且未標(biāo)記遍歷的點(diǎn)u）
      DFS（u）;
}

DFS 使用的是遞歸的方式進(jìn)行搜索的。

示例：在二維字母矩陣中查找是否能夠使用相鄰字母組成目標(biāo)單詞。

var exist = function (board, word) {
    for (let y = 0; y < board.length; y++) {
        for (let x = 0; x < board[0].length; x++) {
            if (find(board, word, y, x, 0)) return true
        }
    }
    return false
};

function find(board, word, y, x, d) {
    if (d == word.length) return true
    if (y < 0 || x < 0 || y == board.length || x == board[y].length) return false;
    if (board[y][x] != word[d]) return false
    let tmp = board[y][x]
    board[y][x] = "*"
    let exist = find(board, word, y, x + 1, d + 1)
        || find(board, word, y, x - 1, d + 1)
        || find(board, word, y + 1, x, d + 1)
        || find(board, word, y - 1, x, d + 1)
    board[y][x] = tmp
    return exist
}

BFS

廣度優(yōu)先搜索（BFS）就是將從條件1到條件2的所有可能性都列出來(lái)同步搜索的過(guò)程。適用于查找最短路徑。舉個(gè)栗子，如果有5條路，那么 BFS 算法就是分別向5條路排出斥候去偵察。

BFS()
{
  輸入起始點(diǎn)；
  初始化所有頂點(diǎn)標(biāo)記為未遍歷；
  初始化一個(gè)隊(duì)列queue并將起始點(diǎn)放入隊(duì)列；

  while（queue不為空）
  {

    從隊(duì)列中刪除一個(gè)頂點(diǎn)s并標(biāo)記為已遍歷； 
    將s鄰接的所有還沒(méi)遍歷的點(diǎn)加入隊(duì)列；
  }
}

BFS是使用數(shù)組存儲(chǔ)下一頂點(diǎn)的方式。

示例：每次改變一次字母，通過(guò)給定數(shù)組中的單詞，從單詞 A 變?yōu)閱卧~ B。（127題）

/**
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {number}
 */
var ladderLength = function (beginWord, endWord, wordList) {
    if (!wordList.includes(endWord)) return 0
    let set = new Set(),
        visited = new Set(),
        len = 1

    set.add(beginWord)
    visited.add(beginWord)
    while (set.size != 0) {
        let tmp = new Set([...set])

        for (let w of tmp) {
            visited.add(w)
            set.delete(w)

            if (changeOneChar(w, endWord))
                return len + 1
            
            for (let word of wordList){
                if (changeOneChar(w, word) && !visited.has(word)){
                    set.add(word)
                }
            }
        }
        len++
    }
    return 0
};

function changeOneChar(a, b) {
    let count = 0
    for (let i = 0; i < a.length; i++)
        if (a[i] != b[i])
            count++
    return count == 1
}

最后

寫(xiě)下 AC 一遍題目之后的收獲。

• 知道了方法論，做起題來(lái)輕松了不少。
• 遇到問(wèn)題多找輪子，一定有某種方法論可以用。
• 不要耍小聰明用一些奇巧淫技，思路不對(duì)再怎么繞都是浪費(fèi)時(shí)間。
• 不要想著自己造輪子（特別是算法方面），絕大多數(shù)問(wèn)題前輩一定有更好更完善的方案在。自己造輪子費(fèi)時(shí)費(fèi)事又沒(méi)太大意義。
• 看答案和自己做是兩回事，自己動(dòng)手實(shí)現(xiàn)了才能算是會(huì)了。
• 算法之所以存在，就是用來(lái)適應(yīng)某些場(chǎng)景、解決某類問(wèn)題的。在對(duì)的場(chǎng)景選擇對(duì)的算法才能體現(xiàn)算法的價(jià)值，不要濫用算法。
• 沒(méi)必要把所有算法都精通，但起碼在遇到問(wèn)題時(shí)可以找到最優(yōu)算法解決問(wèn)題。即知道算法的存在及其用途，按需深入學(xué)習(xí)。

其實(shí)刷算法題還是很有趣的事情，之后計(jì)劃把 LeetCode 題庫(kù)中的所有問(wèn)題都刷一遍~

PS：本文以及相關(guān)項(xiàng)目中有任何錯(cuò)誤或者可以改進(jìn)的地方，還請(qǐng)?zhí)岢觥９餐M(jìn)步~