Leetcode刷题系列1

1. 两数之和
3. 无重复字符的最长子串
7. 整数反转
11. 盛水最多的容器
14. 最长公共前缀
输出: “fl”

1. 两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

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

var twoSum = function(nums, target) {
    const map = {};
    for(let i=0;i<nums.length;i++) {
        let another = target - nums[i];
        if(another in map) {
            return [map[another], i];
        }
        map[nums[i]] = i;
    }
    return null;
};

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

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

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

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int freq[256] = {0};
        int l = 0, r = -1; // sliding window s[l, r]
        int res = 0;
        while(l < s.size()) {
            if(r + 1 < s.size() && freq[s[r + 1]] == 0) {
                freq[s[++r]]++;
            } else {
                freq[s[l++]]--;
            }
            res = max(res, r - l + 1);
        }
        return res;
    }
};

7. 整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

输入: 123 输出: 321 输入: -123 输出: -321 输入: 120 输出: 21

var reverse = function(x) {
  if(typeof x !== 'number') {
      return;
  }
  const MAX = 2147483647;
  const MIN = -2147483648;

  const ret = x > 0 ? 
            String(x).split('').reverse().join(''):
            String(x).slice(1).split('').reverse().join('')

  const result = x > 0 ? parseInt(ret, 10) : 0 - parseInt(ret, 10);
  if(result >= MIN && result <= MAX) {
      return result;
  } 
  return 0;
};

11. 盛水最多的容器

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

输入：[1,8,6,2,5,4,8,3,7] 输出：49

var maxArea = function(height) {
  let max = 0;
  for(let i = 0, j = height.length - 1; i < j;) {
    let minHeight = height[i] < height[j] ? height[i++] : height[j--];
    let area = (j - i + 1) * minHeight;
    max = Math.max(max, area);
  }
  return max;
};

14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。

输入: [“flower”,”flow”,”flight”]

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

var longestCommonPrefix = function(strs) {
  if(strs.length === 0) return "";
  for(let i = 0; i < strs[0].length; i++) {
    let ch = strs[0].charAt(i);
    for(let j = 1; j < strs.length; j++) {
      if(i === strs[j].length || strs[j].charAt(i) !== ch) {
        return strs[0].substring(0, i);
      }
    }
  }
  return strs[0];
};

15. 三数之和

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

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

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

var threeSum = function(nums) {
  nums = nums.sort((a, b) => a - b);
  let res = [];
  let k = 0;
  for(let k = 0; k < nums.length - 2; k++) {
    if(nums[k] > 0) break;
    if(k > 0 && nums[k] == nums[k - 1]) continue;
    let i = k + 1;
    let j = nums.length - 1;
    while(i < j) {
      let n = nums[k] + nums[i] + nums[j];
      if(n < 0) {
        i++;
        while(i < j && nums[i] === nums[i-1]) i++;
      } else if (n > 0) {
        j--;
        while(i < j && nums[j] === nums[j+1]) j--;
      } else {
        res.push([nums[k], nums[i], nums[j]]);
        i += 1;
        j -= 1;
        while(i < j && nums[i] === nums[i-1]) i++;
        while(i < j && nums[j] === nums[j+1]) j--;
      }
    }
  }
  return res;
};

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

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

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

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

var removeNthFromEnd = function(head, n) {
    let len = 0;
    let current = head;
    while(current) {
        len++;
        current = current.next;
    }
    let index = len - n;
    current = head;
    if(index === 0) {
        return current.next;
    }
    for(let i = 0; i < len; i++) {
        if(i === index - 1) {
            current.next = current.next.next;
            return head;
        }else {
            current = current.next;
        }
    }  
};

20. 有效的括号

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

有效字符串需满足：

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

注意空字符串可被认为是有效字符串。

输入: “()” 输出: true

输入: “()[]{}” 输出: true

var isValid = function(s) { 
    if(s.length % 2 === 1) return false;
    let arr = [];
    for(let key of s) {
        if(key === '(' || key === "{" ||key === "[") {
            arr.push(key);
        } else {
            let topChar = arr.pop();
            if(key === ')' && topChar !== '(') {
                return false;
            } else if(key === '}' && topChar !== '{') {
                return false;
            } else if(key === ']' && topChar !== '[') {
                return false;
            }
        }
    }
    return arr.length === 0;
};

21. 合并2个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

