sailei1 / algorithm Goto Github PK

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
      let f=true;
     let ls=digits.length;
     for(let i=ls-1;i>=0;i--){
         if(digits[i]+1>9){  //大于9 数位循环+1;
             digits[i]=0;
         }else{
             digits[i]+=1;   //+1后 小于10 停止  
             f=false; // 进位标记
             break;
         }
     }
     if(f){
        digits.unshift(1);  // 999 情况 进1 
    }
     console.log(digits);
    return digits;
    
};

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

/**
 * @param {ListNode} head
 * @return {boolean}
 */


var hasCycle = function(head) {
  let slow = head;
  let fast = slow;

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

  if (fast == null || fast.next == null) {
    return false;
  }
  
  return true
};

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLastWord = function(s) {
    let arr=s.trim().split(' '); // 去掉两边空格  按空格分割
  
    return arr[arr.length-1].length;
};

/**
 * 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&&l2){
            let node;
            if(l1.val<l2.val){ //节点值 谁小 谁靠前
                node=new ListNode(l1.val);
                node.next=mergeTwoLists(l1.next,l2); //小的节点值的next 跟 大的节点当前值 做比较 决定 next
            }else{ //相反的情况 
                node=new ListNode(l2.val);
                node.next=mergeTwoLists(l1,l2.next);
            } 
            return node;    
        }
     return l1||l2;// 其中一个为空的情况
};

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
//      let o={};
//      for(let i=0;i<nums.length;i++){
//          if(!o[nums[i]]){
//              o[nums[i]]=0;
//          }
//      }
    
//     let rs=[];
//     for(let k in o){
//         rs.push(k);
//     }
//     rs.sort((a,b)=>{return a-b;})
//     for(let i=0;i<rs.length;i++){
//         nums[i]=rs[i];
//     }
//     return rs.length;
    if(nums.length==0){
        return 0;
    }
    
    let i = 0;
    for (let j = 1; j < nums.length; j++) {
        if (nums[j] != nums[i]) { //判断是否重复
            i++;
            nums[i] = nums[j]; //数组元素移动
        }
    }
    return i+1;
    
    
};

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
      for(let i=0;i<numbers.length;i++){
           let f=target-numbers[i];
          for(let l=i+1;l<numbers.length;l++){
              if(f===numbers[l]){
                  return [i+1,l+1];
              }
          }
          
      }
};

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function (numRows) {
    let res = []
    for (let i = 0; i < numRows; i++) {
        if (i === 0) {
            res.push([1])// 第一行 基础行
        } else {
            const arrs = [1];// 初始化当前行的第一个元素为1
            const preRows = res[i - 1];// 上一行数据
            for (let j = 0; j < preRows.length; j++) {// 上一行遍历获取左上方和右上方的数的和
                arrs.push(preRows[j] + (preRows[j + 1] || 0));
            }
            res.push(arrs);
        }
    }
    return res;
};

//**
 * @param {number} n
 * @return {number}
 */
var trailingZeroes = function(n) {
   // return   n>=5?n/5+trailingZeroes(n/5):0;
      let  count = 0;
        while(n >= 5) {
            count += Math.floor(n/5);
            n = n/5;
        }
        return count;

};

    3
   / \
  9  20
    /  \
   15   7

var maxDepth = function(root) {
    if(root===null){  //当前节点为空时 
        return 0
    }
    var left = 1
    var right = 1   //有子节点时 深度+1；
    left += maxDepth(root.left)  
    right += maxDepth(root.right)
    return left > right?left : right  //比较左右值 一层一层往下递归， 都没有子节点时停止递归
};

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {  
    let j=0;
    for(let i=0;i<nums.length;i++){
       if(nums[i]!==val){
           nums[j]=nums[i];
           j++;
       }
    }
    return j;
    
};

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let rs=false;
    let key={
        '(':')',
        '{':'}',
        '[':']'
    };
    if(s.length==0){
        rs=true;
    }
    let stack=[];
    for(let i=0;i<s.length;i++){
        let char=s[i];
        if(char===key[stack[stack.length-1]]){ // 确立关系
            stack.pop();
        }else{
            stack.push(char); 
        }
    }
    if(stack.length==0){
        rs=true;
    }
    return rs;
};

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
     let max=0;
    for(let i=0;i<prices.length-1;i++){
        if(prices[i] < prices[i+1]){
            max+=prices[i+1]-prices[i]; //多个连续峰值的和
        }
    }
    return max;
};

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
...

/**
 * @param {string} s
 * @return {number}
 */
