My accepted java solution, any better code?


  • 58
    M
      public List<Integer> getRow(int rowIndex) {
    	List<Integer> list = new ArrayList<Integer>();
    	if (rowIndex < 0)
    		return list;
    
    	for (int i = 0; i < rowIndex + 1; i++) {
    		list.add(0, 1);
    		for (int j = 1; j < list.size() - 1; j++) {
    			list.set(j, list.get(j) + list.get(j + 1));
    		}
    	}
    	return list;
    }

  • 1
    D

    A concise and efficient solution.
    can I ask you some question

    public static List<Integer> prList = new ArrayList<Integer>();
    	public static List<Integer> getRow(int rowIndex) {
    		if (rowIndex < 0) {
    			return prList;
    		}
    		prList.add(0,1);
    		prList = getRow(rowIndex - 1);
    		for (int j = rowIndex - 1; j > 0; j--) {
    			prList.set(j, prList.get(j - 1) + prList.get(j));
    		}
    		return prList;
    	}
    

    this is my code ,in my local eclipse, it's ok ; but, leetCode show me wrong answer

    Input: 1
    Output: [1,1,1]
    Expected: [1,1]

    I am very confuse


  • 0
    M

    yes, because the variable prList you used is global, and you didn't initialize(clear data) it every time. The test case in Leetcode start from 0, then when it test case 1, it has the data which added in test 0. Move the global to local, or clear it at the first code in method body, you'll get it.


  • 0
    D

    thank you very much!
    because of the recursion ,so I use the global variable.
    Next time ,I will avoid using it.


  • 4
    L
    public static List<Integer> getRow(int rowIndex) {
    	List<Integer> list = new ArrayList<Integer>(rowIndex + 1);
    	if (rowIndex >= 0)
    		list.add(1);
    	for (int i = 1, num = 1; i <= rowIndex; i++) {
    		num = (int) ((double) num / i * (rowIndex - i + 1) + 0.1);
    		list.add(num);
    	}
    	return list;
    }

  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example


  • 0
    G
    public class Solution {
        //value(column) = value(column-1) * (row-(column-1)) / ((column-1) + 1)
        //base case is value(0) = 1
        //all zero  based
        
        public List<Integer> getRow(int row) {
            List<Integer> result = new ArrayList<Integer>();
            
            result.add(1);
            
            for (int column = 1; column <= row; column++) {
                double lastValue = result.get(column - 1);
                double lastColumn = column - 1;
    
                double res = lastValue * (row - lastColumn ) / (lastColumn + 1);
                
                result.add((int) res);
            }
            
            return result;
        }
    }

  • 0
    F
    This post is deleted!

  • 0
    F

    list.add(0, 1) is not efficient.


  • 3
    K

    Here is a Java version similar to @guidocelada and @Liuqi.L, which is based on Binomial theorem. Instead of floating operation, I use long integer to handle multiplication overflow. Hope this will be a little faster in some case.

    public class Solution {
    	public List<Integer> getRow(int rowIndex) {
    		Integer[] integers = new Integer[rowIndex + 1];
    		integers[0] = 1;
    		for (int col = 1; col <= rowIndex; col++) {
    			integers[col] = (int)((long)integers[col - 1] * (rowIndex - col + 1) / col);
    		}
    		return Arrays.asList(integers);
    	}
    }
    

  • 0
    M

    why is list.add(0, 1) not efficient?


  • 0
    A

    I guess what "fullname" meant is adding elements in ArrayList will involve shifting all following elements, which is O(n).
    To prevent that, I guess we can update elements from right to left:

    for (int i = list.size()-1; i-1 >= 0; i--)
    list.set(i, list.get(i) + list.get(i-1));
    list.add(1);


  • 0
    S

    I think it only take O(1) to insert in arraylist


  • 1
    S

    How about reverse the order and won't override value for next calculation

    public class Solution {
        public List<Integer> getRow(int rowIndex) {
            List<Integer> level=new ArrayList<>();
            for(int i=0; i<=rowIndex; i++){
                level.add(1);
                for(int j=i-1; j>=1; j--){
                    level.set(j, level.get(j)+level.get(j-1));
                }
            }
            return level;
        }
    }

  • 0
    K

    list.add(0, 1) uses a native method called arraycopy(Object src, int srcPos,Object dest, int destPos,int length).I cannot find the src of this method, but it uses this method to copy itself, so I think it use extra space


  • 0
    K

    I think it is better.


  • 0
    C
    public class Solution {
        public List<Integer> getRow(int rowIndex) {
            List<Integer> result = new ArrayList<Integer>();
            int numElements = rowIndex + 1;
            for (int i = 0; i < numElements; i++) {
                double coeff = factorial(rowIndex) / (factorial(i) * factorial(rowIndex - i));
                result.add((int)Math.round(coeff));
            }
            return result;
        }
        
        public double factorial(int n) {
           if (n == 0) {
               return 1;
           } else {
               return n * factorial(n - 1);
           }
            
        }
    }

  • 3
    H

    Similar idea here, but with comments

        public List<Integer> getRow(int rowIndex) {
        rowIndex = rowIndex + 1;
        List<Integer> result = new ArrayList<Integer>();
        if(rowIndex <= 0) return result;
        
        for(int i = 0; i < rowIndex; i++){
            result.add(0, 1);
            //last index is reserved for 1, which we insert in the first loop
            for(int j = 1; j < result.size() -1; j++){
                //we are supposed to find j -1 and j, but we have added 0 in front so index is rightshfited
                result.set(j, result.get(j) + result.get(j+1));
            }
        }
        
        return result;
    }

  • 0
    N

    How about using LinkedList


  • 3
    public List<Integer> getRow(int rowIndex) {
        List<Integer> V = new ArrayList<Integer>(rowIndex+1);
        for (int i=0; i<1+rowIndex; i++) {
            for (int j=i-1; j>=1; j--)
                V.set(j,V.get(j)+V.get(j-1));
            V.add(1);
        }
        return V;
    }

Log in to reply
 

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