var mergeTwoLists = function(l1, l2) {
    if(l1 === null) {
        return l2;
    }
    if(l2 === null) {
        return l1;
    }
    if(l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l2.next, l1);
        return l2;
    }
};

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

输入：n = 3 输出：[ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ]

var generateParenthesis = function(n) {
  let arr = [];
  function generate(left, right, n, s) {
    if(left === n && right === n) {
      arr.push(s);
      return;
    }
    if(left < n) generate(left+1,right,n, s+'(');
    if(left > right && right < n) generate(left,right+1,n, s+')');
  }
  generate(0,0,n,'');
  return arr;
};

26. 删除排序数组中的重复项(Facebook, Microsoft)

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

给定数组 nums = [1,1,2],

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

你不需要考虑数组中超出新长度后面的元素。

var removeDuplicates = function(nums) {
  for(let i = nums.length -1 ; i > 0; i--) {
      if(nums[i] === nums[i-1]) {
          nums.splice(i,1);
      }
  }
  return nums.length;
};

27. 移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

给定 nums = [3,2,2,3], val = 3,

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int count = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != val) {
                nums[count++] = nums[i];
            }
        }
        return count;
    }
};

28. 实现 strStr()实现 strStr() 函数。

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

输入: haystack = “hello”, needle = “ll” 输出: 2

var strStr = function(haystack, needle) {
  const haystackLen = haystack.length;
  const needleLen = needle.length;
  if(needleLen === 0) {
      return 0;
  }
  if(needleLen > haystackLen) {
      return -1;
  }
  if(needleLen === haystackLen) {
      return needle === haystack ? 0 : -1;
  }
  for(let i = 0; i <= haystackLen - needleLen; i++) {
      if(haystack.substring(i, i+needleLen) === needle) {
          return i;
      }
  }
  return -1;
};

48. 旋转图像

给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明：
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

给定 matrix = [ [1,2,3], [4,5,6], [7,8,9] ],

原地旋转输入矩阵，使其变为: [ [7,4,1], [8,5,2], [9,6,3] ]

