goodluckalien / leecode-one-question-a-day Goto Github PK

/ 请你来实现一个 atoi 函数，使其能将字符串转换成整数。

// 首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：

// 如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
// 假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
// 该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
// 注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。

// 在任何情况下，若函数不能进行有效的转换时，请返回 0 。

// 提示：

// 本题中的空白字符只包括空格字符 ' ' 。
// 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231,  231 − 1]。如果数值超过这个范围，请返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。
//  

// 示例 1:

// 输入: "42"
// 输出: 42
// 示例 2:

// 输入: "   -42"
// 输出: -42
// 解释: 第一个非空白字符为 '-', 它是一个负号。
//      我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
// 示例 3:

// 输入: "4193 with words"
// 输出: 4193
// 解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
// 示例 4:

// 输入: "words and 987"
// 输出: 0
// 解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
//      因此无法执行有效的转换。
// 示例 5:

// 输入: "-91283472332"
// 输出: -2147483648
// 解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
//      因此返回 INT_MIN (−231) 。



/**
 * @param {string} str
 * @return {number}
 */
var myAtoi = function(str) {
    const newStr = str.trim() 
    const firstStr = newStr.charAt(0)
    /* 如果第一个是非法字符的情况 */
    if(isNaN(firstStr) &&  firstStr !== '+' && firstStr !== '-'   ) return 0
    let result = ''
    for(let i=0; i< newStr.length ; i++ ){
       if(newStr.charAt(i) !==' ' && !isNaN(newStr.charAt(i)) || (i===0 && (newStr.charAt(i) === '-' || newStr.charAt(i) === '+')) ){
           result += newStr.charAt(i)
       }
       else break
    }
    if(result.length === 1 && (  result === '-' || result === '+'  ) ) return 0
    if(result * 1> Math.pow(2,31)-1) return Math.pow(2,31) - 1
    if(result * 1< -Math.pow(2,31)) return -Math.pow(2,31)
    return result * 1
};

console.log(myAtoi("42"))

/**
 * 
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：
L   C   I   R
E T O E S I I G
E   D   H   N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1:
输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"
示例 2:
输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:
L     D     R
E   O E   I I
E C   I H   N
T     S     G
 */
/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
   if(s.length === 1) return s
   const rowsArr = []
   /* 创建行 */
   for(let i = 0 ;i < numRows;i++){
       rowsArr.push([])
   }
   let isConvert = false
   let currentRow = 0
   for(let i=0;i < s.length;i++){
      rowsArr[currentRow].push(s.charAt(i))
      if(currentRow ===0 || currentRow === rowsArr.length -1 ) isConvert =!isConvert
      if(rowsArr.length > 1){
        isConvert ? currentRow++ :currentRow--
      }
   }
   return rowsArr.map(_=>_.join('')).join('')
};

console.log(convert('ab',1))

/**
 实现 pow(x, n) ，即计算 x 的 n 次幂函数。
示例 1:
输入: 2.00000, 10
输出: 1024.00000
示例 2:
输入: 2.10000, 3
输出: 9.26100
示例 3:
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
说明:
-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。
 */

 /**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(num, power) {
  if (power < 0)   return 1 / num * myPow(1 / num, -(power + 1))
  if (power === 0) return 1 
  if (power === 1) return num
  // 以上分别为power小于0 等于0 等于1 的情况
  let res = 1
  while (power > 1) { // power大于1
    if (power % 2 === 1) {
      res = res * num
      power--
    }
    num = num * num
    power = power / 2
  }
  return res * num
}

/**
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6
 */
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    /* 链表两两合并 */
    if(lists.length===0) return null
    if(lists.length<=2) return mergeTwoLists(...lists)
    let result
    for(let i=0 ;i<lists.length-1;i++ ){
       result = mergeTwoLists( result ? result : lists[i] ,lists[i+1] )
    }
    return result
};

