xianjianlf2 / javascript-algorithms Goto Github PK

View Code? Open in Web Editor NEW

2.0 1.0 0.0 7 KB

Leetcode 算法刷题

License: MIT License

JavaScript 40.01% HTML 59.99%

javascript-algorithms's Introduction

javascript-algorithms

每日一练 2022年2月16日

javascript-algorithms's People

Contributors

Stargazers

Watchers

javascript-algorithms's Issues

题目🌵

📝Leetcode 二叉树的最大深度

✏️https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]
输出：true

解题思路💡

递归

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

迭代

按层搜索 BFS遍历

var maxDepth = function (root) {
    // 迭代法
    if (!root) return 0
    let queue = [] //用数组模拟队列
    let depth = 0 //记录深度
    queue.push(root)
    while (queue.length) {
        const size = queue.length
        for (let i = 0; i < size; i++) {
            const current = queue.shift()//依次推出当前层的所有节点
            if (current.left) {
                queue.push(current.left)
            }
            if (current.right) {
                queue.push(current.right)
            }
        }
        depth += 1
    }
    return depth
};

题目🌵

📝Leetcode 232.用栈实现队列

✏️https://leetcode.cn/problems/implement-queue-using-stacks/description/

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

解题思路💡

var MyQueue = function () {
  this.stackIn = []
  this.stackOut = []
}

/**
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function (x) {
  this.stackIn.push(x)
}

/**
 * @return {number}
 */
MyQueue.prototype.pop = function () {
  if (this.stackOut.length) {
    return this.stackOut.pop()
  }
  while (this.stackIn.length) {
    this.stackOut.push(this.stackIn.pop())
  }
  return this.stackOut.pop()
}

/**
 * @return {number}
 */
MyQueue.prototype.peek = function () {
  const x = this.pop()
  this.stackOut.push(x)
  return x
}

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function () {
  return !this.stackIn.length && !this.stackOut.length
}

题目🌵

📝Leetcode 46 全排列

✏️https://leetcode-cn.com/problems/permutations/

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

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

解题思路💡

递归+回溯
回溯的本质就是穷举，我们这里可以抽象成一个n叉树
- 回溯需要终止条件
- 在当前题目中，当路径中的元素个数===数组元素个数，即为一组排列组合
```
if (path.length === k) {
    res.push([...path])     //当数组元素===原来数组的个数，说明一种排列组合完成
    //递归终止
    return
}
```
- 定义used数组，为了保证当前的排列中用的元素唯一

var permute = function (nums) {
    const res = [],
          path = []
    const len = nums.length;
    backtracking(nums, len, [])
    return res

    function backtracking(n, k, used) {
        if (path.length === k) {
            res.push([...path])     //当数组元素===原来数组的个数，说明一种排列组合完成
            //递归终止
            return
        }
        for (let i = 0; i < k; i++) {
            if (used[i]) continue   //遍历过的跳过
            path.push(n[i])         //存入当前路径
            used[i] = true          //标记当前元素已经被使用
            backtracking(n, k, used) // 递归下一层节点  dfs 深度遍历
            path.pop()              //撤销操作，将当前路径出栈一位，回溯
            used[i] = false         //撤销操作
        }
    }
}

result = permute([0, 1])

📝Leetcode 24. 两两交换链表中的节点

一起养成写作习惯！这是我参与「掘金日新计划 · 4 月更文挑战」的第1天，点击查看活动详情。

题目🌵

📝Leetcode 24. 两两交换链表中的节点

✏️https://leetcode-cn.com/problems/swap-nodes-in-pairs/

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

输入：head = [1,2,3,4]
输出：[2,1,4,3]

解题思路💡

递归

直接就是两两交换

var swapPairs = function (head) {
    if (head == null || head.next == null) {
        return head
    }
    const newHead = head.next
    head.next = swapPairs(newHead.next)
    newHead.next = head
    return newHead
};

迭代

（图来自猿来绘）

首先定义一个虚拟节点
定义临时节点保存当前节点，下一节点，下下节点的信息
如图所示，将 12 =>14，13 =>15，14=>13

var swapPairs = function (head) {
    const dummyHead = new ListNode(0, head)
    let cur = dummyHead
    while (cur.next && cur.next.next) {
        // 临时节点  保存节点信息
        let tmp = cur
        let tmp1 = tmp.next
        let tmp2 = tmp1.next
        // 将两个头元素指向变换后的节点
        tmp.next = tmp2
        tmp1.next = tmp2.next
        tmp2.next = tmp1
        // 移动位置
        cur = cur.next.next
    }
    return dummyHead.next
};

题目🌵

📝Leetcode 100.相同的树

✏️https://leetcode.cn/problems/same-tree/description/

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：

输入：p = [1,2,3], q = [1,2,3]
输出：true

解题思路💡

递归
- 分别遍历左子树和右子树

var isSameTree = function (p, q) {
  function traverses(p, q) {
    if (p === null && q === null) {
      return true
    }
    if (p === null || q === null) {
      return false
    }
    const left = traverses(p.left, q.left)
    const right = traverses(p.right, q.right)
    return left && right && p.val === q.val
  }
  return traverses(p, q)
}

用两个队列去迭代

