JAVA solution 1ms 89%,with the explanation


  • 0
    T
     /*first when rowIndex<=30,the fast way to solve id math function by using combination 
          [C(0,n),C(1,n)...C(n,n)];
          then when rowIndex>30, the range of double is limited,so using the recursive function;*/
        public static List<Integer> getRow(int rowIndex) {
            List<Integer> result=new ArrayList<>();
            int mid;
            if (rowIndex<31){
                /*math function*/
                if(rowIndex%2==0){
                    mid=rowIndex/2;
                    for(int i=0;i<=rowIndex;i++){
                        if(i<=mid){
                            result.add(combination(rowIndex,i));
                        }else{
                            result.add(result.get(--mid));
                        }
                    }
    
                }else{
                    mid=rowIndex/2;
                    for(int i=0;i<=rowIndex;i++){
                        if(i<=mid){
                            result.add(combination(rowIndex,i));
                        }else{
                            result.add(result.get(mid--));
                        }
                    }
                }
                return result;
            }else{
                /*recursive function;*/
                List<Integer> tmp=getRow(rowIndex-1);
                result=getRow(tmp,rowIndex);
            }
            return result;
    
        }
        /*recursive function: getRow;*/
        private static List<Integer> getRow(List<Integer> tmp, int row) {
            int count=0;
            List<Integer> result=new ArrayList<>();
            while(count<=row){
                if (count-1<0){
                    result.add(1);
                    count++;
                    continue;
                }
                if (count==tmp.size()){
                    result.add(1);
                    break;
                }
                result.add(tmp.get(count-1)+tmp.get(count));
                count++;
            }
            return result;
        }
    /*math function: C(n,m)*/
        public static int combination(int n, int m){
            if (m==0) return 1;
            double result1=1,result2=1;
            int i=1;
            while(i<=m){
                result1*=i++;
            }
            i=1;
            while(i<=m){
                result2*=n--;
                i++;
            }
            return (int)(result2/result1);
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.