function mergeTwoLists(l1,l2){
   if(!l1 && !l2) return null
   if(!l1) return l2
   if(!l2) return l1
   if(l1.val < l2.val ){
       l1.next = mergeTwoLists(l1.next,l2)
       return l1
   }else{
       l2.next = mergeTwoLists(l1,l2.next)
       return l2
   }
}

/**
给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
 
示例 1:
给定数组 nums = [1,1,2], 
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。
 
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
 */
/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    for(let i=1; i<nums.length; i++){
       if(nums[i]===nums[i-1]){
           nums.splice(i,1)
           i--
       }
    }
    return nums.length
};

console.log( removeDuplicates( [0,0,1,1,1,2,2,3,3,4] ) )

/*
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 */

var lengthOfLongestSubstring = function(s) {
   const hashSet = new Set()
   const length = s.length
   let result = 0 , ak = -1
   for(let i =0 ; i<length ; i++){
       if(i!==0){
           hashSet.delete(s.charAt(i-1))
       }
       while( ak + 1 < length && !hashSet.has(s.charAt(ak+1)) ){
           hashSet.add(s.charAt(ak+1))
           ak++
       }
       result = Math.max(result,ak-i+1)
   } 
   return result
};

console.log( lengthOfLongestSubstring('abcabcbb') )

/**
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例：
输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]
 */
/**
 * 回溯法
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
   const result = []
   const sub = []
   backTrack( result ,sub ,0,0,n )
   return result
};
function backTrack(result,sub,open,close,max){
   if(sub.length === max * 2){
       result.push( sub.join('') )
   }
   if(open < max){
      sub.push('(')
      backTrack( result ,sub , open+1 ,close,max )
      sub.pop()
   }
   if(close<open){
       sub.push(')')
       backTrack( result ,sub , open ,close + 1 ,max )
       sub.pop()
   }
}
console.log(generateParenthesis( 3 ))

/**
 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 4:
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5:
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
 */
/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {
    let n = s.length;
    let m = p.length;
    let dp = Array.from(new Array(n+1),() => new Array(m+1).fill(false));
    dp[0][0] = true;
    for(let i = 0;i <= m;i++){
        if(p[i] == '*' && dp[0][i-1]){
            dp[0][i+1] = true;
        }
    }
    for(let i = 1;i <= n;i++){
        for(let j = 1;j <= m;j++){
            if(p[j-1] == s[i-1] || p[j-1] == '.'){
                dp[i][j] = dp[i-1][j-1]
            }else if(p[j-1] == '*'){
                if(p[j-2] != s[i-1]){
                    dp[i][j] = dp[i][j-2];
                }
                if(p[j-2] == s[i-1] || p[j-2] == '.'){
                    dp[i][j] = dp[i-1][j] || dp[i][j-1] || dp[i][j-2];
                }
            }
        }
    }
    return dp[n][m];
};

/**
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
 */
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
  if(!l1) return l2
  if(!l2) return l1
  if(l1.val<l2.val){
      l1.next = mergeTwoLists(l1.next,l2)
      return l1
  }else{
      l2.next = mergeTwoLists(l1,l2.next)
      return l2
  }
};

/**
 * 
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"
说明：
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
 */
/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function(num1, num2) {
    if (num1 == "0" || num2 == "0") return "0";
    let l1 = num1.length,
    l2 = num2.length;
    let res = new Array(l1 + l2 - 1).fill(0);
    for (let i = 0; i < l2; i++) {
      for (let j = 0; j < l1; j++) {
        res[i + j] += +num2[i] * +num1[j];
      }
    }
    let len = res.length;
    let str = "",
      num = 0;
    while (len--) {
      num += res[len];
      str = (num % 10) + str;
      num = (num / 10) | 0;
    }
    return num > 0 ? num + str : str;
};

console.log( multiply("123" ,"456"  ) )

console.log( new Array(9).fill(0) )

