/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
// 双指针
// var reverseString = function(s) {
//     const n = s.length;
//     for (let left = 0, right = n - 1; left < right; left++, right--) {
//         [s[left], s[right]] = [s[right], s[left]]
//     }
// };

var reverseString = function(s) {
    let left = 0, right = s.length - 1
    while (left < right) {
        [s[left], s[right]] = [s[right], s[left]]
        left++
        right--
    }
}

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let max = ''

    for (let i = 0; i < s.length; i++) {
        helper(i, i)
        helper(i, i+1)
    }

    function helper(l, r) {
        while(l >= 0 && r < s.length && s[l] === s[r]) {
            l--
            r++
        }
        const maxStr = s.slice(l + 1, r - 1 + 1)
        if (maxStr.length > max.length) max = maxStr
    }

    return max
};

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    return +x.toString().split('').reverse().join('') === x;
};

/**
 * @param {number[]} nums
 * @return {number[][]}
 * 广度优先遍历
 * 深度优先遍历
 */
var permute = function(nums) {
 nums.sort((a, b) => a - b)
 const ans = []
 const dfs = (item = []) => {
  if (item.length === nums.length) return ans.push([...item])

  nums.forEach(num => {
   if (!item.includes(num)) {
    dfs([...item, num])
   }
  })
 }
 dfs()
 return ans
};

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
// 终止条件
// 获取链表中间节点
// 断开链表
// 合并有序链表
var sortList = function(head) {
    if (head === null || head.next === null) {
        return head
    }

    let midNode = getMiddleNode(head)
    let rightHead = midNode.next
    midNode.next = null

    let left = sortList(head)
    let right = sortList(rightHead)

    return mergeTwoLists(left, right)
};

// 利用快慢指针找到中间节点
var getMiddleNode = function (head) {
    if (head === null || head.next === null) {
        return head
    }
    let slow = head
    let fast = head.next.next

    while (fast !== null && fast.next !== null) {
        slow = slow.next
        fast = fast.next.next
    }

    return slow
}

// 合并两个有序链表
var mergeTwoLists = function (l1, l2) {
    const dummy = new ListNode()
    let cur = dummy
    while (l1 && l2) {
        if (l1.val < l2.val) {
            [cur.next, l1] = [l1, l1.next]
        } else {
            [cur.next, l2] = [l2, l2.next]
        }
        cur = cur.next
    }
    cur.next = l1 ? l1 : l2
    return dummy.next
}

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    const newNums = nums1.concat(nums2).sort((a, b) => a - b)
    const len = newNums.length
    if (len % 2 === 0) {
        return (newNums[len/2 - 1] + newNums[len/2]) / 2
    } else {
        return newNums[Math.floor(len/2)]
    }
};

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let temp = nums[0]
    let times = 1
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] === temp) {
            times++
        } else {
            times--
            if (times === 0) {
                temp = nums[i + 1]
                times = 1
                i++
            }
        }
    }
    return temp
};

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

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
// 假设链表为 1→2→3→∅，我们想要把它改成 ∅←1←2←3。
// 迭代
var reverseList = function(head) {
    let prev = null
    let curr = head
    while (curr) {
        [curr.next, prev, curr] = [prev, curr, curr.next]
    }
    return prev
};

// 递归
// var reverseList = function(head) {
//     if (head === null || head.next === null) {
//         return head
//     }

//     const nextHead = reverseList(head.next)
//     head.next.next = head
//     head.next = null
//     return nextHead
// }

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 * 二分搜索
 * 关键字：排序，搜索
 */