var titleToNumber = function(s) {
      let key={
          'A':1,
          'B':2,
          'C':3,
          'D':4,
          'E':5,
          'F':6,
          'G':7,
          'H':8,
          'I':9,
          'J':10,
          'K':11,
          'L':12,
          'M':13,
          'N':14,
          'O':15,
          'P':16,
          'Q':17,
          'R':18,
          'S':19,
          'T':20,
          'U':21,
          'V':22,
          'W':23,
          'X':24,
          'Y':25,
          'Z':26
      };
    let str=s.split('').reverse(),rs=0;
    for(let i=0;i<str.length;i++){
        rs=key[str[i]]*Math.pow(26,i)+rs;  //转换公式 
    }
       return rs;
    
};

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {boolean}
 */
var hasPathSum = function(root, sum) {
     let left = false, right = false; 
        if(root) {
            sum -= root.val;//途径节点 相减 缩小范围
            if(root.left) {left = hasPathSum(root.left, sum);}
            if(root.right){ right = hasPathSum(root.right, sum);}
            if(!root.left && !root.right && sum == 0) { //确定节点没有子节点 
               return true;
            }
        }
    return left || right;
};

// let hasPathSum = function(root, sum) {
//     if(!root) return false;
//     if(root.left === null  && root.right === null) return sum === root.val;
//     return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
// };
//思路跟上边一样，少减一次

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
    
      let sort=(left, right)=>{
       
        if(left > right){
            return null;
        }
          // console.log(` ${left} ${right}`);
        var m = left + Math.floor((right-left)/2);  //取中间值 递归排序 
        var node = new TreeNode(nums[m]);
        node.left = sort(left, m-1);
        node.right = sort(m+1, right);
        return node;
    }
    return sort(0, nums.length-1);  
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
    let cur=head;
    let pre=null;
    while(cur){
         if (cur.val === val) {
          if (pre) {
            pre.next = cur.next; //跳过当前节点
          } else {
            head = cur.next;// 如果是第一个节点 直接跳过
          }
        } else {
          pre = cur;    //标记
        }
        cur = cur.next;       
    }

    return head;
};

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    let rs='';
    let str= x+'';
     rs+= str.split('').reverse().join('');
    let t= x===Number(rs);
    return t
};

/**
 * @param {number[]} nums
 * @return {number}
 */
// var singleNumber = function(nums) {
//      let ls=nums.length;
//     for(let i=0;i<ls;i++){
//         let str=nums[i];
//         if(nums.lastIndexOf(str)==nums.indexOf(str)){ //效率不高
//             return  str;
//         }
//     }
// };

var singleNumber = function (nums) {
    let count = {};
    nums.forEach(num => {
        if (count[num]) {
            count[num]++;
        }
        else{
            count[num] = 1;
        }
    });
    for (let key in count) {
        if (count[key] === 1) {
            return key;
        }
    }
};

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

var getIntersectionNode = function(headA, headB) {   
  let lena = getLen(headA);  
  let lenb = getLen(headB); 
  
  let a = headA;
  let b = headB;
  if (lena > lenb) {
    let tem = lena - lenb
    for (let i=0; i<tem; i++) {
      a = a.next;
    }
  } else {
    let tem = lenb - lena
    for (let i=0; i<tem; i++) {
      b = b.next;
    }
  }
    //找到一样长度的尾部
 
    
  while (a) {
    if (a === b) {
      return a;
    }
    a = a.next;
    b = b.next;
  }
  return null;
};

function getLen(list) { //获取长度
  let len = 0;
  while (list) {
    len += 1;
    list = list.next;
  }
  return len;
}

/**
 * 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;
};

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    return haystack.indexOf(needle);
};

1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB 
...

/**
 * @param {number} n
 * @return {string}
 */
/**
 * @param {number} n
 * @return {string}
 */
var convertToTitle = function(n) {
     let m=['A','B','C','D','E','F','G','H','I','J',
            'K','L','M','N','O','P','Q','R','S','T',
            'U','V','W','X','Y','Z'];
    let res='',ls=m.length;

     while(n>=1)
        {   n--;  //字母数组下标对应
            res=m[n%ls]+res; //余数相加
            n=Math.floor(n/ls);
            // console.log(n);
        }
    
    return res;
    
};

 二进制         1010
               1011
              -----
 竖向相加       2021   逢2 进1 
              10101

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
// var addBinary = function(a, b) {
//      let rs=convert(a)+convert(b); 
//     return rs.toString(2); //转换2进制
// };
    
// function convert(str){  return parseInt(str, 2); }    //转换十进制
// 有溢出问题 


