前端一万五 - 数据结构与算法篇

/*
 * https://leetcode-cn.com/problems/reverse-words-in-a-string-iii/description/
 *
 * Testcase Example:  `"Let's take LeetCode contest"`
 *
 * 给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
 *
 * 示例 1:
 *
 *
 * 输入: "Let's take LeetCode contest"
 * 输出: "s'teL ekat edoCteeL tsetnoc"
 *
 *
 * 注意：在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。
 *
 */

/**
 * 解法一
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
  return s.split(' ')
    .map(word => (word.split('').reverse().join('')))
    .join(' ')
}

/**
 * 解法二
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
  return s.split(/\s/g)
    .reduce((str, word) => (str + ' ' + word.split('').reverse().join('')), '')
    .substring(1)
}

/**
 * 解法三
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
  return s.match(/[\w']+/ig)
    .reduce((str, word) => (str + ' ' + word.split('').reverse().join('')), '')
    .substring(1)
}

/*
 * https://leetcode-cn.com/problems/count-binary-substrings/description/
 *
 * 给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。
 *
 * 重复出现的子串要计算它们出现的次数。
 *
 * 示例 1 :
 *
 *
 * 输入: "00110011"
 * 输出: 6
 * 解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。
 *
 * 请注意，一些重复出现的子串要计算它们出现的次数。
 *
 * 另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。
 *
 *
 * 示例 2 :
 *
 *
 * 输入: "10101"
 * 输出: 4
 * 解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。
 *
 *
 * 注意：
 * s.length 在1到50,000之间。
 * s 只包含“0”或“1”字符。
 *
 */

/**
 * @param {string} s
 * @return {number}
 */
var countBinarySubstrings = function(s) {
  const r = []
  const match = (str) => {
    const j = str.match(/^(0+|1+)/)[0] // 连续0或1
    // 逻辑位运算符：位与（&）、位或（|）、位异或（^）、非位（~）
    // 移位运算符：左移（<<）、右移（>>）、无符号右移（>>>）
    // ^ => 相同取0，相异取1
    const o = (j[0] ^ 1).toString().repeat(j.length)
    const reg = new RegExp(`^(${j}${o})`)
    if (reg.test(str)) {
      return RegExp.$1
    } else {
      return ''
    }
  }
  for (let i = 0, len = s.length - 1; i < len; i++) {
    const sub = match(s.slice(i))
    if (sub) {
      r.push(sub)
    }
  }
  return r.length
}

/*
 * https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/description/
 *
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
 *
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 *
 * 示例:
 *
 * 输入："23"
 * 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
 *
 *
 * 说明:
 * 尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
 *
 */

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
  // 1. 建立数字和字母的映射
  const map = new Map([
    [2, 'abc'],
    [3, 'def'],
    [4, 'ghi'],
    [5, 'jkl'],
    [6, 'mno'],
    [7, 'pqrs'],
    [8, 'tuv'],
    [9, 'wxyz']
  ])
  // 2. 把输入的字符串分割成数组 234 => [2, 3, 4]
  const nums = digits.split('').map(str => Number(str))
  // 3. 整数型数组转键盘字母映射数组 [2, 3, 4] => ['abc', 'def', 'ghi]
  const strs = nums.map(num => (map.get(num)))

  const combinations = function(arr) {
    const tmp = []
    for (const wordA of (arr[0] ? arr[0] : [])) {
      for (const wordB of (arr[1] ? arr[1] : [''])) {
        tmp.push(`${wordA}${wordB}`)
      }
    }
    arr.splice(0, 2, tmp) // 删除前两项，在开头增加tmp数组作为0项
    if (arr.length === 1) {
      return arr[0]
    }
    return combinations([...arr])
  }
  return combinations([...strs])
}

/*
 * https://leetcode-cn.com/problems/x-of-a-kind-in-a-deck-of-cards/description/
 *
 * 给定一副牌，每张牌上都写着一个整数。
 *
 * 此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：
 *
 *
 * 每组都有 X 张牌。
 * 组内所有的牌上都写着相同的整数。
 *
 *
 * 仅当你可选的 X >= 2 时返回 true。
 *
 *
 * 示例 1：
 *
 * 输入：[1,2,3,4,4,3,2,1]
 * 输出：true
 * 解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]
 *
 * 示例 2：
 *
 * 输入：[1,1,1,2,2,2,3,3]
 * 输出：false
 * 解释：没有满足要求的分组。
 *
 * 示例 3：
 *
 * 输入：[1]
 * 输出：false
 * 解释：没有满足要求的分组。
 *
 * 示例 4：
 *
 * 输入：[1,1]
 * 输出：true
 * 解释：可行的分组是 [1,1]
 *
 * 示例 5：
 *
 * 输入：[1,1,2,2,2,2]
 * 输出：true
 * 解释：可行的分组是 [1,1]，[2,2]，[2,2]
 *
 * 提示：
 * 1 <= deck.length <= 10000
 * 0 <= deck[i] < 10000
 */

/**
 * @param {number[]} deck
 * @return {boolean}
 */
var hasGroupsSizeX = function(deck) {
  const group = []
  const tmp = {}

  // 统计每一个数字出现的次数 => 对象用来计次很方便哦, key: value
  deck.forEach(item => {
    tmp[item] = tmp[item] ? tmp[item] + 1 : 1
  })

  // group用于存放每张牌的总数
  for (const v of Object.values(tmp)) {
    group.push(v)
  }

  // 求两个数的最大公约数
  const gcd = (a, b) => {
    if (b === 0) {
      return a
    } else {
      return gcd(b, a % b)
    }
  }

  while (group.length > 1) {
    const a = group.shift() // 取第一个数字的次数
    const b = group.shift() // 取第二个数字的次数
    const v = gcd(a, b) // 取两个数字的最大公约数
    if (v === 1) {
      return false
    } else {
      group.unshift(v)
    }
  }
  return group.length ? group[0] > 1 : false
}

/*
 * https://leetcode-cn.com/problems/can-place-flowers/description/
 *
 * 假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
 *
 * 给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n
 * 朵花？能则返回True，不能则返回False。
 *
 * 示例 1:
 *
 *
 * 输入: flowerbed = [1,0,0,0,1], n = 1
 * 输出: True
 *
 *
 * 示例 2:
 *
 *
 * 输入: flowerbed = [1,0,0,0,1], n = 2
 * 输出: False
 *
 *
 * 注意:
 *
 * 数组内已种好的花不会违反种植规则。
 * 输入的数组长度范围为 [1, 20000]。
 * n 是非负整数，且不会超过输入数组的大小。
 */

/**
 * @param {number[]} flowerbed
 * @param {number} n
 * @return {boolean}
 */
var canPlaceFlowers = function(flowerbed, n) {
  let max = 0
  for (let i = 0, len = flowerbed.length - 1; i <= len; i++) {
    if (flowerbed[i] === 0) {
      if ((i === 0 && flowerbed[1] === 0) || // 第一个没有种花， 且第一个也没有种花
        (i === 0 && len === 0) || // 第一个没有种花，且只有一个花位
        (i === len && flowerbed[len - 1] === 0) // 最后一个没有种花， 且倒数第二个没有种花
      ) {
        max++
        i++ // i++ 用于排除当前种花了的位置
      } else if (flowerbed[i - 1] === 0 && flowerbed[i + 1] === 0) { // 不是第一个和最后一个位置的边界情况，且前一个和后一个都没有种花
        max++
        i++
      }
    }
  }
  return max >= n
}