class Solution {
    public void rotate(int[][] matrix) {
        int vecor = matrix.length;

        for(int i = 0; i < vecor /2 ; i++) {
            for(int j = 0; j < vecor; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[vecor-1-i][j];
                matrix[vecor-1-i][j] = tmp;
            }
        }

        for(int i = 0; i < vecor; i++) {
            for(int j = 0; j < i; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
        }
    }
}

49. 字母异位词分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 输出: [ [“ate”,”eat”,”tea”], [“nat”,”tan”], [“bat”] ]

var groupAnagrams = function(strs) {
    const map = {};
    const arr = [];
    for(let i = 0; i < strs.length; i++) {
        const str = strs[i].split('').sort((a,b) => a.localeCompare(b)).join('');
        if(!map[str]) {
            map[str] = [];
        }
        map[str].push(strs[i]);
    }
    for(let key in map) {
        arr.push(map[key]);
    }
    return arr;
};

50. Pow(x,n)

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

输入: 2.00000, 10 输出: 1024.00000

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

53. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

var maxSubArray = function(nums) {
  let ans = nums[0];
    let sum = 0;
    for(const num of nums) {
        if(sum > 0) {
            sum += num;
        } else {
            sum = num;
        }
        ans = Math.max(ans, sum);
    }
    return ans;
};

62. 不同路径

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？

输入: m = 3, n = 2 输出: 3 解释: 从左上角开始，总共有 3 条路径可以到达右下角。

向右 -> 向右 -> 向下
向右 -> 向下 -> 向右
向下 -> 向右 -> 向右

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

66. 加一

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位，数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。

输入: [1,2,3] 输出: [1,2,4] 解释: 输入数组表示数字 123。

var plusOne = function(digits) {
  return (BigInt(digits.join('')) + 1n).toString().split('')
};

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。

1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶

var climbStairs = function(n) {
    if(n === 0 || n === 1 || n === 2) return n;
    let arr = [1, 2];
    for(let i = 2; i < n; i++) {
        arr[i] = arr[i-1] + arr[i-2];
    }
    return arr[n-1];
};

73. 矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

输入: [ [1,1,1], [1,0,1], [1,1,1] ] 输出: [ [1,0,1], [0,0,0], [1,0,1] ]

var setZeroes = function(matrix) {
    const len = matrix.length;
    const width = matrix[0].length;
    let flag = false;
    for(let i = 0; i < len; i++) {
        if(!matrix[i][0]) {
            flag = true;
        }
        for(let j = 1; j < width; j++) {
            if(!matrix[i][j]) {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }
    for(let i = len - 1; i >= 0; i--) {
        for(let j = width - 1; j > 0; j--) {
            if(!matrix[0][j] || !matrix[i][0]) {
                matrix[i][j] = 0;
            }
        }
        if(flag) {
            matrix[i][0] = 0;
        }
    }
};

75. 颜色分类(Facebook, Microsoft)

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2]

class Solution {
public:
    void sortColors(vector<int>& nums) {
        // 存放每个数的个数,下标对应个数
        int count[3] = {0};
        for(int i = 0; i < nums.size(); i++) {
            count[nums[i]]++;
        }
        int idx = 0;
        for(int i = 0; i < count[0]; i++) {
            nums[idx++] = 0;
        }
        for(int i = 0; i < count[1]; i++) {
            nums[idx++] = 1;
        }
        for(int i = 0; i < count[2]; i++) {
            nums[idx++] = 2;
        }
    }
};

88. 合并有序数组

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3

输出: [1,2,2,3,5,6]

var merge = function(nums1, m, nums2, n) {
    const ret = [];
    let j = 0;
    let k = 0;
    while(j < m && k < n) {
        if(nums1[j] > nums2[k]) {
            ret.push(nums2[k])
            k++;
        } else {
            ret.push(nums1[j]);
            j++;
        }
    }
    if(ret.length < m + n) {
        if(j === m) {
            ret.push(...nums2.slice(k,n));
        } else {
            ret.push(...nums1.slice(j,m));
        }
    } 
    nums1.splice(0, nums1.length);
    nums1.push(...ret);
};

var merge = function(nums1, m, nums2, n) {
    nums1.splice(m,n, ...nums2);
    nums1.sort((a,b) => a-b)
};

94. 二叉树的中序遍历

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

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

输出: [1,3,2]

var inorderTraversal = function(root) {
    let list = []
    let stack = []
    let node = root

    while(node || stack.length) {
    // 遍历左子树
      while(node) {
       stack.push(node)
        node = node.left
      }

      node = stack.pop()
      list.push(node.val)
      node = node.right
    }
    return list
};

var inorderTraversal = function(root) {
  const arr = [];
  function inorder(root) {
    if(root) {      
      inorder(root.left);
      arr.push(root.val);
      inorder(root.right);  
    }
  }
  inorder(root);
  return arr;
};

98. 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
输入:
```
2
```
/ \ 1 3 输出: true

var isValidBST = function(root) {
    const quene = [];
    function dfs(root){
        if (!root){
            return;
        }
        root.left && dfs(root.left);
        quene.push(root.val);
        root.right && dfs(root.right);
    }
    dfs(root)
    for(let i=0; i<quene.length; i++){
        if(quene[i] >= quene[i+1]){
            return false;
        }
    }

    return true;
};

101. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

1
/ \ 2 2 / \ / \ 3 4 4 3

var isSymmetric = function(root) {
    if(!root) {
        return true;
    }
    let isEqual = function(left, right) {
        if(!left && !right) {
            return true;
        }
        if(!left || !right) {
            return false;
        }
        return left.val === right.val 
        && isEqual(left.left, right.right) 
        && isEqual(left.right, right.left);
    }
    return isEqual(root.left, root.right);
};

102. 二叉树的层序遍历

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。（即逐层地，从左到右访问所有节点）。

3
/ \ 9 20 / \ 15 7

遍历结果:

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

var levelOrder = function(root) {
  if (!root) {
    return [];
  }
  const stack = [];
  stack.push(root);
  const result = [];
  while (stack.length > 0) {
    const size = stack.length;
    const temp = [];
    for (let i = 0; i < size; i++) {
      const node = stack.shift();
      temp.push(node.val);
      if (node.left) {
        stack.push(node.left);
      }
      if (node.right) {
        stack.push(node.right);
      }
    }
    result.push(temp);
  }
  return result;
};

let levelOrder = function(root) {
  if(root == null) return;
  let queue = [];
  queue.push(root);
  while(queue.length) {
    let node = queue.shift();
    console.log(node);
    if(node.left) {
      queue.push(node.left);
    }
    if(node.right) {
      queue.push(node.right);
    }
  }
}

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，

3
/ \ 9 20 / \ 15 7

返回它的最大深度 3 。

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

// 非递归解法
const maxDepth = function(root) {
  if(root == null) return 0;
  let height = 0;
  let levelSize = 1;  // 存放每一层的元素数量
  let queue = [];
  queue.push(root);
  while(queue.length) {
    let node = queue.shift();
    levelSize--;
    if(node.left) {
      queue.push(node.left);
    }
    if(node.right) {
      queue.push(node.right);
    }
    if(levelSize == 0) {  // 意味着当前层访问结束，将要访问下一层
      levelSize = queue.length;
      height++;
    }
  }
  return height;
}

111. 二叉树的最小深度

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

122. 买卖股票的最佳时期II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

输入: [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

var maxProfit = function(prices) {
   let totalBouns = 0;
   for(let i = 0; i < prices.length-1; i++) {
       if(prices[i+1] > prices[i]) {
           totalBouns += prices[i+1] - prices[i]
       }
   }
   return totalBouns;
};

125. 验证回文串(facebook, microsoft,uber)

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。

输入: “A man, a plan, a canal: Panama” 输出: true

var isPalindrome = function(s) {
  const ret = s.toLowerCase().replace(/[^A-Z0-9a-z]/g, '').split('');
  let first = 0;
  let last = ret.length - 1;
  while(first < last) {
      if(ret[first] === ret[last]) {
          first++;
          last--;
      } else {
          return false;
      }
  }
  return true;

};

var isPalindrome = function(s) {
  const ret = s.toLowerCase().replace(/[^A-Z0-9a-z]/g, '').split('');
  return ret.join('') === ret.reverse().join('');
};

136. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

输入: [2,2,1] 输出: 1

var singleNumber = function(nums) {
  return nums.reduce((a,c) => a ^ c);
};

141. 环形链表

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

var hasCycle = function(head) {
  if(!head) return false;
  const s = Symbol('');
  while(head) {
    if(head.val === s) return true;
      head.val = s;
      head = head.next;
    }
  return false;
};

var hasCycle = function(head) {
    if(!head) return false;
    const map = new Map();
    while(head) {
        if(map.has(head)) return true;
        map.set(head,1);
        head = head.next;
    }
    return false;
}

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

144. 二叉树的前序遍历

var preorderTraversal = function(root) {
    const list = [];
    const stack = [];

    // 当根节点不为空的时候，将根节点入栈
    if(root) stack.push(root)
    while(stack.length > 0) {
        const curNode = stack.pop()
        // 第一步的时候，先访问的是根节点
        list.push(curNode.val)

        // 我们先打印左子树，然后右子树
        // 所以先加入栈的是右子树，然后左子树
        if(curNode.right !== null) {
            stack.push(curNode.right)
        }
        if(curNode.left !== null) {
            stack.push(curNode.left)
        }
    }
    return list
};

var preorderTraversal = function(root) {
  const arr = [];
  function preOrder(root) {
    if(root) {
      arr.push(root.val);
      preOrder(root.left);
      preOrder(root.right);
    }
  }
  preOrder(root);
  return arr;
};

145. 二叉树的后序遍历

var postorderTraversal = function(root) {
    const list = [];
    const stack = [];

    // 当根节点不为空的时候，将根节点入栈
    if(root) stack.push(root)
    while(stack.length > 0) {
        const node = stack.pop()
        // 根左右=>右左根
        list.unshift(node.val)

        // 先进栈左子树后右子树
        // 出栈的顺序就变更为先右后左
        // 右先头插法入list
        // 左再头插法入list
        // 实现右左根=>左右根
        if(node.left !== null) {
            stack.push(node.left)
        }
        if(node.right !== null) {
            stack.push(node.right)
        }
    }
    return list
};

var postorderTraversal = function(root) {
  const arr = [];
  function postOrder(root) {
    if(root) {      
      postOrder(root.left);
      postOrder(root.right);
      arr.push(root.val);
    }
  }
  postOrder(root);
  return arr;
};

146. LRU缓存机制

var LRUCache = function (capacity) {
  this.max = capacity;
  this.keys = new Set();
  this.cache = new Map();
};

LRUCache.prototype.get = function (key) {
  // => 若当前 key 存在，访问时交换位置到最后（最后的是最近访问的）
  if (this.cache.has(key)) {
    this.keys.delete(key);
    this.keys.add(key);
  }

  return this.cache.get(key) || -1;
};

LRUCache.prototype.put = function (key, value) {
  const cacheKey = this.cache.has(key);

  this.cache.set(key, value);

  // => 为 false 说明是新增的，否则就是已经存在，上一行已经重新赋值。
  // => 这里在 keys 集合里交换位置，和 get 时处理方式一样
  if (cacheKey) {
    this.keys.delete(key);
    this.keys.add(key);
  } else {
    this.keys.add(key);

    // => 当集合的大小超过的设定值
    if (this.keys.size > this.max) {
      // => 拿取第一个元素，分别在 Set 集合和 Map 集合中删除
      // => 最耗时的应该是这里，因为要将集合转换成真正的数组
      const first = Array.from(this.keys)[0];

      this.cache.delete(first);
      this.keys.delete(first);
    }
  }
};

151. 反转字符串里的单词

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

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

var reverseWords = function(s) {
  return s.trim().split(/ +/).reverse().join(' ');
};

160. 相交链表

var getIntersectionNode = function(headA, headB) {
    while(headA) {
        headA.flag = true
        headA = headA.next
    }
    while(headB) {
        if (headB.flag) return headB
        headB = headB.next
    }
    return null
};

167. 两数之和2(amazon)

给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

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

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        assert(numbers.size() >= 2);
        int i = 0;
        int j = numbers.size() - 1;
        while(i < j) {
            if(numbers[i] + numbers[j] == target) {
                int res[2] = { i + 1, j + 1};
                return vector<int>(res, res + 2);
            } else if(numbers[i] + numbers[j] < target) {
                i++;
            } else {
                j--;
            }
        }
        throw invalid_argument("The input has no solution");
    }
};

169. 多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

输入: [3,2,3] 输出: 3

var majorityElement = function (nums) {
  const map = {};
  for (let item of nums) {
    if (!map[item]) {
      map[item] = 1;
    } else {
      map[item] += 1;
    }
  }
  let maxKey = 0;
  let maxValue = 0;
  for (let key in map) {
    if (map[key] > maxValue) {
      maxKey = key;
      maxValue = map[key];
    }
  }
  return maxKey;
};

189. 旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右旋转 1 步: [7,1,2,3,4,5,6] 向右旋转 2 步: [6,7,1,2,3,4,5] 向右旋转 3 步: [5,6,7,1,2,3,4]

// var rotate = function(nums, k) {
//   const len = nums.length;
//   k = k % len;
//   nums = nums.unshift(...nums.splice(len-k, k))
// };

var rotate = function(nums, k) {
  const len = nums.length;
  k = k % len;
  for(let i = 0; i < k; i++) {
      nums.unshift(nums.pop());
  }
};

var rotate = function(nums, k) {
  const len = nums.length;
  k = k % len;
  nums = nums.unshift(...nums.splice(len-k, k))
};

191. 位1的个数

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

输入：00000000000000000000000000001011 输出：3 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 ‘1’。

let hammingWeight = function(n) {
    let count = 0;
    while(n) {
        count++;
        n = n & (n - 1);
    }
    return count;
};

位运算要点

1. 判断奇数偶数
  x%2=1 => x&1=1
  x%2=0 => x&1=0
2. x>>1 => x/2
  mid = (left+right)>>1
3. x = x&(x-1) 清零最低位的1
4. x&-x得到最低位的1
5. x&~x => 0

// 异或相同为0，不同为1
x^0=x
x^1s=~x
x^(~x)=1s
x^x=0
a^b=c => a^c=b, b^c=a //swap
a^b^c=a^(b^c)=(a^b)^c  //associative

x&(~0<<n) 将x最右边的n为置0
(x>>n)&1  获取n的第n位（0或1）
x&(1<<(n-1)) 获取x的第n位的幂值
x|(1<<n) 仅将第n位置1
x&(~(1<<n)) 仅将第n位置0
x&((1<<n)-1)  将x最高位至第n位（含）置0
x&(~((1<<(n+1))-1)) 将第n位至第0位（含）置0

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

var rob = function(nums) {
    if(nums.length === 0) {
        return 0;
    }
    if(nums.length === 1) {
        return nums[0];
    }
    const memo = [nums[0], Math.max(nums[0], nums[1])];
    for(let i = 2; i < nums.length; i++) {
        memo[i] = Math.max(nums[i] + memo[i-2], memo[i-1]);
    }
    return memo[nums.length-1];
};

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

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

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int l = 0, r = -1;  // nums[l,r]为滑动窗口
        int sum = 0;
        int res = nums.size() + 1;
        while(l < nums.size()) {
            if(r + 1 < nums.size() && sum < s) {
                sum += nums[++r];
            } else {
                sum -= nums[l++];
            }
            if(sum >= s) {
                res = min(res , r - l + 1);
            }
        }
        if(res == nums.size() + 1)
            return 0;
        return res;
    }
};

