整理了一些平时看到的算法题，以及部分真题。平时积累提升自己的思维能力，面试前也方便自己复习。

• 这里还有一篇面经
• leetcode 刷题之旅

1. 两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

• 给定 nums = [2, 7, 11, 15], target = 9
• 因为 nums[0] + nums[1] = 2 + 7 = 9
• 所以返回 [0, 1]

// 解法1
const twoSum = (nums, target) => {
  let nextIdx
  const idx = nums.findIndex((item, index) => {
    nextIdx = nums.indexOf(target - item)
    return nextIdx !== -1 && index !== nextIdx
  })
  return idx == -1 ? [] : [idx, nextIdx]
}

// 解法2
const twoSum = (nums, target) => {
  let map = new Map()
  for (let i = 0; i < nums.length; i++) {
    let x = target - nums[i]
    if (map.has(x)) return [map.get(x), i]
    map.set(nums[i], i)
  }
  return []
}

// 解法3
const twoSum = (nums, target) => {
  let map = {}
  for (let i = 0; i < nums.length; i++) {
    let x = target - nums[i]
    if (map[x] !== undefined) return [map[x], i]
    map[nums[i]] = i
  }
  return []
}

// 测试用例: twoSum([12, 8, 1, 11], 9) => [1, 2]

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

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例1:

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。

/**
 * @param {string} s
 * @return {number}
 */
const lengthOfLongestSubstring = s => {
  let map = new Map() // 记录每个字符的下标，key是字符，val是下标
  let startIndex = -1 // 记录最长字符串的开始下标
  let max = 0 // 最长字符串个数
  for (let i in s) {
    if (map.has(s[i])) {
      startIndex = Math.max(map.get(s[i]), startIndex)
    }
    max = Math.max(max, i - startIndex)
    map.set(s[i], i)
  }
  return max
}

14. 最长公共前缀

示例1:

输入: ["flower","flow","flight"]
输出: "fl"

示例2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

const longestCommonPrefix = strs => {
  if (strs.length == 0) return ''
  let maxCommonStr = strs[0]
  for (let i = 1; i < strs.length; i++) {
    let j = 0
    for (j; j < strs[i].length; j++) {
      if (strs[i][j] !== maxCommonStr[j]) break
    }
    maxCommonStr = maxCommonStr.substr(0, j)
  }
  return maxCommonStr
}

15. 三数之和

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

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

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[[-1, 0, 1], [-1, -1, 2]]

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const threeSum = nums => {
  nums.sort((a, b) => a - b) // 递增排序
  let res = []
  // 因为排序完了，如果全部正数或者负数，则不存在结果，返回
  if (nums[0] * nums[nums.length - 1] > 0) return res
  for (let i = 0; i < nums.length; i++) {
    // 因为排序完了，所以如果出现连续两个相同的数，就跳过
    if (i > 0 && nums[i] == nums[i - 1]) continue
    let lp = i + 1 // 初始化左指针
    let rp = nums.length - 1 // 初始化右指针
    while (lp < rp) {
      // 找到目标，插入结果队列
      if (nums[i] + nums[lp] + nums[rp] == 0) {
        res.push([nums[i], nums[lp], nums[rp]])
        lp++ // 左指针递增
        rp-- // 右指针递减
        // 如果递增/递减后的指针元素和刚刚的一样，那么跳过
        while (lp < rp && nums[lp] == nums[lp - 1]) lp++
        while (lp < rp && nums[rp] == nums[rp + 1]) rp--
      }
      // 找不到目标，如果相加大于0，表示需要小一点的结果，右指针递减
      // 如果结果小于0，表示需要大一点的结果，左指针递增
      if (nums[i] + nums[lp] + nums[rp] > 0) rp--
      if (nums[i] + nums[lp] + nums[rp] < 0) lp++
    }
  }
  return res
}

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

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

const removeNthFromEnd = (head, n) => {
  // 假设输入的链表为 1-2-3-4-5
  let preHead = new ListNode(0) // 初始化一个只有一个节点的链表，作为目标链表的虚拟头部
  preHead.next = head // 将输入的链表和新链表连起来 0-1-2-3-4-5
  let slow = preHead // 慢指针
  let fast = preHead // 快指针
  // 让快指针 j 先走 n 步
  // 0-1-2-3-4-5
  // |   |
  // s   f
  while (n) {
    fast = fast.next
    n--
  }
  // 快慢指针同时走，直到快指针到尽头，即 fast.next 不存在
  // 0-1-2-3-4-5
  //       |   |
  //       s   f
  while (fast.next) {
    slow = slow.next
    fast = fast.next
  }
  // 此时 fast 走到了最后一个节点，slow 是需要删除节点的前一节点
  // 删除节点，返回剩余节点
  slow.next = slow.next.next // 0-1-2-3-5
  return preHead.next // 1-2-3-5
}

20. 有效的括号

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

/**
 * @param {string} s
 * @return {boolean}
 */
