/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
//递归写法
var removeElements = function (head, val) {
  //先判断不存在条件 如果为空直接返回
  if (head === null) {
    return head
  }
  // 不停的进行调用 删除 返回
  head.next = removeElements(head.next, val)
  //知道最后 一层一层跳出 如果值等于val 返回下个next节点  不相等返回当前head 返回的值赋值给上个head.next
  return head.val === val ? head.next : head
}
//普通写法  新增一个哨兵节点 省去为null的判断
var removeElements = function (head, val) {
  let ele = {
    next: head,
  }
  let p = ele
  while (p.next) {
    //判断val是否和val相等，将p.next的节点指向下下个节点
    if (p.next.val === val) {
      p.next = p.next.next
    } else {
      p = p.next
    }
  }
  return ele.next
}

/**
 * @param {ListNode} head
 * @return {boolean}
 */
//快慢指针
var hasCycle = function (head) {
  //定义两个指针 一个步长快 一个步长慢 如果是环形一定会相遇
  let fast = head
  let slow = head
  while (fast && fast.next) {
    fast = fast.next.next
    slow = slow.next
    if (slow === fast) return true
  }
  return false
}

//普通做法 使用Set集合存储 看是否存在相同的
var hasCycle = function (head) {
  //定义一个Set集合 不是键值 所以用
  let cache = new Set()
  //如果存在next，先判断head是否在cache中，不在新增，遍历head下个节点
  while (head) {
    if (cache.has(head)) {
      return true
    } else {
      cache.add(head)
    }
    head = head.next
  }
  return false
}

//keys.values().next().value  Map是有迭代器 可以使用next取调用 keys 或者values 获取数组
let cache = new Map()
cache.set('1', 1)
cache.set('2', 2)
cache.set('3', 3)
// 生成器的代码
// 使用cache.keys().next().value 相当于取了最先存进去的那个值
console.log(cache.keys().next().value)
// keys()  [Map Iterator] { '1', '2', '3' }
// keys().next()   { value: '1', done: false }
// keys().next().value  1

// @lc code=start
/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
  //使用map进行缓存
  this.cache = new Map()
  this.max = capacity
}

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  //如果存在key 进行删除缓存  原先的值需要进行赋值
  if (this.cache.has(key)) {
    let tmp = this.cache.get(key)
    this.cache.delete(key)
    this.cache.set(key, tmp)
    return tmp
  }
  return -1
}

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
  //如果存在直接删除key
  if (this.cache.has(key)) {
    this.cache.delete(key)
  } else if (this.cache.size >= this.max) {
    // 当cache的数量大于等于最大值 删除之前的缓存
    this.cache.delete(this.cache.keys().next().value)
  }
  this.cache.set(key, 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)
 */

/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfTwo = function (n) {
  // 运用n 与 n-1 之间的特点 进行&操作 1000 & 0111 = 0000
  return n > 0 && (n & (n - 1)) === 0
}
//普通做法
var isPowerOfTwo = function (n) {
  // 先判断跳出条件
  if (n === 1) {
    return true
  }
  // 判断失败的条件
  if (n % 2 !== 0 || n === 0) {
    return false
  }
  // 二分进行递归
  return isPowerOfTwo(n / 2)
}

/**
 * @param {number[]} nums
 * @return {number}
 */
