完成 150 道经典算法题的过程中所收获的经验

注意！

有些题目没有给出相关经验，并不代表这道题目不重要，也不代表这道题目没有坑。因为我是连续顺序刷题，所以还记得一些坑，这能能够一次 AC！但这并不代表我以后就不会遇到这些坑，总的来说，还是要多刷，会的也刷，因为你既然会了，那么也不差那么一点时间！

经验

必背算法

KMP 算法 23-find-the-index-of-the-first-occurrence-in-a-string
DFS 算法，比如 70-invert-binary-tree
二叉树必背：DFS, BFS, 前序、中序、后序、层序、mirror、递归和非递归！

必看思路

投票算法 05-majority-element
买卖股票 07-best-time-to-buy-and-sell-stock
罗马转数字 17-roman-to-integer
二分边界痛点！
- 108-convert-sorted-array-to-binary-search-tree
- 114-search-insert-position

有关比较时的等号问题：

下标 (base-0) 和长度 (base-1) 比较时，不需要相等，因为相等时会越界

使用双指针时注意事项：

在 while 循环中，应该同时判断两个指针是否越界！以01-merge-sorted-array为例。
判断两个指针时，应该考虑两个指针相等的情况。当它俩相等时也应该能够进入 while 循环，
- 以 02-remove-element 为例
- 114-search-insert-position 也类似
while 循环中，有多次判断双指针的情况时，要考虑清楚。详见 25-valid-palindrome

链表

判断是否为空时，不仅要注意 .next，也要注意 head 本身！参见 57-linked-list-cycle
我不期待你马上就能写出精简的代码，所以请你先完成需求，然后再考虑简化代码量。比如 59-merge-two-sorted-lists

二叉树

递归时，注意好当前节点是空节点，还是非空节点。同时判断好是否应该减 1。参见 68-maximum-depth-of-binary-tree

递归

有时会，递归这东西，就是你熟悉后，凭着感觉敲着敲着就过了。参见 71-symmetric-tree

其他需要注意的杂碎，随是杂项，但也重要！：

看清楚题意！比如是让你求根节点到叶子节点的路径，而不是任意一条路径，参见 76-path-sum
注意好顺序问题，参见 03-remove-duplicates-from-sorted-array
如果指针下标始终会加一，用于指向边界外面的话，那么该下标的值其实就是长度。参见 03-remove-duplicates-from-sorted-array
有时候，下标是从 0 还是和从 1 开始，将会对于两种不一样的应对方式，一种简单，一种复杂！。参见 19-length-of-last-word
永远不要真正弄成死循环！即使你觉得始终会跳出循环！参见 20-longest-common-prefix
该用哈希表是用 Map，不要想着用对象方便！因为有时候一些特殊的字符会坑了你，比如 constructor，参见 41-word-pattern
不要省变量长度，不然你可能会分不清哪个是哪个，即使你能改正过来，那也需要花费很多时间！s参见 41-word-pattern
有些题，有假设的话，就照着这个假设先实现，这个时候重要的就是如何自己提供一个测试数据。比如 45-happy-number 中，感觉就是每个数值都能变成小于 10，这个思路是对的，但问题在于，并不知道 7 也是满足的。如果没有给出错误通过的案例，我能想到 7 这个情况吗？
代码长无所谓，重点是不要出错，而且易懂！不要还没做出来，就在想着如何优化了！参见 69-same-tree

速记

0-9 是 48-57 / 0x30-0x39
A-Z 是 65-90 / 0x41-0x5A
a-z 是 97-122 / 0x61-7A
向下取整：使用两次取反，比如 ~~(3/2)
除 2 向下取整：直接使用位运算，比如 3 >> 1

下标除以 2 index >> 1)。案例：

108-convert-sorted-array-to-binary-search-tree

txt

长度除以二 length >> 1

txt

双下标获取中点
- (leftIndex + rightIndex) >> 1
- 如果怕越界，则使用 leftIndex + ((rightIndex - leftIndex) >> 1)
  - 记得加括号，因为 js 中位运算优先级低于加减乘除
- 参见 108-convert-sorted-array-to-binary-search-tree
- 参见 114-search-insert-position

txt

        3  4  5  6
           ↑

        3  4  5  6  7
              ↑

150 题

简单001 merge-sorted-array

01.js

/*
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，
另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
*/
/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    let point1 = 0,
        point2 = 0,
        nums1Length = m,
        lastIndex = m+n-1
    while (point1 < m + n && point2 < n) {
        if (point1 < nums1Length && nums1[point1] < nums2[point2]) {
            point1 ++
        } else {
            nums1.splice(lastIndex, 1)
            nums1.splice(point1, 0, nums2[point2])
            nums1Length++
            point1 ++
            point2 ++
        }
    }
}

简单002 remove-element

02-1.js02-2.js

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    // 思路：双指针，把后面的元素移到前面。
    let left = 0,
        right = nums.length - 1,
        len = 0
    while (left <= right) {
        if (nums[left] !== val && nums[right] === val) {
            left++
            right--
            len++
        } else if (nums[left] === val && nums[right] === val) {
            right--
        } else if (nums[left] !== val && nums[right] !== val) {
            left++
            len++ // 注意这里是只加一个，因为 right 没有动
        } else { // nums[left] === val) && nums[right] !== val
            nums[left] = nums[right]
            left++
            right--
            len++
        }
    }
    return len
};


/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    // 思路：将匹配到的元素一个一个往后移到最后，然后返回下标
    let i = 0
    for(; i < nums.length;) {
        if (nums[i] === val) {
            nums.splice(i, 1)
        } else {
            i++
        }
    }
    return nums.length
};

简单003 remove-duplicates-from-sorted-array

03-1.js03-2.js

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    let set = new Set()
    let slow = 0,
        fast= 0
    while(fast < nums.length) {
        if (!set.has(nums[fast])) {
            nums[slow] = nums[fast]
            slow++
        }
        set.add(nums[fast])
        fast++ // 注意这个不要写在 add 前面
    }

    return slow // 注意这里不要加 1
};


/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    let set = new Set(nums)
    let notRepeat = Array.from(set)
    nums.forEach((_, i) => {
        nums[i] = notRepeat[i]
    })
    return notRepeat.length
};