/**
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。 
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]
 */
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function(candidates, target) {
   const result = []
   let path = []
   candidates.sort((a,b)=>a-b)
   function backtrack(path,target,start){
       if(target===0){
           result.push(path)
           return
       }
       for( let i = start; i < candidates.length;candidates[i] === candidates[i-1] && i++ ){
           if(candidates[i] > target ) break
           path.push(candidates[i])
           backtrack( path.slice(), target - candidates[i] , ++i )
           path.pop()
       }
   }
   backtrack(path,target,0)
   return result
};
console.log( combinationSum2( [2,5,2,1,2] , 5 ) )

/**
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
说明:
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
 */
/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
   const hl = haystack.length
   const nl = needle.length
   if( nl === 0 ) return nl
   /* haystack 指针 */
   let hp = 0
   while(hp < hl - nl + 1 ){
       while( hp < hl -nl + 1 &&  haystack.charAt(hp) !== needle.charAt(0) ) hp++ 
       let cl = 0 /* 当前匹配字符窜长度 */
       let np = 0 /* needle 指针  */
       while( hp < hl && np < nl && haystack.charAt( hp ) === needle.charAt( np ) ){
           hp++
           np++
           cl++
       }
       if( nl === cl ) return hp - cl
       hp = hp - cl + 1
   }
   return -1
};

console.log( strStr( "aaaaa" , "bba" ) )

/**
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
 */
/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function(s) {
    let max = 0
    const stack = [ -1 ]
    for(let i=0;i < s.length; i++ ){
        if(s.charAt(i) === '('){
            stack.push(i)
        }else{
            stack.pop()
            if(stack.length === 0){
                stack.push(i)
            }else{
                max = Math.max( max , i - stack[ stack.length -1 ] )
            }
        }
    }
    return max
};

/**
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]
 */
/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function(s, dp = Array.from(s, _ => Array(s.length).fill(false)), res = []) {
    for(var i = s.length; i--;)
        for (var j = i; j < s.length; j++)
            dp[i][j] = s[i] === s[j] && (j - i < 2 || dp[i + 1][j - 1])
    var dfs = (r, start) => {
        start === s.length && res.push(r)
        for(var j = start; j < s.length; j++)
            dp[start][j] && dfs(r.concat([s.substring(start, j + 1)]), j + 1)
    }
    return dfs([], 0), res
};

/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function(root) {
   let totalNumber = 0
   if(!root) return totalNumber
   const back=(curNode,curNum)=>{
      curNum = String(curNum)
      if(!curNode.left && !curNode.right ){
          totalNumber += Number( curNum + curNode.val )
          return
      }
      if(curNode.left)  back(curNode.left, curNum + curNode.val )
      if(curNode.right) back(curNode.right,curNum + curNode.val )
   }
   if(root.left) back(root.left,root.val)
   if(root.right) back(root.right,root.val)
   if(!root.left && !root.right )totalNumber +=root.val
   return totalNumber
};

/**
给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
 
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1
 
提示：
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。
 */
/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(nums) {
    let n = nums.length;
    for(let i = 0;i < n;i++){
        while(nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]){
            [nums[nums[i] - 1],nums[i]] = [nums[i],nums[nums[i] - 1]];
        }
    }
    for(let i = 0;i < n;i++){
        if(nums[i] != i + 1){
            return i + 1;
        }
    }
    return n + 1;
};

/**
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]
 */



var swap = function(nums, i, j) {
    if (i === j)
        return;
    const t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
};

var cal = function (nums, first, result) {
    if (nums.length === first) {
        result.push([...nums]);
        return;
    }

    const map = new Map();
    for (let i = first; i < nums.length; i++) {
        if (!map.get(nums[i])) {
            map.set(nums[i], true);
            swap(nums, first, i);
            cal(nums, first + 1, result);
            swap(nums, first, i);
        }
    }
};

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(nums) {
    if (nums == null)
        return;
    
    nums.sort((a, b) => a - b);
    const res = [];
    cal(nums, 0, res);
    return res; 
};

