/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function(nums) {
  let i = nums.length - 2
  while(i >= 0 && nums[i] >= nums[i + 1]) i--
  // console.log(i)

  if(i >= 0){
    let j = nums.length - 1
    while(j >= 0 && nums[j] <= nums[i]) j--
    [nums[i], nums[j]] = [nums[j], nums[i]]
  } 

  let left = i + 1, right = nums.length - 1
  while(left < right) {
    [nums[left], nums[right]] = [nums[right], nums[left]]
    left ++
    right --
  }
};

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
  let l = 0, r = nums.length - 1
  // 找出分界点
  while(l < r){
    let mid = Math.floor((l + r) / 2)
    if(nums[mid] >= nums[0]) l = mid + 1
    else r = mid
  }

  // 分两次查找
  let ans1 = find(target, nums, 0, l)
  if(ans1 !== -1) return ans1
  let ans2 = find(target, nums, l, nums.length)
  return ans2
  
  function find(key, arr, left, right){
    let l = left, r = right - 1
    while(l <= r){
      let mid = Math.floor((l + r) / 2)
      if(arr[mid] > key) r = mid - 1
      else if(arr[mid] < key) l = mid + 1
      else return mid
    }
    return -1
  }

};

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
  let l = 0, r = nums.length
  while(l < r){
    let mid = Math.floor((l + r) / 2)
    if(nums[mid] >= target) r = mid
    else l = mid + 1
  }
  if(nums[l] !== target) return [-1, -1]
  let ans1 = l
  l = 0, r = nums.length

  while(l < r){
    let mid = Math.floor((l + r) / 2 + 1)
    if(nums[mid] <= target) l = mid
    else r = mid - 1
  } 
  
  return [ans1, l] 
};

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
  let ans = []
  var arrs = new Array()
  function dfs(can, tar, num, ans, start){
    if(start === can.length) return
    if(num < tar){
        ans.push(can[start])
        dfs(can, tar, num + can[start], ans, start)
        ans.pop()

        if(start + 1 < can.length) dfs(can, tar, num, ans, start + 1)
    }
    else if(num >= tar) {
      if(num === tar) {
        arrs.push(ans.slice())
      }
      return 
    }
  }
  dfs(candidates, target, 0, ans, 0)
  return arrs
};

function add(x,y){  
   alert(x+y) 
}  
add(1,2) //弹窗显示：3  

add(1,2); //弹窗显示：3  
function add(x,y){  
    alert(x+y) 
}  

function Person() {}
   var person = new Person()
   console.log(person.__proto__ === Person.prototype)//true
   console.log(Person.prototype.constructor===Person)//true

