arraylist는 항상 일정한 용량으로 생성됩니다

Question

주어진 행 번호의 파스칼의 삼각형을 계산하려고합니다. 재귀를 사용하고 있습니다.

내 코드는 다음과 같습니다 :

public static List<Integer> getRow(int rowIndex) { 

     if (rowIndex == 1){ 
      List <Integer> list = new ArrayList(rowIndex+1); 
      list.add(1); 
      return list; 
     } 
     else{ 
       List<Integer> oldList = getRow(rowIndex -1); 
       List <Integer> list = new ArrayList(rowIndex+1); 
       int temp = 0; 
       list.add(0,1); 
       list.add(list.size()-1,1); 
       System.out.println("rowIndex "+rowIndex); 

       for (int i = 1; i < list.size()-1; i ++){ 
       temp = oldList.get(i) + oldList.get(i-1); 
       list.add(i,temp); 
       } 
       return list; 

     } 
    } 

그것은 관계없이 항상 내가 얻으려고 노력하고있는 무슨 행의 [1,1] 반환합니다. print 문을 삽입하려고했습니다. 목록의 크기가 rowIndex와 관계없이 항상 2임을 알았습니다.

List <Integer> list = new ArrayList(rowIndex+1); 

위의 줄은 ArrayList를 만드는 올바른 방법이 아닙니까? 내 arraylist처럼 항상 크기 = 2;

Answer 1

데이터 구조를 잘못 해석했다고 생각합니다.

그리고 배열 목록은 배열 위에 구현 된 LIST입니다. 생성자에서 배열의 크기를 설정하는 것은 개발자에게 배열의 초기 크기를 제어하는 ​​방법입니다 (클래스가 배열 크기 자체를 관리하므로 거의 필요하지 않으므로이 인수를 생략하십시오). 따라서 배열 목록의 크기는 실제로 목록의 크기이며, 생성자에 지정된 기본 배열의 버킷 수가 아니라 요소 수입니다.

원하는 배열의 크기를 알고 특정 위치에서 가져오고 추가하려는 경우 배열 목록이 아닌 표준 배열을 사용하십시오.

는 그러나, 나는 당신이 루프 (나는 그것을 경계 예외 중 인덱스를 throw하지 않습니다 실제로 놀랍)하여 이후에

list.add(list.size()-1,1); 

를 이동하면 코드가 작동합니다 생각합니다. 그리고 왼쪽부터 순차적으로 진행되기 때문에, 추가하는 항목 중 어느 것도 지정된 목록이 필요하지 않습니다. 기존 목록의 끝에 추가하기 만하기 때문입니다.

Answer 2

당신은 어떻게 ArrayLists이 작동하는지 오해하고 실제로는 read the Javadoc해야합니다.

즉, 생성자의 매개 변수는 최대 크기가 아닌 메모리에있는 ArrayList의 초기 크기를 정의합니다. new ArrayList<Integer>(2)을 인스턴스화하면 jvm이 두 개의 정수에 대해 충분한 공간을 할당하고 세 번째 요소를 추가하면 jvm이 더 많은 요소를 추가 할 수 있도록 ArrayList의 크기가 커진다는 것을 의미합니다.

또한이 위치에 요소가 추가 된 경우에만 get()으로 ArrayList 위치에 액세스 할 수 있습니다.

마지막으로 특정 위치의 add이 모든 요소를 ​​오른쪽으로 이동한다는 것을 명심하십시오. 따라서 add(10,1) 다음에 add(2,4) 인 경우 첫 번째 추가가 오른쪽으로 이동합니다. 위로 질문에

, 당신이 절대적으로 ArrayList 아닌 array을 사용하려는 경우, 당신은 올바른 위치에 다음, 당신의 ArrayList 적당한 크기로 set 값을 초기화해야합니다. 당신이 그것을 실행하는 경우

// the method with your algorithm which has been slightly modified 
public static List<Integer> getRow(final int rowIndex) { 
    // notice that I call a helper method which initialises correctly the ArrayList 
    final List<Integer> list = init(rowIndex); 
    if (rowIndex == 1) { 
     // notice that I set the value at a given position 
     // I can only do it because I initialised all values to 0 first 
     list.set(0, 1); 
    } else { 
     final List<Integer> previousRowList = getRow(rowIndex - 1); 
     // again, I set values... 
     list.set(0, 1); 
     list.set(rowIndex - 1, 1); 
     for (int i = 1; i < (list.size() - 1); i++) { 
      // set again... 
      list.set(i, previousRowList.get(i - 1) + previousRowList.get(i)); 
     } 
    } 
    // lets print out the row 
    System.err.println(list); 
    // then return it 
    return list; 
} 

public static List<Integer> init(final int size) { 
    // passing the size is overkill, but well... 
    final List<Integer> list = new ArrayList<Integer>(size); 
    // fill the ArrayList with zeros 
    for (int i = 0; i < size; i++) { 
     list.add(i, 0); 
    } 
    // then return it 
    return list; 
} 

public static void main(final String[] args) { 
    getRow(Integer.parseInt(args[0])); 
} 

당신이 (너무 좋지 않아,하지만 작업) 얻을 것이다 파스칼의 삼각형 : 여기

는 작업 솔루션입니다.11 행을 원할 경우 결과는 다음과 같습니다.

[1] 
[1, 1] 
[1, 2, 1] 
[1, 3, 3, 1] 
[1, 4, 6, 4, 1] 
[1, 5, 10, 10, 5, 1] 
[1, 6, 15, 20, 15, 6, 1] 
[1, 7, 21, 35, 35, 21, 7, 1] 
[1, 8, 28, 56, 70, 56, 28, 8, 1] 
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1] 
[1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1] 

희망이 있습니다.