LeetCode119 Pascal's Triangle II

xiaoxiao2021-02-27  214

详细见:leetcode.com/problems/pascals-triangle-ii

Java Solution: github

package leetcode; import java.util.ArrayList; import java.util.List; /* * Given an index k, return the kth row of the Pascal's triangle. For example, given k = 3, Return [1,3,3,1]. Note: Could you optimize your algorithm to use only O(k) extra space? */ public class P119_PascalsTriangleII { public static void main(String[] args) { Solution s = new Solution(); for (int i = -1; i < 11; i ++) { List<Integer> ans = s.getRow(i); tools.Utils.B_打印List_Integer_OneLine(ans); } } static class Solution { public List<Integer> getRow(int rowIndex) { rowIndex ++; List<Integer> ans = new ArrayList<>(rowIndex > 0 ? rowIndex : 1); if (rowIndex <= 1) { ans.add(1); return ans; } for (int i = 0; i < rowIndex; i ++) { ans.add(0); } ans.set(rowIndex - 1, 1); ans.set(rowIndex - 2, 1); int index = rowIndex - 3; while (index != - 1) { for (int jndex = index + 1; jndex < rowIndex - 1; jndex ++) { ans.set(jndex, ans.get(jndex) + ans.get(jndex + 1)); } ans.set(index, 1); index --; } return ans; } } }

C Solution: github

/* url: leetcode.com/problems/pascals-triangle-ii AC 3ms 2.56% */ void swap(int** a, int** b) { int* t = *a; *a = *b; *b = t; } int* getRow(int ri, int* rn) { int* ans = (int*) malloc(sizeof(int) * (ri+1)); int* tmp = (int*) malloc(sizeof(int) * (ri+1)); int i = 0, j = 0, k = 0; for (i = 0; i <= ri; i ++) { ans[0] = 1; for (j = 1; j <= i; j ++) { ans[j] = tmp[j] + tmp[j-1]; } ans[i] = 1; swap(&ans, &tmp); } free(ans); *rn = ri+1; return tmp; }

Python Solution: github

#coding=utf-8 ''' url: leetcode.com/problems/pascals-triangle-ii @author: zxwtry @email: zxwtry@qq.com @date: 2017年5月4日 @details: Solution: 55ms 25.60% ''' class Solution(object): def getRow(self, i): """ :type i: int :rtype: List[int] """ L, R = [1]*(i+1), [1]*(i+1) if i < 2: return L for k in range(2, i): for j in range(1, k): R[k][j] = R[k-1][j-1]+R[k-1][j] L, R = R, L return L

转载请注明原文地址: https://www.6miu.com/read-8734.html

最新回复(0)