/**
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
 */
/**
 * @param {number[]} nums
 * @return {number[][]}
 */

var permute = function(nums) {
   let length = nums.length
   let newArr = nums.map(_=>_)
   let result = []
   backtrack(length,newArr,result,0)
   return result
};

function backtrack(n,arr,result,index){
   if(index === n){
     result.push(arr)
   }
   for(let i= index; i < n; i++){
       swap(arr,index,i) 
       backtrack(n,[...arr],result, index+1)
       swap(arr,index,i) 
   }
}

function swap(arr,i,j){
    let swapItem = arr[i]
    arr[i] = arr[j]
    arr[j]=swapItem
}

console.log( permute( [1,2,3] ) )

/**
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]
 */
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
    let sns = nums.sort((a, b) => a - b);
    let len = sns.length;
    if (len < 4) return [];
    let ans = [];
    for (let i = 0; i < len - 3; i++) {
      // 如果当前循环值与前一个值相同，则判断存在重复，跳过此次循环
      if (i > 0 && sns[i] === sns[i - 1]) continue;
      if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
      if (nums[i] + nums[len - 1] + nums[len - 2] + nums[len - 3] < target) continue;
      for (let j = i + 1; j < len - 2; j++) {
        let left = j + 1;
        let right = len - 1;
        // 如果当前循环值与前一个值相同，则判断存在重复，跳过此次循环
        // 注意这里的判断条件
        // 因为当前j = i + 1
        // 这里判断的是后一个数字是否和现在的数字相等
        // 所以后一个数字的j至少为 j+1 = i+2
        // 所以此处的判断条件为j - 1 > i
        if (j - 1 > i && sns[j] === sns[j - 1]) continue;
        while (left < right) {
          if (sns[i] + sns[j] + sns[left] + sns[right] === target) {
            ans.push([sns[i], sns[j], sns[left], sns[right]]);
            while (left < right && sns[left] === sns[left + 1]) {
              left++;
            }
            while (left < right && sns[right] === sns[right - 1]) {
              right--;
            }
            // 执行到这里，左右指针都指向了最后一个与left值相同的位置，
            // 此时我们还需要将左右指针再次向前进位，跳过最后一个重复值
            // [1,1,1,1,2,3,4,5,6]
            // 此时left指针在最后一个1处，还是与最开头的1重复，所以再次
            // 加1,指针指向不重复的值
            left++;
            right--;
          } else {
            sns[i] + sns[j] + sns[left] + sns[right] > target 
            ? right-- 
            : left++
          }
        }
      }
    }
    return ans;
};

/**
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
 */
/**
 * @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--
    }
    if(i>=0){
       let j = nums.length -1
       while(j >= 0 &&  nums[j] <= nums[i]){
            j--
       }
       console.log(j,i)
       swap(i,j,nums)
    }
    
    reverse( nums ,i + 1)
    return nums
};

/* 翻转剩余的数组 */
function reverse(nums,start){
    let end = nums.length -1 
    while(end > start){
        swap(end,start,nums)
        start++
        end--
    }
}

/* 交换两数 */
function swap(i,j,nums){
   let temp = nums[i]
   nums[i] = nums[j]
   nums[j] = temp
}

console.log( nextPermutation( [5,4,7,5,3,2] ) )

/**
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解
 */
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
   let max = 0
   let catchMax = nums[0]
   for(let i=0;i<nums.length;i++){
     max = Math.max( nums[i] , max + nums[i] )
     catchMax = Math.max( max , catchMax )
   }
   return catchMax
};

console.log( maxSubArray( [-2,1,-3,4,-1,2,1,-5,4] ) )

/**
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
示例 3:
输入: [1,3,5,6], 7
输出: 4
示例 4:
输入: [1,3,5,6], 0
输出: 0
 */

