其他

lc31. 下一个排列中等hot

题目描述

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

• 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

• 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
• 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
• 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

必须** 原地 (opens new window)**修改，只允许使用额外常数空间。

示例 1：

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

示例 2：

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

示例 3：

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

思路

• 先倒序找到在i后面比nums[i]大的数
• 再找到比cur大一点点的数 两者交换
• 因为i后面是倒叙的 若让他尽可能的小，转成升序

var nextPermutation = function(nums) {
  for(let i = nums.length; i >= 0; i--) {
    let cur = nums[i]
    // 找到在i后面比nums[i]大的数
    if(cur < nums[i + 1]){
      let idx = i
      // 找出后面比cur大的数当中的最小值，因为后面是降序排列所以一直判断是否比cur大即可
      while(nums[idx + 1] > cur) idx++
      // 替换
      nums[i] = nums[idx]
      nums[idx] = cur
      // 此时后面是降序的 将它转变为升序的
      let left = i + 1, right = nums.length - 1
      while(left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]]
        left++
        right--
      }
      break
    } else if(i === 0) nums.reverse()
  }
};

时间复杂度:O(n),最多两次扫描序列，以及一次反转操作

空间复杂度:O(1)

lc130. 被围绕的区域中等

题目描述

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

示例 1：

输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

示例 2：

输入：board = [["X"]]
输出：[["X"]]

思路：DFS

类似的先对四个边做判断并标记为A，再次进行遍历，如果是A说明是边界情况，那么还原为O

var solve = function (board) {
  let rows = board.length;
  if (rows == 0) return;
  let cols = board[0].length;
  const dfs = (i, j, board) => {
      if (i < 0 || j < 0 || i >= rows || j >= cols || board[i][j] !== 'O') {
          return;
      } 
      // 判断边界的o是否与内部的o是连接的，连接则不能构成岛屿
      board[i][j] = 'A';
      dfs(i + 1, j, board);
      dfs(i - 1, j, board)
      dfs(i, j + 1, board)
      dfs(i, j - 1, board)
  }

  for (let i = 0; i < rows; i++) {
      dfs(i, 0, board);
      dfs(i, cols - 1, board);
  }
  for (let i = 1; i < cols - 1; i++) {
      dfs(0, i, board);
      dfs(rows - 1, i, board);
  }
  for (let i = 0; i < rows; i++) {
      for (let j = 0; j < cols; j++) {
          if (board[i][j] == 'A') {
              board[i][j] = 'O'
          } else if (board[i][j] == 'O') {
              board[i][j] = 'X'
          }
      }
  }

};

时间复杂度:O(n * m)

空间复杂度:O(n * m)

lc200. 岛屿数量中等hot

题目描述

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

思路

就是两层循环，如果出现1，就递归遍历上下左右，如果有1就置为0，方便计数

var numIslands = function(grid) {
  let count = 0
  grid.forEach((item, idx) => {
    item.forEach((item2, idx2) => {
      if(item2 === '1') {
        count++
        turnZreo(idx, idx2)
      }
    })
  })
  function turnZreo(row, col) {
    // up
    if(grid[row - 1] && grid[row - 1][col] === '1') {
      grid[row - 1][col] = '0'
      turnZreo(row - 1, col)
    }
    // down
    if(grid[row + 1] && grid[row + 1][col] ==='1') {
      grid[row + 1][col] = '0'
      turnZreo(row + 1, col)
    }
    // left
    if(grid[row][col - 1] && grid[row][col - 1] ==='1') {
      grid[row][col - 1] = '0'
      turnZreo(row, col - 1)
    }
    // right
    if(grid[row][col + 1] && grid[row][col + 1] ==='1') {
      grid[row][col + 1] = '0'
      turnZreo(row, col + 1)
    }
  }
  return count
};

时间复杂度:O(mn)

空间复杂度:O(mn) 最坏全是陆地

695. 岛屿的最大面积中等hot

题目描述

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例 1：

输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6
解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。

示例 2：

输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0

dfs

找到1，然后向上下左右发散