var isSameTree = function (p, q) {
  if (p === null && q === null) {
    return true
  }
  if (p === null || q === null) {
    return false
  }

  let queueP = [p]
  let queueQ = [q]
  while (queueP.length && queueQ.length) {
    const nodeP = queueP.shift()
    const nodeQ = queueQ.shift()
    if (nodeP.val !== nodeQ.val) {
      return false
    }

    // 迭代左右子树
    if (nodeP.left && nodeQ.left) {
      queueP.push(nodeP.left)
      queueQ.push(nodeQ.left)
    } else if (nodeP.left || nodeQ.left) {
      return false
    }
    if (nodeP.right && nodeQ.right) {
      queueP.push(nodeP.right)
      queueQ.push(nodeQ.right)
    } else if (nodeP.right || nodeQ.right) {
      return false
    }
  }
  return true
}

题目🌵

📝Leetcode 77. 组合

✏️https://leetcode-cn.com/problems/combinations/

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

解题思路💡

递归+回溯
回溯的本质就是穷举，我们这里可以抽象成一个n叉树
- 回溯需要终止条件
- 在当前题目中，当路径中的元素个数===数组元素个数，即为一组排列组合
```
if (path.length === k) {
    res.push([...path])     //当数组元素===原来数组的个数，说明一种排列组合完成
    //递归终止
    return
}
```

var combine = function (n, k) {
    const result = [], path = []
    const backTracking = (startIndex, n, k) => {
        //剪枝，去掉大于k个的组合
        for (let i = startIndex; i <= n - (k - path.length) + 1; i++) {
            if (path.length === k) {
                result.push([...path])
                return
            }
            path.push(i)
            backTracking(i + 1, n, k)
            path.pop()
        }
    }
    backTracking(1, n, k)
    return result
};

题目🌵

📝Leetcode 35. 搜索插入位置

✏️https://leetcode-cn.com/problems/search-insert-position/

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

输入: nums = [1,3,5,6], target = 5
输出: 2

解题思路💡

二分法

var searchInsert = function (nums, target) {
    let left = 0, right = nums.length - 1
    while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2)
        if (nums[mid] === target) {
            // 找到就返回当前位置
            return mid
        }else if (nums[mid] > target) {
            right = mid - 1
        } else if (nums[mid] < target) {
            left = mid + 1
        }
    }
    // 如果没找到，则此时必然 left=right+1,而left恰好就是我们要找的索引位置
    return left

};

题目🌵

📝Leetcode 两数之和

✏️https://leetcode-cn.com/problems/two-sum/

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

解题思路💡

暴力解法

首先想到的是直接莽，直接对所有的数进行循环
当找到nums[i]+nums[j]==target时返回当前的索引值

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

进一步优化

从图上所示，我们执行的时间靠后，说明程序执行消耗了很多时间，我们可以做进一步的优化。

🔧问题：当与第一个数做匹配时，需要遍历一次数组，消耗很多的时间

💡思路：建立一个HashMap，记录当前的差值和对应的索引号，避免了重复遍历前面的元素。

Hash表

先判断Hash表中是否存在target-nums[i]
如果存在,返回当前的索引值和map.get(target-nums[i])
如果不存在,则以num[i]作为key,以索引地址作为value

var twoSum = function (nums, target) {
    const map = new Map()
    for (let i = 0, len = nums.length; i < len; i++) {
        let match = target - nums[i]
        if (map.has(match)) {
            return [map.get(match), i]
        } else {
            map.set(nums[i], i)
        }
    }
    return []
}

也可以直接使用in操作符

var twoSum = function (nums, target) {
  let obj = {}
  for (let i = 0; i < nums.length; i++) {
    let num = nums[i]
    if (num in obj) {
      return [obj[num], i]
    } else {
      obj[target - num] = i
    }
  }
  return []
}

可以看出经过优化后，程序在性能上得到了优化。

题目🌵

📝Leetcode 141. 环形链表

✏️https://leetcode.cn/problems/linked-list-cycle/

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

解题思路💡

快慢指针
- 如果有环，快指针必然追上慢指针

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

题目🌵

📝Leetcode 209. 长度最小的子数组

✏️https://leetcode.cn/problems/minimum-size-subarray-sum/

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

解题思路💡

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
// 快慢指针，滑动窗口
// 先让快的一直走，sum 一直累加
// 当触发 sum>= target 时 慢指针开始缩小窗口
var minSubArrayLen = function (target, nums) {
    let len = nums.length
    let fast = 0
    let slow = 0
    let sum = 0
    let result = len + 1

    while (fast < len) {
        sum += nums[fast]
        while (sum >= target) {
            let subLen = fast - slow + 1
            result = (result < subLen) ? result : subLen
            sum -= nums[slow]
            slow++
        }
        fast++
    }
    return result > len ? 0 : result
};

题目🌵

📝Leetcode 1047.删除字符串中的所有相邻重复项

✏️https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例 1：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

解题思路💡

用堆栈的**
因为js的链表中是用数组来模拟，所以可以直接用index来访问元素

var removeDuplicates = function (s) {
  let stack = []
  for (const item of s) {
    const len = stack.length
    if (len && stack[len - 1] === item) {
      stack.pop()
      continue
    } else {
      stack.push(item)
    }
  }
  return stack.join('')
}

题目🌵

📝Leetcode 15 三数之和

✏️https://leetcode-cn.com/problems/3sum/

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

解题思路💡

哈希表

两层for循环可以确立a,b的值，最后再比较c的值是否存在于哈希表中
但是，这里有个问题，三元组合可能会存在重复元素
不好做减枝操作
难点：如何去除重复解。

