Leetcode 热题 HOT 100 百日刷题打卡

刷题计划

一天坚持刷一道，三个月刷完简单和中等
刚开始的一个月先把简单刷完，再刷中等难度的
每天刷一道新题 + 重刷昨天的题

刷题方法

极客时间覃超老师的“五毒神掌”刷题法

第一遍

5~10分钟：读题 + 思考，一定要先自己思考！

若有思路，则写代码实现自己的思路

若无思路，则直接看前三名高赞解法。注意！多解法，比较各种解法优劣

看完解法后先理解，写下大致的解题思路或者伪代码，方便后面复现

背诵默写比较好的解法，以后碰到类似的题就有思路了

第二遍

马上关掉答案，看看自己能不能再写出来。遇到 bug 也不用怕，一步一步 debug 提交通过

可以切到国际站看看国外大佬的高票题解，多种解法比较，体会 → 优化自己写的代码

及时总结，记录笔记

第三遍

过一天后，重刷前一天的题目

如果掌握程度不够，去做专项练习，补薄弱部分

专项练习就是去刻意练习自己不熟悉的这类题

整理这类题的算法模板

第四遍

过了一周之后，回来反复练习相同题目

第五遍

面试前的恢复训练：提前两三周重刷之前做过的题目

总结：

刷题只刷一遍是不够的！要反复刷！
要能有理解性的（默）写出来
坚持下去

打卡记录

题目	一刷时间	二刷时间	三刷时间	掌握程度	题目难度	标签
1. 两数之和	2022.11.23	2022.11.29	…	⭐⭐⭐	简单	哈希表；数组
2. 两数相加	2022.11.26	2022.11.30	…	⭐⭐	中等	链表；数学
3. 无重复字符的最长子串	2022.11.26	2022.12.02	…	⭐⭐	中等	哈希表；字符串；滑动窗口
70. 爬楼梯	2022.11.27	2022.12.03	…	⭐⭐⭐	简单	动态规划
338. 比特位计数	2022.11.27	2022.12.04	…	⭐⭐⭐	简单	动态规划
104. 二叉树的最大深度	2022.11.28	2022.12.05	…	⭐⭐⭐	简单	二叉树；DFS
543. 二叉树的直径	2022.11.28	2022.12.10	…	⭐⭐⭐	简单	二叉树；DFS
226. 翻转二叉树	2022.11.29	2022.12.06	…	⭐⭐⭐	简单	二叉树；DFS
461. 汉明距离	2022.12.01	2022.12.09	…	⭐⭐⭐	简单	位运算
136. 只出现一次的数字	2022.12.02	2022.12.07	…	⭐⭐⭐	简单	位运算；数组
94. 二叉树的中序遍历	2022.12.03	2022.12.08	…	⭐⭐⭐	简单	二叉树；DFS；栈
617. 合并二叉树	2022.12.04	…	…	⭐⭐⭐	简单	二叉树；DFS；BFS
101. 对称二叉树	2022.12.05	2022.12.11	…	⭐⭐⭐	简单	二叉树；DFS；BFS
20. 有效的括号	2022.12.06	…	…	⭐⭐⭐	简单	栈；字符串
102. 二叉树的层序遍历	2022.12.07	…	…	⭐⭐⭐	中等	二叉树；BFS
169. 多数元素	2022.12.08	…	…	⭐⭐⭐	简单	数组；哈希表；计数
141. 环形链表	2022.12.09	…	…	⭐⭐⭐	简单	哈希表；链表；双指针
19. 删除链表的倒数第 N 个结点	2022.12.10	…	…	⭐⭐	中等	链表；双指针
206. 反转链表	2022.12.11	…	…	⭐⭐	简单	链表；递归
160. 相交链表	2022.12.12	…	…	⭐⭐	简单	链表；双指针；哈希表

刷题笔记

1.两数之和

暴力解法，O(N^2) 时间复杂度