var addBinary = function (a, b) {
    let carry = 0;// 进位标记
    let res = [];
    aindex = a.length - 1;// 
    bindex = b.length - 1;
    while (aindex >= 0 || bindex >= 0) {// a或b还有位可以相加
        sum = (+a[aindex] || 0) + (+b[bindex] || 0) + carry;// aindex bindex 长度不一致时 0替补
        carry = sum >= 2 ? 1 : 0;//进位数值
        res.push(sum % 2);
        aindex--;
        bindex--;
    }
    if (carry) {
        res.push(1);
    }
    return res.reverse().join(''); // 数组反推 返回结果
};

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
      
     // console.log(n);
      if(n==1||n==2){
          return n;
      }
      // if(n>2){
      //     n--;
      //     return climbStairs(n)+climbStairs(n-1);
      // }
      // 递归超时了，可能效率不行，测试通过不了  只能循环了。
     let b1=1,b2=2,sum=0;
      for(let i=2;i<n;i++){
            sum=b1+b2;
            b1=b2;
            b2=sum; 
      }
    return sum;
     
};

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
// var rotate = function(nums, k) {
//     let ls=nums.length,s=k+1;
//     let arr=nums.splice(s,ls-1).concat(nums.splice(0,s));
//     console.log(arr);
//     return arr;  
// };