215. 数组第K大的值(Facebook, Microsoft, amazon, apple)

输入: [3,2,1,5,6,4] 和 k = 2 输出: 5

function maxK(arr, k) {
  for (let i = 0; i < k; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        var temp = arr[j];
              arr[j] = arr[j+1];
              arr[j+1] = temp;
      }
    }
  }
  return arr[arr.length - k];
}

217. 存在重复元素

给定一个整数数组，判断是否存在重复元素。
如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

输入: [1,2,3,1] 输出: true

var containsDuplicate = function(nums) {
  return nums.length !== Array.from(new Set(nums)).length;
};

226. 翻转二叉树

 4
/ \ 2 7 / \ / \ 1 3 6 9

结果:

 4
/ \ 7 2 / \ / \ 9 6 3 1

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

231. 2的幂

输入: 1 输出: true 解释: 2 = 1

var isPowerOfTwo = function(n) {
    return n > 0 && !(n & (n - 1));
};

234. 回文链表

var isPalindrome = function(head) {
    let positive = '';
    let negative = '';
    while(head) {
        let v = head.val;
        positive += v;
        negative = v + negative;
        head = head.next;
    }
    return positive === negative;
};

235. 二叉搜索树的最近公共祖先

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

var lowestCommonAncestor = function(root, p, q) {
  if(root.val > p.val && root.val > q.val) {
    return lowestCommonAncestor(root.left, p, q);
  }
  if(root.val < p.val && root.val < q.val) {
    return lowestCommonAncestor(root.right, p, q);
  }
  return root;
};

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

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