跳过这种方法

双指针

var threeSum = function (nums) {
    const len = nums.length
    if (len < 3) return []
    nums.sort((a, b) => a - b)
    const res = []
    for (let i = 0; i < len - 2; i++) {
        if (nums[i] > 0) break
        // a 去重
        if (i > 0 && nums[i] === nums[i - 1]) continue
        let l = i + 1,
            r = len - 1
        while (l < r) {
            const sum = nums[l] + nums[r] + nums[i]
            if (sum < 0) {
                l++
                continue
            }
            if (sum > 0) {
                r--
                continue
            }
            res.push([nums[i], nums[l], nums[r]])
            //b c 去重
            while (l < r && nums[l] === nums[l + 1]) l++
            while (l < r && nums[r] === nums[r - 1]) r--
            //
            r--
            l++
        }
    }
    return res
}

题目🌵

📝Leetcode 125. 验证回文串

✏️https://leetcode.cn/problems/valid-palindrome/

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

**说明：**本题中，我们将空字符串定义为有效的回文串。

输入: "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串

解题思路💡

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function (s) {
    let str = s.toLocaleLowerCase().replace(/[^a-z0-9]/g, '')
    let left = 0
    let right = str.length - 1
    while (left <= right) {
        if (str[left] !== str[right]) {
            return false
        }
        left++
        right--
    }
    return true
};

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function (s) {
    let str = s.toLocaleLowerCase().replace(/[^a-z0-9]/g, '')
    return str.split('').reverse().join('') === str
};

题目🌵

📝Leetcode 71.简化路径

✏️https://leetcode.cn/problems/simplify-path/description/

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点（..）表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。

请注意，返回的 规范路径 必须遵循下述格式：

始终以斜杠 '/' 开头。
两个目录名之间必须只有一个斜杠 '/' 。
最后一个目录名（如果存在）不能以 '/' 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。

返回简化后得到的 规范路径 。

示例 1：

输入：path = "/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。

解题思路💡

var simplifyPath = function (path) {
  let stack = [] // 数组模拟栈
  const paths = path.split('/')
  for (item of paths) {
    if (item === '..') {
      stack.pop()
    } else if (item && item !== '.') {
      stack.push(item)
    }
  }
  return '/' + stack.join('/')
}

题目🌵

📝Leetcode 验证二叉搜索树

✏️https://leetcode-cn.com/problems/validate-binary-search-tree/

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]
输出：true

解题思路💡

递归

首先根据题意，我们可以遍历这课树
递归有“三步曲”
- 确定递归参数和返回值
- 确定递归的终止条件
- 单层递归所需要做的事情

根据题目，二叉搜索树是左子树小于根节点，右子树大于根节点。

Warning:不是简单的 root.val>root.left.val && root.val<root.right.val

var isValidBST = function (root, lower = -Infinity, upper = Infinity) {
    if (!root) return true
    if (root.val >= upper || root.val <= lower) return false
    return isValidBST(root.left, lower, root.val) && isValidBST(root.right, root.val, upper)
};

解二

先对二叉树进行中序遍历，如果是二叉搜索树，得到的数组必定是有序递增的

var isValidBST = function (root) {
    // 先对树进行中序遍历
    const cache = []
    const traversal = (root, cache) => {
        if (!root) return
        traversal(root.left, cache)
        cache.push(root.val)
        traversal(root.right, cache)
    }
    traversal(root, cache)
    // 中序遍历结束
    // 对cache结果循环  看下是否是有序递增序列
    for (let i = 0; i < cache.length - 1; i++) {
        if (cache[i] >= cache[i + 1]) return false
    }
    return true
};

迭代

跟之前的前序遍历差不多逻辑
使用一个栈去存储所有的左子树，直到最后一个
此时开始出栈操作，比较右边的节点是否比左边的节点大

var isValidBST = function (root) {
    let stack = []
    let current = root
    let prev = null
    while (current || stack.length > 0) {
        while (current) {
            stack.push(current)
            current = current.left
        }
        current = stack.pop()
        if (prev && current.val <= prev.val) {
            return false
        }
        prev = current
        current = current.right
    }
    return true
}

Tips：

同一个题目可以有多个写法，如果是用递归的写法，需要按“三步曲”走，确认好递归终止的条件和单层处理的逻辑。

题目🌵

📝Leetcode 876.链表的中间结点

✏️https://leetcode.cn/problems/middle-of-the-linked-list/description/

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

解题思路💡

快慢指针

var middleNode = function (head) {
  let fast = head
  let slow = head

  while (fast && fast.next) {
    fast = fast.next.next
    slow = slow.next
  }
  return slow
}

每日一题，LeetCode相关，前面是题号，后面是描述

每天对应leet code上面的题目
掘金：https://juejin.cn/user/4495219058030952
github：https://github.com/La2yTibers

题目🌵

📝Leetcode 203. 移除链表元素

✏️https://leetcode-cn.com/problems/remove-linked-list-elements/

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

解题思路💡

在链表前面增加一个虚拟节点

var removeElements = function (head, val) {
    let ret = new ListNode(0, head)
    let cur = ret
    while (cur.next) {
        if (cur.next.val === val) {
            cur.next = cur.next.next
            continue
        }
        cur = cur.next
    }
    return ret.next
};

题目🌵

📝Leetcode 344. 反转字符串

✏️https://leetcode.cn/problems/reverse-string/

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

