LeetCode/Pascal's Triangle II

( 블로그 기사 의 전재)

AtCoder의 Beginner Content에 첫 참전해 보았습니다.

결과는 초록( 여기 페이지 에 의하면 "소프트웨어 엔지니어로서 확실한 실력입니다"수준) 상당히는 후일보 미치지 않는다고 하는 곳. 아직 정진입니다.

글쎄, 오늘의 문제.

[ h tps : // / ㅇ t 여기. 이 m / p 로 b ぇ ms / 빠 s 또는 ls - t 리안 g ぇ - 좋다 / ]

Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle.

Note that the row index starts from 0.

In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example:

Input: 3
Output: [1,3,3,1]

Follow up:

Could you optimize your algorithm to use only O(k) extra space?

이번에는 파스칼의 삼각형 k 행의 수열을 반환해야합니다.
전회 기사의 문제를 풀었다면 풀기 자체는 제작도 없습니다만, $O(k)$ 의 메모리가 적은 해법을 생각하는 곳에서 깊이가 있습니다.

해답·해설

해법 1

마지막 기사 로 다음의 코드를 나타냈습니다만,

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ans = []
        if numRows > 0:
            ans.append([1])
            for _ in range(numRows-1):
                l_pre = [0]+ans[-1]+[0]
                l_nxt = [l_pre[i]+l_pre[i+1] for i in range(len(l_pre)-1)]
                ans.append(l_nxt)
        return ans

이것을 조금 변경하는 것도 해결할 수있었습니다.

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        l_pre = [1]
        if rowIndex > 0:
            for _ in range(rowIndex):
                l_pre = [0]+l_pre+[0]
                l_nxt = [l_pre[i]+l_pre[i+1] for i in range(len(l_pre)-1)]
                l_pre = l_nxt
        return l_pre

해법 2

파스칼 삼각형의 각 수열의 계산은 아래와 같이 상단의 수열의 한쪽 끝에 [0]을 붙인 두 개의 수열을 더해도 계산할 수 있습니다.

이쪽이 해법 1보다 깔끔하네요.

이것을 이용한 해법이 이하.

class Solution(object):
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        row = [1]
        for _ in range(rowIndex):
            row = [x + y for x, y in zip([0]+row, row+[0])]
        return row

해법 3

가장 공간 계산량을 억제한 해법은 이쪽이라고 생각합니다.
해에 필요한 요소수의 리스트를 준비해, 그 안에서 Iterative에 수열을 계산해 가는 메모리가 적은 해법입니다.

class Solution(object):
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        ans = [0]*(rowIndex+1)
        ans[0] = 1
        for i in range(1,rowIndex+1):
            for j in range(i,0,-1):
                ans[j] += ans[j-1]
        return ans

구체적으로 출력 변수 ans의 변화를 살펴보면 이미지가 솟아난다고 생각합니다. (rowIndex=5)

[1, 1, 0, 0, 0, 0]
[1, 2, 1, 0, 0, 0]
[1, 3, 3, 1, 0, 0]
[1, 4, 6, 4, 1, 0]
[1, 5, 10, 10, 5, 1]