/*
 * https://leetcode-cn.com/problems/gray-code/description/
 * 格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。
 *
 * 给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0 开头。
 *
 * 示例 1:
 *
 * 输入: 2
 * 输出: [0,1,3,2]
 * 解释:
 * 00 - 0
 * 01 - 1
 * 11 - 3
 * 10 - 2
 *
 * 对于给定的 n，其格雷编码序列并不唯一。
 * 例如，[0,2,3,1] 也是一个有效的格雷编码序列。
 *
 * 00 - 0
 * 10 - 2
 * 11 - 3
 * 01 - 1
 *
 * 示例 2:
 *
 * 输入: 0
 * 输出: [0]
 * 解释: 我们定义格雷编码序列必须以 0 开头。
 * 给定编码总位数为 n 的格雷编码序列，其长度为 2^n。当 n = 0 时，长度为 2^0 = 1。
 * 因此，当 n = 0 时，其格雷编码序列为 [0]。
 */

/**
 * @param {number} n
 * @return {number[]}
 */
var grayCode = function(n) {
  const make = function(m) {
    if (m === 1) {
      return ['0', '1']
    } else if (m === 0) {
      return ['0']
    }
    const prev = make(m - 1) // 递归
    const len = Math.pow(2, m)
    const res = []
    for (let i = 0; i < len / 2; i++) {
      res[i] = `0${prev[i]}`
      res[len - i - 1] = `1${prev[i]}`
    }
    return res
  }
  // 二进制转十进制
  return make(n).map(binary => (parseInt(binary, 2)))
}

// 进制转换
parseInt(num, 8) // 八进制转十进制
parseInt(num, 16) // 十六进制转十进制
parseInt(num).toString(8) // 十进制转八进制
parseInt(num).toString(16) // 十进制转十六进制
parseInt(num, 2).toString(8) // 二进制转八进制
parseInt(num, 2).toString(16) // 二进制转十六进制
parseInt(num, 8).toString(2) // 八进制转二进制
parseInt(num, 8).toString(16) // 八进制转十六进制
parseInt(num, 16).toString(2) // 十六进制转二进制
parseInt(num, 16).toString(8) // 十六进制转八进制

/*
 * https://leetcode-cn.com/problems/repeated-substring-pattern/description/
 *
 * 给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
 *
 * 示例 1:
 *
 *
 * 输入: "abab"
 *
 * 输出: True
 *
 * 解释: 可由子字符串 "ab" 重复两次构成。
 *
 *
 * 示例 2:
 *
 *
 * 输入: "aba"
 *
 * 输出: False
 *
 *
 * 示例 3:
 *
 *
 * 输入: "abcabcabcabc"
 *
 * 输出: True
 *
 * 解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
 *
 *
 */

/**
 * @param {string} s
 * @return {boolean}
 */
var repeatedSubstringPattern = function(s) {
  const re = /^(\w+)\1+$/g
  return re.test(s)
}

const mpSort = ([...arr]) => {
  for (let i = arr.length, tmp; i > 0; i--) {
    for (let j = 0; j < i; j++) {
      tmp = arr[j]
      if (tmp > arr[j + 1]) {
        arr[j] = arr[j + 1]
        arr[j + 1] = tmp
      }
    }
  }
  return arr
}

const selectSort = ([...arr]) => {
  for (let i = 0, len = arr.length, minIndex; i < len; i++) {
    minIndex = i
    for (let j = i + 1; j < len; j++) {
      if (arr[minIndex] > arr[j]) { minIndex = j }
    }
    const c = arr[i]
    arr[i] = arr[minIndex]
    arr[minIndex] = c
  }
  return arr
}

/*
 * @lc app=leetcode.cn id=164 lang=javascript
 *
 * [164] 最大间距
 *
 * https://leetcode-cn.com/problems/maximum-gap/description/
 *
 * algorithms
 * Hard (52.83%)
 * Likes:    132
 * Dislikes: 0
 * Total Accepted:    12.8K
 * Total Submissions: 23.3K
 * Testcase Example:  '[3,6,9,1]'
 *
 * 给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
 *
 * 如果数组元素个数小于 2，则返回 0。
 *
 * 示例 1:
 *
 * 输入: [3,6,9,1]
 * 输出: 3
 * 解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
 *
 * 示例 2:
 *
 * 输入: [10]
 * 输出: 0
 * 解释: 数组元素个数小于 2，因此返回 0。
 *
 * 说明:
 *
 *
 * 你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。
 * 请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。
 *
 *
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumGap = function(nums) {
  if (nums.length < 2) { return 0 }
  let max = 0
  nums.sort((a, b) => (a - b))
  for (let i = 0; i < nums.length - 1; i++) {
    const c = nums[i + 1] - nums[i]
    if (max < c) { max = c }
  }
  return max
}
// @lc code=end

console.log('log => : maximumGap([1, 2, 3, 10])', maximumGap([1, 2, 3, 10]))

// 冒泡排序版
/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumGap = function(nums) {
  let max = 0
  if (nums.length < 2) { return max }
  for (let i = nums.length, tmp; i > 0; i--) {
    for (let j = 0; j < i; j++) {
      if (nums[j + 1] < nums[j]) {
        tmp = nums[j + 1]
        nums[j + 1] = nums[j]
        nums[j] = tmp
      }
    }
    const c = nums[i] - nums[i - 1]
    if (max < c) {
      max = c
    }
  }
  return max
}

/*
 * @lc app=leetcode.cn id=922 lang=javascript
 *
 * [922] 按奇偶排序数组 II
 *
 * https://leetcode-cn.com/problems/sort-array-by-parity-ii/description/
 *
 * algorithms
 * Easy (66.58%)
 * Likes:    84
 * Dislikes: 0
 * Total Accepted:    26.3K
 * Total Submissions: 39.2K
 * Testcase Example:  '[4,2,5,7]'
 *
 * 给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。
 *
 * 对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。
 *
 * 你可以返回任何满足上述条件的数组作为答案。
 *
 *
 *
 * 示例：
 *
 * 输入：[4,2,5,7]
 * 输出：[4,5,2,7]
 * 解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。
 *
 *
 *
 *
 * 提示：
 *
 *
 * 2 <= A.length <= 20000
 * A.length % 2 == 0
 * 0 <= A[i] <= 1000
 *
 *
 *
 *
 */

// @lc code=start
/**
 * @param {number[]} A
 * @return {number[]}
 */
var sortArrayByParityII = function(A) {
  A.sort()
  const arr = []
  for (let i = 0, oddIndex = 1, evenIndex = 0; i < A.length; i++) {
    if (A[i] % 2 === 0) {
      arr[evenIndex] = A[i]
      evenIndex += 2
    } else {
      arr[oddIndex] = A[i]
      oddIndex += 2
    }
  }
  return arr
}
// @lc code=end

console.log('log => : sortArrayByParityII([4, 2, 5, 7])', sortArrayByParityII([4, 2, 5, 7]))