解题思路💡

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function (s) {
    // return s.reverse()
    let left = 0
    let right = s.length - 1
    while (left <= right) {
        let tmp = s[left]
        s[left] = s[right]
        s[right] = tmp
        left++
        right--
    }
};

题目🌵

📝Leetcode 150. 逆波兰表达式求值

✏️https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/

根据逆波兰表示法，求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

注意两个整数之间的除法只保留整数部分。

可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

解题思路💡

最外层定义一个object

  let calc = {
    '+': (a, b) => a + b,
    '-': (a, b) => b - a,
    '*': (a, b) => a * b,
    '/': (a, b) => (b / a) | 0, //Math.trunc((b / a))
  }

然后利用堆栈来处理后缀表达式

var evalRPN = function (tokens) {
  let calc = {
    '+': (a, b) => a + b,
    '-': (a, b) => b - a,
    '*': (a, b) => a * b,
    '/': (a, b) => (b / a) | 0,
  }

  let stack = []

  for (let i = 0; i < tokens.length; i++) {
    const t = tokens[i]

    if (t in calc) {
      stack.push(calc[t](stack.pop(), stack.pop()))
    } else {
      stack.push(Number(t))
    }
  }
  return stack.pop()
}

题目🌵

📝Leetcode 977. 有序数组的平方

✏️https://leetcode.cn/problems/intersection-of-two-arrays/

给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

解题思路💡

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function (nums) {
    let result = []
    for (let i = 0; i < nums.length; i++) {
        result.push(nums[i] * nums[i])
    }
    return result.sort((a, b) => a - b)
};

优化一：

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function (nums) {
    return nums.map((v) => v * v).sort((a, b) => a - b)
};

双指针：

var sortedSquares = function (nums) {
    let left = 0
    let right = nums.length - 1
    // 初始化数组才能直接用K 去访问
    let arr = Array(nums.length)
    let k = right
    while (left <= right) {
        let l = nums[left] * nums[left]
        let r = nums[right] * nums[right]
        if (l < r) {
            arr[k] = r
            right--
        } else {
            arr[k] = l
            left++
        }
        k--
    }
    return arr
}

版本二：

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function (nums) {
    let res = []
    let left = 0
    let right = nums.length - 1
    let k = 0
    while (left <= right) {
        let leftNum = nums[left] * nums[left]
        let rightNum = nums[right] * nums[right]
        if (leftNum < rightNum) {
            res.unshift(rightNum)
            right--
        } else {
            res.unshift(leftNum)
            left++
        }
    }
    return res
};

题目🌵

📝Leetcode 1. 两数之和

✏️https://leetcode.cn/problems/two-sum/

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

解题思路💡

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
    let map = new Map()
    for (let i = 0; i < nums.length; i++) {
        if (map.has(nums[i])) {
            return [map.get(nums[i]), i]
        } else {
            map.set(target - nums[i], i)
        }
    }
    return []
};

题目🌵

📝Leetcode 二叉树的前序遍历

✏️https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

给你二叉树的根节点 root ，返回它节点值的前序遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]

解题思路💡

递归

根据二叉树前序遍历的规定先遍历自己，再遍历左子树，再遍历右子树。
直接使用递归的形式，用一个数组arr来存储遍历节点的值即可。

var preorderTraversal = function (root, arr = []) {
    if (root) {
        arr.push(root.val)
        preorderTraversal(root.left, arr)
        preorderTraversal(root.right, arr)
    }

    return arr
}

迭代

先利用一个栈存储当前的节点
一直遍历左子树，直到所有的左子树遍历完
在弹出最后入栈的一个节点，然后遍历其右子树

var preorderTraversal = function (root) {
    //   迭代
    //   开始遍历，使用一个栈存储
    let result = []
    let stack = []
    let current = root
    while (current || stack.length > 0) {
        while (current) {
            result.push(current.val)
            stack.push(current) //后面通过current 找左右子树
            current = current.left
        }
        current = stack.pop()
        current = current.right
    }
    return result
}

题目🌵

📝Leetcode 有效的括号

✏️https://leetcode-cn.com/problems/valid-parentheses/

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()"
输出：true

解题思路💡

需要一个数组模拟栈的数据结构

根据题意，需要建立括号的匹配规则。这里使用key-value的形式去创建

let obj = {
        '(': ')',
        '[': ']',
        '{': '}'
}

var isValid = function (s) {
    let stack = []
    let obj = {
        '(': ')',
        '[': ']',
        '{': '}'
    }
    for (let i = 0; i < s.length; i++) {
        const ele = s[i]
        //判断括号的匹配关系
        if (ele in obj) {
            //搜索左边的括号是否存在
            //如果存在，就入栈
            stack.push(ele)
        } else {
            if (ele != obj[stack.pop()]) {
                //如果不存在，则将堆栈的顶部元素弹出，取obj的value值，看是否匹配
                //不匹配
                return false
            }
        }
    }
    // 判断堆栈是否为空
    return !stack.length
};

📝Leetcode 167. 两数之和 II - 输入有序数组

题目🌵

📝Leetcode 167. 两数之和 II - 输入有序数组

✏️https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/

给你一个下标从 1 开始的整数数组 numbers ，该数组已按非递减顺序排列，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