/**
 * 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 === null) return list2
  else if(list2 === null) return list1
  else if(list1.val > list2.val) {
    list2.next = mergeTwoLists(list1, list2.next)
    return list2
  }
  else {
    list1.next = mergeTwoLists(list1.next, list2)
    return list1
  }
};

//自己的原始想法
/**
 * 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 === null) return list2
  if(list2 === null) return list1
  let head = new ListNode(-1)
  let i = head
  while(list1 || list2){
    let num1 = list1 ? list1.val : 1000
    let num2 = list2 ? list2.val : 1000
    let num = Math.min(num1, num2)
    if(num === num1) list1 = list1.next
    else list2 = list2.next

    i.next = new ListNode(num)
    i = i.next
  }
  return head.next
};

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
  let ans = []
  let dfs = (str, i, j, n) => {
    
    if(i < n && i >= j) dfs(str + '(', i + 1, j, n)
    if(j < n && i > j) dfs(str + ')', i, j + 1, n)
    if(i === n && j === n) {
      ans.push(str)
      return
    }
  }

  dfs('', 0, 0, n)
  return ans
};

<script>
console.log("Start");

setTimeout(function(){
	console.log("SetTimeout");
},0);

new Promise(function(resolve,reject){
	console.log("Promise");
	resolve();
}).then(function(){
	console.log("Then");
});

console.log("End");
<script>

async function async1() {
  console.log('async1 start');
  await async2();
  console.log('async1 end');
}
async function async2() {
  console.log('async2');
}
console.log('script start');
setTimeout(function() {
    console.log('setTimeout1');
}, 200);
setTimeout(function() {
    console.log('setTimeout2');
    new Promise(function(resolve) {
        resolve();
    }).then(function() {
        console.log('then1')
    })
    new Promise(function(resolve) {
        console.log('Promise1');
        resolve();
    }).then(function() {
        console.log('then2')
    })
},0)
async1();
new Promise(function(resolve) {
    console.log('promise2');
    resolve();
  }).then(function() {
    console.log('then3');
  });
console.log('script end');

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let n = s.length
    if (n < 2) return s
    let begin = 0, maxLen  = 1

    const arr = new Array(n).fill(false).map(() => new Array(n).fill(false))
    for(let i = 0; i < n; i++) arr[i][i] = true
    // L为枚举长度
    for(let L = 2; L <= n; L++){
        for(let i = 0; i < n; i++){
            // 由于 j - i + 1 = L
            let j = L + i - 1
            // 如果长度超出, 则break
            if(j >= n) break

            if(s[i].charCodeAt() !== s[j].charCodeAt()){
                arr[i][j] = false
            }
            else {
                if(j - i < 3) arr[i][j] = true
                else arr[i][j] = arr[i + 1][j - 1]
            }
            if(arr[i][j] && j - i + 1 > maxLen){
                maxLen = j - i + 1
                begin = i
            }
        }
    }
    return s.substr(begin, maxLen)
};

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    function sum (h, t) {
        return (t - h) * Math.min(height[h], height[t])
    }

    let n = height.length
    if(n < 3) return Math.min(height[0], height[1])
    let head = 0, tail = n - 1
    let maxSize = sum(head, tail)
    while(head < tail){
        if(height[head] < height[tail]) {
          maxSize = Math.max(sum(head + 1, tail), maxSize) 
          ++head
        }
        else  {
          maxSize = Math.max(sum(head, tail - 1), maxSize) 
          --tail
        }
    }
    return maxSize
};

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
  let ans = []
  let n = nums.length
  if(n < 3) return ans
  //排序后就能用双指针了
  nums.sort((a, b) => a - b)
  // 固定第一个数
  for(let i = 0; i < n; i++){
    if(nums[i] > 0) return ans

    if(i > 0 && nums[i] === nums[i - 1]) continue
    
    // 双向遍历, 双指针必要条件之一
    let left = i + 1, right = n - 1

    while(left < right){
      // 大了就right--
      if(nums[left] + nums[right] > -nums[i]) --right
      // 小了就left++
      else if(nums[left] + nums[right] < -nums[i]) ++left
      // 正好满足条件, 保存答案, 移动左右指针一格
      else {
        ans.push([nums[left], nums[right], nums[i]])
        
        ++left
        --right

        // 第二 第三个数也不能重复
        while(left < right && nums[left] === nums[left - 1]) left++
        while(left < right && nums[right] === nums[right + 1]) right-- 
      }
    }
  }
  return ans
};

// dfs

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
  // 初始化数据
  const board = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
  const ans = [], n = digits.length
  // 构建递归函数, 另一种构造函数方法
  const dfs = (letter, i) => {
    if(n === i) 
    {
      ans.push(letter)
      return
    }
      // 展开数组写法
    let s = [...board[parseInt(digits[i])]]

    i++
    for(item of s){
      dfs(letter + item, i)
    }
  }
  // 递归入口
  dfs('', 0)
  // 判断结果长度, 为1则证明是空数组
  return ans.length < 2 ? [] : ans
};

// bfs

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
  const board = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']

  // 创建队列
  let que = ['']
  
  // 广搜的层数
  for(let i = 0; i < digits.length; i++){
    let curNum = que.length   //当前队列中的元素个数
    let newQue = []
    for(let j = 0; j < curNum; j++){
      let newLetter = que.shift() //取出第一个字符串

      for(idx of board[parseInt(digits[i])]){
        newQue.push(newLetter + idx)    //放入新数组
      }
    }
    // 指向新数组
    que = newQue
  }
  return que.length < 2 ? [] : que
};

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
  // 建立映射
  const rules = new Map([['(', ')'], ['{', '}'], ['[', ']']])
  const stk = []  //模拟栈
  for(i of s){
    if(i === '(' || i === '[' || i === '{') stk.push(i)
    else {
      if(stk.length === 0) return false
      else {
        let pop = stk.pop()
        if(i !== rules.get(pop)) return false
      }
    }
  }
  // 如果栈不为空 错误
  if(stk.length !== 0) return false
  return true
};

var flatten = function(root) {
    const list = [];
    dfs(root, list);
    const size = list.length;
    for(let i = 1; i < size; i++){
        const pre = list[i - 1], cur = list[i];
        pre.left = null;
        pre.right = cur;
    }
};

const dfs = (root, list) => {
    if(root == null) return;
    list.push(root);
    dfs(root.left, list);
    dfs(root.right, list);
}

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    
    const p = new Array(128).fill(0);
    const a = 0;
    let res = 0;
    for(let i = 0, j = 0; i < s.length; i++){
        p[s.charCodeAt(i)]++;
        while(p[s.charCodeAt(i)] > 1){
            p[s.charCodeAt(j)]--;
            j++;
        }
        res = Math.max(i - j + 1, res);
        
    }
    return res;
};

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function(cost) {
    if(cost.length == 2) return Math.min(cost[0], cost[1]);
    
    for(let i = 2; i < cost.length; i++){
        cost[i] += Math.min(cost[i - 1], cost[i - 2]);
    }
    return Math.min(cost[cost.length - 1], cost[cost.length - 2]);
};

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
// 二维数组版本
var uniquePaths = function(m, n) {
    const f = new Array(m).fill(0).map(() => new Array(n).fill(0));
    for(let i = 0; i < m; i++) f[i][0] = 1;
    for(let i = 0; i < n; i++) f[0][i] = 1;

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

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    const f = new Array(n).fill(0);
    //定义一个n列的数列
    
    for(let i = 0; i < n; i++) f[i] = 1;
    //初始时所有的格子路径数为1
    
    for(let i = 1; i < m; i++){
        //m次循环
        for(let j = 1; j < n; j++){
            //更新n列,  每次都是在上次的基础上相加
            f[j] += f[j - 1];
        }
    }
    return f[n - 1];
};