简单005 majority-element

05-1.js05-2.js05-3.js

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    // Boyer-Moore 投票算法
    // 不会证明，所以只能理解，而我的理解就是：
    // 既然你出现的次数大于长度的一半，
    // 那么你 (count) 干掉（减去）其他所有人后，肯定还大于一！

    let candidate
    let count = 0
    for (let n of nums) {
        if (count === 0) {
            // 还没有候选人，那就随便选一个
            candidate = n

            // 这里其实可以简写到后面，但是这样写更加容易理解，
            count = 1
            continue
        }

        // 进入到这里，说明有候选人，那就开始投票
        // 投票时，肯定非减即增！
        count += n === candidate ?
            1 :
            -1
    }

    return candidate
};


/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    // Boyer-Moore 投票算法
    // 不会证明，所以只能理解，而我的理解就是：
    // 既然你出现的次数大于长度的一半，
    // 那么你 (count) 干掉（减去）其他所有人后，肯定还大于一！

    let candidate // 无所谓是谁
    let count = 0 // 刚开始的投票数是 0
    for (let n of nums) {

        // 投票数等于 0，意味着两种情况：
        //      - 还没人当选，原因是现在是第一个元素
        //      - 还没人当选，原因是前面的所有人都同归于尽了
        if (count === 0) {
            candidate = n // 这里是在选一个当候选人
        }

        // 这里只是算法层面上简写了
        count += n === candidate ?
            1 :
            -1
    }

    // nums.forEach(v => {
    //     // 每一轮投票后，投票数肯定 +1 / -1
    //     if (v === candidate) count++
    //     else count--

    //     // 注意等于 0 也是满足条件的！
    //     if (count <= 0) {
                // 问题出现在这这里！ v 让 candidate 变成了 0
                // 并不意味着 v 就有资格当选 candidate！
                // 因为他们同归于尽了，所以这里不能对 candidate 赋值为 v
    //         candidate = v
    //         count = 0 // 注意要重置为 0
    //     }
    // })
    return candidate
};


/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    nums.sort((a, b) => b-a)
    let len = nums.length
    return nums[~~(len/2)]
};

简单007 best-time-to-buy-and-sell-stock

07-1.js

/*
刚开始看到题解时，我困惑的点就在于为什么只需要考虑最低点，
按理来说，只在最低点时买入并不代表能得到最大利润。

其实，我困惑的点本身就有问题。因为题解得出的并不是指最低点买入时，所能得到的
最大利润。题解中的最低点，指的是在第 i 天时卖出，所能得到的最大利润，那肯定
是在前面天数中的最低点买入呀！

也就是说，在遍历过程中，最低点一直都有多个！

/**
 * @param {number[]} prices
 * @return {number}
 */
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
	let minPriceBeforeCurrent = Infinity
	let max_profit = 0
	prices.forEach(todayPrice => {
		max_profit = Math.max(max_profit, todayPrice - minPriceBeforeCurrent)
		minPriceBeforeCurrent = Math.min(minPriceBeforeCurrent, todayPrice)
	})
	return max_profit
}

简单017 roman-to-integer

17-1.js

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    let i = 0
    let sLen = s.length
    let ans = 0
    for (; i < sLen;) {
        const [offset, num] = roman_int(s.slice(i))
        i += offset
        ans += num
    }
    return ans
};

function roman_int (str) {
    if (str.startsWith('CM')) return [2, 900]
    if (str.startsWith('CD')) return [2, 400]
    if (str.startsWith('XC')) return [2, 90]
    if (str.startsWith('XL')) return [2, 40]
    if (str.startsWith('IX')) return [2, 9]
    if (str.startsWith('IV')) return [2, 4]
    if (str.startsWith('I'))  return [1, 1]
    if (str.startsWith('V'))  return [1, 5]
    if (str.startsWith('X'))  return [1, 10]
    if (str.startsWith('L'))  return [1, 50]
    if (str.startsWith('C'))  return [1, 100]
    if (str.startsWith('D'))  return [1, 500]
    if (str.startsWith('M'))  return [1, 1000]
}

简单019 length-of-last-word

19-1.js19-2.js

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLastWord = function (s) {
    s = s.trim()
    // 这里如果设置为 1 的话，情况会很麻烦。
    // 因为 'ab' 和 'x ab' 这两种情况需要你自己去区分
    let i = 0
    let len = s.length
    for (; i < len; i++) {
        if (s[len - i - 1] === ' ') { break }
    }
    return i
}

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLastWord = function(s) {
    return (
        s
        .split(' ')
        .filter(v => v.trim() !== '')
        .slice(-1)[0]
        .length)
};

简单020 longest-common-prefix

20-1.js

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function (strs) {
    let answer = ''
    let i = 0
    for (; i <= 200; i++) {
        let curChar
        for (const str of strs) {
            // 刚开始我写的是
            // curChar && (i >= str.length || str[i] != curChar)
            // 我本以为这样是正确的，但当输入的是 [''] 时候，这里就永远进不去了
            // 所以，永远不要真正写一个死循环的函数！
            if (i >= str.length || (
                curChar && str[i] != curChar
            )) {
                return answer
            }
            curChar = str[i]
        }
        answer += curChar
    }
    return answer
}

简单023 find-the-index-of-the-first-occurrence-in-a-string

23-1.js23-2.js