/*
 * @lc app=leetcode.cn id=215 lang=javascript
 *
 * [215] 数组中的第K个最大元素
 *
 * https://leetcode-cn.com/problems/kth-largest-element-in-an-array/description/
 *
 * algorithms
 * Medium (60.36%)
 * Likes:    424
 * Dislikes: 0
 * Total Accepted:    101.7K
 * Total Submissions: 164.4K
 * Testcase Example:  '[3,2,1,5,6,4]\n2'
 *
 * 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 *
 * 示例 1:
 *
 * 输入: [3,2,1,5,6,4] 和 k = 2
 * 输出: 5
 *
 *
 * 示例 2:
 *
 * 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
 * 输出: 4
 *
 * 说明:
 *
 * 你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
 *
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
  return nums.sort((a, b) => b - a)[k - 1]
}
// @lc code=end

console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6, 7, 7, 8, 2, 3, 1, 1, 1, 10, 11, 5, 6, 2, 4, 7, 8, 5, 6], 2))

// 冒泡排序版
// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
  for (let i = nums.length, tmp; i > 0; i--) {
    for (let j = 0; j < i; j++) {
      if (nums[j + 1] < nums[j]) {
        tmp = nums[j + 1]
        nums[j + 1] = nums[j]
        nums[j] = tmp
      }
    }
    if (nums.length - i === k - 1) {
      return nums[i - 1]
    }
  }
  return 0
}
// @lc code=end

console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4))

/*
 * @lc app=leetcode.cn id=41 lang=javascript
 *
 * [41] 缺失的第一个正数
 *
 * https://leetcode-cn.com/problems/first-missing-positive/description/
 *
 * algorithms
 * Hard (37.27%)
 * Likes:    457
 * Dislikes: 0
 * Total Accepted:    44.8K
 * Total Submissions: 118.2K
 * Testcase Example:  '[1,2,0]'
 *
 * 给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
 *
 *
 *
 * 示例 1:
 *
 * 输入: [1,2,0]
 * 输出: 3
 *
 *
 * 示例 2:
 *
 * 输入: [3,4,-1,1]
 * 输出: 2
 *
 *
 * 示例 3:
 *
 * 输入: [7,8,9,11,12]
 * 输出: 1
 *
 *
 *
 *
 * 提示：
 *
 * 你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。
 *
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(nums) {
  nums = nums.filter(num => num > 0)
  nums.sort((a, b) => a - b) // 可以优化，没必要全部进行排序，边排边找答案就行
  if (!nums.length || nums[0] !== 1) {
    return 1
  }
  for (let i = 0; i < nums.length - 1; i++) {
    if (nums[i + 1] - nums[i] > 1) {
      return nums[i] + 1
    }
  }
    // return nums[nums.length - 1] + 1 // 等同于↓
  return nums.pop() + 1
}
// @lc code=end

console.log(firstMissingPositive([-1, 4, 2, 1, 9, 10]))

// 冒泡排序版
// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(nums) {
  nums = nums.filter(num => num > 0)
  if (nums.length === 0) { return 1 }
  for (let i = nums.length, tmp; i > 0; i--) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[j + 1]) {
        tmp = nums[j]
        nums[j] = nums[j + 1]
        nums[j + 1] = tmp
      }
    }
    if (i !== nums.length) {
      if (nums[i - 1] - nums[i] > 1) {
        return nums[i] + 1
      }
    } else {
      if (nums[i - 1] !== 1) { // 最后一位，最小的不是1， 直接返回1
        return 1
      }
    }
  }
  return nums.shift() + 1 // 排序完了还没满足，取最大的+1
}

// 二分法
const quickSort = (arr) => {
  if (arr.length < 1) return arr
  const midValue = arr.splice(Math.floor(arr.length / 2), 1)[0]
  const left = []
  const right = []
  arr.forEach((item) => {
    item > midValue ? right.push(item) : left.push(item)
  })
  return [...quickSort(left), midValue, ...quickSort(right)]
}

// 快排(书上的版本)
// P248
/**
 * 数组交换两个Index的值
 * @param {Array} array 数组
 * @param {Number} a 数组Index
 * @param {Number} b 数组Index
 */
function swap(array, a, b) {
  [array[a], array[b]] = [array[b], array[a]]
}

function partition(array, left, right) {
  // 基数: [0,1,2] // 0,2 => 1
  // 偶数: [0,1,2,3] // 0,3 => 1
  const pivot = array[Math.floor((left + right) / 2)] // 主元（取中间元素, 可以取其他位置)
  let i = left // 左指针，找大(停止循环)
  let j = right // 右指针，找小(停止循环)

  while (i <= j) { // 直到左右指针交汇
    while (array[i] < pivot) { // 左指针要找大(停止循环)，当遇到的比主元小，就一直向右移动
      i++
    }
    while (array[j] > pivot) { // 右指针要找小(停止循环)，当遇到的比主元大，就一直往左移动
      j--
    }
    if (i <= j) { // 左右指针都停止的时候(且左<=右)，交换左右指针所指的值
      swap(array, i, j)
      i++ // 左指针继续往右移动
      j-- // 右指针继续往左移动
      // PS: 如果i<=j 还是会继续移动指针，直到left > right
    }
  }
  return i // 返回左指针作为分隔
}

/**
 * 快速排序-递归
 * @param {Array} array 待排序数组
 * @param {Number} left 起始Index
 * @param {Number} right 结尾Index
 */
function quick(array, left, right) {
  let index
  if (array.length > 1) {
    index = partition(array, left, right)
    if (left < index - 1) {
      quick(array, left, index - 1) // 递归排序完左右左边的，才会排序右边的
    }
    if (index < right) {
      quick(array, index, right)
    }
  }
  return array
}

function quickSort(array) {
  return quick(array, 0, array.length - 1)
}

console.log('[3, 5, 1, 6, 4, 7, 2] => ', quickSort([3, 5, 1, 6, 4, 7, 2]))

function factorial(){
    let i = 0 // 执行了1次
    let re = 1 // 执行了1次
    for(;i < n; i++ ){ // 执行了n次
        re*= n // 执行了n次
    }
    return re // 执行了1次
}

/*
 * @lc app=leetcode.cn id=93 lang=javascript
 *
 * [93] 复原IP地址
 *
 * https://leetcode-cn.com/problems/restore-ip-addresses/description/
 *
 * algorithms
 * Medium (45.33%)
 * Likes:    229
 * Dislikes: 0
 * Total Accepted:    35K
 * Total Submissions: 75.5K
 * Testcase Example:  '"25525511135"'
 *
 * 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
 *
 * 示例:
 *
 * 输入: "25525511135"
 * 输出: ["255.255.11.135", "255.255.111.35"]
 *
 */

// @lc code=start
/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function(str) {
  // 保存所有符合条件的IP地址
  const r = []
  // 分四步递归处理ip分段
  const search = (cur, sub) => {
    if (str.length > 12) { return }
    if (cur.length === 4 && cur.join('') === str) {
      r.push(cur.join('.'))
    }
    const min = Math.min(sub.length, 3)
    for (let i = 0; i < min; i++) {
      const s = sub.substr(0, i + 1)
      if (s - 256 < 0) {
        search(cur.concat([s * 1]), sub.substr(i + 1))
      }
    }
  }
  search([], str)
  return r
}
// @lc code=end