237. 删除链表中的节点

输入: head = [4,5,1,9], node = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

// var deleteNode = function(node) {
//    node.val = node.next.val;
//    node.next = node.next.next; 
// };

var deleteNode = function(node) {
   Object.assign(node, node.next); 
};

var deleteNode = function(node) {
   node.val = node.next.val;
   node.next = node.next.next; 
};

242. 有效的字母异位词

输入: s = “anagram”, t = “nagaram” 输出: true

var isAnagram = function(s, t) {
    if(s.length !== t.length) {
        return false;
    }
    const sMap = {};
    const tMap = {};
    for(let item of s) {
        if(sMap[item]) {
            sMap[item]++;
        } else {
            sMap[item] = 1;
        }
    }
    for(let item of t) {
        if(tMap[item]) {
            tMap[item]++;
        } else {
            tMap[item] = 1;
        }
    }
    for(let item in sMap) {
        if(!tMap[item] || sMap[item] !== tMap[item]) {
            return false;
        }
    }
    return true;
};

// var isAnagram = function(s, t) {
//   const retS = s.split('').sort((a,b) => a.charCodeAt() - b.charCodeAt());
//   const retT = t.split('').sort((a,b) => a.charCodeAt() - b.charCodeAt());
//   return retS.join('') === retT.join('');
// };

