java 1ms,beat 85%


  • 0
    W

    the method through computing C(M,N), for example row(3)={C(3,0),C(3,1),C(3,2),C(3,3)),which C(3,0) = C(3,3) .To avoid overflowing , using greatest common divisor ( gcd ) to optimize...

    public int gcd(int a ,int b){
    	if(a%b==0)return b;
    	else return gcd(b,a%b);
    }
    public List<Integer> getRow(int rowIndex) {
    	List<Integer> r = new ArrayList<Integer>();
    	int i = 0;
    	int k = rowIndex/2;
    	int count_up=rowIndex ,count_down=1;
    	int last=1;
    	r.add(++i);
    	while(i<=k){
    		if(last%count_down==0) {
    			last/=count_down;
    			last*=count_up;
    		}
    		else if(count_up%count_down==0) last *=  (count_up / count_down);
    		else {
    			int t1 = gcd(last ,count_down );
    			int cdown = count_down;
    			int cup = count_up;
    			last/=t1;
    			cdown/=t1;
    			if(cup%cdown==0) last *=  (cup / cdown);
    			else{
    				int t2= gcd(count_up ,count_down );
    				cup/=t2;
    				cdown/=t2;
    				
    					
    				last =  last*cup / cdown;
    			}
    			
    		}
    		
    		r.add(last) ;
    		i++;
    		count_up--;
    		count_down++;
    	}
    	--i;
    	if(rowIndex%2!=0 && rowIndex!=0) r.add(r.get(i));
    	while(i<=rowIndex && i>0){
    		r.add(r.get(--i));
    	}
    	return r;
    }

Log in to reply
 

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