/*
 * @lc app=leetcode.cn id=682 lang=javascript
 *
 * [682] 棒球比赛
 *
 * https://leetcode-cn.com/problems/baseball-game/description/
 *
 * algorithms
 * Easy (65.23%)
 * Likes:    112
 * Dislikes: 0
 * Total Accepted:    18.9K
 * Total Submissions: 28.5K
 * Testcase Example:  '["5","2","C","D","+"]'
 *
 * 你现在是棒球比赛记录员。
 * 给定一个字符串列表，每个字符串可以是以下四种类型之一：
 * 1.整数（一轮的得分）：直接表示您在本轮中获得的积分数。
 * 2. "+"（一轮的得分）：表示本轮获得的得分是前两轮有效 回合得分的总和。
 * 3. "D"（一轮的得分）：表示本轮获得的得分是前一轮有效 回合得分的两倍。
 * 4. "C"（一个操作，这不是一个回合的分数）：表示您获得的最后一个有效 回合的分数是无效的，应该被移除。
 *
 * 每一轮的操作都是永久性的，可能会对前一轮和后一轮产生影响。
 * 你需要返回你在所有回合中得分的总和。
 *
 * 示例 1:
 *
 * 输入: ["5","2","C","D","+"]
 * 输出: 30
 * 解释:
 * 第1轮：你可以得到5分。总和是：5。
 * 第2轮：你可以得到2分。总和是：7。
 * 操作1：第2轮的数据无效。总和是：5。
 * 第3轮：你可以得到10分（第2轮的数据已被删除）。总数是：15。
 * 第4轮：你可以得到5 + 10 = 15分。总数是：30。
 *
 *
 * 示例 2:
 *
 * 输入: ["5","-2","4","C","D","9","+","+"]
 * 输出: 27
 * 解释:
 * 第1轮：你可以得到5分。总和是：5。
 * 第2轮：你可以得到-2分。总数是：3。
 * 第3轮：你可以得到4分。总和是：7。
 * 操作1：第3轮的数据无效。总数是：3。
 * 第4轮：你可以得到-4分（第三轮的数据已被删除）。总和是：-1。
 * 第5轮：你可以得到9分。总数是：8。
 * 第6轮：你可以得到-4 + 9 = 5分。总数是13。
 * 第7轮：你可以得到9 + 5 = 14分。总数是27。
 *
 *
 * 注意：
 *
 *
 * 输入列表的大小将介于1和1000之间。
 * 列表中的每个整数都将介于-30000和30000之间。
 *
 *
 */

// @lc code=start
/**
 * @param {string[]} ops
 * @return {number}
 */
var calPoints = function(ops) {
  const score = []
  return ops.reduce((acc, current) => {
    if (current === 'C' && score.length !== 0) {
      const s = score.pop()
      return acc - s
    }
    if (current === 'D') {
      let s = 0
      if (score.length >= 1) {
        s = score[score.length - 1] * 2
      }
      score.push(s)
      return acc + s
    }
    if (current === '+') {
      let s = 0
      if (score.length >= 2) {
        s = score[score.length - 1] + score[score.length - 2]
      } else if (score.length === 1) {
        s = score[score.length - 1]
      }
      score.push(s)
      return acc + s
    }
    score.push(current * 1)
    return acc + current * 1
  }, 0)
}
// @lc code=end

calPoints(['5', '2', 'C', 'D', '+'])

// 没写完, 记录一下思路：
// 1. 转换原本二位数组矩阵的形式为
/**
 * 记录每一行连续1的起始位置和结束位置， 入栈保存
 [  
   [ [起始位置, 结束位置],[起始位置, 结束位置] ], // 第一行
   [ [起始位置, 结束位置],[起始位置, 结束位置] ], // 第二行
   [ [起始位置, 结束位置],[起始位置, 结束位置] ], // 第三行
 ],
 */

// 2. 弹出前两项做计算，结果入栈，递归计算

var maximalRectangle = function(matrix) {
  const re = /1{2,}/g
  const stack = matrix.map(item => {
    const arr = []
    const str = item.join('')
    let r = re.exec(str)
    while (r) {
      arr.push([r.index, r.index + r[0].length - 1])
      r = re.exec(str)
    }
    return arr
  })
  return stack
}

/*
 * @lc app=leetcode.cn id=622 lang=javascript
 *
 * [622] 设计循环队列
 *
 * https://leetcode-cn.com/problems/design-circular-queue/description/
 *
 * algorithms
 * Medium (39.67%)
 * Likes:    95
 * Dislikes: 0
 * Total Accepted:    25.6K
 * Total Submissions: 63K
 * Testcase Example:  '["MyCircularQueue","enQueue","enQueue","enQueue","enQueue","Rear","isFull","deQueue","enQueue","Rear"]\n' +
  '[[3],[1],[2],[3],[4],[],[],[],[4],[]]'
 *
 * 设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于
 * FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
 *
 *
 * 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
 *
 * 你的实现应该支持如下操作：
 *
 *
 * MyCircularQueue(k): 构造器，设置队列长度为 k 。
 * Front: 从队首获取元素。如果队列为空，返回 -1 。
 * Rear: 获取队尾元素。如果队列为空，返回 -1 。
 * enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
 * deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
 * isEmpty(): 检查循环队列是否为空。
 * isFull(): 检查循环队列是否已满。
 *
 *
 *
 *
 * 示例：
 *
 * MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
 *
 * circularQueue.enQueue(1);  // 返回 true
 *
 * circularQueue.enQueue(2);  // 返回 true
 *
 * circularQueue.enQueue(3);  // 返回 true
 *
 * circularQueue.enQueue(4);  // 返回 false，队列已满
 *
 * circularQueue.Rear();  // 返回 3
 *
 * circularQueue.isFull();  // 返回 true
 *
 * circularQueue.deQueue();  // 返回 true
 *
 * circularQueue.enQueue(4);  // 返回 true
 *
 * circularQueue.Rear();  // 返回 4
 *
 *
 *
 *
 * 提示：
 *
 *
 * 所有的值都在 0 至 1000 的范围内；
 * 操作数将在 1 至 1000 的范围内；
 * 请不要使用内置的队列库。
 *
 *
 */

// @lc code=start
/**
 * Initialize your data structure here. Set the size of the queue to be k.
 * @param {number} k
 */
var MyCircularQueue = function(k) {
  this.list = Array(k) // 每一项都是undefined
  this.max = k
  this.front = 0 // 队头指针(删除)
  this.rear = 0 // 队尾指针(插入)
}

/**
 * Insert an element into the circular queue. Return true if the operation is successful.
 * @param {number} value
 * @return {boolean}
 */
MyCircularQueue.prototype.enQueue = function(value) {
  if (this.isFull()) {
    return false
  }
  this.list[this.rear] = value
  this.rear = (this.rear + 1) % this.max
  return true
}

/**
 * Delete an element from the circular queue. Return true if the operation is successful.
 * @return {boolean}
 */
MyCircularQueue.prototype.deQueue = function() {
  const value = this.list[this.front]
  this.list[this.front] = undefined
  if (value !== undefined) {
    this.front = (this.front + 1) % this.max
    return true
  }
  return false
}

/**
 * Get the front item from the queue.
 * @return {number}
 */
MyCircularQueue.prototype.Front = function() {
  const val = this.list[this.front]
  if (val !== undefined) {
    return val
  }
  return -1
}

/**
 * Get the last item from the queue.
 * @return {number}
 */
MyCircularQueue.prototype.Rear = function() {
  const rear = this.rear - 1
  const val = this.list[rear < 0 ? this.max - 1 : rear]
  if (val !== undefined) {
    return val
  }
  return -1
}

/**
 * Checks whether the circular queue is empty or not.
 * @return {boolean}
 */
MyCircularQueue.prototype.isEmpty = function() {
  return this.rear === this.front && !this.list[this.front]
}

/**
 * Checks whether the circular queue is full or not.
 * @return {boolean}
 */
MyCircularQueue.prototype.isFull = function() {
  return this.rear === this.front && !!this.list[this.front]
}

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * var obj = new MyCircularQueue(k)
 * var param_1 = obj.enQueue(value)
 * var param_2 = obj.deQueue()
 * var param_3 = obj.Front()
 * var param_4 = obj.Rear()
 * var param_5 = obj.isEmpty()
 * var param_6 = obj.isFull()
 */
// @lc code=end