var maxAreaOfIsland = function(grid) {
  let max = 0
  for(let i = 0; i < grid.length; i++) {
    for(let j = 0; j < grid[0].length; j++) {
      if(grid[i][j] == 1) {
        max = Math.max(max, cntArea(grid, i, j, grid.length, grid[0].length))
      }
    }
  }
  return max
};

function cntArea(grid, i, j, x, y) {
  if(i < 0 || i >= x || j < 0 || j >= y || grid[i][j] == 0) return 0

  let cnt = 1
  grid[i][j] = 0
  cnt += cntArea(grid, i - 1, j, x, y)
  cnt += cntArea(grid, i + 1, j, x, y)
  cnt += cntArea(grid, i, j - 1, x, y)
  cnt += cntArea(grid, i, j + 1, x, y)
  return cnt
}

时间复杂度:O(mn)

空间复杂度:O(mn)

bfs

var maxAreaOfIsland = function(grid) {
  let maxIsland = 0
  let row = grid.length, col = grid[0].length
  for(let i = 0; i < row; i++){
    for(let j = 0; j < col; j++){
      //对于海洋板块直接跳过
      if(grid[i][j] === 0) continue
      //bfs的解题模板，建立bfs栈以及始点
      let bfs = [[i, j]]
      let cntIsland = 0
      //bfs栈不断弹出，直至全部遍历完成
      while(bfs.length){
        let [x, y] = bfs.shift()
        //边界条件
        if(x < 0 || x >= row || y < 0 || y >= col || grid[x][y] === 0) continue
        cntIsland++
        grid[x][y] = 0
        //向上下左右bfs遍历，向栈中加入符合条件的元素（岛屿）
        bfs.push([x - 1, y])
        bfs.push([x + 1, y])
        bfs.push([x, y - 1])
        bfs.push([x, y + 1])
      }
      maxIsland = Math.max(maxIsland, cntIsland)
    }
  }
  return maxIsland
}

时间复杂度:O(mn)

空间复杂度:O(mn)

lc26. 删除有序数组的重复项简单

题目描述

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

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

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1：

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

示例 2：

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

思路：

设置一个变量len，作用是标注每次处理nums数组后共有几个不重复的数字

因为是有序数组，所以nums数组遇到相同的跳过，找到后一个不相同的，然后把不相同的赋值给len 然后len++

var removeDuplicates = function(nums) {
  let len = 1
  for(let i = 1; i < nums.length; i++) {
    if(nums[i] === nums[i - 1]) {
      continue
    }
    nums[len++] = nums[i]
  }
  return len
};

lc384. 打乱数组

题目描述

给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。打乱后，数组的所有排列应该是 等可能 的。

实现 Solution class:

• Solution(int[] nums) 使用整数数组 nums 初始化对象
• int[] reset() 重设数组到它的初始状态并返回
• int[] shuffle() 返回数组随机打乱后的结果

示例 1：

输入
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
输出
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

解释
Solution solution = new Solution([1, 2, 3]);
solution.shuffle();    // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如，返回 [3, 1, 2]
solution.reset();      // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]
solution.shuffle();    // 随机返回数组 [1, 2, 3] 打乱后的结果。例如，返回 [1, 3, 2]

洗牌算法

var Solution = function(nums) {
  this.nums = nums
};

/**
 * @return {number[]}
 */
Solution.prototype.reset = function() {
  return this.nums
};

/**
 * @return {number[]}
 */
Solution.prototype.shuffle = function() {
  const res = [...this.nums]
  for(let i = 0; i < res.length; i++) {
    let index = Math.floor((i + 1)* Math.random());
    [res[index],res[i]] = [res[i],res[index]]
  }
  return res
};

lc134. 加油站中等

题目描述

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

说明:

• 如果题目有解，该答案即为唯一答案。
• 输入数组均为非空数组，且长度相同。
• 输入数组中的元素均为非负数。

示例 1:

输入: 
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]

输出: 3

解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

示例 2:

输入: 
gas  = [2,3,4]
cost = [3,4,3]

输出: -1

解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

思路

1. 计算总剩余量
2. 找出总剩余量最低点

如果最低点的后面一个加油站都不能满足绕一圈的话，那就没有加油站可以满足了