const isValid = s => {
  // 思路就是用栈，匹配的左右括号相加为 0
  // 遇到左括号入栈，遇到右括号就弹出栈顶
  // 如果两者相加不为0，return false
  // 如果遍历完栈长度大于0，意味着左右括号不对称，return false
  // 其他情况return true
  let map = {
    '(': 1,
    ')': -1,
    '{': 2,
    '}': -2,
    '[': 3,
    ']': -3
  }
  let stack = []
  for (let i in s) {
    if (map[s[i]] > 0) {
      stack.push(s[i])
    } else {
      const target = stack.pop()
      if (map[target] + map[s[i]] !== 0) return false
    }
  }
  if (stack.length > 0) return false
  return true
}

94. 二叉树的中序遍历

给定一个二叉树，返回它的中序遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
const inorderTraversal = function(root) {
  return root ? [...inorderTraversal(root.left), root.val, ...inorderTraversal(root.right)] : []
}

104. 二叉树的最大深度

/**
 * @param {TreeNode} root
 * @return {number}
 */
const maxDepth = root => {
  if (!root) {
    return 0
  } else {
    const left = maxDepth(root.left)
    const right = maxDepth(root.right)
    return Math.max(left, right) + 1
  }
}

107. 二叉树的层次遍历

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：
给定二叉树 [3,9,20,null,null,15,7],

     3  
    / \  
   9  20  
     /  \  
    15   7  

返回其自底向上的层次遍历为：

[
  [15,7],
  [9,20],
  [3]
]

const levelOrderBottom = root => {
  let res = []
  const dfs = (node, depth) => {
    if (!node) return
    res[depth] ? res[depth].push(node.val) : (res[depth] = [node.val])
    dfs(node.left, depth + 1)
    dfs(node.right, depth + 1)
  }
  dfs(root, 0)
  return res.reverse()
}

112. 路径总和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

const hasPathSum = (root, sum) => {
  if (!root) return false
  if (root.left === null && root.right === null) return root.val === sum
  sum = sum - root.val
  return hasPathSum(root.left, sum) || hasPathSum(root.right, sum)
}

144. 二叉树的先序遍历

给定一个二叉树，返回它的先序遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,2,3]

const preorderTraversal = root => {
  return root ? [root.val, ...preorderTraversal(root.left), ...preorderTraversal(root.right)] : []
}

145. 二叉树的后序遍历

给定一个二叉树，返回它的后序遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [3,2,1]

const postorderTraversal = root => {
  return root ? [...postorderTraversal(root.left), ...postorderTraversal(root.right), root.val] : []
}

151. 翻转字符串里的单词

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：

输入: "the sky is blue"
输出: "blue is sky the"

示例 2：

输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

/**
 * @param {string} s
 * @return {string}
 */
const reverseWords = function(s) {
  let arr = s
    .split(' ')
    .filter(item => item.length)
    .reverse()
    .join(' ')
  return arr
}

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

示例:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

/**
 * initialize your data structure here.
 */
let MinStack = function() {
  this.stack = []
}

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

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
  return this.stack.pop()
}

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
  return this.stack[this.stack.length - 1]
}

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
  return Math.min(...this.stack)
}

/**
 * Your MinStack object will be instantiated and called as such:
 * let obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * let param_3 = obj.top()
 * let param_4 = obj.getMin()
 */

160. 相交链表

编写一个程序，找到两个单链表相交的起始节点。

// 解法一: 标记法
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
const getIntersectionNode = (headA, headB) => {
  while (headA) {
    headA.temp = 1
    headA = headA.next
  }
  while (headB) {
    if (headB.temp) return headB
    headB = headB.next
  }
}

// 解法二: 变轨链法
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
const getIntersectionNode = (headA, headB) => {
  let pA = headA
  let pB = headB
  while (pA !== pB) {
    pA = pA ? pA.next : headB
    pB = pB ? pB.next : headA
  }
  return pA
}

236. 二叉树的最近公共祖先

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
const lowestCommonAncestor = (root, p, q) => {
  if (!root || root == p || root == q) return root
  let left = lowestCommonAncestor(root.left, p, q)
  let right = lowestCommonAncestor(root.right, p, q)
  if (left && right) return root
  return left ? left : right
}

349. 两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。

示例 1：

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

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]

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

567. 字符串的排列

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例1:

输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function(s1, s2) {
    let lp = 0
    let rp = 0
    let needs = {}
    let windows = {}
    let match = 0

    for(let i in s1) {
        needs[s1[i]] ? needs[s1[i]]++ : (needs[s1[i]] = 1)
    }

    while(rp < s2.length) {
        if(needs[s2[rp]]) {
            windows[s2[rp]] ? windows[s2[rp]]++ : (windows[s2[rp]] = 1)
            if(windows[s2[rp]] === needs[s2[rp]]) match++
        }
        rp++
        while(match === Object.keys(needs).length) {
            if(rp - lp === s1.length) return true
            if(needs[s2[lp]]) {
                windows[s2[lp]]--
                if(windows[s2[lp]] < needs[s2[lp]]) match--
            }
            lp++
        }
    }

    return false
};