/*
 * @lc app=leetcode.cn id=621 lang=javascript
 *
 * [621] 任务调度器
 *
 * https://leetcode-cn.com/problems/task-scheduler/description/
 *
 * algorithms
 * Medium (46.82%)
 * Likes:    238
 * Dislikes: 0
 * Total Accepted:    18.5K
 * Total Submissions: 38.4K
 * Testcase Example:  '["A","A","A","B","B","B"]\n2'
 *
 * 给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26
 * 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU
 * 在任何一个单位时间内都可以执行一个任务，或者在待命状态。
 *
 * 然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
 *
 * 你需要计算完成所有任务所需要的最短时间。
 *
 *
 *
 * 示例 ：
 *
 * 输入：tasks = ["A","A","A","B","B","B"], n = 2
 * 输出：8
 * 解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
 *
 *
 *
 *
 * 提示：
 *
 *
 * 任务的总个数为 [1, 10000]。
 * n 的取值范围为 [0, 100]。
 *
 *
 */

// @lc code=start
/**
 * @param {character[]} tasks
 * @param {number} n
 * @return {number}
 */
var leastInterval = function(tasks, n) {
  const o = {}
  tasks.forEach(key => {
    if (o[key]) {
      o[key] += 1
    } else {
      o[key] = 1
    }
  })
  const Q = []
  while (1) {
    const keys = Object.keys(o)
    const q = []
    if (keys.length === 0) { break }
    keys.sort((a, b) => o[b] - o[a]) // 大到小排序，先执行任务数目较多的任务 #STU: 数组根据对象值排序 ~
    for (let i = 0; i <= n; i++) {
      const fkey = keys.shift() // #STU: 取第一项
      if (typeof fkey !== 'undefined') {
        q.push(fkey)
        if (o[fkey] <= 1) {
          delete o[fkey]
        } else {
          o[fkey] -= 1
        }
      } else {
        break
      }
    }
    if (q.length < n + 1) {
      Q.push(...q.join('').padEnd(n + 1, '-').split('')) // STU：补齐数组项至多少的长度
    } else {
      Q.push(...q)
    }
  }
  const queue = Q.join('').replace(/-+$/g, '') // STU: 删除末尾的-字符串
  return queue.length
}
// @lc code=end

console.log(leastInterval(['A', 'A', 'A', 'B', 'B', 'B'], 2))
console.log(leastInterval(['A', 'A', 'A', 'A', 'A', 'A', 'B', 'C', 'D', 'E', 'F', 'G'], 2))

/*
 * @lc app=leetcode.cn id=148 lang=javascript
 *
 * [148] 排序链表
 *
 * https://leetcode-cn.com/problems/sort-list/description/
 *
 * algorithms
 * Medium (63.08%)
 * Likes:    480
 * Dislikes: 0
 * Total Accepted:    52.5K
 * Total Submissions: 81K
 * Testcase Example:  '[4,2,1,3]'
 *
 * 示例 1:
 *
 * 输入: 4->2->1->3
 * 输出: 1->2->3->4
 *
 *
 * 示例 2:
 *
 * 输入: -1->5->3->4->0
 * 输出: -1->0->3->4->5
 *
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

function swap(p, q) {
  const val = p.val
  p.val = q.val // 做交换的时候, begin的值也会跟着变
  q.val = val
}

const partion = (begin, end = null) => {
  const val = begin.val
  let p = begin
  let q = begin.next
  while (q !== end) {
    if (q.val < val) {
      p = p.next
      swap(p, q)
    }
    q = q.next
  }
  // 让基准元素跑到中间去
  swap(p, begin)
  return p
}

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(begin, end) {
  if (begin !== end && begin !== null) {
    const part = partion(begin, end)
    // begin和end会在partion函数中被修改
    sortList(begin, part)
    sortList(part.next, end)
  }
  return begin
}
// @lc code=end

class Node {
  constructor(val) {
    this.val = val
    this.next = null
  }
}

class LinkList {
  constructor(arr) {
    const head = new Node(arr.shift())
    let next = head
    arr.forEach(num => {
      next.next = new Node(num)
      next = next.next
    })
    return head // this绑定到了返回的对象上
  }

  static toArray(list) {
    const arr = []
    while (list.next) {
      arr.push(list.val)
      list = list.next
    }
    return arr
  }
}

const list = new LinkList([6, 1, 2, 7, 9, 3, 4, 5, 10, 8])
sortList(list)
console.log('log => : ListNode', LinkList.toArray(list))

/*
 * @lc app=leetcode.cn id=141 lang=javascript
 *
 * [141] 环形链表
 *
 * https://leetcode-cn.com/problems/linked-list-cycle/description/
 *
 * algorithms
 * Easy (45.50%)
 * Likes:    552
 * Dislikes: 0
 * Total Accepted:    137.1K
 * Total Submissions: 289.3K
 * Testcase Example:  '[3,2,0,-4]\n1'
 *
 * 给定一个链表，判断链表中是否有环。
 *
 * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
 *
 *
 *
 * 示例 1：
 *
 * 输入：head = [3,2,0,-4], pos = 1
 * 输出：true
 * 解释：链表中有一个环，其尾部连接到第二个节点。
 *
 *
 *
 *
 * 示例 2：
 *
 * 输入：head = [1,2], pos = 0
 * 输出：true
 * 解释：链表中有一个环，其尾部连接到第一个节点。
 *
 *
 *
 *
 * 示例 3：
 *
 * 输入：head = [1], pos = -1
 * 输出：false
 * 解释：链表中没有环。
 *
 *
 *
 *
 *
 *
 * 进阶：
 *
 * 你能用 O(1)（即，常量）内存解决此问题吗？
 *
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
  const v = Symbol('v') // 唯一值法
  while (head) {
    if (head[v] === true) { return true }
    head[v] = true
    head = head.next
  }
  return false
}

// 双指针法, 一慢一快只要相遇，就是环形
var hasCycle = function(head) {
  try {
    let slow = head
    let fast = head.next
    while (true) {
      if (slow === fast) return true
      slow = slow.next
      fast = fast.next.next
    }
  } catch (e) {
    return false
  }
}

class Node {
  constructor(val) {
    this.val = val
    this.next = null
  }
}

class LinkList {
  constructor(arr) {
    const head = new Node(arr.shift())
    let next = head
    arr.forEach(num => {
      next.next = new Node(num)
      next = next.next
    })
    return head // this绑定到了返回的对象上
  }
}

const ListNode = new LinkList([4, 2, 1, 3])

function ListNode(val) {
  this.val = val
  this.next = null
}

function LinkList(arr) {
  const head = new ListNode(arr.shift())
  let next = head
  arr.forEach(num => {
    next.next = new ListNode(num)
    next = next.next
  })
  return head
}

const list = new LinkList([1, 2, 3])
console.log('log => : list', list)

/*
 * @lc app=leetcode.cn id=54 lang=javascript
 *
 * [54] 螺旋矩阵
 *
 * https://leetcode-cn.com/problems/spiral-matrix/description/
 *
 * algorithms
 * Medium (38.17%)
 * Likes:    336
 * Dislikes: 0
 * Total Accepted:    50.9K
 * Total Submissions: 129.2K
 * Testcase Example:  '[[1,2,3],[4,5,6],[7,8,9]]'
 *
 * 给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
 *
 * 示例 1:
 *
 * 输入:
 * [
 * ⁠[ 1, 2, 3 ],
 * ⁠[ 4, 5, 6 ],
 * ⁠[ 7, 8, 9 ]
 * ]
 * 输出: [1,2,3,6,9,8,7,4,5]
 *
 *
 * 示例 2:
 *
 * 输入:
 * [
 * ⁠ [1, 2, 3, 4],
 * ⁠ [5, 6, 7, 8],
 * ⁠ [9,10,11,12]
 * ]
 * 输出: [1,2,3,4,8,12,11,10,9,5,6,7]
 *
 *
 */