/**
 * 求解 KMP，重点是理解前后缀数组
 * 理解前后缀数组，首先要能够自己手动算出这个数组
 * 然后再去理解程序是怎么更快的算出这个数组中的
 *
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function (haystack, needle) {
    const haystackLen = haystack.length,
        needleLen = needle.length

    if (needleLen === 0) {
        return 0
    }


    // 这里是在求 needle 的真前后缀数组（needle 前有一个虚拟的 # 符号）
    const pi = new Array(needleLen).fill(0)
    for (let i = 1, j = 0; i < needleLen; i++) {
        while (j > 0 && needle[i] !== needle[j]) {
            j = pi[j - 1]
        }
        if (needle[i] === needle[j]) {
            j++
        }
        pi[i] = j
    }

    // 这里是在 haystack 中求取真后缀 needle 所对应的真前缀
    // 只不过我们不需要保存整个数组的值，只需要保存最新的那个 j 值就可以了
    for (let i = 0, j = 0; i < haystackLen; i++) {
        while (j > 0 && haystack[i] !== needle[j]) {
            j = pi[j - 1]
        }

        if (haystack[i] === needle[j]) {
            j++
        }
        if (j === needleLen) {
            return i - needleLen + 1
        }
    }
    return -1
}

/**
 * 暴力
 *
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function (haystack, needle) {
    let matchIndex = 0
    let len = haystack.length
    while (matchIndex < len) {
        if (haystack[matchIndex] === needle[0]) {
            if (Array.from(needle).every((char, index) => {
                return char === haystack[matchIndex + index]
            })) {
                return matchIndex
            }
        }
        matchIndex++
    }
    return -1
}

简单025 valid-palindrome

25-1.js25-2.js

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function (s) {
    s = s.toUpperCase()
    let left = 0,
        right = s.length - 1
    while (left <= right) {
        while (left <= right && !/[a-z0-9]/i.test(s[left])) {
            left++
        }
        while (left <= right && !/[a-z0-9]/i.test(s[right])) {
            right--
        }
        if (left > right) return true // 处理空字符串
        if (s[left] === s[right]) {
            left++
            right--
        } else {
            return false
        }
    }
    return true
}

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function (s) {
    // 或者
    // let filterStr =
    //      (s.match(/[a-z0-9]+/ig) || ['']).join('').toUpperCase()
    let filterStr = Array.from(s)
        .map(v => v.toUpperCase())
        .filter(v => {
            const code = v.charCodeAt()
            return (
                (0x41 <= code && code <= 0x5A)
                ||
                (0x30 <= code && code <= 0x39)
            )
        })
    let left = 0,
        right = filterStr.length - 1
    while (left <= right) {
        if (filterStr[left] === filterStr[right]) {
            left++
            right--
        } else {
            return false
        }
    }
    return true
}

简单026 is-subsequence

26-1.js26-2.js

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function (s, t) {
    let searchLen = s.length,
        targetLen = t.length

    // dp[i][char] 表示字符串 t 中
    // 从位置 i 开始往后字符 char 第一次出现的位置下标
    // 此处要注意 js 创建二维数组的方法！
    let dp = Array(targetLen).fill().map(() => Array(26).fill(0))
    // 很明显，在 targetLen 位置（越界）上所有字母都是越界的，所以将它们置为 targetLen
    dp.push(Array(26).fill(targetLen))

    for (let i = targetLen - 1; i > -1; i--) {
        for (let c = 0; c < 26; c++) {
            dp[i][c] =
                c === t[i].charCodeAt() - 0x61 ?
                    i :
                    dp[i + 1][c] // 注意这里有 [c]
        }
    }

    // 现在，我们就不需要一步一步地在 t 中搜索 s 中的下一个字符了
    // 可以直接通过 dp 获取下一个字符所在位置！
    let nextIndex = 0
    for (const sChar of s) {
        const code = sChar.charCodeAt() - 0x61
        if (targetLen === dp[nextIndex][code]) {
            return false
        }
        nextIndex = dp[nextIndex][code] +1 // 注意这里要 +1
    }
    return true
}

/**
 * 虽然该方法的时间复杂度是 m+n
 * 但如果有 10亿 个 s 需要判断，那么复杂度非常大！
 *
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function (s, t) {
    let i = 0
    for (const char of t) {
        if (char === s[i]) {
            i++
        }
    }
    return i === s.length
}

简单039 ransom-note

39-1.js39-2.js

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function (ransomNote, magazine) {
    if (ransomNote.length > magazine.length) {
        return false
    }

    const count = new Array(26).fill(0)
    for (const char of magazine) {
        const code = char.charCodeAt() - 0x61
        count[code]++
    }
    for (const char of ransomNote) {
        const code = char.charCodeAt() - 0x61
        count[code]--
        if (count[code] < 0) {
            return false
        }
    }
    return true
}

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function (ransomNote, magazine) {
    const ransomMap = {}
    for (const char of ransomNote) {
        if (char in ransomMap) {
            ransomMap[char]++
        } else {
            ransomMap[char] = 1
        }
    }

    const magazineMap = {}
    for (const char of magazine) {
        if (char in magazineMap) {
            magazineMap[char]++
        } else {
            magazineMap[char] = 1
        }
    }

    for (const [char, count] of Object.entries(ransomMap)) {
        if (!(char in magazineMap) || magazineMap[char] < count) {
            return false
        }
    }

    return true


}

简单040 isomorphic-strings

40-1.js40-2.js

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isIsomorphic = function (s, t) {
    if (s.length !== t.length) {
        return false
    }
    const len = s.length
    const s2t = {}
    const t2s = {}
    for (let i = 0; i < len; i++) {
        const sChar = s[i]
        const tChar = t[i]
        if ((s2t[sChar] && s2t[sChar] !== tChar)
            ||
            (t2s[tChar] && t2s[tChar] !== sChar)
        ) {
            return false
        }
        s2t[sChar] = tChar
        t2s[tChar] = sChar
    }
    return true
}

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isIsomorphic = function (s, t) {
    if (s.length !== t.length) {
        return false
    }
    let len = s.length
    let base1 = [],
        base2 = []
    let baseChar = 0
    let mapping = {}
    for (const char of s) {
        if (!(char in mapping)) {
            mapping[char] = baseChar
            baseChar++
        }
        base1.push(mapping[char])
    }
    mapping = {}
    baseChar = 0
    for (const char of t) {
        if (!(char in mapping)) {
            mapping[char] = baseChar
            baseChar++
        }
        base2.push(mapping[char])
    }
    for (let i = 0; i < len; i++) {
        if (base1[i] !== base2[i]) {
            return false
        }
    }
    return true

}

简单041 word-pattern

41-1.js41-2.js

/**
 * @param {string} pattern
 * @param {string} s
 * @return {boolean}
 */