解题思路💡

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (numbers, target) {
    let map = new Map()
    for (let i = 0; i < numbers.length; i++) {
        if (map.has(numbers[i])) {
            return [map.get(numbers[i]), i + 1]
        } else {
            map.set(target - numbers[i], i + 1)
        }
    }
    return []
};

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
// 双指针
var twoSum = function (numbers, target) {
    let i = 0
    let j = numbers.length - 1
    while (i < j) {
        const sum = numbers[i] + numbers[j]
        if (sum === target) {
            return [i + 1, j + 1]
        } else if (sum > target) {
            j--
        } else {
            i++
        }
    }
};

题目🌵

📝Leetcode 283. 移动零

✏️https://leetcode.cn/problems/move-zeroes/

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意，必须在不复制数组的情况下原地对数组进行操作。

示例 1：

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

解题思路💡

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
//快慢指针
var moveZeroes = function (nums) {
    let i = 0
    let j = 0

    while (j < nums.length) {
        if (nums[j]) {
            [nums[i], nums[j]] = [nums[j], nums[i]]
            i++
        }
        j++
    }
    return nums
};

题目🌵

📝Leetcode 151. 颠倒字符串中的单词

✏️https://leetcode.cn/problems/reverse-words-in-a-string/description/

给你一个字符串 s ，颠倒字符串中单词的顺序。

单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。

返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。

**注意：**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"

解题思路💡

直接使用js中的内置函数

var reverseWords = function (s) {
  return s
    .trim() // 去掉前后空格
    .split(' ') // 以空格分割
    .filter((v) => v) //  去掉空字符串
    .reverse() // 反转数组
    .join(' ')
}

双端队列

var reverseWords = function (s) {
  let left = 0
  let right = s.length - 1
  let queue = [] // 双端队列
  let word = ''
  while (s.charAt(left) === ' ') {
    left++
  }
  while (s.charAt(right) === ' ') {
    right--
  }
  // 去掉前后空格
  while (left <= right) {
    const ch = s.charAt(left)
    if (ch === ' ' && word) {
      queue.unshift(word) // 入队
      word = '' // 清空字符串
    } else if (ch !== ' ') {
      word += ch // 拼接单个字符串
    }
    left++
  }
  queue.unshift(word) // 最后一个单词入队
  return queue.join(' ') //  拼接成字符串
}

题目🌵

📝Leetcode 50 Pow(x, n)

✏️https://leetcode-cn.com/problems/powx-n/

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn ）。

输入：x = 2.00000, n = 10
输出：1024.00000

解题思路💡

分治
- 将大的问题划分成一个个小的问题，此时需要注意每个子问题之间需要合并处理
- 这里使用递归的形式，将x^n的问题划分成x^(2/n)，x^(2/n)

var myPow = function (x, n) {
    if (n === 0) return 1 //递归结束条件
    if (n < 0) return 1 / myPow(x, -n)	//计算小于0时的指数幂
    if (n % 2) return x * myPow(x, n - 1) //继续划分

    return myPow(x * x, n / 2)  //分治
};

题目🌵

📝Leetcode 相同的树

✏️https://leetcode-cn.com/problems/same-tree/

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：

输入：p = [1,2,3], q = [1,2,3]
输出：true

解题思路💡

递归

可以使用递归的形式，去比较左右子树的值是否相等

var isSameTree = function (p, q) {
    if (p == null && q == null) {
        return true
    }
    if (p == null || q == null) {
        return false
    }
    if (p.val !== q.val) {
        return false
    }
    // p和q的值相等，需要递归判断左右子树
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
};

题目🌵

📝Leetcode 翻转二叉树

✏️https://leetcode-cn.com/problems/invert-binary-tree/

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

解题思路💡

树的遍历

递归

树的本身属性，自带递归的属性，可以很方便的使用递归。

var invertTree = function (root) {
    // 递归
    if (root === null) {
        return
    }
    [root.left, root.right] = [invertTree(root.right), invertTree(root.left)]
    return root
}

相关知识点

LeetCode
- 二叉树的前序遍历
树的遍历
- 前中后序
  
  以图左边为例
  
  前序：N => L => R
  
  中序：L => N => R
  
  后序：L => R => N

前序：4213769
中序：1234679
后序：1326974

题目🌵

📝Leetcode 101.对称二叉树

✏️https://leetcode.cn/problems/symmetric-tree/description/

给你一个二叉树的根节点 root ，检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

解题思路💡

递归
- 分别遍历左子树和右子树

var isSymmetric = function (root) {
  function traverse(root1, root2) {
    if (!root1 && !root2) {
      return true
    }
    if (root1 === null || root2 === null) {
      return false
    }
    if (root1.val === root2.val) {
      return (
        traverse(root1.left, root2.right) && traverse(root1.right, root2.left)
      )
    }
    return false
  }
  return traverse(root.left, root.right)
}

题目🌵

📝Leetcode 225. 用队列实现栈

✏️https://leetcode.cn/problems/implement-stack-using-queues/description/

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例 1：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

解题思路💡

var MyStack = function () {
  this.queue1 = []
  this.queue2 = []
}

/**
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function (x) {
  this.queue1.push(x)
}

/**
 * @return {number}
 */
MyStack.prototype.pop = function () {
  if (!this.queue1.length) {
    [this.queue1, this.queue2] = [this.queue2, this.queue1]
  }
  while (this.queue1.length > 1) {
    this.queue2.push(this.queue1.shift())
  }
  return this.queue1.shift()
}

/**
 * @return {number}
 */
MyStack.prototype.top = function () {
  const x = this.pop()
  this.queue1.push(x)
  return x
}

