Pascal's|Pascal's Triangle II 与 Triangle（lettcode） Pascal'sTriangleII与Triangle（lettc

Pascal's Triangle II

文章图片
来自 lettcode
给出一个数字，然后计算那一层的数字。

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

看讨论求，用 Python 求解，巧妙的利用了 zip 这个特性：

def getRow(rowIndex): row = [1] for _ in range(rowIndex): row = [x+y for x, y in zip([0] + row, row+[0])] return row

当前数字等于上一层当前位置的数字加之前一个数字。
使用 C++ 来写更容易明白一些：

vector getRow(int rowIndex) { vector vi(rowIndex+1); vi[0] = 1; for(int i = 0; i <= rowIndex; ++i) { for(int j = i; j > 0; --j){ vi[j] = vi[j] + vi[j-1]; } } return vi; }

构造 Triangle
与上面不同的是，这个问题是需要构造完整的 Triangle

def generate(numRows): pascal = [[1] *(i+1) for i in range(numRows)] for i in range(numRows): for j in range(1, i): pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j] return pascal

Triangle 找出一条最小的路径

[ [2], [3,4], [6,5,7], [4,1,8,3] ] 最小路径是 2 + 3 + 5 + 1 = 11.

首先可以构造一个一模一样的数组：

def minimumTotal(triangle): """ :type triangle: List[List[int]] :rtype: int 构造一个一模一样的数组 """ if not triangle: return res = [[0 for i in range(len(row))] for row in triangle] res[0][0] = triangle[0][0] for i in range(1, len(triangle)): for j in range(len(triangle[i])): if j == 0: res[i][j] = res[i-1][j] + triangle[i][j] elif j == len(triangle[i])-1: res[i][j] = res[i-1][j-1] + triangle[i][j] else: res[i][j] = min(res[i-1][j-1], res[i-1][j]) + triangle[i][j] return min(res[-1])

不用构造数组，直接修改原数组：

def minum(traingle): # 从上往下 if not traingle: return for i in range(1, len(traingle)): for j in range(len(traingle[i])): if j ==0: traingle[i][j] += traingle[i-1][j] elif j == len(traingle[i])-1: traingle[i][j] += traingle[i-1][j-1] else: traingle[i][j] += min(traingle[i-1][j], traingle[i-1][j-1]) return min(traingle[-1])

【Pascal's|Pascal's Triangle II 与 Triangle（lettcode）】由底向上计算：

def minimumTotal(triangle): """ :type triangle: List[List[int]] :rtype: int """ if not triangle: return res = triangle[-1] for i in range(len(triangle)-2, -1, -1): for j in range(len(triangle[i])): res[j] = min(res[j], res[j+1]) + triangle[i][j] return res[0]