var search = function(nums, target) {
 let [left, right] = [0, nums.length - 1]
 
 while (left <= right) {
  const mid = (left + right) >>> 1
  if (nums[mid] === target) return mid

  if (nums[mid] > nums[right]) {
   if (nums[left] <= target && nums[mid] > target) right = mid - 1
   else left = mid + 1
  } else {
   if (nums[mid] < target && nums[right] >= target) left = mid + 1
   else right = mid - 1
  }
 }
 return -1
}

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    let ans = []
    const len = nums.length
    if (nums === null || len < 3) return ans
    nums.sort((a, b) => a - b)

    for (let i = 0; i < nums.length; i++) {
        if (nums[0] > 0) break
        if (i > 0 && nums[i] === nums[i-1]) continue
        let l = i + 1
        let r = len - 1
        while (l < r) {
            const sum = nums[i] + nums[l] + nums[r]
            if (sum === 0) {
                ans.push([nums[i], nums[l], nums[r]])
                while (l<r && nums[l] === nums[l+1]) l++
                while (l<r && nums[r] === nums[r-1]) r--
                l++
                r--
            }
            else if (sum < 0) l++
            else if (sum > 0) r--
        }
    }

    return ans
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    let slow = 0
    let fast = 0
    while (fast < nums.length) {
        if (nums[fast] !== nums[slow]) {
            slow++
            nums[slow] = nums[fast]
        }
        fast++
    }
    return slow + 1
};

// stack正常push，min_stack只会push需要入栈和栈顶中较小的元素
// stack正常pop，min_stack正常pop
// 返回stack栈顶元素
// 返回min_stack栈顶元素
var MinStack = function() {
    this.stack = [];
    this.min_stack = [Infinity]
};

MinStack.prototype.push = function(x) {
    this.stack.push(x)
    this.min_stack.push(Math.min(x, this.min_stack[this.min_stack.length - 1]))
};

MinStack.prototype.pop = function() {
    this.stack.pop()
    this.min_stack.pop()
};

MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1]
};

MinStack.prototype.getMin = function() {
    return this.min_stack[this.min_stack.length - 1]
};

/**
 * 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}
 */
// DFS
var maxPathSum = function(root) {
    let ans = -Infinity
    dfs(root)
    return ans

    function dfs(root) {
        if (!root) return 0
        let left = dfs(root.left)
        let right = dfs(root.right)
        ans = Math.max(ans, root.val + left + right)
        return Math.max(0, Math.max(left, right) + root.val)
    }
};

/**
 * @param {string} s
 * @return {number}
 */
var myAtoi = function(s) {
    const number = parseInt(str, 10)

    if (isNaN(number)) {
        return 0
    } else if (number < Math.pow(-2, 31) || number > Math.pow(2, 31) - 1) {
        return number < Math.pow(-2, 31) ? Math.pow(-2, 31) : Math.pow(2, 31) - 1
    } else {
        return number
    }
};

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
// 递归
// var mergeTwoLists = function(list1, list2) {
//     if (!list1) {
//         return list2
//     } else if (!list2) {
//         return list1
//     } else if (list1.val < list2.val) {
//         list1.next = mergeTwoLists(list1.next, list2)
//         return list1
//     } else {
//         list2.next = mergeTwoLists(list1, list2.next)
//         return list2
//     }
// }

// 迭代
var mergeTwoLists = function(list1, list2) {
    const dummy = new ListNode()
    let curr = dummy
    while (list1 && list2) {
        list1.val < list2.val
            ? [curr.next, list1] = [list1, list1.next]
            : [curr.next, list2] = [list2, list2.next]
        curr = curr.next
    }
    // curr.next = list1 ? list1 : list2
    curr.next = list1 ?? list2
    return dummy.next
}

/**
 * @param {number[]} nums
 * @return {number[]}
 */
// 从左往右遍历: 记录从左到当前位置前一位的乘积
// 从右往左遍历: 从左到当前位置前一位的乘积 乘上 右边元素的积
var productExceptSelf = function(nums) {
    const res = []
    res[0] = 1
    for (let i = 1; i < nums.length; i++) {
        res[i] = res[i - 1] * nums[i - 1]
    }
    let right = 1
    for (let j = nums.length - 1; j >= 0; j--) {
        res[j] *= right
        right *= nums[j]
    }
    return res
};

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
// 递归法实现子集枚举
// var subsets = function (nums) {
//     let result = []
//     let path = []
//     function backtracking(startIndex) {
//         result.push(path.slice())
//         for (let i = startIndex; i < nums.length; i++) {
//             path.push(nums[i])
//             backtracking(i + 1)
//             path.pop()
//         }
//     }
//     backtracking(0)
//     return result
// }