var twoSum = function(nums, target) {
     let res = [];
        for(let i = 0; i < nums.length; i++){
            for(let j = i + 1;j < nums.length; j++){
                if(nums[i] + nums[j] == target){
                    res.push(i)
                    res.push(j)
                }
            }
        }
    return res;
};

更好的解法：用哈希表空间换时间
- 使用一个哈希表存储 nums 数组每个数的下标，如果 target - nums[i] 存在则返回结果，否则保存这个数的下标到哈希表中

var twoSum = function(nums, target) {
    let hash = {}
    for(let i = 0; i < nums.length; i++){
        if(hash[target - nums[i]] !== undefined){
            return [i,hash[target - nums[i]]]
        }
        hash[nums[i]] = i
    }
};

2.两数相加

将两个链表看成是相同长度的进行遍历，如果一个链表较短则在前面补 0
同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加
- 而当前位计算结束后同样需要更新进位值
此外，如果链表遍历结束后，有 carry > 0，还需要在答案链表的后面附加一个节点，节点的值为 carry

var addTwoNumbers = function(l1, l2) {
    let carry = 0
    let head = null,tail = null

    while(l1 || l2){
        const a = l1 == null ? 0 : l1.val
        const b = l2 == null ? 0 : l2.val
        const sum = a + b + carry
        // 分为头节点和非头节点两种情况
        if(!head){
            head = new ListNode(sum % 10)
            tail = head
        }else{
            tail.next = new ListNode(sum % 10)
            tail = tail.next
        }
				// 计算进位，这里要向下取整，不然是小数
        carry = Math.floor(sum / 10)

        if(l1){
            l1 = l1.next
        }
        if(l2){
            l2 = l2.next
        }
    }
    // 如果两个链表都走完了，还有进位，要新创建一个节点保存这个进位
    if(carry > 0){
        tail.next = new ListNode(carry)
    }

    return head
};

3.无重复字符的最长子串

滑动窗口，使用两个指针表示字符串中的某个子串（或窗口）的左右边界：[start,end]
然后我们可以不断地向右移动右指针，直到跟 [start,end] 里面的字符重复，记录下这个无重复子串的长度
将左指针 start 向右移动一位，更新起始的位置
更新后的 [start,end] 里面的字符仍不重复，继续移动右指针

var lengthOfLongestSubstring = function(s) {
    const hash = new Set()
    let rk = -1
    let ans = 0
    let length = s.length
    for(let i = 0; i < length; i++){
        if(i !== 0){
            hash.delete(s[i-1])
        }
      	// 为什么这里要判断 rk+1 而不是 rk？
        // 因为 [i,rk] 不重复，需要判断 rk+1 与 [i,rk] 内的字符是否重复
        while(rk + 1 < length && !hash.has(s[rk+1])){
            hash.add(s[rk+1])
            rk++
        }
        ans = Math.max(ans, rk + 1 - i)
    }
    return ans
};

70.爬楼梯

递归版会超时，用动态规划来做
定义 dp[n]：在第 n 阶爬楼梯的方法数，每次可以爬 1 或 2 阶
状态转移方程：dp[n] = dp[n-1] + dp[n-2]

var climbStairs = function(n) {
    let dp = []
    dp[0] = 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]
};

338.比特位计数

动态规划 O(N) 时间复杂度
判断是不是 2 的 n 次方，如果是说明二进制1的个数只有1个
状态转移方程：dp[i] = dp[i - Math.pow(2, Math.floor(Math.log2(i))) ] + 1。用一个数举例，比如 7 = 4 + 3，dp[7] = dp[3] + 1

var countBits = function(n) {
    let dp = [0]
    for(let i = 1; i <= n; i++){
        let sum = Math.floor(Math.log2(i))
        if(Math.pow(2,sum) === i){
            dp.push(1)
        }else{
            dp.push(dp[i - Math.pow(2,sum)] + 1)
        }
    }
    return dp
};

一种更好的办法（规律），基于奇偶数判断