268. 缺失数字

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

输入: [3,0,1] 输出: 2

var missingNumber = function(nums) {
    let len = nums.length;
    let obj = {}
    nums.map((item)=>{
        obj[item] = item
    })
    let result = null;
    for(let i = 0 ; i < len ; i++){
        if(obj[i] == undefined){
            result = i
        }
    }
    if(result == null){
        result= len
    }
    return result
};

283. 移动0

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

var moveZeroes = function(nums) {
    let j = 0;
    for(let i = 0; i < nums.length; i++) {
        if(nums[i] !== 0) {
            nums[j] = nums[i];
            j++;
        }
    }
    nums.fill(0,j,nums.length);
};

var moveZeroes = function(nums) {
    for(let i = nums.length - 1; i >= 0; i--) {
        if(nums[i] === 0) {
            nums.splice(i,1);
            nums.push(0);
        }
    }
};

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        vector<int> noZeroElements;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i])
                noZeroElements.push_back(nums[i]);
        }
        for (int i = 0; i < noZeroElements.size(); i++)
            nums[i] = noZeroElements[i];
        for (int i = noZeroElements.size(); i < nums.size(); i++) {
            nums[i] = 0;
        }
    }
};

class Solution {
public:

    void swap(vector<int>& nums, int k, int i) {
        int tmp = nums[k];
        nums[k] = nums[i];
        nums[i] = tmp;
    }

