头像

codeAcmer


访客:311

离线:1个月前



codeAcmer
1个月前

后序遍历,递归O(n)
遍历的当前节点为cur,因为是后序遍历,
要先处理左右子树分别返回left,和right;

1.如果root 为空返回null
2. 如果一为root 则返回 root
3.遍历左子树得到left
4.遍历右子树得到right
5.如果left和right 都在则 返回root
6.如果left 存在则返回left ,如果left或者right 其中一个为null
另外一个不是为空则返回不是空的那一个。
7.返回right
```
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

    if(root==null){
        return null;
    }
    if(root==p || root ==q) return root;
    TreeNode left =lowestCommonAncestor(root.left, p, q);
    TreeNode right =lowestCommonAncestor(root.right, p, q);
    if(left!=null && right!=null)return root;
    if(left!=null) return left;
    return  right ;
}

}




codeAcmer
2个月前

class Solution {
public int strToInt(String str) {

    if(str==null || str.length()==0){
        return 0;
    }
    long num=0;
    int count=1;
    char[] ch =str.toCharArray();


    for(int i=ch.length-1;i>=0;i--){
        //空格
        if(ch[i]==' '){
            continue ;
        }
        //正负数
     if(ch[i]=='-'){

        num=-1*num;
       // System.out.println("fushu");
    }
      //整数前面有字母la123


      if(i+1<ch.length){
      if(ch[i+1] >='0'  && ch[i+1]<='9'  ){


       if((ch[i]>='A'&& ch[i]<='Z') || (ch[i]>='a'  && ch[i]<='z')){

           return 0;
       }
      }
      }
      //整数后面是字母 123la
      if(i-1  >0){
      if(ch[i-1]<='0' && ch[i-1]>='9'){

          if((ch[i]>='A'&& ch[i]<='Z') || (ch[i]>='a'  && ch[i]<='z')){

           return 0;
       }

       }
      }

       if(ch[i]>='0' && ch[i]<='9'){
           // System.out.println(ch[i]);
           num+=(ch[i]-'0')*count;
           // System.out.println("num ="+num);
           count=count*10;
       }


    }

    if(num>Integer.MAX_VALUE ){

       return Integer.MAX_VALUE;
    }
    if(num<Integer.MIN_VALUE){
        return Integer.MIN_VALUE;
    }

    return (int)num;

}
}




codeAcmer
2个月前

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



codeAcmer
2个月前

class Solution {
public int strToInt(String str) {

    if(str==null || str.length()==0){
        return 0;
    }
    long num=0;
    int count=1;
    char[] ch =str.toCharArray();


    for(int i=ch.length-1;i>=0;i--){
        //空格
        if(ch[i]==' '){
            continue ;
        }
        //正负数
     if(ch[i]=='-'){

        num=-1*num;
       // System.out.println("fushu");
    }
      //整数前面有字母la123


      if(i+1<ch.length){
      if(ch[i+1] >='0'  && ch[i+1]<='9'  ){


       if((ch[i]>='A'&& ch[i]<='Z') || (ch[i]>='a'  && ch[i]<='z')){

           return 0;
       }
      }
      }
      //整数后面是字母 123la
      if(i-1  >0){
      if(ch[i-1]<='0' && ch[i-1]>='9'){

          if((ch[i]>='A'&& ch[i]<='Z') || (ch[i]>='a'  && ch[i]<='z')){

           return 0;
       }

       }
      }

       if(ch[i]>='0' && ch[i]<='9'){
           // System.out.println(ch[i]);
           num+=(ch[i]-'0')*count;
           // System.out.println("num ="+num);
           count=count*10;
       }


    }

    if(num>Integer.MAX_VALUE ){

       return Integer.MAX_VALUE;
    }
    if(num<Integer.MIN_VALUE){
        return Integer.MIN_VALUE;
    }

    return (int)num;

}
}




codeAcmer
2个月前

class Solution {
public int[] multiply(int[] A) {
int[] B= new int[A.length];
if(A==null || A.length==0){
return B;
}
//分为左右两边

    for(int i=0,p=1;i<A.length;i++){

      B[i]=p;
      p*=A[i];
    }
    for(int i=A.length-1,p=1;i>=0;i--){

      B[i]*=p;
      p*=A[i];

    }

    return B;
}

}




codeAcmer
2个月前

class Solution {
public boolean isContinuous(int [] numbers) {
//1.判断是否为空
if(numbers==null || numbers.length<1){
return false;
}
Arrays.sort(numbers);
// System.out.println(Arrays.toString(numbers));
int numbersOfZero=0;//0的个数
int numbersOfGap=0;//间隔
//1.
for(int i=0;i<numbers.length;i++){

        if(numbers[i]==0){
            numbersOfZero++;
        }    
    }
    //
    int small=numbersOfZero;
    int big=small+1;//  为什么要设置 small  和zero从不是0 的位置开始遍历
     while(big<numbers.length){

        if(numbers[small]==numbers[big]){//有顺子
            return false;
        }

        numbersOfGap+=numbers[big]-numbers[small]-1;
        small=big;
        big++;
     }
    // System.out.println(" gap"+  numbersOfGap +"   numbersOfZero  "+ numbersOfZero);
      return numbersOfGap > numbersOfZero ? false :true;
}

}