/**
 * 利用队列的出队和入队**
 * 时间复杂度；O()，空间复杂度O(1)
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
  let len = nums.length
  if (len < 2) {
    return
  }
  while (k--) {
    // 先出队再入队
    nums.unshift(nums.pop())  
  }
};

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let ls=nums.length;m=Math.ceil(ls/2),o={};
    
    if(ls===1){
        return nums[0];
    }
    
    for(let i=0;i<ls;i++){
        if(o[nums[i]]){
            o[nums[i]]=o[nums[i]]+1;
            if(o[nums[i]]>=m){  //大于一半时的
                return  nums[i];
            }
        }else{
            o[nums[i]]=1;
        }
    }
    
};

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let res = nums[0];
    let sum = 0;
    for(let i=0;i<nums.length;i++){
        if(sum>0) {    //sum 大于0 累加
            sum += nums[i];
        }else {
            sum = nums[i];  //sum 直接等于下一位
        }
         res = Math.max(res,sum);// 循环对比最大值 返回最大值
    }
    return res;
};

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    let arr=s.split('');
    let m={
        I:1,
        V:5,
        X:10,
        L:50,
        C:100,
        D:500,
        M:1000
    };
    let rs=0,pre=0;
    for(let i=0;i<arr.length;i++){
        if(rs ===0){
           rs=m[arr[i]];
            pre=m[arr[i]]; // 别忘了标记初始值 为前一位 使用
        }else{
            let b=rs,n=0;
             if(m[arr[i-1]]<m[arr[i]]){ //IV型 运算 
                n=m[arr[i]]-m[arr[i-1]];
                rs=b+n-pre;
            }else{
                pre=m[arr[i]];
                rs=b+pre;
            }
        }
    }
    return rs;
    
};

    1
   / \
  2   2
 / \ / \
3  4 4  3

    1
   / \
  2   2
   \   \
   3    3

var isSymmetric = function(root) {
    if(!root)return true;
    let result = true;  //默认对称
    let fun = (l, r) => {
        if(!l && !r){ return;} //最底层节点 不比较

        if(!l || !r){ // 一个存在时 不对称
            result = false;
            return;
        }

        if(l.val === r.val){ //相等 递归比较
            fun(l.left, r.right) // 左左 右右比较
            fun(l.right, r.left) // 左右 右左比较 
        }else{
            result = false;  //不对称
            return;
        }
    }
    fun(root.left, root.right);  
    return result;
};

    3
   / \
  9  20
    /  \
   15   7

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function(root) {

      let findDepth=(node)=>{
         if(!node){return 0;}
          let left=findDepth(node.left); //获取左边最小深度
          let right=findDepth(node.right);// 获取后边最小深度
          if(left&&right){
            return Math.min(left, right)+1;
          } 
          return 1+left+right; //如果数据结构为[1,2]，则为特殊情况，单独一个根节点，不为最小深度
      }
      return findDepth(root);      
};

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    let str=s.toLowerCase().replace(/[^a-z0-9]/g,''); //过滤
    let re=str.split('').reverse().join(''); // 反转
   return str===re
};

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
        
    if(nums.length==0){
        return 0;
    }
     if(nums.length<3){
         return Math.max(...nums);
     }
    
    let rs=[];
    rs[0] = nums[0];                    
    rs[1] = Math.max(nums[0],nums[1]); 
    
    for(let i = 2;i< nums.length ;i++) {
        rs[i] = Math.max(rs[i-1] , rs[i-2]+nums[i]); // 状态转移方程
    };
    
    // console.log(rs)
    return rs[nums.length - 1];
};

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    if(target-nums[0]<=0){ //小于 第一个
        return 0; 
    }
    
     for(let i = 0 ;i<nums.length;i++){
        if(target == nums[i]){ //相等
            return i;
        }
        if(target > nums[i] && target < nums[i+1]){ //大于前面 小于后面
            return i+1;
        }
    }
    if(target-nums[nums.length-1]>0){ //大于最后一个
        return nums.length;
    }     
};

/**
 * @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=n-1;i>=0;i--){
         // console.log(nums1);
        let k=nums2[i];
        
        if(k>nums1[m-1]|| m == 0){  //最大值比较 大于 尾部追加最大值   
           nums1[m+i]=k; //   
        }else{
           // console.log(`${m+i}  ${m-1}`);
           nums1[m + i] = nums1[m - 1] //nums2不大于 num1最大值往后移动 
            m--; 
            i++; // nums2 当前值 跟 nums1 前一位 比较  m==0 防止越界
           
        }
    }
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
      if(!head){return head;}  //尾部返回
      while(head.next&&head.val === head.next.val){
            head.next=head.next.next;    //   当前值跟下一个值 一样时， 跳过当前值
      }
     // console.log(head.val);
    deleteDuplicates(head.next); //依次递归
    return head
    
};

    3
   / \
  9  20
    /  \
   15   7

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
       let rs=true; //默认平衡
      let findDepth=(node)=>{
         if(!node){return 0;}
          let left=findDepth(node.left); //获取左边最大深度
          let right=findDepth(node.right);// 获取后边最大深度
          if(Math.abs(left-right)>1){ //不平衡
              rs=false; 
          }
          return Math.max(left, right)+1;
      }
      findDepth(root);
    return rs;
     
      
};

/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function(n) {
    var res = (n).toString(2);//转换string 
     let arr=res.match(new RegExp('1', 'g'))||[] //正则查找
     return arr.length;
};

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
  return Math.floor(Math.pow(x,0.5));
};

/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function(rowIndex) {
    let res = []
    for (let i = 0; i <=rowIndex; i++) {
        if (i === 0) {
            res.push([1])// 第一行 基础行
        } else {
            let arrs = [1];// 初始化当前行的第一个元素为1
            let preRows = res[i - 1];// 上一行数据
            for (let j = 0; j < preRows.length; j++) {// 上一行遍历获取左上方和右上方的数的和
                arrs.push(preRows[j] + (preRows[j + 1] || 0));
            }
            res.push(arrs);
        }
    }
    return res[rowIndex];
    
};

        1         1
       / \       / \
      2   3     2   3

     [1,2,3],   [1,2,3]

           1        1
          /           \
         2             2

        [1,2],     [1,null,2]

          1         1
         / \       / \
        2   1     1   2

       [1,2,1],   [1,1,2]

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    // console.log(p);
    // console.log(q);
       
      if(p&&q && p.val == q.val){   
          return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
      }else{
          if(p||q){
            return false;
          }else{
              return true;
         }
       }
   //  解法2
    //  return JSON.stringify(p) === JSON.stringify(q)    树 本身就是object 直接转 json  对比 最快

    
};

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    
     let val=prices[0],max=0;
    for(let i=0;i<prices.length;i++){
        if(prices[i] < val){
            val = prices[i]; //找低峰值
        }else if(prices[i] - val > max){ // 低峰值时的最大值比较
            max = prices[i] - val;
        }
    }
    return max;

};

    3
   / \
  9  20
    /  \
   15   7

[
  [15,7],
  [9,20],
  [3]
]

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
    // if(root === null ){
    //     return  [];
    // }
    //  let arr=[];
//      arr.push([root.val]);
//     let findNode=(root)=>{
       
//         if(root){
 
//             if(root.left&&root.right){
//               arr.push([root.left.val,root.right.val]);
//                 findNode(root.left);
//                 findNode(root.right);
//             }else{
//                 if(root.left){
//                     arr.push([root.left.val]);
//                     findNode(root.left);
//                 }
                
//                 if(root.right){
//                     arr.push([root.right.val]);
//                     findNode(root.right);
//                 }
//             }
//         }
//         //console.log(arr);
//     }    
//      findNode(root);
//  上面没考虑深度合并    
  
        if(root === null ){
        return  [];
    }
     let arr=[];
      let findNode= (root,deep)=>{ // 
          if(root){
              arr[deep]=arr[deep]||[];//兼容
              arr[deep].push(root.val) // 靠deep 来合并数值
              
              if(root.left){
                    findNode(root.left,deep+1);
                } 
                if(root.right){
                    findNode(root.right,deep+1);  //先左后右
                }
          }
      }
      findNode(root,0);
      
    
    return arr.reverse();//反转 输出
    
  
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {  
//     循环  
    let pre=null;
     while(head){
          let next=head.next; //先保存原始next 
           head.next=pre; //改变next 关系
           pre=head; //标记前一位
           head=next;//后移
          
     }
    return pre;
    
    //function reverse(pre,cur){ //递归 
    //     if (cur == null){
    //         return pre
    //     } 
    //     let  head= reverse(cur, cur.next)
    //     cur.next = pre;
    //     return head
    // }
    //   return reverse(null,head);

};

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    let rs='';  //不匹配时 返回'';
     if(strs.length==1){  // 只有一个的时候返回 当前值 
        rs=strs[0];
    }else if(strs.length>1){
    let t_arr=strs.sort((el,next)=>{
        return el.length-next.length;
    })    
    
        
    let els=t_arr[0].split(''),temp=-1; //找到长度最低的那个元素
    for(let l=0;l<els.length;l++){
        let t=true;
        for(let i=1;i<t_arr.length;i++){  //从后面依次按照字母找
               if(t_arr[i][l].indexOf(els[l])==-1){
                   t=false; //找到没有的时候跳出循环
                   break;
               }
        }
        if(t){  //如果都存在 确定是不是相邻的 
            if(l-temp===1){ rs+=els[l];}
            temp=l;
        }
    }
    }
    return rs;
   
    
};

/**
 * @param {number} n
 * @return {number}
 */