//使用异或方法 任何两个相同的数异或后为0
var singleNumber = function (nums) {
  let ret = 0
  nums.forEach((num) => [(ret ^= num)])
  return ret
}
//普通做法
var singleNumber = function (nums) {
  let obj = new Map()
  for (let i = 0; i < nums.length; i++) {
    if (obj.has(nums[i])) {
      obj.set(nums[i], 2)
    } else {
      obj.set[(nums[i], 1)]
    }
  }
  for (let o of obj.keys()) {
    if (obj.get(o) === 1) {
      return o
    }
  }
}

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function (root) {
  if (root === null) {
    return 0
  }
  // 最大深度是 左子树的深度 和右子树的深度 最大的那个+1？ 从null返回为0 返回到上层的时候+1
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
}

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function (root) {
  if (root !== null) {
    // 递归子问题 循环遍历调用子节点进行调换
    ;[root.left, root.right] = [invertTree(root.right), invertTree(root.left)]
  }
  return root
}

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  // 解题思路： 用一个数组存放每次遍历的值  枚举这些对应的括号， 将左边括号进行存储，当遇到不是obj的规则
  // 先比较stack中pop的值与当前的值是不是相等，不相等直接返回
  // [{}()]   [{()}]   [({}) {}()]
  let stack = []
  let obj = {
    '(': ')',
    '{': '}',
    '[': ']',
  }
  for (let i = 0; i < s.length; i++) {
    const el = s[i]
    if (el in obj) {
      stack.push(el)
    } else {
      if (el !== obj[stack.pop()]) {
        return false
      }
    }
  }
  // 所有stack中的数据匹配完成后，返回true
  return !stack.length
}

/**
 * @param {string} path
 * @return {string}
 */
var simplifyPath = function (path) {
  //解题思路：栈 将path通过/分割成数组 只含有 .  ..  '' 字母 遇到. 直接删除 .. 删除上个path
  let pathArr = path.split('/')
  const stack = []
  for (let i = 0; i < pathArr.length; i++) {
    let s = pathArr[i]
    if (s === '..') {
      stack.pop()
    } else if (s && s !== '.') {
      stack.push(s)
    }
  }
  return '/' + stack.join('/')
}

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  // 如果长度小于3 返回空
  if (nums.length < 3) {
    return []
  }
  let list = []

  //在一个无序的数组中，查询目标与大小相关，可以利用排序进行降低复杂度
  nums.sort((a, b) => a - b)
  //最小+最大之和，如果比目标值大， 说明我们要缩小这个值，最大值左移动，否则最小右移
  for (let i = 0; i < nums.length; i++) {
    //如果下一个数与前一个数相同直接跳过
    if (nums[i] === nums[i - 1]) {
      continue
    }
    //以nums[i]为基准，找出其他两个值为-nums[i]. 数组和为0
    let left = i + 1
    let right = nums.length - 1
    //
    while (left < right) {
      //需要跳过i自身
      if (right === i) {
        right--
      } else if (nums[left] + nums[right] + nums[i] === 0) {
        list.push([nums[left], nums[right], nums[i]])
        //继续找
        while (nums[left] === nums[left + 1]) {
          //由于排序了 去重相邻的重复的数字
          left++
        }
        left++
        while (nums[right] === nums[right - 1]) {
          //由于排序了 去重相邻的重复的数字
          right--
        }
        right--
      } else if (nums[left] + nums[right] + nums[i] > 0) {
        //数字变大
        right--
      } else {
        //数字变小
        left++
      }
    }
  }
  return list
}

// leftpad
let s = 'hello'

console.log(s.padStart(10, '0'))
// 性能慢 二分思想
function leftpad(str, length, ch) {
  let len = length - str.length + 1
  return Array(len).join(ch) + str
}
console.log(1, leftpad(s, 20, '0'))
// '0'
// '00'
// '0000'
// '00000000'
function leftpad2(str, length, ch) {
  let len = length - str.length
  total = ''
  while (true) {
    // if (len % 2 === 1) {
    if (len & 1) {
      total += ch
    }
    if (len === 1) {
      return total + str
    }
    ch += ch
    // len = parseInt(len/2)
    len = len >> 1
  }
}

console.time('leftpad')
for (let i = 0; i < 10000; i++) {
  leftpad('hello', 100000, 'o')
}
console.timeEnd('leftpad')
console.time('leftpad2')
for (let i = 0; i < 10000; i++) {
  leftpad2('hello', 100000, 'o')
}
console.timeEnd('leftpad2')

//leftpad: 9.044s
// leftpad2: 5.152ms

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
//公式
/*
temp [1]
    backtrack
        temp[1,2]
            backtrack
                temp [1,2,3]终止
                temp.pop[1,2]
            temp[1]
    

 */