/**
 * @return {boolean}
 */
MyStack.prototype.empty = function () {
  return !this.queue1.length && !this.queue2.length
}

题目🌵

📝Leetcode 26. 删除有序数组中的重复项

✏️https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

给你一个升序排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

解题思路💡

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function (nums) {
    let slow = fast = 0
    let len = nums.length
    while (fast < len) {
        if (nums[slow] !== nums[fast]) {
            slow++
            nums[slow] = nums[fast]
        }
        fast++
    }
    return slow + 1

};

题目🌵

📝Leetcode 216. 组合总和 III

✏️https://leetcode-cn.com/problems/combination-sum-iii/

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9
每个数字最多使用一次
返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

解题思路💡

递归+回溯

回溯的本质就是穷举，我们这里可以抽象成一个n叉树

回溯需要终止条件

在当前题目中，当路径中的元素个数===数组元素个数，即为一组排列组合

if (path.length === k) {//当数组元素===原来数组的个数，说明一种排列组合完成
    if(sum===n){ // 满足题意的存进结果
        res.push([...path])     
    }
    //递归终止
    return
}

定义used数组，为了保证当前的排列中用的元素唯一

var combinationSum3 = function (k, n) {
    const result = [], path = []

    backTracking(1, 0, k, n)

    function backTracking(startIndex, sum, limitLen) {
        if (sum > n)
            return
        if (path.length === limitLen) {
            if (sum === n) {
                result.push([...path])
            }
            return
        }
        for (let i = startIndex; i <= 9; i++) {
            path.push(i)
            sum += i
            backTracking(i + 1, sum, limitLen)
            sum -= i
            path.pop()
        }
    }
    return result
};

题目🌵

📝Leetcode 374 猜数字大小

✏️https://leetcode-cn.com/problems/guess-number-higher-or-lower/

猜数字游戏的规则如下：

每轮游戏，我都会从 1 到 n 随机选择一个数字。请你猜选出的是哪个数字。
如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：

-1：我选出的数字比你猜的数字小 pick < num
1：我选出的数字比你猜的数字大 pick > num
0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num
返回我选出的数字。

示例 1：

输入：n = 10, pick = 6
输出：6

解题思路💡

二分法

从数组的中间元素开始查找，如果正好是中间值，直接return
如果是其他情况，必定在左区间或者右区间，再去折中查找，直到满足第一个条件

var guessNumber = function (n) {
    let left = 1, right = n
    while (left < right) {
        const mid = Math.floor(left + (right - left) / 2)
        if (guess(mid) <= 0) {
            // 更新查找区间为[left,mid]
            right = mid
        } else {
            //更新查找区间为[mid+1, right]
            left = mid + 1
        }
    }
    return left
};

题目🌵

📝Leetcode 简化路径

✏️https://leetcode-cn.com/problems/simplify-path/description/

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。

请注意，返回的 规范路径 必须遵循下述格式：

始终以斜杠 '/' 开头。
两个目录名之间必须只有一个斜杠 '/' 。
最后一个目录名（如果存在）不能以 '/' 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。

返回简化后得到的 规范路径 。

示例 1：

输入：path = "/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。

解题思路💡

会用到栈来操作，分几种情况

如果是遇到'..'，stack顶弹出
如果是'.'或' '，则表示当前目录或不作处理
如果不是上面两种情况，且存在字符，则将当前的路径入栈

所以，我们得到了如下代码

var simplifyPath = function (path) {
    let stack = []
    //将传入的路径切割
    let paths = path.split('/')
    for (let i = 0; i < paths.length; i++) {
        const p = paths[i]
        // 分情况处理
        // '..'返回上一级 
        //'' '.'不用管
        if (p == '..') {
            stack.pop()
        } else if (p && p != '.') {
            stack.push(p)
        }
    }
    return '/' + stack.join('/')
}

进一步思考

题目只是简单需求，如果复杂度增加，比如增加多种规则，加入正则等匹配方式，原有的if else写法可读性会下降，不够优雅。

问题：复杂情况下代码多层if else会导致代码可读性下降
解决：利用一个obj去存储这些规则，方便管理，增加可读性。

var simplifyPath = function (path) {
    const obj = {
        '': (stack) => stack,
        '.': (stack) => stack,
        '..': (stack) => {
            stack.pop()
            return stack
        },
    }
    let stack = []
    let paths = path.split('/')

    for (let i = 0; i < paths.length; i++) {
        const p = paths[i]
        // 分情况
        // '' '..'返回上一级 '.'不用管
        if (p in obj) {
            stack = obj[p](stack)
        } else {
            stack.push(p)
        }
    }
    return '/' + stack.join('/')
}

解析：

Q:为什么在'..'的情况下要包一层对象返回
A:可能会遇到`/../`的情况，当出现这个情况时，当前数组为空，使用`pop()`操作会导致返回undefined

相关应用

在Node.js中也有相关的应用，如path.resolve()
- 生成的路径会被规范化，并删除尾部斜杠
```
path.resolve('/foo/bar','./baz')
//返回：'/foo/bar/baz'
```
JSX解析判断是否合法
- 判断html标签是否成对出现<div></div>
表达式转为后缀表达式（运算符使用栈）

题目🌵

📝Leetcode 47. 全排列 II

✏️https://leetcode-cn.com/problems/permutations-ii/

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

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

解题思路💡