var canCompleteCircuit = function(gas, cost) {
    const n = gas.length
    let innage = 0 // 剩余总量
    let minInnage = Number.MAX_VALUE // 剩余油量最低点
    let ret = 0
    for(let i = 0; i < n; i++){
        innage += gas[i] - cost[i]
        if(innage < minInnage){
            minInnage = innage
            ret = (i + 1) % n // 最低点的下一个点 就是最合适的出发点
        }
    }
    return innage < 0 ? -1 : ret 
};

lc146. LRU 缓存中等top

题目描述

请你设计并实现一个满足 LRU (最近最少使用) 缓存 (opens new window) 约束的数据结构。

实现 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) 的平均时间复杂度运行。

示例：

输入
["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

var LRUCache = function(capacity) {
  this.map = new Map()
  this.capacity = capacity
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
  if(this.map.has(key)) {
    let temp=this.map.get(key)
    this.map.delete(key);
    this.map.set(key, temp);
    return temp
  } 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)
 */

lc54. 螺旋矩阵中等hot

题目描述

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

思路

var spiralOrder = function (matrix) {
  const arr = [];
  let left = 0,
    top = 0;
  let right = matrix[0].length - 1,
    down = matrix.length - 1;

  while (true) {
    for (let i = left; i <= right; i++) {
      arr.push(matrix[top][i]);
    }
    top++;
    if (top > down) break;
    for (let i = top; i <= down; i++) {
      arr.push(matrix[i][right]);
    }
    right--;
    if (left > right) break;
    for (let i = right; i >= left; i--) {
      arr.push(matrix[down][i]);
    }
    down--;
    if (top > down) break;
    for (let i = down; i >= top; i--) {
      arr.push(matrix[i][left]);
    }
    left++;
    if (left > right) break;
  }
  return arr;
};

lc59. 螺旋矩阵 II中等

题目描述

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

输入：n = 1
输出：[[1]]

思路

跟上题一毛一样

var generateMatrix = function(n) {
  let left = 0, top = 0
  let right = n - 1, down = n - 1
  let cur = 1
  const res = new Array()
  for(let i = 0; i < n; i++) {
    res[i] = new Array()
  }

  while(true) {
    for(let i = left; i <= right; i++) {
      res[top][i] = cur
      cur++
    }
    top++

    if(top > down) break
    for(let i = top; i <= down; i++) {
      res[i][right] = cur
      cur++
    }
    right--

    if(right < left) break
    for(let i = right; i >= left; i--) {
      res[down][i] = cur
      cur++
    }
    down--

    if(down < top) break
    for(let i = down; i >= top; i--) {
      res[i][left] = cur
      cur++
    }
    left++

    if(left > right) break
  }
  return res
};

lc189. 轮转数组中等

题目描述

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [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]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

思路

unshift加pop

var rotate = function (nums, k) {
	if (k >= 0) {
		for (let i = 0; i < k; i++) {
			let last = nums[nums.length - 1];
			nums.pop();
			nums.unshift(last);
		}
	}
};

时间复杂度:O(nk) unshift 时间复杂度为O(n),最外层k层循环

空间复杂度:O(1)

leetcode会超时

思路二

两次splice

var rotate = function(nums, k) {
  k = k % nums.length

  nums.splice(0, 0, ...nums.splice(nums.length - k, k))
};

时间复杂度:O(n) splice时间复杂度为O(n)

空间复杂度:O(1)

lc36. 有效的数独中等

题目描述

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

• 一个有效的数独（部分已被填充）不一定是可解的。
• 只需要根据以上规则，验证已经填入的数字是否有效即可。
• 空白格用 '.' 表示。

示例 1：

输入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true

示例 2：

输入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

思路

就是判断3x3里面有没有重复的数字 && 每一行有没有重复数字 && 每一列有没有重复数字

var isValidSudoku = function(board) {
  for(let i = 0; i < 9; i++) {
    if(!verify(board[i])) return false
    if(!verify(getCol(board, i))) return false
    for(let j = 0; j < 9; j++) {
      if(i % 3 === 0 && j % 3 === 0 && !verify(get3x3(board, i, j))) return false
    }
  }
  return true
};

function getCol(nums, index) {
  const res = []
  for(let i = 0; i < nums.length; i++) {
    res.push(nums[i][index])
  }
  return res
}

function get3x3(nums, row, col) {
  const res = []
  for(let i = row; i < row + 3; i++) {
    for(let j = col; j < col + 3; j++) {
      res.push(nums[i][j])
    }
  }
  return res
}

function verify(nums) {
  const validateMap = new Map()
  const isExist = (map, item) => {
    if(map.has(item) && map.get(item) !== '.') return false
    else {
      map.set(item, item) 
      return true
    } 
  }
  return nums.every(num => isExist(validateMap, num))
}

lc48. 旋转图像中等hot

题目描述

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 (opens new window) 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

思路

首先输入

1 2 3
4 5 6
7 8 9

通过交换matrix[i][j], matrix[j][i] 得到

1 4 7
2 5 8
3 6 9

最后将得到每组数组倒序排列即可

7 4 1
8 5 2
9 6 3

var rotate = function(matrix) {
  for(let i = 0; i < matrix.length; i++) {
    for(let j = i; j < matrix.length; j++) {
      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]]
    }
  }
  return matrix.map(item => item.reverse())
};