/**
 * 二分法
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
   let left = 0
   let right = nums.length -1
   while(left<=right){
       const middle = Math.floor( ( left + right ) / 2 )
       if(target === nums[middle] ){
           return middle 
       }
       else if(target > nums[middle] ){
           left = middle + 1
       }else{
           right =middle - 1
       }
   }
   return left
};

console.log( searchInsert( [1,3,5,6], 7 ) )

/**
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 put("2", "abc");
    put("3", "def");
    put("4", "ghi");
    put("5", "jkl");
    put("6", "mno");
    put("7", "pqrs");
    put("8", "tuv");
    put("9", "wxyz");
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
 */
/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
    const output = []
    const mapObject = {
        '2':'abc',
        '3':'def',
        '4':'ghi',
        '5':'jkl',
        '6':'mno',
        '7':'pqrs',
        '8':'tuv',
        '9':'wxyz'
    }
    function backtrack(current,next_digits){
        if(next_digits.length===0){
            output.push(current)
        }else{
            const new_digits = next_digits.slice(0,1)
            const numberMaps = mapObject[new_digits]
            for(let i=0;i<numberMaps.length;i++){
                const currentNumber = numberMaps.charAt(i)
                backtrack(current+currentNumber,next_digits.slice(1))
            }
        }
    }
    if(digits.length !== 0 ){
        backtrack('',digits)
    }
    return output
};

/**
 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗
 */
/**
 * Definition for singly-linked list.
 */
function ListNode(val) {
    this.val = val;
    this.next = null;
}
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
   const dirmy = new ListNode(0)
   dirmy.next = head
   let first = dirmy
   let last = dirmy
   /* 让第一个指针走到 n + 1位置  */
   for(let i=0;i<n+1;i++){
       first = first.next
   }
   while(first !== null){
       first = first.next
       last = last.next
   }
   last.next = last.next.next
   return dirmy.next
};

/**
 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0
示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5
 */


 /* TODO: 性能很垃圾 ～～～～～～～～  */
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    const newNumberList = [ ...nums1 , ...nums2 ].sort((a,b)=>a-b)
    const length = newNumberList.length
    /* 奇数情况 */
    if(length % 2){
       return newNumberList[ Math.floor(length / 2 ) ] 
    /* 偶数请求 */    
    }else {
       return (newNumberList[length /2]  + newNumberList[length/2 - 1] ) /2
    }
};


console.log( findMedianSortedArrays( [1,2] , [3,4] ) )

/**
 编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
 */

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
   if(strs.length === 0) return ''
   let current = strs[0]
   for(let i = 1; i < strs.length; i++){
     while(strs[i].indexOf(current) !==0 ){
         current = current.slice(0,current.length-1)
         if(!current) return current
     }
   }
   return current
};

console.log( longestCommonPrefix( ["dog","racecar","car"]) )

/***
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明:
假设你总是可以到达数组的最后一个位置
 */
/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
   const length = nums.length
   let maxPositon = 0
   let end = 0
   let step = 0
   for(let i = 0;i<length - 1; i++ ){
       maxPositon = Math.max(maxPositon,i + nums[i])
       if(end===i){
           end = maxPositon
           step++
       }
   }
   return step
};


console.log( jump( [2,3,1,1,4] ) )

/**
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。 
示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]
示例 2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]
 */