var countBits = function(n) {
    let dp = [0]
    for(let i = 1; i <= n; i++){
        if(i % 2 === 1){
            dp.push(dp[i-1] + 1)
        }else{
            dp.push(dp[i/2])
        }
    }
    return dp
};

104.二叉树的最大深度

以 root 为根节点的二叉树最大深度：Math.max(左子树的最大深度，右子树的最大深度) + 1
如果访问到空节点，则返回 0

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

543.二叉树的直径

最初的解法：递归里面有其他递归，时空间复杂度都很高

var diameterOfBinaryTree = function(root) {
    let ans = maxDepth(root.left) + maxDepth(root.right)
    if(root.left){
        ans = Math.max(ans, diameterOfBinaryTree(root.left))
    }
    if(root.right){
        ans = Math.max(ans, diameterOfBinaryTree(root.right))
    }
    // return maxDepth(root.left) + maxDepth(root.right)
    return ans
};

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

跟二叉树的最大深度这题很类似，转换为求解每个节点（并不只是根节点）的左右子树最大深度之和的最大值

var diameterOfBinaryTree = function(root) {
    let ans = 0
    dfs(root)
    return ans
    
    function dfs(root){
      	// 到达空节点则返回 0
        if (!root) {
            return 0;
        }
        let left = dfs(root.left) // 左子树最大深度
        let right = dfs(root.right) // 右子树最大深度
        // 比较每个节点的直径，更新最大值
        ans = Math.max(ans,left + right)
        return Math.max(left,right) + 1 // 返回节点深度
    }
};

226.翻转二叉树

递归版：采用前序遍历
- 交换当前节点的左节点和右节点
- 递归左子树和右子树

var invertTree = function(root) {
    if(!root){
        return null
    }
		[root.left,root.right] = [root.right,root.left]
  	invertTree(root.left)
    invertTree(root.right)
    return root
};

递归版：采用后序遍历，自底向上
- 如果当前遍历到的节点 root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 root 为根节点的整棵子树的翻转。

var invertTree = function(root) {
    // 后序遍历，从下往上交换
    if(!root)   return null
    let leftNode = invertTree(root.left)
    let rightNode = invertTree(root.right)
    
    root.left = rightNode
    root.right = leftNode
    return root
};

非递归版：采用层序遍历，从上往下交换左节点和右节点

var invertTree = function(root) {
    if(!root)   return null
    let queue = [root]
    while(queue.length){
        let node = queue.shift()
        if(node.left || node.right){
            [node.left,node.right] = [node.right,node.left]
        }
        if(node.left){
            queue.push(node.left)
        }
        if(node.right){
            queue.push(node.right)
        }
    }
    return root
};

461.汉明距离

其实就是求异或，然后求二进制中 1 的个数

最开始用的是最笨的方法
- 求完异或，使用 toString(2) 将结果转换为二进制
- 然后迭代二进制字符串统计 1 的个数

var hammingDistance = function(x, y) {
    let sum = x ^ y
    let binary_str = sum.toString(2)
    let ans = 0
    for(let i = 0; i < binary_str.length; i++){
        if(binary_str.charAt(i) === '1'){
            ans++
        }
    }
    return ans
};

更优的解法
- 将异或值的每一位都与 1 进行与操作，统计结果为 1 的数量
- 每次与操作完成后，将异或值右移一位，直到为 0

var hammingDistance = function(x, y) {
    let sum = x ^ y
    let ans = 0
    while(sum !== 0){
        if(sum & 1 === 1){
            ans++
        }
        sum >>= 1
    }
    return ans
};

136.只出现一次的数字

这题简单，对所有数求异或就行了。因为其他数都出现两次，而相同的数异或值为 0，最后得到的就是只出现一次的数字

var singleNumber = function(nums) {
    let ans = 0
    for(let i = 0; i < nums.length; i++){
        ans ^= nums[i]
    }
    return ans
};

94.二叉树的中序遍历

递归法

var inorderTraversal = function(root) {
    let ans = []
    inorder(root,ans)
    return ans
};

