SOURCE

const containsDuplicate = function(nums) {
    let map = new Map();
    for(let i of nums){
        if(map.has(i)){
            return true;
        }else{
            map.set(i, 1);
        }
    }
    return false;
};

// const nums = [1, 2, 3, 1];
// console.log(containsDuplicate(nums));

var firstUniqChar = function(s) {
    const map = {};
    for(let v of s) {
        map[v] = (map[v] || 0) + 1;
    }
    for(let i = 0; i < s.length; i++) {
        if(map[s[i]] === 1) {
            return i;
        }
    }
    return -1;
};

// const s = "loveleetcode";
// console.log(firstUniqChar(s));


var isAnagram = function(s, t) {
  const sLen = s.length;
  const tLen = t.length;
  if(sLen !== tLen ) {
      return false;
  }
  const obj = {};
  for(let i = 0 ; i < sLen ; i++){
      const currentS = s[i];
      const currentT = t[i];
      obj[currentS] ? obj[currentS]++ : obj[currentS] = 1;
      obj[currentT] ? obj[currentT]-- : obj[currentT] = -1;
  }
  return Object.values(obj).every(v => v === 0);
};

// let s = "anagram", t = "nagaram";
// console.log(isAnagram(s, t));


var majorityElement = function(nums) {
  const map = {}
  const n = nums.length / 2;
  for(let i = 0; i < nums.length; i++){
      map[nums[i]] = map[nums[i]] !== undefined ? map[nums[i]] + 1 : 1;
      if(map[nums[i]] > n) {
          return nums[i];
      }
  }
}

// let nums = [1, 3, 1, 3, 1];

// console.log(majorityElement(nums));


let singNum = function(nums) {
    let mapObj = {};
    nums.forEach(item => {
        mapObj[item] ? mapObj[item] += 1 : mapObj[item] = 1;
    })
    // console.log(mapObj);
    for (let [key, val] of Object.entries(mapObj)) {
        if(val === 1) {
            return key;
        }
    }
}

// let arr1 = [4,1,2,1,2];
// console.log(singNum(arr1));


var twoSum = function(nums, target) {
    const map = new Map();
    for(let i = 0, len = nums.length; i < len; i++){
        if(map.get(nums[i]) !== undefined){
            return [map.get(nums[i]), i];
        }
        map.set(target - nums[i], i);
    }
    return [];
};

// let nums = [2,7,11,15], target = 9;
// console.log(twoSum(nums, target));

var intersection = function(nums1, nums2) {
    const map = {};
    const ret = [];
    for(let i = 0; i < nums1.length; i++){
        map[nums1[i]] = true;
    }
    for(let i = 0; i < nums2.length; i++){
        if(map[nums2[i]]){
            ret.push(nums2[i]);
            map[nums2[i]] = false;
        }
    }
    return ret;
};

// let nums1 = [4,9,5], nums2 = [9,4,9,8,4];
// console.log(intersection(nums1, nums2));

var romanToInt = function(s) {
    const map = {
        I: 1,
        V: 5,
        IV: 4,
        IX: 9,
        X: 10,
        XL: 40,
        XC: 90,
        L: 50,
        C: 100,
        CD: 400,
        CM: 900,
        D: 500,
        M: 1000,
    }
    let res = 0;
    let index = 0;
    let len = s.length;
    while(index < len){
        if(index + 1 < len && map[s.slice(index, index+2)]){
            res += map[s.slice(index, index+2)];
            index += 2;
            console.log('111---', index);
        }
        else {
            res += map[s.slice(index, index+1)];
            index += 1;
            console.log('2222---', index);
        }
    }
    return res;
};

let s = "LVIXI";
// console.log(romanToInt(s));

// 这个是求出两个元素最长公共前缀的方法
var longestCommonPrefix = function (strs) {
  if (strs.length === 0) {
      return '';
  }
  if (strs.length === 1) {
      return strs[0];
  }
  return strs.reduce(getSameStr, strs[0]);
};

function getSameStr(a, b) {
    console.log(a, b);
    let res = ''
    for (let j = 0; j < a.length; j++) {
        if (a[j] === b[j]) {
            res += a[j];
        }
        else {
            return res;
        }
    }
    return res
}

// let strs = ["flower","flow","flight"];
// console.log(longestCommonPrefix(strs));


// 链表定义函数
function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val);
    this.next = (next === undefined ? null : next);
}

var mergeTwoLists = function(l1, l2) {
    const dummpy = node = new ListNode();
    while(l1 && l2){
        console.log(l1.val);
        if(l1.val >= l2.val){
            console.log('11');
            node.next = l2;
            node = node.next;
            l2 = l2.next;
        }
        else {
            console.log('22');
            node.next = l1;
            node = node.next;
            l1 = l1.next;
        }
    }
    node.next = l1 || l2;
    return dummpy.next;
};

// let l1 = [1,2,4], l2 = [1,3,4];
// console.log(mergeTwoLists(l1, l2));