lc73. 矩阵置零中等

题目描述

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

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

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

思路

暴力法，用时间换空间

var setZeroes = function(matrix) {
  const temp = []
  for(let i = 0; i < matrix.length; i++) {
    for(let j = 0; j < matrix[0].length; j++) {
      if(matrix[i][j] === 0) temp.push([i, j])
    }
  }

  for(let i = 0; i < temp.length; i++) {
    for(let j = 0; j < matrix.length; j++) {
      if(temp[i][0] === j) matrix[j].fill(0)
      else matrix[j][temp[i][1]] = 0
    }
  }
};

lc179. 最大数中等hot

题目描述

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意： 输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例 1：

输入：nums = [10,2]
输出："210"

示例 2：

输入：nums = [3,30,34,5,9]
输出："9534330"

示例 3：

输入：nums = [1]
输出："1"

示例 4：

输入：nums = [10]
输出："10"

思路:sort

var largestNumber = function(nums) {
  nums = nums.map(item => String(item))

  nums.sort((a, b) => {
    let res1 = a + b
    let res2 = b + a
    return res2 - res1
  })
  if(nums[0] === '0') return '0'
  return nums.join('')
};

快排

var largestNumber = function (nums) {
  quickSort(nums, 0, nums.length - 1);
  return nums[0] == "0" ? "0" : nums.join("");
};
function quickSort(nums, start, end) {
  if (start >= end) return;
  var index = start;
  var pivot = nums[start];
  for (let i = start + 1; i <= end; i++) {
    if (nums[i] + "" + pivot > pivot + "" + nums[i]) {
      index++;
      swap(nums, index, i);
    }
  }
  swap(nums, index, start);
  quickSort(nums, start, index - 1);
  quickSort(nums, index + 1, end);
}
function swap(nums, l, r) {
  var temp = nums[l];
  nums[l] = nums[r];
  nums[r] = temp;
}

lc169. 多数元素/超过一半的数字简单hot

题目描述

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

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

示例 2：

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

思路一

用map计数

var majorityElement = function(nums) {
  let map = new Map()
  let count = Math.ceil(nums.length / 2)
  for(let i = 0; i < nums.length; i++) {
    if(!map.has(nums[i])) map.set(nums[i], 1)
    else {
      map.set(nums[i], map.get(nums[i]) + 1)
    }
  }
  for(let [key, val] of map) {
    if(val >= count) return key
  }
};

时间复杂度:O(n)

空间复杂度:O(n)

思路二：摩尔投票法

声明一个变量vote,因为超过半数这种特殊性我们可以遍历数组

• 令vote等于1，final等于第一个值nums[i]
  • 如果nums[i] === nums[i + 1]，vote加一，final不变
  • 如果后面的值不相等，vote减一
• 如果是vote减为0了，他会等于再下一个值 nums[i + 2] vote重新置为1

这是因为超过半数的数字一定会把剩下数字给抵消掉的

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

时间复杂度:O(n)

空间复杂度:O(1)

思路三：排序后的中位数

同样也是因为超过半数的特殊性，使得排序后的众数一定占据了中位数

var majorityElement = function(nums) {
    nums.sort((a,b)=>a-b);
    return nums[Math.floor(nums.length/2)];
};