var inorder = function(root,ans){
    // 遍历顺序：左->根->右
    if(root != null){
        inorder(root.left,ans)
        ans.push(root.val)
        inorder(root.right,ans)
    }
}

非递归法，利用栈
- 除了定义一个栈之外，还需要一个指针用于遍历节点
- 根据左子树优先遍历的原则，一直往左走并将访问的节点放入栈中
  - 记忆：中序遍历不忘“左链入栈”
- 直到到达左子树的最左端，访问到空节点时将节点出栈
- 处理右子树

var inorderTraversal = function(root) {
    let cur = root
    let stack = []
    let res = []
    while(stack.length || cur){
        if(cur){
            stack.push(cur)
            cur = cur.left
        }else{
            cur = stack.pop()
            res.push(cur.val)
            cur = cur.right
        }
    }
    return res
};

617.合并二叉树

递归三部曲

https://leetcode.cn/problems/merge-two-binary-trees/solution/by-carlsun-2-jroe/
- 确定递归函数的参数和返回值
  - 参数就是传入两个二叉树的根节点
  - 返回值就是合并之后二叉树的根节点
- 确定终止条件
  - 如果 root1 和 root2 都为 null，停止往下递归
- 确定单层递归的逻辑
  - 用的是二叉树的先序遍历
  - 先合并两棵二叉树的根节点
  - 再递归左子树和右子树，给根节点的左节点和右节点赋值

var mergeTrees = function(root1, root2) {
    if(!root1 && !root2){
        return null
    }
    let root = null
    if(root1 || root2){
        let a = root1 ? root1.val : 0
        let b = root2 ? root2.val : 0
        root = new TreeNode(a + b)
        root.left = mergeTrees(root1 ? root1.left : null,root2 ? root2.left : null)
        root.right = mergeTrees(root1 ? root1.right : null,root2 ? root2.right : null)
    }
    return root
};

101.对称二叉树

根节点左子树：left，根节点右子树：right
比较（left 的左节点和 right 的右节点） && （right 的左节点和 left 的右节点）是否相同
- 如果有一个为空则返回 false
- 如果两个值不同则返回 false
递归终止条件
- 都为空指针则返回 true

var isSymmetric = function(root) {
    if(!root)   return false
    return isSymmetric2(root.left,root.right)
};

function isSymmetric2(root1,root2){
    if(root1 == null && root2 == null){
        return true
    }else if(root1 == null || root2 == null){
        return false
    }else if(root1.val !== root2.val){
        return false
    }else{
        return isSymmetric2(root1.left,root2.right) && isSymmetric2(root1.right,root2.left)
    }
}

20.有效的括号

如果迭代到左括号，将其进栈
如果迭代到右括号，将其与栈顶比较是否成对
- 如果成对则弹出栈顶元素
如果最后栈为空，则说明是有效括号

var isValid = function(s) {
    let stack = []
    for(let i = 0; i < s.length; i++){
        // 把左括号进栈
        if(s[i] === '(' || s[i] === '{' || s[i] === '['){
                stack.push(s[i])
        }
        else{
            // 如果遇到非法字符直接返回结果
            if(!stack.length)    return false
            
            let top = stack[stack.length - 1]
            // 如果遍历到的右括号与栈顶的左括号对应上，则将左括号出栈
            if(s[i] === ')' && top === '(' || s[i] === '}' && top === '{' || s[i] === ']' && top === '['){
                stack.pop()
            }
        }
    }
    return stack.length ? false : true
};

102.二叉树的层序遍历

BFS 使用的是队列数据结构
将当前层的节点出队，同时将孩子节点入队
进入下一轮循环，直到队列为空

var levelOrder = function(root) {
    if(root == null)    return []
    let res = []
    let queue = [root]
    while(queue.length){
        // 设置一个计数器，值为某一层节点的数量
        let count = queue.length
        let level = []
        // 分层，当一层遍历完成后，进入下一次循环（下一层）
        while(count){
            let cur = queue.shift()
            level.push(cur.val)
            if(cur.left)    queue.push(cur.left)
            if(cur.right)   queue.push(cur.right)
            count--
        }
        res.push(level)
    }
    return res
};