// @lc code=start
/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
  const map = (arr, r = []) => {
    for (let i = 0, len = arr.length; i < len; i++) {
      if (i === 0) {
        r = r.concat(arr[i]) // 先来第一行
      } else if (i === len - 1) {
        r = r.concat(arr[i].reverse()) // 最后一行翻转
      } else {
        if (arr[i].length !== 0) { r.push(arr[i].pop()) } // 最右边一列弹出 push
      }
    }
    arr.pop()
    arr.shift()
    // 第一行 最右边一列 最后一行，都有了，我们再来复制最左边一列
    for (let j = arr.length - 1; j >= 0; j--) {
      if (arr[j].length !== 0) { r.push(arr[j].shift()) }
    }
    if (arr.length !== 0) {
      return map(arr, r) // 上右下左 一圈一圈的递归
    }
    return r
  }

  return map(matrix)
}
// @lc code=end

console.log(spiralOrder([[1], [2], [3], [4], [5], [6], [7], [8], [9], [10]]))

/*
 * @lc app=leetcode.cn id=48 lang=javascript
 *
 * [48] 旋转图像
 *
 * https://leetcode-cn.com/problems/rotate-image/description/
 *
 * algorithms
 * Medium (66.31%)
 * Likes:    411
 * Dislikes: 0
 * Total Accepted:    65.5K
 * Total Submissions: 96.7K
 * Testcase Example:  '[[1,2,3],[4,5,6],[7,8,9]]'
 *
 * 给定一个 n × n 的二维矩阵表示一个图像。
 *
 * 将图像顺时针旋转 90 度。
 *
 * 说明：
 *
 * 你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
 *
 * 示例 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]
 * ]
 *
 *
 */

// @lc code=start
/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var rotate = function(matrix) {
  // 1. 垂直方向上下交换
  for (let i = 0, len = matrix.length, tmp; i < len / 2; i++) {
    tmp = matrix[i]
    matrix[i] = matrix[len - i - 1]
    matrix[len - i - 1] = tmp
  }

  // 2. 以-45°方向对角线交换两侧元素
  for (let i = 0, len = matrix.length, tmp; i < len; i++) {
    for (let j = 0; j < i; j++) {
      tmp = matrix[i][j]
      matrix[i][j] = matrix[j][i]
      matrix[j][i] = tmp
    }
  }
  // 大功告成!
  return matrix
}
// @lc code=end

console.log(rotate([
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]))

/*
 * @lc app=leetcode.cn id=101 lang=javascript
 *
 * [101] 对称二叉树
 *
 * https://leetcode-cn.com/problems/symmetric-tree/description/
 *
 * algorithms
 * Easy (49.47%)
 * Likes:    701
 * Dislikes: 0
 * Total Accepted:    117.7K
 * Total Submissions: 232.3K
 * Testcase Example:  '[1,2,2,3,4,4,3]'
 *
 * 给定一个二叉树，检查它是否是镜像对称的。
 *
 * 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
 *
 * ⁠   1
 * ⁠  / \
 * ⁠ 2   2
 * ⁠/ \ / \
 * 3  4 4  3
 *
 *
 * 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
 *
 * ⁠   1
 * ⁠  / \
 * ⁠ 2   2
 * ⁠  \   \
 * ⁠  3    3
 *
 *
 * 说明:
 *
 * 如果你可以运用递归和迭代两种方法解决这个问题，会很加分。
 *
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
  if (!root) return true
  const walk = (left, right) => {
    if (!left && !right) { return true }
    if ((left && !right) || (!left && right) || (left.val !== right.val)) { return false }
    return walk(left.left, right.right) && walk(left.right, right.left) // 递归
  }
  return walk(root.left, root.right)
}
// @lc code=end

/*
 * @lc app=leetcode.cn id=98 lang=javascript
 *
 * [98] 验证二叉搜索树
 *
 * https://leetcode-cn.com/problems/validate-binary-search-tree/description/
 *
 * algorithms
 * Medium (28.34%)
 * Likes:    501
 * Dislikes: 0
 * Total Accepted:    89.1K
 * Total Submissions: 299.8K
 * Testcase Example:  '[2,1,3]'
 *
 * 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
 *
 * 假设一个二叉搜索树具有如下特征：
 *
 *
 * 节点的左子树只包含小于当前节点的数。
 * 节点的右子树只包含大于当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 *
 *
 * 示例 1:
 *
 * 输入:
 * ⁠   2
 * ⁠  / \
 * ⁠ 1   3
 * 输出: true
 *
 *
 * 示例 2:
 *
 * 输入:
 * ⁠   5
 * ⁠  / \
 * ⁠ 1   4
 * / \
 * 3   6
 * 输出: false
 * 解释: 输入为: [5,1,4,null,null,3,6]。
 * 根节点的值为 5 ，但是其右子节点值为 4 。
 *
 *
 */

const { Tree } = require('./tree')

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root, min = -Infinity, max = Infinity) {
  if (!root) return true
  if (root.val <= min || root.val >= max) return false
  return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max)
}
// @lc code=end

const tree = new Tree([5, 1, 4, null, null, 3, 6])
const c = isValidBST(tree)
console.log('log => : c', c)

// 递归法
/*
 * @lc app=leetcode.cn id=226 lang=javascript
 *
 * [226] 翻转二叉树
 *
 * https://leetcode-cn.com/problems/invert-binary-tree/description/
 *
 * algorithms
 * Easy (73.19%)
 * Likes:    403
 * Dislikes: 0
 * Total Accepted:    68.2K
 * Total Submissions: 91.3K
 * Testcase Example:  '[4,2,7,1,3,6,9]'
 *
 * 翻转一棵二叉树。
 *
 * 示例：
 *
 * 输入：
 *
 * ⁠    4
 * ⁠  /   \
 * ⁠ 2     7
 * ⁠/ \   / \
 * 1   3 6   9
 *
 * 输出：
 *
 * ⁠    4
 * ⁠  /   \
 * ⁠ 7     2
 * ⁠/ \   / \
 * 9   6 3   1
 *
 * 备注:
 * 这个问题是受到 Max Howell 的 原问题 启发的 ：
 *
 * 谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
 *
 */
const { Tree } = require('./tree')
// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
  if (root === null) {
    return null
  }
  [root.left, root.right] = [invertTree(root.right), invertTree(root.left)]
  return root
}
// 等同于↑
var invertTree = function(root) {
  if (root === null) {
    return null
  }
  const right = invertTree(root.right)
  const left = invertTree(root.left)
  root.left = right
  root.right = left
  return root
}
// @lc code=end

const tree = new Tree([1, 2])
console.log('log => : tree', tree)
const invert = invertTree(tree)
console.log('log => : invert', invert)

// 构造完全二叉树

class Node {
  constructor(val) {
    this.val = val
    this.left = this.right = null
  }
}