// var countPrimes = function(n) {
//     //质数：只能被1和本身整除，1不是质数
//       let  res=1;//从3开始计算，所以初始为1 
//         if(n<3){ res=0;}
//         else{
//             for(let i=3;i<n;i++){
//                 if(i%2 == 0){
//                     continue;
//                 }
//                 let  flag=true;//false表示不是素数
//                 for(let j=3;j<=Math.sqrt(i);j+=2){
//                     if(i%j==0){
//                         flag=false;
//                         break;
//                     }
//                 }
//                 if(flag){res++; }
//             }
//         }
//         return res;
// };

var countPrimes = function(n) {
 if(n <= 2) {
        return 0
    }
    if(n === 3) {
        return 1
    }
    let count = 1;
    let arr = {};
    for(let i = 3; i < n; i += 2) {//叠加
        if(arr[i]) {
            continue;
        }
        count++;
        for(let j = i; j < n; j += i) { //叠加
            arr[j] = true; 
        }
    }
    return count;
};

/**
 * initialize your data structure here.
 */
var MinStack = function() {
    this.stack=[];
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.stack.push(x);
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    return this.stack.pop();
};

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

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
     return Math.min.apply(this, this.stack);
};

/** 
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

/**
 * @param {number} n - a positive integer
 * @return {number} - a positive integer
 */
var reverseBits = function(n) {
    var res = (n).toString(2);//转换string 
    
    while(res.length<32){
        res = '0'+res;  //没有的前面补齐 给反转做准备
    }
    res = res.split('').reverse().join(''); //反转
    return parseInt(res, 2);  //转换字符串 二进制
};

//位移
// var reverseBits = function(n) {
//   let res = 0;
//   for (let i = 0; i < 32; i++) {  
//     res = (res << 1) + (n & 1);  //(进位运算) 将 res 的二进制形式向左移1位，右边用0填充。 n&1 比较 0&1=0 1&1=1 二进制运算
//       // console.log(res.toString(2));
//       // console.log((n & 1).toString(2))
//     n = n >>> 1;  //(反转)  将 n 的二进制表示向右移1位，丢弃被移出的位，并使用 0 在左侧填充。
//   }
//     // console.log(res);

//   return res >>> 0; //左侧填充0 二进制转换;
// };

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isIsomorphic = function(s, t) {
    
    for (let i = 0; i < s.length; i++) {
        if (s.indexOf(s[i], i + 1) !== t.indexOf(t[i], i + 1)) {
            //遍历两个字符串，查找当前字符出现在后续字符串中的位置，如果是同构字符串，每个字符出现的位置是相同的
            return false;
        }
    }
    return true;
};