/**
 * 回溯算法
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
   const result =[]
   let length = candidates.length
   let path = []
   candidates.sort((a,b)=>a-b)
   function backtrack(pathArr,target,start){
       if(target===0){
           return result.push(pathArr)
       }  
       for(let i = start;i<length;i++){
           if(target < candidates[i]) break
           pathArr.push( candidates[i] )
           backtrack(pathArr.slice(),target-candidates[i],i)
           pathArr.pop()
       }
   }
   backtrack( path ,target , 0 )
   return result
};
console.log( combinationSum( [2,3,5] , 8  ) )

/**
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
 
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]
 */
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
   nums.sort((a,b)=>a-b)
   const newList = []
   for(let i=0;i <= nums.length-3 ;i++){
       /* 当i>0 证明后面全部大于0 ，所以不会出现等于零的情况 */
       if(nums[i] > 0) break
       /* 如果 i 和 i-1 相当 那么说明 i-1已经被用过 ，跳过下一个 */
       if(i > 0 &&  nums[i] === nums[i-1])  continue
       /* 双指针 */
       let left = i + 1 , right = nums.length -1
       while(left < right){
           const num = nums[i] + nums[left] + nums[right] 
           if(num<0){
               /* num 小于零 ，left往后近一位 ，防止 多个left相等情况发生  */
              while( left < right && nums[left] === nums[++left] ){}
           }else if(num>0){
                /* num 小于零 ，left往后近一位 ，防止 多个left相等情况发生  */
                while( left < right && nums[right] === nums[--right] ){}
           }else if(num ===0) {
               newList.push([ nums[i] , nums[left] , nums[right]  ])
               while( left < right && nums[left] === nums[++left] ){}
               while( left < right && nums[right] === nums[--right] ){}
           }
       }     
   }
   return newList
};

console.log( threeSum( [-1,0,1,2,-1,-4] ) )

//给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
//你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。


// 给定 nums = [2, 7, 11, 15], target = 9
// 因为 nums[0] + nums[1] = 2 + 7 = 9
// 所以返回 [0, 1]



/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */


var twoSum = function(nums, target) {
    let numMapObject = {} , indexarr = []
    for(let i=0 ;i < nums.length;i++ ){
        numMapObject[nums[i]] = i
    }
    for(let i=0;i < nums.length;i++){
        const current = String(target-nums[i])
        if(current in numMapObject && i !== numMapObject[current]){
            indexarr = [ i ,numMapObject[current] ]
            break
        }
    }
    return indexarr
};


console.log( twoSum( [2, 7, 11, 15] , 9 ) )

/**
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
示例 1:
输入: "III"
输出: 3
示例 2:
输入: "IV"
输出: 4
示例 3:
输入: "IX"
输出: 9
示例 4:
输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
示例 5:
输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
 */

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    const map = {
        I : 1,
        IV: 4,
        V: 5,
        IX: 9,
        X: 10,
        XL: 40,
        L: 50,
        XC: 90,
        C: 100,
        CD: 400,
        D: 500,
        CM: 900,
        M: 1000
    }
    let ans = 0
    for(let i = 0;i < s.length;) {
        if(i + 1 < s.length && map[s.substring(i, i+2)]) {
            ans += map[s.substring(i, i+2)]
            i += 2;
        } else {
            ans += map[s.substring(i, i+1)]
            i ++
        }
    }
    return ans
};

/**
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
 */
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
   if(!head || !head.next ) return head
   let frist = head
   let second = head.next
   frist.next = swapPairs(second.next)
   second.next = frist
   return second
};

/**
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
 
示例 1:
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2
 
提示：
被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231,  231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。
 */
/**
 * 二分法
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function(dividend, divisor) {
    /* 是否正负数 */
    const isforward = (dividend > 0 && divisor > 0) || ( divisor < 0 && dividend < 0 ) ? true : false
    dividend = dividend > 0 ? dividend : -dividend
    divisor = divisor >0 ? divisor : -divisor 
    let left = 0
    let right = isforward ? 2147483647 : 2147483648
    let result = 0
    while( left <= right){
        /* 中间位置 */
        const middle = Math.floor( ( left + right ) / 2 )
        if(divisor * middle == dividend ){
            result = middle
            break
        }else if( divisor * middle > dividend ){
            right = middle - 1   
        }else {
            result = middle
            left = middle + 1
        }
    }
    return isforward ? result : -result
};
console.log( divide( 10 ,3 ) )

/**
罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。
示例 1:
输入: 3
输出: "III"
示例 2:
输入: 4
输出: "IV"
示例 3:
输入: 9
输出: "IX"
示例 4:
输入: 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.
示例 5:
输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.
 */