// DFS回溯思路
var subsets = function (nums) {
 const res = []
 const dfs = (index, list) => {
  res.push(list.slice())
  for (let i = index; i < nums.length; i++) {
   list.push(nums[i])
   dfs(i + 1, list)
   list.pop()
  }
 }
 dfs(0, [])
 return res
}

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    if (s.length % 2 !== 0) return false
    const map = {
        '(' : ')',
        '{' : '}',
        '[' : ']'
    };
    let stack = []
    for (let char of s) {
        if (map[char]) {
            stack.push(map[char])
        } else {
            let ret = stack.pop()
            if (ret !== char) {
                return false
            }
        }
    }
    return stack.length === 0
};

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
// 闭合为环
var rotateRight = function(head, k) {
    if (k === 0 || !head || !head.next) {
        return head
    }

    let len = 1
    let cur = head
    while (cur.next) {
        cur = cur.next
        len++;
    }

    cur.next = head
    k = len - k % len
    
    while (k--) {
        cur = cur.next
    }
    head = cur.next
    cur.next = null
    return head
};

/**
 * @param {number[]} prices
 * @return {number}
 */
// dp[5][0] = Math.max(dp[4][0], dp[4][1] + price[5]) // 卖
// dp[5][1] = Math.max(dp[4][1], dp[4][0] - price[5]) // 买
// 动态规划
var maxProfit = function(prices) {
    const n = prices.length;
    const dp = new Array(n).fill(0).map(() => new Array(2).fill(0))

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

// 贪心
// var maxProfit = function(prices) {
//     let ans = 0
//     let n = prices.length
//     for (let i = 1; i < n; i++) {
//         ans += Math.max(0, prices[i] - prices[i-1])
//     }
//     return ans
// }

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */

// var merge = function(nums1, m, nums2, n) {
//     for (let i = 0, len = nums1.length; i < len; i++) {
//         if (m === 0) {
//             nums1[len-1-i] = nums2[--n];
//         } else if (n === 0) {
//             break
//         } else {
//             nums1[len-1-i] = nums1[m-1] > nums2[n-1] ? nums1[--m] : nums2[--n]
//         }
//     }
// };

// 直接合并后排序
var merge = function(nums1, m, nums2, n) {
    nums1.splice(m, nums1.length - m, ...nums2)
    nums1.sort((a, b) => a - b)
}

/**
 * @param {number} capacity
 */
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 value = this.map.get(key)
  // 重新set，相当于更新到 map 最后
  this.map.delete(key)
  this.map.set(key, value)
  return value
 }
 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)
 }
};

/**

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
 let [pre, maxAns] = [0, nums[0]]
 nums.forEach((x) => {
  pre = Math.max(pre + x, x)
  maxAns = Math.max(maxAns, pre)
 })
 return maxAns
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
// 递归 
var lowestCommonAncestor = function(root, p, q) {
    if (p.val < root.val  && q.val < root.val) {
        return lowestCommonAncestor(root.left, p, q)
    }
    if (p.val > root.val && q.val > root.val) {
        return lowestCommonAncestor(root.right, p, q)
    }
    return root
};

// 迭代
// var lowestCommonAncestor = function(root, p, q) {
//     while (root) {
//         if (p.val < root.val && q.val < root.val) {
//             root = root.left
//         } else if (p.val > root.val && q.val > root.val) {
//             root = root.right
//         } else {
//             break
//         }
//     }
//     return root
// }

/**
 * @param {number} n
 * @return {boolean}
 */
// 二进制表示
// var isPowerOfTwo = function(n) {
//     return n > 0 && (n & (n - 1)) === 0
// };

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


var isPowerOfTwo = function(n) {
    if (n <= 0) return false
    return (n & (n-1)) === 0
};

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 * 思路：
 * 每一格的路径由其上一格和左一格决定。
 * 方法：动态规划
 * 动态方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]
 * 注意：对于第一行 dp[0][j]，或者第一列 dp[i][0]，由于都是在边界，所以只能为1
 * 建立m*n的矩阵，注意第0行和第0列元素均为1
 */