function backtrack(list, temp, nums) {
  /*
放进去一个元素
执行递归公式
撤回这个元素
 */
  // 1.终止条件
  if (temp.length === nums.length) {
    return list.push([...temp])
  }

  for (let i = 0; i < nums.length; i++) {
    //找到一个不在temp中的值
    if (temp.includes(nums[i])) {
      continue
    }
    //push数组中
    temp.push(nums[i])
    backtrack(list, temp, nums)
    temp.pop()
  }
  // 2.递归公式
}
var permute = function (nums) {
  let list = []
  backtrack(list, [], nums)
  return list
}

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
/*
  1. 全部答案的路径 需要个list
   let list = []
   function backtrack(list,临时路径,输入){
       //结束条件
           临时路径，新增一个路径
       循环{
           选择一个数据
           递归backtrack(list,临时路径,输入)
           撤回选择的数据
       }
   }
   backtrack(list,[],输入)

   2 不需要全部路径 只需要true/false 不需要临时路径 
*/
var exist = function (board, word) {
  //输入终止条件
  if (board.length === 0) {
    return false
  }
  if (word.length === 0) {
    return true
  }
  //定义行列数
  let row = board.length
  let col = board[0].length
  //遍历
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      // 每一个字母都可以作为一个起点
      //传入索引，方便上下左右移动，最后0是当前值的索引
      const ret = find(i, j, 0)
      if (ret) {
        return ret
      }
    }
  }
  return false //结束未找到

  //递归函数
  function find(i, j, cur) {
    if (i >= row || i < 0) {
      return false
    }
    if (j >= col || j < 0) {
      return false
    }
    //查找的数字至空，如果空不要再查找
    let letter = board[i][j]
    //查找当前的值不等于word的对应为的字母
    if (letter !== word[cur]) {
      return false
    }
    //最后一个都是匹配的
    if (cur === word.length - 1) {
      return true
    }
    board[i][j] = null
    //进行下一步
    //四个方向查找  有一个方向找到即可
    const ret = find(i + 1, j, cur + 1) || find(i - 1, j, cur + 1) || find(i, j + 1, cur + 1) || find(i, j - 1, cur + 1)
    //回撤
    board[i][j] = letter
    //再下一步塞回去，查找下一个
    return ret
  }
}

/**
 * @param {number[]} bills
 * @return {boolean}
 */
// 给5 收入
// 给10 就找5
// 给20 给个10+5 或者 5+5+5 优先给10
var lemonadeChange = function (bills) {
  let fiveNum = 0
  let tenNum = 0
  for (let i = 0; i < bills.length; i++) {
    let bill = bills[i]
    if (bill === 5) {
      fiveNum += 1
    } else if (bill === 10) {
      //如果10块有5块找 就找没有就返回false
      if (fiveNum > 0) {
        fiveNum -= 1
        tenNum += 1
      } else {
        return false
      }
    } else {
      //20的情况
      if (fiveNum > 0 && tenNum > 0) {
        fiveNum -= 1
        tenNum -= 1
      } else if (fiveNum > 2) {
        fiveNum -= 3
      } else {
        return false
      }
    }
  }
  return true
}

/**
 * @param {number[]} nums
 * @return {boolean}
 */
//跳跃的范围覆盖就可以
var canJump = function (nums) {
  //cover如果比length-1 大 认为可以跳过
  let cover = 0
  //遍历 到cover 如果cover小说明 遍历不到后面的值
  for (let i = 0; i <= cover; i++) {
    // 当前覆盖的范围是 cover到第i+nums[i]的值
    cover = Math.max(cover, i + nums[i])
    //如果覆盖的值大于等于nums的最后的下表 说明成功
    if (cover >= nums.length - 1) {
      return true
    }
  }
  //一直没有匹配到 说明不可以
  return false
}

/**
 * @param {number[]} g
 * @param {number[]} s
 * @return {number}
 */