递归+回溯
回溯的本质就是穷举，我们这里可以抽象成一个n叉树
- 回溯需要终止条件
- 在当前题目中，当路径中的元素个数===数组元素个数，即为一组排列组合
```
if (path.length === nums.length) {
    res.push([...path])     //当数组元素===原来数组的个数，说明一种排列组合完成
    //递归终止
    return
}
```
- 定义used数组，为了保证当前的排列中用的元素唯一
需要考虑重复的元素，首先需要一个有序数组，然后在递归层进行剪枝操作

var permuteUnique = function (nums) {
    nums.sort((a, b) => a - b)
    const res = [],
        path = []
    backTracking([])
    return res

    function backTracking(used) {
        if (path.length === nums.length) {
            res.push([...path])
            return
        }
        for (let i = 0; i < nums.length; i++) {
            //去重，在树层上剪去重复的分支
            if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) {
                continue
            }
            if (!used[i]) {
                path.push(nums[i])
                used[i] = true
                backTracking(used)
                path.pop()
                used[i] = false
            }
        }
    }
}

题目🌵

📝Leetcode 反转链表

✏️https://leetcode-cn.com/problems/reverse-linked-list/description/

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

解题思路💡

遍历

链表翻转，只需要将当前节点的next指针指向前驱节点。
需要一个临时变量去存储当前next指向的节点
需要一个变量去做交换

var reverseList = function (head) {
    let cur = head
    let prev = null
    while (cur != null) {
        //解构的方式
        [cur.next, prev, cur] = [prev, cur, cur.next]
    }
    return prev
}

迭代

**和双指针的一样，代码有所不同
这里可能会比较绕

var reverseList = function (head) {
    if (!head || !head.next) {
        return head
    }
    const p = reverseList(head.next)
    head.next.next = head
    head.next = null
    return p
}

题目🌵

📝Leetcode 234. 回文链表

✏️https://leetcode.cn/problems/palindrome-linked-list/

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

解题思路💡

快慢指针，当快指针走完，慢指针恰好在中间
- 分奇偶情况讨论
- 奇数：middle = middle.next
- 偶数：middle = middle
比对前半截和后半截的值是否相同

var isPalindrome = function (head) {
    let slow = fast = head
    let prev
    while (fast && fast.next) {
        fast = fast.next.next
        let next = slow.next
        slow.next = prev
        prev = slow
        slow = next
    }

    // 奇数处理
    if (fast) {
        slow = slow.next
    }

    while (slow && prev) {
        if (slow.val !== prev.val) {
            return false
        }
        slow = slow.next
        prev = prev.next
    }
    return true
};

题目🌵

📝Leetcode 236 二叉树的最近公共祖先

✏️https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

解题思路💡

递归

确定终止条件
单层处理逻辑
返回值

var lowestCommonAncestor = function (root, p, q) {
    if (!root || root == p || root == q) {
        return root
    }
    const left = lowestCommonAncestor(root.left, p, q)
    const right = lowestCommonAncestor(root.right, p, q)
    if (!left) {
        return right
    }
    if (!right) {
        return left
    }
    return root
};

题目🌵

📝Leetcode 349. 两个数组的交集

✏️https://leetcode.cn/problems/intersection-of-two-arrays/

给定两个数组 nums1 和 nums2 ，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

解题思路💡

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function (nums1, nums2) {
    return [...new Set(nums1.filter((item) => nums2.includes(item)))]
};

题目🌵

📝Leetcode 142. 环形链表 II

✏️https://leetcode.cn/problems/linked-list-cycle-ii/

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

解题思路💡

快慢指针
- 如果有环，快指针必然追上慢指针
- 此时从头开始出发，当缓存指针与慢指针相等时，返回当前节点

var detectCycle = function (head) {
    let slow = head
    let fast = head
    // 初始变量
    let tmpNode = head
    while (fast && fast.next) {
        fast = fast.next.next
        slow = slow.next
        if (fast === slow) {
            while (slow && tmpNode) {
                if (slow === tmpNode) {
                    return slow
                }
                slow = slow.next
                tmpNode = tmpNode.next
            }
        }
    }
    return null
};

题目🌵

📝Leetcode 环形链表

✏️https://leetcode-cn.com/problems/linked-list-cycle/description/

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

解题思路💡

遍历（偷鸡写法）

因为链表存在环，会一直遍历下去，直到计数器大于10000

var hasCycle = function (head) {
    let count = 1
    while (head) {
        if (count > 10000) {
            return true
        }
        count += 1
        head = head.next
    }
    return false
}

如果面试的时候这样写，面试官大概会....

使用`Hash表`记录

利用我们之前讲到cache缓存的方式，建立一个Map或者Set去记录当前链表
如果存在该元素，则说明有环

var hasCycle = function (head) {
    let cache = new Set()
    while (head) {
        if (cache.has(head)) {
            return true
        } else {
            cache.add(head)
        }
        head = head.next
    }
    return false
}

进一步优化

**进阶：**你能用 O(1)（即，常量）内存解决此问题吗？

使用快慢指针的解法，类似于操场上龟兔赛跑。
跑的快的总会追上跑得慢的，形成套圈。

var hasCycle = function (head) {
    // 快慢指针
    let fast = head
    let slow = head
    while (fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
        if (fast == slow) {
            return true
        }
    }
    return false
}

通过两个变量的声明，把空间复杂度降到了O(1)。

题目🌵

📝Leetcode 20. 有效的括号

