leetcode: Pascal 's Triangle II | Java 최 단 코드 구현

1334 단어
원본 링크:
Pascal's Triangle II
[사고방식]
... 과 leetcode: Pascal 's Triangle | Java 최 단 코드 구현 다른 것 은 이 문 제 는 한 줄 만 되 돌려 주 고 공간 복잡 도가 O (k) 를 초과 하도록 요구 합 니 다. 우 리 는 모든 줄 의 결 과 를 result 결과 에 집중 시 키 고 한 줄 한 줄 업데이트 합 니 다.
    public List<Integer> getRow(int rowIndex) {
        List<Integer> result = new ArrayList<Integer>();
        result.add(1);
        for (int i = 0; i < rowIndex; i++) {  //   rowIndex - 1  (hang)  
            for (int j = i; j > 0; j--)  //       ,        
                result.set(j, result.get(j) + result.get(j - 1));  //      j           j - 1    j      
            result.add(1);
        }
        return result;
    }

34 / 34
 test cases passed. Runtime: 3 ms  Your runtime beats 21.02% of javasubmissions.
[최적화]
우 리 는 rowIndex 에 따라 그 줄 의 결 과 를 직접 내 놓 을 수 있 으 며, 이전 줄 에 따라 유도 할 필요 가 없다.
    public List<Integer> getRow(int rowIndex) {
        List<Integer> ans = new ArrayList();
        ans.add(1);
        for(int i = 1; i <= rowIndex; i++)
            ans.add((int)(Math.round(ans.get(i - 1) * ((double)(rowIndex - i + 1) / i))));
        return ans;
    }

34 / 34
 test cases passed. Runtime: 1 ms  Your runtime beats 84.70% of javasubmissions.

좋은 웹페이지 즐겨찾기