笔记23 #54 #118 Spinal Matrix Pascal‘s Triangle"/>
Leetcode日练笔记23 #54 #118 Spinal Matrix Pascal‘s Triangle
#54 Spiral Matrix
Given an
m x n
matrix
, return all elements of thematrix
in spiral order.
解题思路:
for循环m*n次,然后先column+=1,当column遇到最大值时,再row+=1。等到row也到了最大值,就掉头(体现为d *= -1),column-=1,当column遇到最小值时,再row-=1.每次掉头,都要改变row和column的极限值,因为读过数的idx就不能要了。要么是改row的最小值和column的最大值;要么是改row的最大值和column的最小值。取决于是第几次掉头。偶数次掉头,包括零,就前者;基数次掉头就后者。掉完头也记得column-=或+=1.
class Solution:def spiralOrder(self, matrix: List[List[int]]) -> List[int]:if not matrix:return []r, c = len(matrix), len(matrix[0])result = []i = j = counter = 0d = 1lower_limit_column = lower_limit_row = -1upper_limit_column, upper_limit_row = c, rfor x in range(r * c):result.append(matrix[i][j])pointer_c, pointer_r = j+d, i+dif lower_limit_column < pointer_c < upper_limit_column:j += delif lower_limit_row < pointer_r < upper_limit_row:i += delse:d *= -1if counter % 2 == 0:lower_limit_row += 1upper_limit_column -= 1else:lower_limit_column += 1upper_limit_row -= 1counter += 1j += dreturn result
runtime:
参考一下更快的解法:
思路是差不多,不过表达方法更简练。直接把读取和移动合并成了一个动作,减少循环次数,数列的读取效率非常高,把动作化简成4个步骤,完成后一次性改所有的极限值。绝了。
试着重写一下:
class Solution:def spiralOrder(self, matrix: List[List[int]]) -> List[int]:m,n = len(matrix), len(matrix[0])down, right = m-1,n-1up = left = 0result = []while len(result) < m*n:result.extend(matrix[up][left:right+1])result.extend([matrix[i][right] for i in range(up+1, down+1)])if up != down:result.extend(matrix[down][left:right][::-1])if left != right:result.extend([matrix[i][left] for i in range(down-1, up, -1)])up += 1down -= 1left += 1right -= 1return result
if up != down的意义在于,可能余下的空间并不足以跑第三步,就是底下的从右往左这步。
同理,left != right 可能最后只剩一列,就无法进行第四部,最左从下往上。
runtime:
再找个时间看一下官方solution和discussion里的其他思路。一道题分3次用。隔段时间再练也可以加深印象。
#118 Pascal's Triangle
Given an integer
numRows
, return the first numRows of Pascal's triangle.In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:
解题思路:
本来想用recursive的,但是跑不了,显示recursive的次数超出。应该是recursive的语句表达还是有不懂的地方。就先用while循环把每一层添加上。
res起始是[[1]]。while condition是numRow>1。然后定义新层的填充数字,最后加上res。
新层定义的填充数字,头尾是[1],中间是循环得出的数列,循环次数是上一行的元素个数减1。循环过程中,每个数字是上一行的同个idx加上idx+1之和。
class Solution:def generate(self, numRows: int) -> List[List[int]]:res = [[1]]while numRows > 1:res += [[1] + [res[-1][i] + res[-1][i+1] for i in range(len(res[-1])-1)] +[1]]numRows -= 1return res
runtime:
看油管视频=nPVEaB3AjUM=nPVEaB3AjUM的思路是把最后一行前后加上0,就可以直接相加得到要填充新行的值了。先到这里。第二次复习的时候再深入研究一下其他的解法和更好的表达。
更多推荐
Leetcode日练笔记23 #54 #118 Spinal Matrix Pascal‘s Triangle
发布评论