class Tree {
  constructor(data) {
    const nodeList = []
    for (let i = 0, len = data.length; i < len; i++) {
      const node = new Node(data[i])
      nodeList.push(node)
      if (i > 0) {
        // 计算当前节点属于哪一层
        const n = Math.floor(Math.log2(i + 1))
        // 记录当前层的起始点
        const q = Math.pow(2, n) - 1
        // 记录上一层的起始点
        const p = Math.pow(2, n - 1) - 1
        // 找到当前节点的父节点
        const parent = nodeList[p + Math.floor((i - q) / 2)]
        // 将当前节点和上一层的父节点做关联
        if (parent.left) { // 因为是完全二叉树，所以可以这么判断填充
          parent.right = node
        } else {
          parent.left = node
        }
      }
    }
    const root = nodeList.shift()
    nodeList.length = 0
    return root
  }
}

const t = new Tree([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
console.log(t)

/**
 * 构建二叉搜索树
 */

class Node {
  constructor(val) {
    this.val = val
    this.left = this.right = null
  }
}

class SearchBTree {
  constructor(data) {
    if (data.length === 0) { return null }
    const root = new Node(data.shift())
    data.forEach(item => {
      this.insert(root, item)
    })
    return root
  }

  insert(node, val) {
    if (val < node.val) {
      if (!node.left) {
        node.left = new Node(val)
      } else {
        this.insert(node.left, val)
      }
    } else {
      if (!node.right) {
        node.right = new Node(val)
      } else {
        this.insert(node.right, val)
      }
    }
  }
}

const tree = new SearchBTree([10, 5, 15, 6, 20])
console.log(tree)

module.exports = {
  SearchBTree
}

var preorderTraversal = function(root) {
  var result = []
  function pushRoot(node) {
    if (node !== null) {
      result.push(node.val) // 前
      if (node.left !== null) { // 左
        pushRoot(node.left)
      }
      if (node.right !== null) { // 右
        pushRoot(node.right)
      }
    }
  }
  pushRoot(root)
  return result
}

var inorderTraversal = function(root) {
  var result = []
  function pushRoot(node) {
    if (node !== null) {
      if (node.left !== null) { // 左
        pushRoot(node.left)
      }
      result.push(node.val) // 根
      if (node.right !== null) { // 右
        pushRoot(node.right)
      }
    }
  }
  pushRoot(root)
  return result
}

var postorderTraversal = function(root) {
  const result = []
  const pushRoot = (node) => {
    if (node !== null) {
      if (node.left !== null) { // 左
        pushRoot(node.left)
      }
      if (node.right !== null) { // 右
        pushRoot(node.right)
      }
      result.push(node.val) // 根
    }
  }
  pushRoot(root)
  return result
}

const list = [
  {
    name: '1',
    children: [
      {
        name: '2',
        children: [
          { name: '3' },
          { name: '4', children: [{ name: '5' }, { name: '6' }] }
        ]
      },
      { name: '7', children: [{ name: '8', children: [{ name: '9' }] }] }
    ]
  }
]
// 深度遍历
function getName(data) {
  const result = []
  data.forEach((item) => {

    const map = (data) => {
      result.push(data.name)
      data.children &&
        data.children.forEach((child) => {
          map(child)
        })
    }

    map(item)
  })
  return result.join(',')
}
console.log(getName(list)) // 1,2,3,4,5,6,7,8,9

// 广度遍历上述list
function getName2(data) {
  let result = [];
  let queue = data;
  while (queue.length > 0) {
    [...queue].forEach(child => {
      queue.shift();
      result.push(child.name);
      child.children && (queue.push(...child.children));
    })
  }
  return result.join(',');
}
console.log(getName2(list)) // 1,2,7,3,4,8,5,6,9

/*
 * @lc app=leetcode.cn id=122 lang=javascript
 *
 * [122] 买卖股票的最佳时机 II
 *
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/description/
 *
 * algorithms
 * Easy (56.94%)
 * Likes:    659
 * Dislikes: 0
 * Total Accepted:    143.2K
 * Total Submissions: 244K
 * Testcase Example:  '[7,1,5,3,6,4]'
 *
 * 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
 *
 * 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
 *
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 *
 *
 *
 * 示例 1:
 *
 * 输入: [7,1,5,3,6,4]
 * 输出: 7
 * 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
 * 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
 *
 *
 * 示例 2:
 *
 * 输入: [1,2,3,4,5]
 * 输出: 4
 * 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4
 * 。
 * 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
 * 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
 *
 *
 * 示例 3:
 *
 * 输入: [7,6,4,3,1]
 * 输出: 0
 * 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
 *
 *
 *
 * 提示：
 *
 *
 * 1 <= prices.length <= 3 * 10 ^ 4
 * 0 <= prices[i] <= 10 ^ 4
 *
 *
 */

// @lc code=start
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
  let profit = 0
  // 今天相对昨天赚了，我今天就卖，明天能赚，我今天就买
  for (let i = 0; i < prices.length; i++) {
    if (prices[i] > prices[i - 1]) {
      profit += prices[i] - prices[i - 1]
    }
  }
  return profit
}
// @lc code=end

/*
 * @lc app=leetcode.cn id=860 lang=javascript
 *
 * [860] 柠檬水找零
 *
 * https://leetcode-cn.com/problems/lemonade-change/description/
 *
 * algorithms
 * Easy (53.44%)
 * Likes:    103
 * Dislikes: 0
 * Total Accepted:    19.3K
 * Total Submissions: 35.4K
 * Testcase Example:  '[5,5,5,10,20]'
 *
 * 在柠檬水摊上，每一杯柠檬水的售价为 5 美元。
 *
 * 顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
 *
 * 每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
 *
 * 注意，一开始你手头没有任何零钱。
 *
 * 如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
 *
 * 示例 1：
 *
 * 输入：[5,5,5,10,20]
 * 输出：true
 * 解释：
 * 前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
 * 第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
 * 第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
 * 由于所有客户都得到了正确的找零，所以我们输出 true。
 *
 *
 * 示例 2：
 *
 * 输入：[5,5,10]
 * 输出：true
 *
 *
 * 示例 3：
 *
 * 输入：[10,10]
 * 输出：false
 *
 *
 * 示例 4：
 *
 * 输入：[5,5,10,10,20]
 * 输出：false
 * 解释：
 * 前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
 * 对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
 * 对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
 * 由于不是每位顾客都得到了正确的找零，所以答案是 false。
 *
 *
 *
 *
 * 提示：
 *
 *
 * 0 <= bills.length <= 10000
 * bills[i] 不是 5 就是 10 或是 20
 *
 *
 */

// @lc code=start
/**
 * @param {number[]} bills
 * @return {boolean}
 */
var lemonadeChange = function(bills) {
  const hand = [] // 我目前有的钱
  while (bills.length !== 0) { // 当还有顾客
    const money = bills.shift() // 当前顾客给的钱
    if (money === 5) { // 顾客正好给了5元
      hand.push(money) // 直接把钱放进收钱箱
    } else {
      hand.sort((a, b) => b - a) // 顾客给的不是5元，把钱进行排序，先用大钱找零

      let change = money - 5 // 需要找给顾客的零钱
      for (let i = 0, len = hand.length; i < len; i++) { // 遍历钱箱里所有的钱
        if (change >= hand[i]) { // 要找的钱大于或等于现在箱子里拿出来的这张钱(大到小)
          change -= hand[i] // 先找零一张
          hand.splice(i, 1) // 钱箱子里找零后的这张钱就没了
          i--
        }
        if (change === 0) { // 找零成功了
          hand.push(money) // 顾客给的钱放进钱箱
          break // 结束这个顾客的找零
        }
      }

      if (change !== 0) { return false } // 如果结束找零了，顾客需要找零的钱还不是0，找零失败
    }
  }
  return true
}
// @lc code=end

/*
 * @lc app=leetcode.cn id=63 lang=javascript
 *
 * [63] 不同路径 II
 *
 * https://leetcode-cn.com/problems/unique-paths-ii/description/
 *
 * algorithms
 * Medium (32.22%)
 * Likes:    264
 * Dislikes: 0
 * Total Accepted:    52.6K
 * Total Submissions: 160.6K
 * Testcase Example:  '[[0,0,0],[0,1,0],[0,0,0]]'
 *
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
 *
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
 *
 * 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
 *
 *
 *
 * 网格中的障碍物和空位置分别用 1 和 0 来表示。
 *
 * 说明：m 和 n 的值均不超过 100。
 *
 * 示例 1:
 *
 * 输入:
 * [
 * [0,0,0],
 * [0,1,0],
 * [0,0,0]
 * ]
 * 输出: 2
 * 解释:
 * 3x3 网格的正中间有一个障碍物。
 * 从左上角到右下角一共有 2 条不同的路径：
 * 1. 向右 -> 向右 -> 向下 -> 向下
 * 2. 向下 -> 向下 -> 向右 -> 向右
 *
 *
 */

export default (arr, m, n) => {
  const dp = (m, n) => {
    // 检查起始或者目标元素是不是1（被占用了），如果起始或者最后那个格就是1，说明怎么都怎么不到那，直接返回0
    if (arr[m - 1][n - 1] === 1 || arr[0][0] === 1) {
      return 0
    }
    if (m === 2 && n === 2) {
      return (arr[1][1] === 1 || arr[1][0] + arr[0][1] === 2) ? 0 : (arr[1][0] === 1 || arr[0][1] === 1) ? 1 : 2
    } else if (m < 2 || n < 2) {
      if (m < 2) {
        return arr[m - 1].includes(1) ? 0 : 1
      } else {
        for (let i = 0; i < m; i++) {
          if (arr[i][0] === 1) {
            return 0
          }
        }
        return 1
      }
    } else {
      return dp(m - 1, n) + dp(m, n - 1)
    }
  }
  return dp(m, n)
}
// 下面的加了备忘录优化，但是还是超时。

// @lc code=start
/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function(obstacleGrid) {
  const m = obstacleGrid.length
  const n = obstacleGrid[0].length
  const cacheData = {}
  const getCache = (m, n) => {
    return cacheData[`${m}-${n}`]
  }
  const setCache = (m, n, val) => {
    cacheData[`${m}-${n}`] = val
    return val
  }
  const run = (m, n) => {
    const num = getCache(m, n)
    if (typeof num !== 'undefined') {
      return num
    }
    if (obstacleGrid[m - 1][n - 1] === 1 || obstacleGrid[0][0] === 1) {
      return setCache(m, n, 0)
    }
    if (m === 2 && n === 2) {
      return (obstacleGrid[1][1] === 1 || obstacleGrid[0][1] + obstacleGrid[1][0] === 2) ? setCache(m, n, 0)
        : (obstacleGrid[0][1] === 1 || obstacleGrid[1][0] === 1) ? setCache(m, n, 1)
          : setCache(m, n, 2)
    }
    if (m === 1 || n === 1) {
      if (m === 1) {
        return obstacleGrid[0].includes(1) ? setCache(m, n, 0) : setCache(m, n, 1)
      }
      if (n === 1) {
        return obstacleGrid.every(arr => {
          if (arr[0] === 1) {
            return false
          }
          return true
        }) ? setCache(m, n, 1) : setCache(m, n, 0)
      }
    }
    return run(m - 1, n) + run(m, n - 1)
  }
  return run(m, n)
}
// @lc code=end

uniquePathsWithObstacles([[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]])

/*
 * @lc app=leetcode.cn id=787 lang=javascript
 *
 * [787] K 站中转内最便宜的航班
 *
 * https://leetcode-cn.com/problems/cheapest-flights-within-k-stops/description/
 *
 * algorithms
 * Medium (34.97%)
 * Likes:    83
 * Dislikes: 0
 * Total Accepted:    5.1K
 * Total Submissions: 14.6K
 * Testcase Example:  '3\n[[0,1,100],[1,2,100],[0,2,500]]\n0\n2\n1'
 *
 * 有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。
 *
 * 现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。
 * 如果没有这样的路线，则输出 -1。
 *
 *
 *
 * 示例 1：
 *
 * 输入:
 * n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
 * src = 0, dst = 2, k = 1
 * 输出: 200
 * 解释:
 * 城市航班图如下
 *
 *
 * 从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。
 *
 * 示例 2：
 *
 * 输入:
 * n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
 * src = 0, dst = 2, k = 0
 * 输出: 500
 * 解释:
 * 城市航班图如下
 *
 *
 * 从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500，如图中蓝色所示。
 *
 *
 *
 * 提示：
 *
 *
 * n 范围是 [1, 100]，城市标签从 0 到 n - 1.
 * 航班数量范围是 [0, n * (n - 1) / 2].
 * 每个航班的格式 (src, dst, price).
 * 每个航班的价格范围是 [1, 10000].
 * k 范围是 [0, n - 1].
 * 航班没有重复，且不存在环路
 *
 *
 */

// @lc code=start
/**
 * @param {number} n
 * @param {number[][]} flights
 * @param {number} src
 * @param {number} dst
 * @param {number} K
 * @return {number}
 */
var findCheapestPrice = function(n, flights, src, dst, K) {
  const cheap = (flights, src, dst, k) => {
    const prev = flights.filter(f => f[1] === dst) // 所有能到达该城市的航班
    const min = Math.min.apply(null, prev.map(item => {
      if (item[0] === src && k > -1) { // 已经到达了起始站，说明符合（边界）
        return item[2]
      } else if (k === 0 && item[0] !== src) { // 如果已经超过了中转次数（边界2）
        return Number.MAX_SAFE_INTEGER // 返回一个超大值(技巧)
      } else {
        return item[2] + cheap(flights, src, item[0], k - 1) // 状态转移方程
      }
    }))
    return min
  }
  const min = cheap(flights, src, dst, K)
  return min >= Number.MAX_SAFE_INTEGER ? -1 : min
}
// @lc code=end

/*
 * @lc app=leetcode.cn id=5 lang=javascript
 *
 * [5] 最长回文子串
 *
 * https://leetcode-cn.com/problems/longest-palindromic-substring/description/
 *
 * algorithms
 * Medium (28.09%)
 * Likes:    1996
 * Dislikes: 0
 * Total Accepted:    230K
 * Total Submissions: 784.8K
 * Testcase Example:  '"babad"'
 *
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 *
 * 示例 1：
 *
 * 输入: "babad"
 * 输出: "bab"
 * 注意: "aba" 也是一个有效答案。
 *
 *
 * 示例 2：
 *
 * 输入: "cbbd"
 * 输出: "bb"
 *
 *
 */

// @lc code=start
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
  const n = s.length // n为初始字符串长度
  let res = ''
  const dp = Array.from(new Array(n), () => new Array(n).fill(0)) // 二维数组 dp[i][j] 字符串s从索引i到j的子串是否是回文串
  for (let i = n - 1; i >= 0; i--) {
    for (let j = i; j < n; j++) {
      // s[i] === s[j]：说明当前中心可以继续扩张，进而有可能扩大回文串的长度
      // j - i < 2：意即子串是一个长度为0或1的回文串
      dp[i][j] = s[i] === s[j] && (j - i < 2 || dp[i + 1][j - 1])
      if (dp[i][j] && j - i + 1 > res.length) {
        res = s.substring(i, j + 1)
      }
    }
  }
  return res
}
// @lc code=end

longestPalindrome('babad')