Using the binomial coefficient to get the result directly rather than iteration.


  • 0
    F
    public class Solution {
        public List<Integer> getRow(int rowIndex) {
            List<Integer> res=new ArrayList<Integer>();
            if(rowIndex==0){
                res.add(1);
                return res;
            }
            int tmp=1;
            res.add(tmp);
            for(int i=1;i<=rowIndex/2;i++){
                int a=rowIndex-i+1;
                if(tmp>Integer.MAX_VALUE/a){
                     int gcd=gcd(a,i);
                     a=a/gcd;
                     int b=i/gcd;
                     tmp=tmp/b*a;
                }
                else
                    tmp=tmp*a/i;
                res.add(tmp);
            }
            int k=rowIndex/2;
            if(rowIndex%2==0)
                k--;
            for(int i=rowIndex/2+1;i<=rowIndex;i++){
                res.add(res.get(k--));
            }
            return res;
        }
        public int gcd(int a,int b){
            if(a<b){
                return gcd(b,a);
            }
            if(b==0)
                return a;
            else
                return gcd(b,a%b);
        }
    }

Log in to reply
 

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