// g 胃口 s有的饼干
// 贪心策略
var findContentChildren = function (g, s) {
  g.sort((a, b) => a - b)
  s.sort((a, b) => a - b)
  //饼干满足胃口最大的小朋友
  let ret = 0
  let index = s.length - 1
  //找出胃口最大的小朋友
  for (let i = g.length - 1; i >= 0; i--) {
    //如果饼干数量>0 饼干大于小朋友的胃口 结果+1 最大数量的索引-1
    if (index >= 0 && s[index] >= g[i]) {
      ret++
      index--
    }
  }
  return ret
}

/**
 * @param {number} n
 * @return {number}
 */
var fib = function (n) {
  // 1.递归
  if (n <= 1) {
    return n
  }
  return fib(n - 1) + fib(n - 2)

  //2.递推
  // dp[i] 就是第i的值
  // dp[i] = dp[i-1]+dp[i-2]

  let dp = [0, 1]
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }
  return dp[n]

  //3.备忘录
  //备忘录+递推
  function helper(meno, n) {
    if (n <= 1) {
      return n
    }
    if (meno[n]) {
      return meno[n]
    }
    meno[n] = helper(meno, n - 1) + helper(meno, n - 2)
    return meno[n]
  }
  let meno = []
  return helper(meno, n)

  //熟组优化成两个数字
  if (n <= 1) {
    return n
  }
  let dp1 = 0
  let dp2 = 1
  let dp3
  for (let i = 2; i <= n; i++) {
    dp3 = dp1 + dp2
    dp1 = dp2
    dp2 = dp3
  }
  return dp3

  //数学公式
  //可以用矩阵
}

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function (coins, amount) {
  // 固定金额下，最少的个数
  // 边界条件
  //     循环
  //         递推公式
  // dp[n] n的钱数下最优解
  //只有2，5 硬币 找12
  // dp[n-coins[i]] + 1
  // 10 + 2
  // 7 + 5
  //金额为0 直接返回0
  if (!amount) {
    return 0
  }
  //coins=[1,2,5] amount =11
  let dp = Array(amount + 1).fill(Infinity)
  dp[0] = 0
  for (let i = 0; i < coins.length; i++) {
    //针对每一个硬币
    // i=0 j=1
    for (let j = coins[i]; j <= amount; j++) {
      dp[j] = Math.min(dp[j - coins[i]] + 1, dp[j])
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount]
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function (nums) {
  //贪心+二分
  //让序列尽可能慢
  // [1,3,5,7] 9  大于最后一个push  中间在插入 [1,4,5]
  let n = nums.length
  if (n === 0) {
    return 0
  }
  let arr = [nums[0]]
  for (let i = 0; i < n; i++) {
    if (nums[i] > arr[arr.length - 1]) {
      arr.push(nums[i])
    } else {
      //找到arr中第一个比nums[i]大的数组 修改他
      let left = 0
      let right = arr.length - 1
      while (left < right) {
        let mid = (left + right) >> 1
        if (arr[mid] < nums[i]) {
          left = mid + 1
        } else {
          right = mid
        }
      }
      arr[left] = nums[i]
    }
  }
  return arr.length

  // [0,1,0,3,2,3]
  //选择极值用dp
  // dp[i] 在i的位置以前的数组 最长递增子序列的长度
  // 例如 刚开始是1个数[1,1,1,1,1,1]
  // 第二个数 nums[i]>nums[i-1] [1,2,1,1,1,1]
  // 第三个数 比之前的小  [1,2,2,1,1,1]
  // 第四个数 比之前的大  [1,2,2,3,1,1]
  // 第五个数 比之前的小  [1,2,2,3,3,1]
  // 第六个数 比之前的大  [1,2,2,3,3,4]
  //动态规划
  let n = nums.length
  if (n === 0) {
    return 0
  }
  let dp = Array(n).fill(1)
  for (let i = 0; i < n; i++) {
    for (j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1)
      }
    }
  }
  return Math.max(...dp)
}

遍历
while (head) {
  head = head.next
}
return head
//定义一个哨兵节点
let dummny = {
  next: head.next,
}
return dummny.next