var wordPattern = function (pattern, s) {
    const word2ch = new Map()
    const ch2word = new Map()
    const words = s.split(' ').filter(v => v.trim() !== '')
    if (words.length !== pattern.length)  {
        return false
    }

    for (const [i, word] of words.entries()) {
        const ch = pattern[i]
        if (
            (word2ch.has(word) && word2ch.get(word) !== ch)
            ||
            (ch2word.has(ch) && ch2word.get(ch) !== word)
        ) {
            return false
        }
        word2ch.set(word, ch)
        ch2word.set(ch, word)
    }

    return true

}

/**
 * @param {string} pattern
 * @param {string} s
 * @return {boolean}
 */
var wordPattern = function (pattern, s) {
    // 哈希表，该用 map 就用 map，
    // 不然会被特殊的字符串所迷惑，比如 constructor
    const p2s = new Map()
    const s2p = new Map()
    let sPoint = 0,
        pPoint = 0
    const sLen = s.length
    const pLen = pattern.length
    for (; pPoint < pLen; pPoint++) {
        const pChar = pattern[pPoint]
        let sStr = ''
        while (sPoint < sLen && s[sPoint] !== ' ') {
            sStr += s[sPoint]
            sPoint++
        }
        // 跳过空格
        while (sPoint < sLen && s[sPoint] === ' ') {
            sPoint++
        }
        if (sStr === '') {
            return false
        }
        // ~~此时 sStr 可能是空字符串，但 p 不可能是空字符串，所以比较时肯定为 false~~
        // 错啦，sStr 为空字符串时，根本不会进行判断！
        if (
            (s2p.has(sStr) && s2p.get(sStr) !== pChar)
            ||
            (p2s.has(pChar) && p2s.get(pChar) !== sStr)
        ) {
            return false
        }
        s2p.set(sStr, pChar)
        p2s.set(pChar, sStr)
    }
    // pattern 走完了，s 还有余
    if (sPoint < sLen) return false
    return true
}

简单042 valid-anagram

42-1.js42-2.js

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function (s, t) {
    if (s.length !== t.length) {
        return false
    }
    // 因为只有两个，可以直接只使用一个哈希表，两两相减即可

    const map = new Map()
    for (const ch of s) {
        map.set(ch, (map.get(ch) || 0) + 1)
    }
    for (const ch of t) {
        map.set(ch, (map.get(ch) || 0) - 1)
        if (map.get(ch) < 0) {
            return false
        }
    }
    return true
}

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function (s, t) {
    if (s.length !== t.length) {
        return false
    }
    // 因为只有两个，可以直接只使用一个哈希表，两两相减即可

    const map = new Map()
    for (let i = 0; i < 26; i++) {
        map.set(String.fromCharCode(i + 0x61), 0)
    }
    const len = s.length
    for (let i = 0; i < len; i++) {
        const sChar = s[i]
        const tChar = t[i]
        if (sChar === tChar) continue
        map.set(sChar, map.get(sChar) + 1)
        map.set(tChar, map.get(tChar) - 1)
    }
    for (let i = 0; i < 26; i++) {
        if (map.get(String.fromCharCode(i + 0x61)) !== 0) {
            return false
        }
    }
    return true
}

简单044 two-sum

44-1.js44-2.js

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
    const map = new Map()
    for (const [i, num] of nums.entries()) {
        if (map.has(num)) {
            return [map.get(num), i]
        } else {
            map.set(target - num, i)
        }
    }
    return []
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
    let i, j,
        len = nums.length
    for (i = 0; i < len - 1; i++) {
        for (j = 1; j < len; j++) {
            if (i !== j && nums[i] + nums[j] === target) {
                return [i, j]
            }
        }
    }
    return []
}

简单045 happy-number

45-1.js45-2.js45-3.js45-4.js

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function (n) {
    const str_square = {'0': 0}
    for (let i = 0; i < 10; i++) {
        str_square[i.toString()] = i**2
    }

    const getNext = (n) => {
        let ans = 0
        strArr = Array.from(n.toString())
        strArr.forEach(str => {
            ans += str_square[str]
        })
        return ans
    }

    let slow = n
    let fast = getNext(n)
    while (fast !== 1 && slow !== fast) {
        slow = getNext(slow)
        fast = getNext(getNext(fast))
    }
    return fast === 1
}

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function (n) {
    const str_square = { '0': 0 }
    for (let i = 0; i < 10; i++) {
        str_square[i.toString()] = i ** 2
    }

    const seen = new Set()
    while (n !== 1 && !seen.has(n)) {
        seen.add(n)
        n = getNext(n)
    }
    return n === 1

    function getNext(n) {
        let ans = 0
        strArr = Array.from(n.toString())
        strArr.forEach(str => {
            ans += str_square[str]
        })
        return ans
    }
}

/**
 * 这是根据数据证明得到的题解
 * 对于所有数字，如何会进入循环，则一定会进入这条路：
 *  4, 16, 37, 58, 89, 145, 42, 20
 *
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function (n) {
    const str_square = {'0': 0}
    for (let i = 0; i < 10; i++) {
        str_square[i.toString()] = i**2
    }

    const getNext = (n) => {
        let ans = 0
        strArr = Array.from(n.toString())
        strArr.forEach(str => {
            ans += str_square[str]
        })
        return ans
    }

    const cycle_members = new Set([
        4, 16, 37, 58, 89, 145, 42, 20
    ])
    while (n !== 1 && !cycle_members.has(n)) {
        n = getNext(n)
    }
    return n === 1
}

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function (n) {
    const nums_square = { '0': 0 }
    for (let i = 1; i < 10; i++) {
        nums_square[i.toString()] = i ** 2
    }
    let numberArr
    while (n > 9) {
        numberArr = Array.from(n.toString())
        n = 0
        numberArr.forEach(str => {
            n += nums_square[str]
        })
    }
    return n === 1 || n === 7
}

简单046 contains-duplicate-ii

46-1.js46-2.js

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var containsNearbyDuplicate = function (nums, k) {
    let had = new Set()
    const len = nums.length
    for (let i = 0; i < len; i++) {
        if (i > k) {
            // 删掉最左边，其下标是 i - k - 1
            had.delete(nums[i - k - 1])
        }
        if (had.has(nums[i])) {
            return true
        }
        had.add(nums[i])
    }
    return false
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var containsNearbyDuplicate = function(nums, k) {
    let repeat_map = new Map()
    for (const [i, num] of nums.entries())
    {
        if (repeat_map.has(num)) {
            if (i - repeat_map.get(num) <= k) {
                return true
            }
        }
        repeat_map.set(num, i)
    }
    return false
};

简单048 summary-ranges

48-1.js48-2.js

/**
 * @param {number[]} nums
 * @return {string[]}
 */