时间复杂度:O(nlogn)

空间复杂度:O(1ogn)

lc238. 除自身以外数组的乘积中等

题目描述

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请**不要使用除法，**且在 O(*n*) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

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

var productExceptSelf = function (nums) {
  let res = [];
  let prod = 1;
  for (let i = 0; i < nums.length; i++) {
    res[i] = prod;
    prod *= nums[i];
  }

  prod = 1;
  for (let i = nums.length - 1; i > -1; i--) {
    res[i] *= prod;
    prod *= nums[i];
  }

  return res;
};

lc289. 生命游戏中等

题目描述

根据 百度百科 (opens new window) ， 生命游戏 ，简称为 生命 ，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

1. 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
2. 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
3. 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
4. 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；

下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。

示例 1：

输入：board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
输出：[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

示例 2：

输入：board = [[1,1],[1,0]]
输出：[[1,1],[1,1]]

思路一：额外空间

这个题目有一个坑，某一轮更改的数字的周围的个数的计数是按照最初的数组计算，而不是按照上一轮的计算

创建一个额外的数组，然后对每个元素遍历，看看周围八个元素的情况

var gameOfLife = function(board) {
  if(!board.length) return
  let rows = board.length
  let cols = board[0].length
  let copy = new Array()
  for(let row = 0; row < rows; row++) {
    copy[row] = new Array()
    for(let col = 0; col < cols; col++) {
      copy[row][col] = board[row][col]
    }
  }

  let around = [0, -1, 1]
  for(let row = 0; row < rows; row++) {
    for(let col = 0; col < cols; col++) {
      let count = 0
      for(let i = 0; i < 3; i++) {
        for(let j = 0; j < 3; j++) {
          if(!i && !j) continue
          let r = row + around[i]
          let c = col + around[j]

          if((r >= 0 && r < rows) && (c >= 0 && c < cols) && copy[r][c] === 1){
            count++
          }
        }
      }
      if ((copy[row][col] === 1) && (count < 2 || count > 3)) {
        board[row][col] = 0;
      }
      if (copy[row][col] === 0 && count === 3) {
        board[row][col] = 1;
      }
    }
  }

};

时间复杂度:O(mn)

空间复杂度:O(mn)

思路二

我们可以把变死亡改成-1，复活改成2即可，到最后 2->1 -1->0即可

var gameOfLife = function(board) {
  if(!board.length) return
  let rows = board.length
  let cols = board[0].length

  let around = [0, -1, 1]
  for(let row = 0; row < rows; row++) {
    for(let col = 0; col < cols; col++) {
      let count = 0
      for(let i = 0; i < 3; i++) {
        for(let j = 0; j < 3; j++) {
          if(!i && !j) continue
          let r = row + around[i]
          let c = col + around[j]
          // 注意：有些位置为 -1，但是当前它还是活的，这轮过后才死
          if((r >= 0 && r < rows) && (c >= 0 && c < cols) && Math.abs(board[r][c]) === 1){
            count++
          }
        }
      }
      if ((board[row][col] === 1) && (count < 2 || count > 3)) {
        board[row][col] = -1;
      }
      if (board[row][col] === 0 && count === 3) {
        board[row][col] = 2;
      }
    }
  }
  

  for(let row = 0; row < rows; row++) {
    for(let col = 0; col < cols; col++) {
      board[row][col] = board[row][col] > 0 ? 1 : 0
    }
  }
};

时间复杂度:O(mn)

空间复杂度:O(1)

lc455. 分发饼干简单

题目描述

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例 1:

输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

示例 2:

输入: g = [1,2], s = [1,2,3]
输出: 2
解释: 
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

思路：排序 + 贪心

升序排序，每一个试一下

var findContentChildren = function(g, s) {
    g.sort((a, b) => a - b);
    s.sort((a, b) => a - b);
    const numOfChildren = g.length, numOfCookies = s.length;
    let count = 0;
    for (let i = 0, j = 0; i < numOfChildren && j < numOfCookies; i++, j++) {
        while (j < numOfCookies && g[i] > s[j]) {
            j++;
        }
        if (j < numOfCookies) {
            count++;
        }
    }
    return count;
};

时间复杂度:O(nlogn + mlogm)

空间复杂度:O(nlogn + mlogm)

lc380. O(1) 时间插入、删除和获取随机元素简单

题目描述

实现RandomizedSet 类：

• RandomizedSet() 初始化 RandomizedSet 对象
• bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
• bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
• int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

示例：

输入
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
输出
[null, true, false, true, 2, true, false, 2]

解释
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。
randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。
randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。

let RandomizedSet = function() {
    this.list = []
    this.map = {}
};

RandomizedSet.prototype.insert = function(val) {
    if(this.map[val]) return false

    this.list.push(val)
    this.map[val] = this.list.length
    return true
};

RandomizedSet.prototype.remove = function(val) {
    if(!this.map[val]) return false

    const final = this.list[this.list.length-1]

    // 下面这块主要是把要数组的尾值赋给对应的val值的位置，之后把数组最后的值踢出去即可
    const index = this.map[val]
    // 这里的index-1即我们拿到的index不是数组的下标，还需要减1。
    this.list[index-1] = final
    this.map[final] = index

    delete this.map[val]
    this.list.pop()

    return true
};

RandomizedSet.prototype.getRandom = function() {
    const index = Math.floor(Math.random() * this.list.length)
    return this.list[index]
};

lc997. 找到小镇的法官简单

题目描述

小镇里有 n 个人，按从 1 到 n 的顺序编号。传言称，这些人中有一个暗地里是小镇法官。

如果小镇法官真的存在，那么：

1. 小镇法官不会信任任何人。
2. 每个人（除了小镇法官）都信任这位小镇法官。
3. 只有一个人同时满足属性 1 和属性 2 。

给你一个数组 trust ，其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人。

如果小镇法官存在并且可以确定他的身份，请返回该法官的编号；否则，返回 -1 。

示例 1：

输入：n = 2, trust = [[1,2]]
输出：2

示例 2：

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

示例 3：

输入：n = 3, trust = [[1,3],[2,3],[3,1]]
输出：-1

思路：图

法官的入度为n - 1，出度为0

var findJudge = function(N, trust) {
  //构造0-N个节点的图
  let graph = Array.from({length:N+1}, () => ({outDegree:0, inDegree:0}))
  trust.forEach(([a, b]) => {
    graph[a].outDegree++
    graph[b].inDegree++
  })
  return graph.findIndex(({outDegree, inDegree}, index) => {
    //剔除0
    return index != 0 && outDegree === 0 && inDegree === N-1 
  })
};

581. 最短无序连续子数组中等

题目描述

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的 最短 子数组，并输出它的长度。

示例 1：

输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

示例 2：

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

示例 3：

输入：nums = [1]
输出：0

排序 + 比较

var findUnsortedSubarray = function(nums) {
  if(isSort(nums)) return 0
  const sortNums = [...nums].sort((a, b) => a - b)
  let l = 0
  while(nums[l] === sortNums[l]) {
    l++
  }
  let r = nums.length - 1
  while(nums[r] === sortNums[r]) {
    r--
  }
  return r - l + 1
};

function isSort(nums) {
  for(let i = 1; i < nums.length; i++) {
    if(nums[i] < nums[i - 1]) return false
  }
  return true
}

时间复杂度:O(nlogn)

空间复杂度:O(n)

一次遍历

var findUnsortedSubarray = function(nums) {
  const n = nums.length;
  let max = -Infinity, right = -1;
  let min = +Infinity.MAX_VALUE, left = -1;
  for (let i = 0; i < n; i++) {
    if (max > nums[i]) {
      right = i;
    } else {
      max = nums[i];
    }
    if (min < nums[n - i - 1]) {
      left = n - i - 1;
    } else {
      min = nums[n - i - 1];
    }
  }
  return right === -1 ? 0 : right - left + 1;
};

时间复杂度:O(n)

空间复杂度:O(1)

lc232. 用栈实现队列简单hot

题目描述

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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.stack1 = []
  this.stack2 = []
};

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

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

  return this.stack2.pop()
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function() {
  if(!this.stack2.length) {
    while(this.stack1.length) {
      this.stack2.push(this.stack1.pop())
    }
  }

  return this.stack2[this.stack2.length - 1]
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
  return this.stack1.length === 0 && this.stack2.length === 0
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * var obj = new MyQueue()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.peek()
 * var param_4 = obj.empty()
 */

lc151. 翻转字符串里的单词中等hot

题目描述

给你一个字符串 s ，逐个翻转字符串中的所有 单词 。

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

请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。

说明：

输入字符串 s 可以在前面、后面或者单词间包含多余的空格。 翻转后单词间应当仅用一个空格分隔。 翻转后的字符串中不应包含额外的空格。

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

输入：s = "  Bob    Loves  Alice   "
输出："Alice Loves Bob"

示例 5：

输入：s = "Alice does not even like bob"
输出："bob like even not does Alice"

法一：js api + 正则

• 去除空格

• 逆向

• 数组还原成字符串

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

法二： 自己实现trim 和双端队列

• 首先去除字符串左右空格

• 逐个读取字符串中的每个单词，依次放入双端队列的对头

• 再将队列转换成字符串输出（已空格为分隔符）

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    let left = 0
    let right = s.length - 1
    while(s.charAt(left) === ' ') left++
    while(s.charAt(right) === ' ') right--
    let word = ''
    const queue = []
    while(left <= right) {
        let char = s.charAt(left)
        if(char === ' ' && word) {
            queue.unshift(word)
            word = ''
        } else if (char !== ' ') {
            word += char
        }
        left++
    }
    queue.unshift(word)
    return queue.join(' ')
};