var strStr = function (haystack, needle) {
    if (needle === "") {
        return 0;
    }
    for (var i = 0; i < haystack.length; i++) {
        if (haystack[i] === needle[0]) {
            if (haystack.slice(i, i + needle.length) === needle) {
                return i;
            }
        }
    }
    return -1
};

// let haystack = "aaaaa", needle = "bba"
// console.log(strStr(haystack, needle));


var generate = function(numRows) {
    if(numRows === 0) { 
        return []; 
    }
    const result = Array.from(new Array(numRows), ()=>[])
    for(let i = 0; i < numRows; i++){
            result[i][0] = 1;
            result[i][i] = 1;
            for(let j = 1; j < i; j++){
                result[i][j] = result[i-1][j-1] + result[i-1][j]; 
            }
    }
    return result;
};

// let numRows = 5;
// console.log(generate(numRows));


var maxProfit = function(prices) {
    let res = 0;
    let min = prices[0];
    for(let i = 1; i < prices.length; i++){
        if(prices[i] < min){
            min = prices[i]
            console.log('1111-----', min);
        }
        else {
            res = Math.max(res, prices[i] - min)
            console.log(res);
        }   
    }
    return res;
};

// let prices = [7,1,5,3,6,4];
// console.log(maxProfit(prices));


var maxProfit = function(prices) {
    let result = 0;
    for(let i = 1; i < prices.length; i++) {
        if(prices[i] > prices[i-1]) {
            result += prices[i] - prices[i - 1];
        }
    }
    return result;
};

// let prices = [1,2,3,4,5];
// console.log(maxProfit(prices));

var removeDuplicates = function(nums) {
    let i = 0;
    for(let j = 1; j < nums.length; j++){
        if(nums[j] !== nums[i]){
            nums[i+1] = nums[j];
            i++;
        }
    }
    nums = nums.slice(0, i + 1);
    console.log(nums);
    return i + 1;
};

// let nums = [0,0,1,1,1,2,2,3,3,4];
// console.log(removeDuplicates(nums));


var merge = function (nums1, m, nums2, n) {
    let len = m + n - 1;
    m--;
    n--;
    while (m >= 0 && n >= 0) {
        if (nums1[m] > nums2[n]) {
            nums1[len] = nums1[m--]
            console.log('111----', nums1);
        } 
        else {
            nums1[len] = nums2[n--]
            console.log('2222--', nums1);
        }
        len--;
        console.log(m, n, len);
    }
    if(m === -1){
        return nums1.splice(0, len+1, ...nums2.slice(0, n + 1));
    }
    if(n === -1){
        return nums1;
    }
};

// let nums1 = [1,2,7,0,0,0], m = 3, nums2 = [2,5,6], n = 3;

// console.log(merge(nums1, m, nums2, n));


var isPalindrome = function(s) {
    s = s.replace(/[^\w]/g, '').toLowerCase();
    let leftPointer = 0;
    let rightPointer = s.length - 1;
    while(rightPointer > leftPointer){
        if(s[leftPointer++] === s[rightPointer--]){
            continue;
        }
        else {
            return false;
        }
    }
    return true;
};

// let str = "race a car";

// console.log(isPalindrome(str));

// b();

// let b = function() {
//     console.log('b');
// }


// Promise
// .resolve('a')
// .then('b')
// .then(Promise.resolve('c'))
// .then(console.log)
// Promise.resolve('a').then(console.log).then(Promise.resolve('c')).then(console.log)


var plusOne = function(digits) {
    let carry = 1; // 进位（因为我们确定+1，初始化进位就是1）
    for(let i = digits.length - 1; i >= 0; i--){
        let sum = 0; // 这个变量是用来每次循环计算进位和digits[i]的值的
        sum = digits[i] + carry; 
        digits[i] = sum % 10; // 模运算取个位数
        carry = (sum / 10) | 0; //  除以10是取百位数，并且｜0表示舍弃小数位
    }
    if(digits[0] === 0) digits.unshift(carry);
    return digits
};



function sum(str1, str2) {
    const arr1 = str1.split(''),arr2 = str2.split('');
    const len1 = arr1.length,len2 = arr2.length;
    const maxLen = Math.max(len1, len2);
    let res = [];
    let flag = false;
    for(let i = 0; i < maxLen; i++) {
        let temp;
        let num1 = arr1.pop() , num2 = arr2.pop();
        num1 = num1 ? num1 : 0;
        num2 = num2 ? num2 : 0;
        if(flag) {
            temp =  parseInt(num1) + parseInt(num2) + 1;
        }
        else {
            temp =  parseInt(num1) + parseInt(num2);
        }
        if(parseInt(temp/10) > 0) {
            // 有进位
            res.push(temp%10);
            flag = true;
        } else {
            res.push(temp);
            flag = false;
        }
        if( i == maxLen -1 && flag) {
            res.push(1);
        }
    }
    return res.reverse().join('');
}

var missingNumber = function(nums) {
    const len = nums.length
 
   let sum = ((1 + len) * len) / 2
 
   for (let i = 0; i < len; i++) {
     sum -= nums[i]
   }
 
   return sum
 }