var summaryRanges = function (nums) {
    const ret = []
    let i = 0
    const len = nums.length
    while (i < len) {
        const low = i
        i++
        // 搜索连续
        while (i < len && nums[i] - 1 === nums[i - 1]) {
            i++
        }

        const high = i - 1
        if (low === high) {
            ret.push(nums[low].toString())
        } else {
            ret.push(nums[low] + '->' + nums[high])
        }
    }
    return ret
}

/**
 * @param {number[]} nums
 * @return {string[]}
 */
var summaryRanges = function (nums) {
    const ans = []

    for (const [i, num] of nums.entries()) {
        if (i === 0) {
            ans.push([num])
            continue
        }
        if (num - 1 === nums[i - 1]) {
            ans.push(
                [...ans.pop(), num]
            )
        } else {
            ans.push(
                [num]
            )
        }
    }
    return ans.map(arr => {
        if (arr.length === 1) {
            return arr[0].toString()
        } else {
            return arr[0] + '->' + arr.slice(-1)
        }
    })
}

简单052 valid-parentheses

52-1.js

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
    // 当我看到“左括号必须以正确的顺序闭合”这句话时，
    // 我就应该找出一个案例，应该指的是 [{(]}) 这种情况是错误的
    const leftStack = []
    const mapping = { '(': ')', '[': ']', '{': '}' }
    for (let ch of s) {
        if (['(', '[', '{'].includes(ch)) {
            leftStack.push(ch)
            continue
        }
        if (ch !== mapping[leftStack.pop()]) {
            return false
        }
    }
    return leftStack.length === 0
}

简单057 linked-list-cycle

57-1.js57-2.js

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
    if (!head || !head.next) {
        return false
    }
    let slow = head
    let fast = head.next
    while (fast && slow !== fast) {
        slow = slow.next
        fast = fast?.next?.next
    }
    return slow === fast
}

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
    const seen = new Set()
    while (head) {
        if (seen.has(head)) {
            return true
        }
        seen.add(head)
        head = head.next
    }
    return false
}

简单059 merge-two-sorted-lists

59-1.js59-2.js59-3.js59-4.js

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
    if (list1 === null) {
        return list2
    }
    if (list2 === null) {
        return list1
    }
    if (list1.val < list2.val) {
        list1.next = mergeTwoLists(list1.next, list2)
        return list1
    } else {
        list2.next = mergeTwoLists(list2.next, list1)
        return list2
    }
}

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
    const preHead = new ListNode()

    let prev = preHead
    while (list1 && list2) {
        if (list1.val <= list2.val) {
            prev.next = list1
            list1 = list1.next
        } else {
            prev.next = list2
            list2 = list2.next
        }
        prev = prev.next
    }

    prev.next = list1 ? list1 : list2

    return preHead.next
}

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
    if (!list1) return list2
    if (!list2) return list1

    let ans
    let head

    while (list1 && list2) {
        // 初始化头结点
        if (!ans) {
            if (list1.val < list2.val) {
                ans = list1
                head = list1
                list1 = list1.next
            } else {
                ans = list2
                head = list2
                list2 = list2.next
            }
            continue
        }

        if (list1.val < list2.val) {
            head.next = list1
            list1 = list1.next
            head = head.next
        } else {
            head.next = list2
            list2 = list2.next
            head = head.next
        }
    }
    if (list1) {
        head.next = list1
    } else if (list2) {
        head.next = list2
    }
    return ans
}

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
    let tmpArr = []
    while (list1) {
        tmpArr.push(list1.val)
        list1 = list1.next
    }
    while (list2) {
        tmpArr.push(list2.val)
        list2 = list2.next
    }
    if (tmpArr.length < 1) return null

    tmpArr.sort((a, b) => Number(a) - Number(b))
    console.log(tmpArr)
    let ans
    let head
    tmpArr.forEach(v => {
        if (!ans) {
            ans = new ListNode(v)
            head = ans
            return
        }
        head.next = new ListNode(v)
        head = head.next
    })
    return ans
}

简单068 maximum-depth-of-binary-tree

68-1.js68-2.js68-3.js

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * 非递归 BFS
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if (!root) {
        return 0
    }

    let queue = [root]
    let ans = 0
    while (queue.length !== 0) {
        let size = queue.length
        // 将当前层级的节点全部取出
        while (size > 0) {
            size -= 1
            let node = queue.shift()
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
        ans += 1
    }
    return ans
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * 递归 DFS
 *
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if (!root) {
        return 0
    }
    let leftMaxDepth = maxDepth(root.left)
    let rightMaxDepth = maxDepth(root.right)
    return 1 + Math.max(leftMaxDepth, rightMaxDepth)
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root, curDepth=1) {
    if (!root) {
        // 当前是空节点，不算入深度，所以 - 1
        return curDepth - 1
    }
    let leftMaxDepth = maxDepth(root.left, curDepth + 1)
    let rightMaxDepth = maxDepth(root.right, curDepth + 1)
    return Math.max(leftMaxDepth, rightMaxDepth)
}

简单069 same-tree

69-1.js69-2.js

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * 直接递归
 *
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    if (!p && !q) return true
    if (!p || !q) return false

    if (p.val !== q.val) {
        return false
    }
    if (!isSameTree(p.left, q.left)) {
        return false
    }
    if (!isSameTree(p.right, q.right)) {
        return false
    }
    return true
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * DFS 非递归。代码长无所谓，重点是不要出错，而且易懂！
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    if (!p && !q) return true
    if (!p || !q) return false

    let p_queue = [p],
        q_queue = [q]

    while (p_queue.length > 0 && q_queue.length > 0) {

        let p_size = p_queue.length
        let q_size = q_queue.length

        if (p_size !== q_size) return false

        while (p_size > 0) {
            p_size -= 1

            let p_node = p_queue.shift()
            let q_node = q_queue.shift()

            // 节点值要相同
            if (p_node.val !== q_node.val) return false

            // 都 有/没有 左节点
            if (p_node.left && q_node.left) {
                p_queue.push(p_node.left)
                q_queue.push(q_node.left)
            } else if (p_node.left || q_node.left) {
                return false
            }

            // 都 有/没有 右节点
            if (p_node.right && q_node.right) {
                p_queue.push(p_node.right)
                q_queue.push(q_node.right)
            } else if (p_node.right || q_node.right) {
                return false
            }
        }
    }
    return true
};

