Given an array, rotate the array to the right by k steps, where k is non-negative.
解题思路：
for循环range(k), 然后用pop()去掉最后一位并通过insert()加入数列最前面。
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
for i in range(k):
nums.insert(0, nums.pop())
runtime:
想了想，确实还有更快的办法，直接把nums[-k:]移到nums最前面。
在PyCharm里写nums = nums[-k:] + nums[:-k] 是可以直接得到答案的，但是在leetcode里就不行。一定要改成nums[:] = nums[-k:] + nums[:-k]才行。暂时不理解，整个list的modify是必须要提idx的范围吗？直接用=表示为什么不行？
还有一种edge case要考虑，就是k大于nums的总长度，比如说k=5，nums = [1,2]。还用-k就会取不到正确的值。所以改成 nums[:] = nums[-(k % len(nums)):] + nums[:-(k%len(nums))]。这样才能得到[2,1]。
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
nums[:] = nums[-(k%len(nums)):] + nums[:-(k%len(nums))]
runtime:
查了forum之后，看到大家讨论说，nums[:]实际上已经是一个新的list了，不满足in-place修改的条件。所以就再看了下Neetcode的解法。是用了三次reverse做到的。
第一次reverse是针对整个nums。第二次和第三次分别是针对reverse后的nums前k个element后剩下的部分。
试着写一下：
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
k %= len(nums)
nums.reverse()
def helper(left, right):
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left, right = left + 1, right - 1
helper(0, k-1)
helper(k, len(nums)-1)
runtime:
这个方法算是满足了条件也算快。
#119 Pascal's Triangle II
Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:
解题思路：
之前Pascal‘s Triangle I最后的return是整个list，里面有每一层的元素。偷懒的方法就是最后输出list[-1]。
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
res = [[1]]
while rowIndex > 0:
res += [[1] + [res[-1][i] + res[-1][i+1] for i in range(len(res[-1])-1)] +[1]]
rowIndex -= 1
return res[-1]
runtime:
但应该还有更快的办法，不用每一层都重新求一遍的。可以直接根据层数算出该层的每一个元素时多少。
Sai Anish Malla介绍了一种超的思路：
首先已知的数是层数，以及第一个和最后一个是1。求第二个的时候，已知可用的信息就是前一个元素的值和层数了。
找出当前元素的值和之前一个值的关系。先用层数n和idx数，表示每个元素的所在位置。只要知道位置，这个值就是=n!/idx!(n-idx)!
（暂时不理解这个是怎么的出来的：看了binomial expansion的视频，这个其实就是combination的过程。5个球任取3个的N种组合方法，就是row5的第三个数的值。也是(a+b)^5的展开式的第三个项a^3b^2的系数。就是10。好神奇的杨辉三角，绝了，更多特质参考 Pascal's Triangle）
考虑到每个值都这样算比较麻烦，可以借用上前面已经算出来的值。-> =上一个值*(n-idx+1)/idx
这样会快很多。
试着写一下：
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
res = [1]
for i in range(1, rowIndex+1):
res.append(res[i-1]*(rowIndex-i+1)//i)
return res
runtime:
还是整个三角形挨个算更快？weird。
等Array and String这一章全部做完之后复习的时候再研究一下solution。