var uniquePaths = function(m, n) {
 const dp = new Array(m).fill(0).map(() => new Array(n).fill(0))

 for (let i = 0; i < m; i++) {
  dp[i][0] = 1
 }

 for (let j = 0; j < n; j++) {
  dp[0][j] = 1
 }

 for (let i = 1; i < m; i++) {
  for (let j = 1; j < n; j++) {
   dp[i][j] = dp[i-1][j] + dp[i][j-1]
  }
 }

 return dp[m-1][n-1]
}

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

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
// 快慢指针
// 快慢指针初始化指向 head
// 快指针走到末尾时停止
// 慢指针走一步，快指针走两步
// 快慢指针相遇，说明含有环
// 任一一节点指向头节点
// 同步向前进
// 返回入口节点
var detectCycle = function(head) {
    let slow = head
    let fast = head
    while (fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
        if (slow === fast) {
            fast = head
            while (fast !== slow) {
                fast = fast.next
                slow = slow.next
            }
            return fast
        }
    }
    return null
}

// 哈希表
// var detectCycle = function(head) {
//     const map = new Map()
//     let p = head
//     while (p) {
//         if (map.get(p)) return p
//         else {
//             map.set(p, p.val)
//             p = p.next
//         }
//     }
//     return null
// }

// var detectCycle = function(head) {
//     const set = new Set()
//     while (head) {
//         if (set.has(head)) return head
//         else {
//             set.add(head)
//             head = head.next
//         }
//     }
//     return null
// }

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let [l, r, ans] = [0, height.length - 1, 0]

    while (l < r) {
        let [lh, lr] = [height[l], height[r]]
        ans = Math.max(ans, Math.min(lh, lr) * (r - l))

        lh < lr ? l++ : r--
    }

    return ans
};

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

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
// 哈希集合
// var getIntersectionNode = function(headA, headB) {
//     const set = new Set()
//     let temp = headA
//     while (temp) {
//         set.add(temp)
//         temp = temp.next
//     }
//     temp = headB
//     while (temp) {
//         if (set.has(temp)) return temp
//         temp = temp.next
//     }
//     return null
// }

// 哈希集合
// var getIntersectionNode = function(headA, headB) {
//     const map = new Map()
//     let temp = headA
//     while (temp) {
//         map.set(temp)
//         temp = temp.next
//     }
//     temp = headB
//     while (temp) {
//         if (map.has(temp)) return temp
//         temp = temp.next
//     }
//     return null
// }

// 双指针
var getIntersectionNode = function(headA, headB) {
    if (headA === null || headB === null) return null
    let pA = headA, pB = headB
    while (pA !== pB) {
        pA = pA === null ? headB : pA.next
        pB = pB === null ? headA : pB.next
    }
    return pA
}

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function(num1, num2) {
 if (num1 === '0' || num2 === '0') return '0'
 let len1 = num1.length, len2 = num2.length, res = new Array(len1 + len2).fill(0)
 for (let i = len1 - 1; i >= 0; i--) {
  for (let j = len2 - 1; j >= 0; j--) {
   const mul = num1[i] * num2[j]
   const p1 = i + j, p2 = i + j + 1
   const sum = mul + res[p2]
   res[p1] += Math.floor(sum / 10)
   res[p2] = sum % 10
  }
 }
 if (res[0] === 0) res.shift()
 return res.join('')
};

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
    let ans = nums[0] + nums[1] + nums[2]
    if (nums.length === 3) return ans
    nums.sort((a, b) => a - b)
    let len = nums.length

    for (let i = 0; i < len; i++) {
        let l = i + 1
        let r = len - 1
        while (l < r) {
            let tempNum = nums[i] + nums[l] + nums[r]
            if (Math.abs(target - tempNum) < Math.abs(target - ans)) {
                ans = tempNum
            }
            if (tempNum > target) {
                r--
            } else if (tempNum < target) {
                l++
            } else {
                return tempNum
            }
        }
    }

    return ans
};

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    let re = strs[0] || ''
    if (strs.length === 1) return strs[0]

    for (let i = 1; i < strs.length; i++) {
        while (strs[i].slice(0, re.length) !== re) {
            re = re.slice(0, re.length - 1)
        }
    }

    return re
};

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
// 数组排序，取第 k 个数
// var findKthLargest = function (nums, k) {
//     nums.sort((a, b) => b - a).slice(0, k)
//     return nums[k - 1]
// };