简单070 invert-binary-tree

70-1.js70-2.js

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function (root) {
    // 4. 不要忘了递归肯定要有终止条件
    if (!root) return null

    // 1. 先翻转当前子节点
    let tmp = root.left
    root.left = root.right
    root.right = tmp

    // 2. 孙子节点交给后面的去翻转
    invertTree(root.left)
    invertTree(root.right)

    // 3. 然后返回翻转后的节点
    return root
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function (root) {
    if (!root) return null

    let queue = [root]

    while (queue.length > 0) {
        let size = queue.length

        while (size > 0) {
            size -= 1

            let node = queue.shift()
            let tmp = node.left
            node.left = node.right
            node.right = tmp

            if (node.left) queue.push(node.left)
            if (node.right) queue.push(node.right)
        }
    }

    return root

}

简单071 symmetric-tree

71-1.js71-2.js71-3.js71-4.js

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    return check(root, root)

};

function check (root1, root2) {
    const queue = [root1, root2]

    while (queue.length > 0) {
        root1 = queue.shift()
        root2 = queue.shift()

        if (!root1 && !root2) continue
        if (!root1 || !root2) return false
        if (root1.val !== root2.val) return false

        queue.push(root1.left)
        queue.push(root2.right)


        queue.push(root1.right)
        queue.push(root2.left)
    }

    return true
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    return check(root, root)
};

function check(p, q) {
    if (!p && !q) return true
    if (!p || !q) return false

    return (
        p.val === q.val
        &&
        check(p.left, q.right)
        &&
        check(p.right, q.left)
    )
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    return isSymmetric2(root, root)
};

function isSymmetric2(root1, root2) {
    // 只有当传入是根节点时，root1 和 root2 才想通
    // 根节点之后，root1 和 root2 就是不同的子树了。
    if (!root1 && !root2) return true
    if (!root1 || !root2) return false
    // 现在，root1 和 root2 肯定都不为空

    // 错误优先
    if (root1.val !== root2.val) return false

    return (
        isSymmetric2(root1.left, root2.right)
        &&
        isSymmetric2(root1.right, root2.left)
    )

}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * 简单的想法，并不代表差，能一次 AC 就是好的！
 * 想要优化，那也得 AC 后再去优化！
 *
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    // 创建出一个翻转后的二叉树
    const newRoot = new TreeNode(root.val)
    invert(root, newRoot)

    // 然后判断两棵树是否相同
    if (isSame(root, newRoot)) {
        return true
    } else {
        return false
    }
};

function isSame(root1, root2) {
    if (!root1 && !root2) return true
    if (!root1 || !root2) return false

    if (root1.val !== root2.val) return false

    return (
        isSame(root1.left, root2.left)
        &&
        isSame(root1.right, root2.right)
    )
}

function invert(root, newRoot) {
    if (!root) return null

    if (root.right) {
        newRoot.left = new TreeNode(root.right.val)
    }
    if (root.left) {
        newRoot.right = new TreeNode(root.left.val)
    }

    invert(root.left, newRoot.right)
    invert(root.right, newRoot.left)
}

简单076 path-sum