169.多数元素

摩尔投票算法
- 将第一个数初始化为候选众数（candidate），令 count = 1
- 遍历 nums 时与 candidate 比较，相同则 count + 1，否则 count - 1
- 如果 count == 0，更改 candidate 并重新开始计数
- 算法的可行性：众数的出现次数大于半数，所以最后的 count 必定大于 0，其他数都会被抵消掉

var majorityElement = function(nums) {
    let res = nums[0]
    let count = 1
    for(let i = 1; i < nums.length; i++){
        if(res === nums[i]){
            count++
        }else{
            count--
        }
        if(count === 0){
            res = nums[i]
            count = 1
        }
    }
    return res
};

141.环形链表

利用快慢指针，慢指针一次走一步，快指针一次走两步
如果快慢指针相遇，说明链表有环

var hasCycle = function(head) {
    let slow = fast = head
    while(slow && fast && fast.next){
        slow = slow.next
        fast = fast.next.next
        if(slow === fast){
            return true
        }
    }
    return false
};

19.删除链表的倒数第N个结点

设置快慢指针，先让快指针先走 N 步
然后快慢指针同时往下走，直到快指针到达最后一个结点，此时慢指针为倒数第 N 个结点的前一个结点
找到前一个结点后，即可删除倒数第 N 个结点
这里要注意删除第一个结点的特殊情况

//快慢指针
function removeNthFromEnd( head ,  n ) {
    // write code here
    if(head == null)    return null
    let slow = head
    let fast = head
    
    for(let i = 0; i < n;i++){
        fast = fast.next
    }
    // 删除第1个
    if(fast == null){
        return head.next
    }
    while(fast.next){
        fast = fast.next
        slow = slow.next
    }
    slow.next = slow.next.next
    return head
}

206.反转链表

迭代法

定义三个指针，分别指向当前遍历到的结点 cur、它的前一个结点 pre 及后一个结点 next

var reverseList = function(head) {
    if(!head || !head.next){
        return head
    }
    let pre = null,cur = head
    while(cur){
        let next = cur.next
        cur.next = pre
        pre = cur
        cur = next
    }
    return pre
};

递归法

建议看图解演示，更好理解一些

https://leetcode.cn/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/

var reverseList = function(head) {
    if(!head || !head.next){
        return head
    }
    // 这里的 cur 指的是最后一个节点
    let cur = reverseList(head.next)
    head.next.next = head
  	// 避免出现环
    head.next = null
    return cur 
};

160.相交链表

设 A 链表头节点到相交处节点的长度为 a，B 链表头节点到相交处节点的长度为 b，相交处节点到尾节点的长度为 c，（a + c）+ b = （b + c）+ a
设置两个指针，一个从 A 链表头节点开始迭代，另一个从 B 链表头节点开始迭代
为了使这两个指针走过相同的长度，并在相交的节点上相遇：若有一个指针到达末尾，则将其置为另一个链表的头节点，继续往下走

var getIntersectionNode = function(headA, headB) {
    let a = headA
    let b = headB
    while(a !== b){
        a = (a === null) ? headB : a.next
        b = (b === null) ? headA : b.next
    }
    return a
};

Silentlight's blog

Leetcode 热题 HOT 100 百日刷题打卡

刷题计划

刷题方法

打卡记录

刷题笔记

1.两数之和

2.两数相加

3.无重复字符的最长子串

70.爬楼梯

338.比特位计数

104.二叉树的最大深度

543.二叉树的直径

226.翻转二叉树

461.汉明距离

136.只出现一次的数字

94.二叉树的中序遍历

617.合并二叉树

101.对称二叉树

20.有效的括号

102.二叉树的层序遍历

169.多数元素

141.环形链表

19.删除链表的倒数第N个结点

206.反转链表

160.相交链表

Silentlight