/**
 * @param {number} num
 * @return {string}
 */
var intToRoman = function(num) {
   /* 贪心算法 */
   const values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
   const sysbel = ["M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"]
   let result = ''
   for(let i =0; i< values.length && num > 0 ;i++ ){
       while(values[i] <= num ){
          num -= values[i];
          result += sysbel[i]
       }
   }
   return result 
};
console.log(intToRoman(1994))

/**
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1
 */
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
   const length = nums.length
   if(!length) return -1
   if(length === 1) return nums[0] === target ? 0 : -1
   let left = 0
   let right = length -1 
   while(left <= right){
       const middle = Math.floor( ( left + right ) / 2 )
       if(target === nums[middle]) return middle
       if(nums[0] <= nums[middle]){
           if(nums[0]<= target && target<nums[middle] ){
               right = middle - 1                 
           }else{
               left = middle + 1
           }
       }else{
           if(nums[middle] < target && target <= nums[length-1]   ){
               left = middle + 1
           }else{
               right = middle -1
           }
       }
   }
   return -1
};
console.log( search( [3,1] ,1 ) )

/**
给定一个 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]
]
 */
/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var rotate = function(matrix) {
   const n = matrix.length
   for(let i =0 ; i< n; i++ ){
      for(let j=i; j < n ;j++ ){
          [ matrix[i][j] ,matrix[j][i]  ] = [ matrix[j][i] ,matrix[i][j]  ]
      }
   }
   for(let i = 0; i< n ; i++ ){
       for(let j=0 ; j < Math.floor( n /2 ) ; j++){
           [ matrix[i][j] , matrix[i][n - j -1]  ] = [ matrix[i][n - j -1] ,matrix[i][j]  ]
       }
   }
   return matrix
};

let textArr = [
    [1,2,3],
    [4,5,6],
    [7,8,9]
  ]

console.log(rotate( textArr ))

/**
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
 */
/**
 * 利用栈 (先入后出)
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
   const map = new Map()
   const stack = []
   map.set(')','(')
   map.set(']','[')
   map.set('}','{')
   for(let i=0;i<s.length;i++ ){
       const current = s.charAt(i)
       if(map.has(current)){ /* ) } ]情况 */
           const topValue = stack.length === 0 ? '#' : stack.pop()
           if(topValue !== map.get(current)){
               return false
           }
       }else{ /* ( { [  */
          stack.push( current )
       }
   }
   return stack.length === 0
};
console.log(isValid( "()[]{}" ))

/**
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]
说明：
所有输入均为小写字母。
不考虑答案输出的顺序。
 */
/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
   const map = {} , result = []
   for(let i = 0; i < strs.length; i++ ){
       const current = strs[i].split('').sort().join('')
       map[current] ?  map[current].push(strs[i]) : map[current] = [ strs[i] ]
   }
   for( let i in map ){
       result.push( map[i] )
   }
   return result
};

console.log( groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]) )

/**
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
 */


 function extremeInsertionIndex(nums,target){
     let left = 0 
     let right = nums.length 
     while(left < right){
          const midden = Math.floor( ( left + right ) / 2 )
          if(nums[midden] >= target ){
              right = midden
          }else{
              left = midden + 1
          }
     }
     return left
 }
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
   const range = [ -1 , -1 ]
   const leftIndex = extremeInsertionIndex(nums,target)
   if(leftIndex===nums.length || nums[leftIndex] !== target  ){
       return range
   }
   range[0] = leftIndex
   let rightIndex = leftIndex + 1
   while(nums[rightIndex] === target )rightIndex++
   range[1]= rightIndex -1
   
   return range

};

console.log( searchRange( [5,7,7,8,8,10] ,6 ) )