76-1.js76-2.js76-3.js

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * BFS
 *
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function (root, targetSum) {
    if (!root) return false

    node_queue = [root]
    val_queue = [root.val]

    while (node_queue.length > 0) {
        let node = node_queue.shift()
        let curSumVal = val_queue.shift()

        if (!node.left && !node.right) {
            if (curSumVal === targetSum) return true
            continue
        }

        if (node.left) {
            node_queue.push(node.left)
            val_queue.push(curSumVal + node.left.val)
        }
        if (node.right) {
            node_queue.push(node.right)
            val_queue.push(curSumVal + node.right.val)
        }
    }
    return false
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * DFS
 *
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function (root, targetSum) {
    if (!root) return false
    if (!root.left && !root.right) {
        return targetSum === root.val
    }

    return (
        hasPathSum(root.left, targetSum - root.val)
        ||
        hasPathSum(root.right, targetSum - root.val)
    )
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function(root, targetSum) {
    if (!root) return false
    // 注意题目要求的是根节点到叶子节点，而不是存在这么一条路径
    if (!root.left && !root.right && root.val === targetSum) return true

    return (
        hasPathSum(root.left, targetSum - root.val)
        ||
        hasPathSum(root.right, targetSum - root.val)
    )
};

简单080 count-complete-tree-nodes

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * BFS 非递归
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes = function (root) {
    if (!root) return 0

    let queue = [root]
    let count = 0
    while (queue.length > 0) {
        let curLevelSize = queue.length

        while (curLevelSize > 0) {
            curLevelSize--

            const node = queue.shift()
            count++

            if (node.left) queue.push(node.left)
            if (node.right) queue.push(node.right)
        }
    }
    return count
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * 有点杀鸡焉用牛刀了，因为二叉树也最多就两个“出度”
 *
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes = function (root) {
    if (!root) return 0

    const stack = [root]
    const seen = new Set([root])
    let count = 1
    while (stack.length > 0) {
        const node = stack.pop()

        if (node.left && !seen.has(node.left)) {
            count++
            stack.push(node, node.left)
            seen.add(node.left)
            continue
        }
        if (node.right && !seen.has(node.right)) {
            count++
            stack.push(node, node.right)
            seen.add(node.right)
            continue
        }
    }
    return count
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * DFS 递归
 *
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes = function (root) {
    if (!root) return 0
    return (
        1 +
        countNodes(root.left) +
        countNodes(root.right)
    )
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * morris 中序遍历
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes = function (root) {
    if (!root) return false

    let cur = root
    let count = 0
    while (cur) {

        if (cur.left) {
            // 这里的 while 目的找到左←子树上的最右节点
            let mostRight = cur.left
            while (mostRight.right && mostRight.right !== cur) {
                mostRight = mostRight.right
            }

            if (!mostRight.right) {
                // 第一次到达尽头，于是搭建一条桥梁
                mostRight.right = cur
                // 然后直接跳到左子树上，等会我们可以通过刚刚搭建的桥梁
                // 重新回到头节点
                cur = cur.left
                continue
            }
            // 第二次到达尽头，我们需要把桥梁拆掉，不打扰到原结构。
            mostRight.right = null
        }
        count++
        cur = cur.right // 这里可能是是在走我们的刚刚搭建的桥梁
    }
    return count
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * 二分查找
 *
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes = function(root) {
    if (!root) return 0

    let depth = 0
    let node = root
    // 获取深度
    while (node.left) {
        depth++
        node = node.left
    }

    let low = 1 << depth, // 最底层的最左侧
        high = (1 << (depth + 1)) - 1 // 最底层的最右侧
    while (low < high) {
        // 二分查找，判断第 mid 个节点是否存在
        const mid = low + Math.floor((high - low + 1) / 2)
        if (exists(root, depth, mid)) {
            low = mid
        } else {
            high = mid - 1
        }
    }
    return low

};

/**
 * 判断第 k 个节点是否在 depth 层中
 * 注意：调用 exists 时已经确保了 k 的范围是在 depth 层的有效范围
 */
function exists (root, depth, k) {
    // 第 depth 层有效的范围，即节点数量
    let bits = 1 << (depth - 1)
    let node = root
    while (node && bits > 0) {
        if (!(bits & k)) {
            node = node.left
        } else {
            node = node.right
        }
        bits >>= 1
    }
    return node !== null
}

简单083 average-of-levels-in-binary-tree

83-1.js83-2.js

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * DFS
 * @param {TreeNode} root
 * @return {number[]}
 */
var averageOfLevels = function(root) {

    const dfs = (root, level) => {
        if (!root) return

        if (level < totals.length) {
            totals[level] += root.val
            counts[level] += 1
        } else {
            totals.push(root.val)
            counts.push(1)
        }
        dfs(root.left, level + 1)
        dfs(root.right, level + 1)
    }

    // 第 i 个元素，代表第 i 层的节点数量、第 i 层的数值总和
    const counts = []
    const totals = []
    dfs(root, 0)
    return counts.map((count, i) => (totals[i] / count).toFixed(5))
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * BFS
 * @param {TreeNode} root
 * @return {number[]}
 */
var averageOfLevels = function (root) {
    const queue = [root]
    const ans = []
    while (queue.length > 0) {
        let size = queue.length
        let average = 0
        let averageLen = size
        while (size > 0) {
            size--
            const node = queue.shift()
            average += node.val

            if (node.left) queue.push(node.left)
            if (node.right) queue.push(node.right)
        }
        ans.push((average / averageLen).toFixed(5))
    }
    return ans
}

简单086 minimum-absolute-difference-in-bst

86-1.js86-2.js

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * 非递归中序遍历
 *
 * @param {TreeNode} root
 * @return {number}
 */
var getMinimumDifference = function (root) {
    if (!root) return

    const stack = []
    let point = root
    let minDiff = Infinity
    let pre
    // 当 point 不为空时，也可以继续进入！
    while (stack.length > 0 || point) {
        if (point) {
            // 不断地将左边界入栈
            stack.push(point)
            point = point.left
        } else {
            // 一个节点即是左节点，同时也是头结点。
            // 由于最左节点是最后入栈的，头节点是晚入栈的，
            // 所以出栈时,先出的是左节点
            point = stack.pop()

            if (pre !== undefined) {
                minDiff = Math.min(minDiff, Math.abs(pre - point.val))
            }
            pre = point.val

            // 左节点和头结点都处理后,才可以处理右节点
            point = point.right
        }
    }
    return minDiff
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * 二叉搜索树，中序遍历！
 *
 * @param {TreeNode} root
 * @return {number}
 */
var getMinimumDifference = function(root) {

    const inOrder = (root) => {
        if (!root) return
        if (root.left) {
            inOrder(root.left)
        }
        if (pre !== undefined) {
            minDiff = Math.min(minDiff, Math.abs(root.val - pre))
        }
        pre = root.val
        inOrder(root.right)
    }
    let pre
    let minDiff = Infinity
    inOrder(root)
    return minDiff
};

简单108 convert-sorted-array-to-binary-search-tree

108-1.js108-2.js

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function (nums) {

    let rootIndex = ~~((nums.length - 1) / 2)
    let root = new TreeNode(nums[rootIndex])

    const stack = [[root, 0, nums.length - 1]]

    while (stack.length > 0) {

        // leftIndex 和 rightIndex 表示当前 node 所能处理的下标边界（包含）
        const [node, leftIndex, rightIndex] = stack.pop()

        // 当 node 发现自己能控制的只有一个节点时，说明它就是叶子节点
        // 这里的情况后面其实处理了。所以这里可以省略
        // if (leftIndex >= rightIndex) continue

        // node 本身的下标
        const headIndex = ~~((rightIndex + leftIndex) / 2)

        // 处理 node 的左子树
        if (leftIndex < headIndex) {
            // 左子树下标
            const leftHeadIndex = ~~((leftIndex + headIndex-1) / 2)
            node.left = new TreeNode(nums[leftHeadIndex])
            stack.push([node.left, leftIndex, headIndex - 1])
        }

        // 处理 node 的右子树
        if (headIndex < rightIndex) {
            // 右子树下标
            const rightHeadIndex = ~~((headIndex+1 + rightIndex) / 2)
            node.right = new TreeNode(nums[rightHeadIndex])
            stack.push([node.right, headIndex + 1, rightIndex])
        }
    }

    return root
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * 递归
 *
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function (nums) {
    if (nums.length < 1) return null

    let rootIndex = ~~((nums.length - 1) / 2)
    let root = new TreeNode(nums[rootIndex])

    root.left = sortedArrayToBST(nums.slice(0, rootIndex))
    root.right = sortedArrayToBST(nums.slice(rootIndex + 1))

    return root
}

简单114 search-insert-position

114-1.js114-2.js

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
    let leftIndex = 0,
        rightIndex = nums.length - 1
    let insertIndex = nums.length
    while (leftIndex <= rightIndex) {
        const mid = (rightIndex + leftIndex) >> 1
        if (target <= nums[mid]) {
            insertIndex = mid
            rightIndex = mid - 1
        } else {
            leftIndex = mid + 1
        }
    }
    return insertIndex
}

/**
 * 这里是根据自己思路写的，虽不如答案简洁，但重点在于理解！
 * 熟悉后自然可以合并成答案的那样子
 *
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
    let leftIndex = 0,
        rightIndex = nums.length - 1


    while (leftIndex < rightIndex) {
        // 还可以继续二分

        const mid = ~~((leftIndex + rightIndex) / 2)
        if (nums[mid] === target) {
            return mid
        }
        if (nums[mid] < target) {
            leftIndex = mid + 1
        } else {
            rightIndex = mid - 1
        }
    }

    // 找到尽头了，现在只剩下一个值还没匹配
    if (nums[leftIndex] === target) {
        return leftIndex
    }
    if (target < nums[leftIndex]) {
        return leftIndex
    }
    if (nums[leftIndex] < target) {
        return leftIndex + 1
    }
}

简单126 add-binary

126.js126.py

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function (a, b) {
    let len = Math.max(a.length, b.length)
    a = a.padStart(len, '0')
    b = b.padStart(len, '0')

    let ans = ''
    let carry = 0

    while (len > 0) {
        len--
        const tmp = add(a[len], b[len], carry)
        carry = tmp[0]
        ans = tmp[1] + ans
    }

    return (carry === 1 ? '1' : '') + ans

}

function add(bit1, bit2, carry) {
    let sum = Number(bit1) + Number(bit2) + Number(carry)

    switch (sum) {
        case 0: return [0, 0]
        case 1: return [0, 1]
        case 2: return [1, 0]
        case 3: return [1, 1]
    }
}

# 位运算的方式，只能用 py 实现
class Solution:
    def addBinary(self, a, b) -> str:
        x, y = int(a, 2), int(b, 2)
        while y:
            answer = x ^ y # 异或相加
            carry = (x & y) << 1
            x, y = answer, carry
        return bin(x)[2:]

简单127 reverse-bits

127.js

/**
 * @param {number} n - a positive integer
 * @return {number} - a positive integer
 */
var reverseBits = function (n) {
    return Number.parseInt(
        Array.from(
            n.toString(2).padStart(32, '0')
        ).reverse().join(''),
        2
    )
}

简单128 number-of-1-bits

128.js

/**
 * @param {number} n
 * @return {number}
 */
var hammingWeight = function(n) {
    const str = n.toString(2)
    let ans = 0
    for (const ch of str) {
        if (ch === '1') ans++
    }
    return ans
};

简单129 single-number

129.js

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
    let ans = 0
    for (let num of nums) {
        ans ^= num
    }
    return ans
}

简单131 palindrome-number

131-1.js

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function (x) {
    x = x.toString()
    let leftIndex = 0,
        rightIndex = x.length - 1
    while (leftIndex < rightIndex) {
        if (x[leftIndex] !== x[rightIndex]) {
            return false
        }
        leftIndex++
        rightIndex--
    }
    return true
}

简单132 plus-one

132-1.js

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function (digits) {
    let lastIndex = digits.length - 1
    // 初识时直接设置为 1，因为要加 1
    let carry = 1
    for (; lastIndex >= 0; lastIndex--) {
        if (digits[lastIndex] + carry <= 9) {
            digits[lastIndex]++
            return digits
        } else {
            digits[lastIndex] = 0
            carry = 1
        }
    }
    if (carry) {
        digits.unshift(1)
    }
    return digits
}

简单134 sqrtx

134.js

/**
 * 没事就看看
 *
 * @param {number} x
 * @return {number}
 */
var mySqrt = function (x) {
    if (x <= 1) return x

    let left = 0,
        right = (x >> 1) + 1
    res = 0

    while (left < right) {
        let middle = (left + right) >> 1
        if (middle ** 2 <= x) {
            res = middle
            left = middle + 1
        } else {
            right = middle
        }
    }
    return res
}

简单137 climbing-stairs

137.js

/**
 * 多看
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if (n < 2) return 1
    let dp = Array(n+1).fill(0)
    dp[1] = 1
    dp[2] = 2

    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

完成 150 道经典算法题的过程中所收获的经验 ​

经验 ​

动态规划…… ​

速记 ​

150 题 ​

简单001 merge-sorted-array ​

简单002 remove-element ​

简单003 remove-duplicates-from-sorted-array ​

简单005 majority-element ​

简单007 best-time-to-buy-and-sell-stock ​

简单017 roman-to-integer ​

简单019 length-of-last-word ​

简单020 longest-common-prefix ​

简单023 find-the-index-of-the-first-occurrence-in-a-string ​

简单025 valid-palindrome ​

简单026 is-subsequence ​

简单039 ransom-note ​

简单040 isomorphic-strings ​

简单041 word-pattern ​

简单042 valid-anagram ​

简单044 two-sum ​

简单045 happy-number ​

简单046 contains-duplicate-ii ​

简单048 summary-ranges ​

简单052 valid-parentheses ​

简单057 linked-list-cycle ​

简单059 merge-two-sorted-lists ​

简单068 maximum-depth-of-binary-tree ​

简单069 same-tree ​

简单070 invert-binary-tree ​

简单071 symmetric-tree ​

简单076 path-sum ​

简单080 count-complete-tree-nodes ​

简单083 average-of-levels-in-binary-tree ​

简单086 minimum-absolute-difference-in-bst ​

简单108 convert-sorted-array-to-binary-search-tree ​

简单114 search-insert-position ​

简单126 add-binary ​

简单127 reverse-bits ​

简单128 number-of-1-bits ​

简单129 single-number ​

简单131 palindrome-number ​

简单132 plus-one ​

简单134 sqrtx ​

简单137 climbing-stairs ​