    void moveZeroes(vector<int>& nums) {
        int k = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i])
                if (i != k)
                    swap(nums, k++, i);
                else
                    k++;
        }
    }
};

344. 反转字符串

输入：[“h”,”e”,”l”,”l”,”o”] 输出：[“o”,”l”,”l”,”e”,”h”]

var reverseString = function(s) {
  const len = s.length;
  for(let i = 0; i < len / 2; i++) {
      [s[i], s[len - i - 1]] = [s[len - i -1], s[i]];
  }
  return s;
};

345. 反转字符串中的原音字母(google)

输入：“hello” 输出：“holle”

class Solution {
public:
    string reverseVowels(string s) {
        int i = 0, j = s.size() - 1;
        while (i < j) {
            i = s.find_first_of("aeiouAEIOU", i);
            j = s.find_last_of("aeiouAEIOU", j);
            if (i < j) {
                swap(s[i++], s[j--]);
            }
        }
        return s;
    }
};

349. 2个数组的交集

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

var intersection = function(nums1, nums2) {
 const arr = new Set();
 const nums2Set = new Set(nums2);
 for(let key of nums1) {
     if(nums2Set.has(key)) {
         arr.add(key);
     }
 }
 return Array.from(arr);
};

387. 字符串中的第一个唯一字符

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

s = “leetcode” 返回 0

s = “loveleetcode” 返回 2

var firstUniqChar = function(s) {
  let map = new Map();
  for(let k of s) {
    if(!map.has(k)) {
      map.set(k,1);
    } else {
      map.set(k, map.get(k) + 1);
    }
  }
  for(let i = 0; i < s.length; i++) {
    if(map.get(s.charAt(i)) === 1) {
      return i;
    }
  }
  return -1;
};

459. 重复的子字符串

输入: “abab”

输出: True

解释: 可由子字符串 “ab” 重复两次构成。

var repeatedSubstringPattern = function(s) {
    return /^(\w+)\1+$/.test(s);
};

557. 反转字符串中的单词III

输入: “Let’s take LeetCode contest” 输出: “s’teL ekat edoCteeL tsetnoc”

var reverseWords = function(s) {
    return s.split(' ').map(item => {
        return item.split('').reverse().join('');
    }).join(' ');
};

876. 链表的中间结点

var middleNode = function(head) {
    let fast = head, slow = head
    while(fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
    }
    return slow
};

914. 卡牌分组

给定一副牌，每张牌上都写着一个整数。

此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：

每组都有 X 张牌。
组内所有的牌上都写着相同的整数。
仅当你可选的 X >= 2 时返回 true。

输入：[1,2,3,4,4,3,2,1] 输出：true 解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]

var hasGroupsSizeX = function(deck) {
    let group = []
  let tmp = {}
  deck.forEach(item => {
    tmp[item] = tmp[item] ? tmp[item] + 1 : 1
  })
  for (let v of Object.values(tmp)) {
    group.push(v)
  }
  // 此时group已经存放的是每张牌的总数了（数组只遍历一遍，避免了排序和正则的耗时）
  // 求两个数的最大公约数
  let gcd = (a, b) => {
    if (b === 0) {
      return a
    } else {
      return gcd(b, a % b)
    }
  }
  while (group.length > 1) {
    let a = group.shift()
    let b = group.shift()
    let v = gcd(a, b)
    if (v === 1) {
      return false
    } else {
      group.unshift(v)
    }
  }
  return group.length ? group[0] > 1 : false
};

1185. 一周中的第几天

给你一个日期，请你设计一个算法来判断它是对应一周中的哪一天。

输入为三个整数：day、month 和 year，分别表示日、月、年。

您返回的结果必须是这几个值中的一个 {“Sunday”, “Monday”, “Tuesday”, “Wednesday”, “Thursday”, “Friday”, “Saturday”}。

输入：day = 31, month = 8, year = 2019 输出：“Saturday”

var dayOfTheWeek = function(day, month, year) {
    const date = new Date(Date.parse(`${year}/${month}/${day}`));
    const week = ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"];
    return week[date.getDay()]
};