/**
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
 */
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let left = 0
    let right = height.length -1 
    let left_max = 0
    let right_max = 0
    let result = 0
    while(left < right ){
        if( height[left] < height[right]){
            height[left] > left_max ? ( left_max = height[left] ) : ( result += left_max - height[left] ) 
            left++
        }else{
            height[right] > right_max ? ( right_max = height[right] ) : (result += right_max - height[right] ) 
            right--
        }
    }
    return result
};


console.log( trap( [0,1,0,2,1,0,1,3,2,1,2,1]  ) )

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {
   /* 判断符号 */
   const isMinuSign = Math.sign(x) === -1 
   /* 得出结果 */
   let result = String(Math.abs(x)).split('').reverse().join('') * 1
   if(isMinuSign) result = -result 
   /* 考虑溢出情况 */
   if(result > Math.pow(2,31) - 1 || result < -Math.pow(2,31)) return 0
   return result 
};

console.log( reverse(-21232432) )

/**
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
 
/**
 * 运用双指针解决这个问题
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
   let left = 0 ,right = height.length -1 ,result = 0
   while(left < right){
       const newResule = Math.min( height[ left ] , height[right] ) * (right - left)
       result = Math.max(result ,newResule)
       if(height[left] < height[right] ){
           left++
       }else{
           right--
       }
   }
   return result
};

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

// 判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

// 示例 1:

// 输入: 121
// 输出: true
// 示例 2:

// 输入: -121
// 输出: false
// 解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
// 示例 3:

// 输入: 10
// 输出: false
// 解释: 从右向左读, 为 01 。因此它不是一个回文数。
// 进阶:

// 你能不将整数转为字符串来解决这个问题吗？

/* 用字符选解决 */
/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
   const isSign = Math.sign(x) === -1
   if(isSign) return false
   const ocver = String(x).split('').reverse().join('') * 1
   return ocver === x
};

/* 不用字符窜解决 */
var isPalindromeNoString = function(x) {
    /* 考虑到负数的情况 */
    if(x < 0 || ( x % 10 === 0  && x !== 0) ){
        return false
    }
    let palindNumbber = 0
    while(x > palindNumbber ){
        palindNumbber = palindNumbber * 10 + x % 10
        x = Math.floor( x / 10 )  
    }
    console.log(palindNumbber , x)
    return x === palindNumbber || x === Math.floor( palindNumbber /10 )
}

/**
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
 
示例 1:
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。
 
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
 */
/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
   let i = 0
   for( ; i<nums.length ;i++ ){
       if(val===nums[i]){
           nums.splice(i,1)
           i--
       }
   }
   return i 
};
console.log( removeElement( [3,2,2,3] , 3) )

/**
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
 
示例 1：
输入：
  s = "barfoothefoobarman",
  words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。
示例 2：
输入：
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
输出：[]
 */
/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function(s, words) {
    if (!s || !words || !words.length) return [];
    let windows = {}, needs = {}, oneWordLen = words[0].length;
    for (let w of words) {
        needs[w] ? needs[w]++ : needs[w] = 1;
    }
    let l = 0, r = 0, count = 0, needsKeyLen = Object.keys(needs).length, ans = [];
    for (let i = 0; i < oneWordLen; i++) {
        windows = {};
        r = l = i;
        count = 0;
        while (r <= s.length - oneWordLen) {
            let w1 = s.slice(r, r + oneWordLen);
            r += oneWordLen;
            if (!needs[w1]) {
                windows = {};
                l = r;
                count = 0;
                continue;
            }
            windows[w1] ? windows[w1]++ : windows[w1] = 1;
            if (windows[w1] === needs[w1]) count++;
            while (count === needsKeyLen) {
                if (r - l === oneWordLen * words.length) ans.push(l);
                let w2 = s.slice(l, l + oneWordLen);
                l += oneWordLen;
                if (needs[w2]) {
                    windows[w2]--;
                    if (windows[w2] < needs[w2]) count--;
                }
            }
        }
    }
    return ans;
};