// 构造前 k 个最大元素小顶堆，取堆顶
// 从数组中取出 k 个元素构造一个小顶堆，然后将其余元素与小顶堆对比，如果大于堆顶则替换堆顶，然后堆化，所有元素遍历完成后，堆中的堆顶即为第 k 个最大值
var findKthLargest = function (nums, k) {
    let heap = [,], i = 0
    while (i < k) {
        heap.push(nums[i++])
    }
    buildHeap(heap, k)

    for (let i = k; i < nums.length; i++) {
        if (heap[1] < nums[i]) {
            heap[1] = nums[i]
            heapify(heap, k, 1)
        }
    }
    return heap[1]
};

let buildHeap = (arr, k) => {
    if (k === 1) return
    for (let i = Math.floor(k/2); i>=1; i--) {
        heapify(arr, k, i)
    }
}

let heapify = (arr, k, i) => {
    while(true) {
        let minIndex = i
        if (2*i <= k && arr[2*i] < arr[i]) {
            minIndex = 2*i
        }
        if (2*i+1 <= k && arr[2*i+1] <arr[minIndex]) {
            minIndex = 2*i + 1
        }
        if (minIndex !== i) {
            swap(arr, i, minIndex)
            i = minIndex
        } else {
            break
        }
    }
}

let swap = (arr, i, j) => {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    return s.split(' ').map(item => {
        return item.split('').reverse().join('')
    }).join(' ')
};

/**
 * @param {number[]} prices
 * @return {number}
 */
// 买入卖出各一次
//  贪心
// var maxProfit = function(prices) {
//     if (prices.length === 0) return 0

//     let min = prices[0]
//     let max = 0

//     for (let p of prices) {
//         min = Math.min(min, p)
//         max = Math.max(max, p - min)
//     }

//     return max
// }

// 动态规划 时间复杂度O(n) 空间复杂度O(n)，dp数组第二维是常数
var maxProfit = function(prices) {
    let n = prices.length
    let dp = new Array(n).fill(0).map(() => new Array(2));

    dp[0][0] = 0
    dp[0][1] = -prices[0]

    for (let i = 1; i < n; i++) {
        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i])
        dp[i][1] = Math.max(dp[i-1][1], - prices[i])
    }

    return dp[n-1][0]
}

// 压缩空间
// var maxProfit = function(prices) {
//     let n = prices.length
//     let dp = Array.from(new Array(n), () => new Array(2))

//     dp[0] = 0
//     dp[1] = -prices[0]

//     for (let i = 1; i < n; i++) {
//         dp[0] = Math.max(dp[0], dp[1] + prices[i])
//         dp[1] = Math.max(dp[1], -prices[i])
//     }
//     return dp[0]
// }

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
// 和下一个节点交换
var deleteNode = function(node) {
    node.val = node.next.val
    node.next = node.next.next
};

/**
 * 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
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function (root, k) {
    let res
    let count = 0
    function traversal(node) {
        if (node !== null) {
            if (count < k) traversal(node.left)
            if (++count === k) res = node.val
            if (count < k) traversal(node.right)
        }
    }
    traversal(root)
    return res
}
// var kthSmallest = function(root, k) {
//     let arr = []
//     function traversal (node) {
//         if (node !== null && arr.length < k) {
//             traversal(node.left)
//             arr.push(node.val)
//             traversal(node.right)
//         }
//     }
//     traversal(root)
//     return arr[k-1]
// };

/**
 * @param {number[]} nums
 * @return {boolean}
 */
// 排序
// var containsDuplicate = function(nums) {
//     nums.sort((a, b) => a - b)
//     const n = nums.length
//     for (let i = 0; i < n - 1; i++) {
//         if (nums[i] === nums[i + 1]) {
//             return true
//         }
//     }
//     return false
// };