时间复杂度:O(n)

空间复杂度:O(n)

lc41. 缺失的第一个正数困难hot

题目描述

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [7,8,9,11,12]
输出：1

置换

var firstMissingPositive = function(nums) {
  for(let i = 0; i < nums.length; i++){
    // 将原始的数组当成哈希表来用，即将数值为i的数映射到下标为i-1上
    // 本题求没有出现的最小正整数，因此忽略为负数的

    // 这里while很重要，因为置换之后的值不一定满足条件, 要检查
    // 如果满足条件或超出数组长度，则跳过，不需要置换
      while(nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i] ){
        [nums[nums[i] - 1], nums[i]] = [nums[i], nums[nums[i] - 1]]
      }
  }
  for(let i = 0; i < nums.length; i++){
    if(nums[i] != i + 1){
      return i + 1;
    }
  }

  return nums.length + 1;
};

时间复杂度:O(n)

空间复杂度:O(1)

470. 用 Rand7() 实现 Rand10()中等hot

题目描述

给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。

你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。

每个测试用例将有一个内部参数 n，即你实现的函数 rand10() 在测试时将被调用的次数。请注意，这不是传递给 rand10() 的参数。

示例 1:

输入: 1
输出: [2]

示例 2:

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

示例 3:

输入: 3
输出: [3,8,10]