二叉树
function walk(treeNode) {
  if (treeNode === null) {
    return
  }
  //停止条件
  //处理treeNode

  //处理treeNode
  walk(treeNode.left)
  walk(treeNode.right)

  walk(treeNode.left)
  //处理treeNode
  walk(treeNode.right)

  walk(treeNode.left)
  walk(treeNode.right)
  //处理treeNode
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
  let arr = []
  function dfs(r) {
    if (r === null) {
      return
    }
    dfs(r.left)
    arr.push(r.val)
    dfs(r.right)
  }
  dfs(root)
  return arr
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
  let arr = []
  function dfs(r) {
    if (r === null) {
      return
    }
    arr.push(r.val)
    dfs(r.left)
    dfs(r.right)
  }
  dfs(root)
  return arr
}
//迭代写法
var preorderTraversal = function (root) {
  let res = []
  if (root === null) {
    return []
  }
  let stack = [root]
  while (stack.length) {
    let cur = stack.pop()
    res.push(cur.val)
    cur.right && stack.push(cur.right)
    cur.left && stack.push(cur.left)
  }
  return res
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
  let arr = []
  function dfs(r) {
    if (r === null) {
      return
    }
    dfs(r.left)
    dfs(r.right)
    arr.push(r.val)
  }
  dfs(root)
  return arr
}

let fast = null
let slow = null
if (fast && fast.next) {
  处理
}

function backtrack(数据，缓存路径){
    循环
        标记
        backtrack(数据，缓存路径)
        取消标记
}

想清楚结果怎么推导，找零钱
1，2，5
dp[11] 11块钱找零的最佳解
dp[10] dp[9] dp[6] 三个最优解 +1

/**
 * @param {number[]} nums
 * @return {number}
 */
//思路：定义一个快慢指针 slow fast
//[1,1,2,3,3]=> 如果fast和slow不相等 让fast的值赋给slow slow++
//  [1,1,2,3,3]=>[1,2,2,3,3]=>[1,2,3,3,3]=>返回slow索引 长度需要加1
var removeDuplicates = function (nums) {
  if (nums.length === 0) {
    return 0
  }
  let slow = 0
  let fast = 0
  while (fast < nums.length) {
    if (nums[fast] !== nums[slow]) {
      slow++
      nums[slow] = nums[fast]
    }
    fast++
  }
  return slow + 1
}

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
//思路 定义一个k指针 如果nums[i]不等于val  利用下表代表返回后新数组的长度
var removeElement = function (nums, val) {
  let k = 0
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== val) {
      nums[k++] = nums[i]
    }
  }
  return k
}

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
  //先不移动0 最后将后面的数修改为0
  let fast = 0
  let slow = 0
  while (fast < nums.length) {
    if (nums[fast]) {
      let tmp = nums[slow]
      nums[slow] = nums[fast]
      nums[fast] = tmp
      slow++
    }
    fast++
  }
}

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (numbers, target) {
  //两个递增相加之和 从两个方向进行移动
  let left = 0
  let right = numbers.length - 1
  while (left <= right) {
    let sum = numbers[left] + numbers[right]
    //下标记从1开始
    if (sum === target) {
      return [left + 1, right + 1]
    }
    if (sum > target) {
      right--
    } else if (sum < target) {
      left++
    }
  }
}

/**
 * 如何原地？
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function (nums) {
  let left = 0
  let right = nums.length - 1
  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} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function (target, nums) {
  //暴力解法
  let len = nums.length
  let result = len + 1
  for (let i = 0; i < len; i++) {
    let sum = 0
    for (let j = i; j < len; j++) {
      sum += nums[j]
      //如果找到sum大于等于target subLen 是j-i+1长度
      if (sum >= target) {
        let subLen = j - i + 1
        result = result < subLen ? result : subLen
        break
      }
    }
  }
  return result > len ? 0 : result
}

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function (target, nums) {
  //动态规划
  let len = nums.length
  let fast = (slow = 0)
  let sum = 0
  let result = len + 1
  while (fast < len) {
    sum += nums[fast++]
    while (sum >= target) {
      let subLen = fast - slow
      result = result < subLen ? result : subLen
      sum -= nums[slow++]
    }
  }
  return result > len ? 0 : result
}