// 哈希表
var containsDuplicate = function(nums) {
    const set = new Set()
    for (let x of nums) {
        if (set.has(x)) return true
        set.add(x)
    }
    return false
};

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    let dummy = new ListNode()
    let curr = dummy
    let carry = 0

    while (l1 || l2) {
        const x = l1 ? l1.val : 0
        const y = l2 ? l2.val : 0

        const total = x + y + carry
        curr.next = new ListNode(total % 10)
        curr = curr.next
        carry = Math.floor(total / 10)

        if (l1) l1 = l1.next
        if (l2) l2 = l2.next
    }
    if (carry) curr.next = new ListNode(carry)

    return dummy.next
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
// 递归
var lowestCommonAncestor = function(root, p, q) {
    if (root === null || root === p || root === q) {
        return root
    }

    const left = lowestCommonAncestor(root.left, p, q)
    const right = lowestCommonAncestor(root.right, p, q)

    if (left === null) return right
    if (right === null) return left

    return root
};

/**
 * @param {number[]} nums
 * @return {number}
 */
// var singleNumber = function(nums) {
//     let ans = 0;
//     for(const num of nums) {
//         ans ^= num;
//     }
//     return ans;
// };

var singleNumber = function(nums) {
    return nums.reduce((pre, cur) => {
        return pre ^ cur;
    }, 0)
}

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

/**
 * @param {ListNode} head
 * @return {boolean}
 */
// 快慢指针
// 快慢指针初始化指向 head
// 快指针走到末尾时停止
// 慢指针走一步，快指针走两步
// 快慢指针相遇，说明含有环，否则不含有环
var hasCycle = function(head) {
    let slow = head
    let fast = head
    while (fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
        if (slow === fast) {
            return true
        }
    }
    return false
}

// 哈希表
// var hasCycle = function(head) {
//     const map = new Map()
//     let p = head
//     while (p) {
//         if (map.get(p)) return true
//         else {
//             map.set(p, p.val)
//             p = p.next
//         }
//     }
//     return false
// }

/**
 * @param {number} n
 * @return {number}
 * 题目分析:
 * 第1级台阶：1种方法（爬1级）
 * 第2级台阶：2种方法（爬1级或爬2级）
 * 第n级台阶：dp[i] = dp[i-1] + dp[i-2]
 */
// 动态规划
// 滚动数组**
// var climbStairs = function(n) {
//     if (n === 1) return 1
//     if (n === 2) return 2
//     let [pre, cur, sum] = [1, 1, 2]
//     for (let i = 3; i <= n; i++) {
//         [pre, cur] = [cur, sum]
//         sum = pre + cur
//     }
//     return sum
// }

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

/**
 * 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 maxDepth = function(root) {
    let res = 0
    function traversal (root, depth) {
        if (root) {
            if (depth > res) {
                res = depth
            }
            if (root.left) {
                traversal (root.left, depth + 1)
            }
            if (root.right) {
                traversal (root.right, depth + 1)
            }
        }
    }
    traversal(root, 1)
    return res
};

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 * 递归合并链表+两两合并
 */
var mergeKLists = function(lists) {
    if (!lists.length) return null
    function merge(l1, l2) {
        if (!l1) return l2
        if (!l2) return l1
        if (l1.val < l2.val) {
            l1.next = merge(l1.next, l2)
            return l1
        } else {
            l2.next = merge(l1, l2.next)
            return l2
        }
    }
    return lists.reduce((pre, cur) => merge(pre, cur))
}

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {
    let result = 0

    while(x) {
        result = result * 10 + x % 10
        x = x / 10 | 0
    }

    return (result | 0) === result ? result : 0
};

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
    let n = []
    while (matrix.length) {
        n = _.concat(n, matrix.shift())
        matrix = _.reverse(_.zip(...matrix))
    }
    return n
};

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
    let left = 0
    let right = n - 1
    let bottom = n - 1
    let top = 0
    const total = n * n

    const dep = []

    for (let i = 0; i < n; i++) {
        dep[i] = []
    }

    let count = 0

    while (count < total) {
        for (let i = left; i <= right; i++) dep[left][i] = ++count
        top++
        for (let i = top; i <= bottom; i++) dep[i][right] = ++count
        right--
        for (let i = right; i >= left; i--) dep[bottom][i] = ++count
        bottom--
        for (let i = bottom; i >= top; i--) dep[i][left] = ++count
        left++
    }

    return dep
};