✏️https://leetcode.cn/problems/valid-parentheses/description/

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()"
输出：true

解题思路💡

构造一个Map对成对的括号进行匹配

var isValid = function (s) {
  let stack = []
  const map = {
    '(': ')',
    '[': ']',
    '{': '}'
  }
  for (x of s) {
    if (x in map) {
      stack.push(map[x])
    } else {
      if (stack.pop() !== x) {
        return false
      }
    }
  }
  return stack.length === 0
}

题目🌵

📝Leetcode 斐波那契数列

✏️https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：1

解题思路💡

递归

后面一个数是前面两个数之和,首先想到的是递归解决

var fib = function (n) {
    if (n == 1 || n == 0) {
        return n
    }
    return fib(n - 1) + fib(n - 2)
}

进一步优化

从图上看出，执行时间是比较靠后的，说明代码还是消耗了较多时间，需要进一步的优化。

🔧问题：递归每次都需要重新计算前面的

💡思路：采取缓存的方式，利用一个数组`cache`来存储前面计算的结果（动态规划）

var fib = function (n) {
    //递推
    let cache = []
    for (let i = 0; i <= n; i++) {
        if (i == 1 || i == 0) {
            cache[i] = i
        } else {
            cache[i] = cache[i - 1] + cache[i - 2]
        }
    }
    return cache[n]
}

相比之前的所消耗的时间，有了明显的提升。

题目🌵

📝Leetcode 27. 移除元素

✏️https://leetcode.cn/problems/remove-element/

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

解题思路💡

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function (nums, val) {
    for (let i = nums.length; i >= 0; i--) {
        if (nums[i] === val) {
            nums.splice(i, 1)
        }
    }
    return nums.length
};

题目🌵

📝Leetcode 146. LRU 缓存

✏️https://leetcode.cn/problems/lru-cache/

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例 1：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

解题思路💡

Hash表+双向链表做处理
- Hash表负责做查询的记录
- 双向链表可以方便的从头或尾插入数据

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
    this.capacity = capacity
    this.map = new Map()
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
    if (this.map.has(key)) {
        const value = this.map.get(key)
        // 相当于链表操作,将当前的Key移动到最后面
        this.map.delete(key)
        this.map.set(key, value)
        return value
    } else {
        return -1
    }
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
    if (this.map.has(key)) {
        this.map.delete(key)
    }
    this.map.set(key, value)
    // 超出容量  移除
    if (this.map.size > this.capacity) {
        // 移除头节点
        this.map.delete(this.map.keys().next().value)
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

📝69-x 的平方根

题目🌵

📝Leetcode 69 x 的平方根

✏️https://leetcode-cn.com/problems/sqrtx/

给你一个非负整数 x ，计算并返回 x 的算术平方根。

由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

输入：x = 4
输出：2

解题思路💡

二分法
- 已知：x的算术平方根小于或等于x
  - 取1-x 的中间值mid，假如 mid² ≤ x，即mid有可能是x的算术平方根
    - 此时再判断 (mid+1)²，如果大于x，则说明Mid 为x的算术平方根
    - 如果小于 x，则从左趋近于右边界，将left=mid+1
  - 如果mid² > x ，则从右侧趋近，将right= mid-1
  - 直到满足情况 return
- 如果循环结束，还是没有找到，说明输入的值为0
  - return 0

var mySqrt = function (x) {
    let left = 1, right = x;
    while (left <= right) {
        let mid = left + ((right - left) >> 1)
        if (mid * mid <= x) {
            if ((mid + 1) * (mid + 1) > x) {
                return mid;
            }
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return 0;
};

📝104-二叉树的最大深度

题目🌵

📝Leetcode 二叉树的最大深度

✏️https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]
输出：true

解题思路💡

递归

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

迭代

按层搜索 BFS遍历

var maxDepth = function (root) {
    // 迭代法
    if (!root) return 0
    let queue = [] //用数组模拟队列
    let depth = 0 //记录深度
    queue.push(root)
    while (queue.length) {
        const size = queue.length
        for (let i = 0; i < size; i++) {
            const current = queue.shift()//依次推出当前层的所有节点
            if (current.left) {
                queue.push(current.left)
            }
            if (current.right) {
                queue.push(current.right)
            }
        }
        depth += 1
    }
    return depth
};

📝142-环形链表 II

题目🌵

📝Leetcode 环形链表 II

✏️https://leetcode-cn.com/problems/linked-list-cycle-ii/

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

不允许修改链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

解题思路💡

使用`Hash表`记录

跟环形链表1 一样，只不过修改了返回的值

var detectCycle = function (head) {
    let cache = new Set()
    while (head) {
        if (cache.has(head)) {
            return head
        } else {
            cache.add(head)
        }
        head = head.next
    }
    return null
}

进一步优化

**进阶：**你能用 O(1)（即，常量）内存解决此问题吗？

快慢指针
当找到快慢指针相等时，说明链表中存在环
再利用一个指针从头出发，当慢指针和该指针相遇时，此时必然处于环开始的节点

var detectCycle = function (head) {
  // 快慢指针
  let fast = head
  let slow = head
  let start = head
  while (fast && fast.next) {
    slow = slow.next
    fast = fast.next.next
    if (fast === slow) {
      //   return true
      while (slow && start) {
        if (slow === start) {
          return slow
        }
        slow = slow.next
        start = start.next
      }
    }
  }
  return null
}