思路

var rand10 = function () {
  // 已知 randN() 可以等概率的生成[1, N]范围的随机数
  // 那么：(randX() - 1) × Y + randY() ==> 可以等概率的生成[1, X * Y]范围的随机数
  while (true) {
      let a = rand7()
      let b = rand7()
      // a - 1随机生成0 - 6
      // (a - 1)*7随机生成0 7 14 21 28 35 42 
      // +b后会充盈7的倍数之间的空隙
      // 所以res会是随机的[1,49]
      let res = (a - 1) * 7 + b
      // 为什么不直接在49里面模10 + 1？
      // 因为不随机了
      // 拒绝采样
      if (res <= 40) return res % 10 + 1
  }
};

时间复杂度:O(1)

空间复杂度:O(1)

860. 柠檬水找零简单

题目描述

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

示例 1：

输入：bills = [5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。

示例 2：

输入：bills = [5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。

var lemonadeChange = function(bills) {
  let five = 0, ten = 0
  for(let i = 0; i < bills.length; i++) {
    if(bills[i] === 5) five++
    else if(bills[i] === 10) {
      five--
      ten++
      if(five < 0) return false
    }
    else{
      if(ten > 0){
        ten--
        five--
      }else{
        five -= 3
      }
      if(five < 0) return false
      }
  }
  return true
};

时间复杂度:O(n)

空间复杂度:O(1)