[[1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0], [0, 1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]]
dp[0][j]==1表示第一个骰子和为j+1的次数为1，因为数组下标从0开始。
def dice_probability(n, val=6):
dp = [[0]*val*n for _ in range(n)]
dp[0][:val] = [1] * val # 初始化第一个骰子
for i in range(n-1): # 根据第i个骰子更新第i+1个骰子
for j in range(i, len(dp[i+1])):
# 第i+1个骰子和为j（实际为j+1，因为数组下标从0开始）的次数，等于第i个
# 骰子j-1 ~ j-6次数的总和
dp[i+1][j] = sum([dp[i][j-k] for k in range(1, val+1)])
# 整理数据成为dict，key表示和，value表示出现的次数
# count = {i+1: times for i, times in enumerate(dp[-1])}
# 计算概率
count = {i+1: round(float(times / (val**n)), 5)
for i, times in enumerate(dp[-1]) if times!=0}
return count感觉用dict来表示更加明确，没有数组下标从0开始的混淆。按照AcWing中的返回写出一种解法。
from collections import defaultdict
from itertools import repeat
def numberOfDice(self, n):
last_p = defaultdict(int)
last_p.update(dict(zip(range(1, 7), repeat(1))))
for i in range(2, n+1):
new_p = defaultdict(int)
for j in range(i, i*6+1):
new_p[j] = sum(last_p[j-k] for k in range(1, 7))
# print(new_p)
last_p = new_p
return list(last_p.values())开始以为还要用个dict来映射值，后来发现直接传得卡牌的值。思想就是先排序，然后查joker的数量，看剩下牌的差值加起来能不能用已有的joker连起来。
def IsContinuous(self, numbers):
if not numbers:
return False
joker_count = numbers.count(0)
left_cards = sorted(numbers)[joker_count:]
need_joker = 0
for i in range(len(left_cards)-1):
if left_cards[i+1] == left_cards[i]:
return False
need_joker += (left_cards[i+1]-left_cards[i]-1)
return need_joker <= joker_count使用标准库，更加优雅，原理相同。
from itertools import tee
def IsContinuous(self, numbers):
if not numbers:
return False
joker_count = numbers.count(0)
left_cards = sorted(numbers)[joker_count:]
need_joker = 0
c1, c2 = tee(left_cards)
next(c2, None)
for s, g in zip(c1, c2):
if g == s:
return False
need_joker += g - 1 - s
return need_joker <= joker_count方法一：其实不需要环形链表，使用一个list足矣，每次将其旋转rot位，一开始想将要把第m个数旋转到list首部，然后再pop(0)，后来想到直接可以通过切片取出来，节省了pop(0)的O(n)复杂度。
def LastRemaining_Solution(self, n, m):
if n<=0 or m<=0:
return -1
seats = range(n)
while seats:
rot = (m-1) % len(seats)
seats, last = seats[rot+1:] + seats[:rot], seats[rot]
return last方法二：书中的推导过程过于复杂，这里学到了一个稍微简单的推导过程。参考约瑟夫环问题。我自己的拙见。
def LastRemaining_Solution(self, n, m):
if n<=0 or m<=0:
return -1
last_num = 0
for i in range(2, n+1):
last_num = (last_num+m) % i
return last_num方法一：Brute Force.其实就是求最高峰点和前面最低谷点的差。
def maxProfit(self, prices: List[int]) -> int:
profit, min_buy = 0, float('inf')
for p in prices:
min_buy = min(min_buy, p)
profit = max(profit, p-min_buy)
return profit方法二：标准的卡登算法。此题为53.连续数组最大和的变形，如果价格比之前小，则舍弃，否则一起计算连续子数组的和。
def maxProfit(self, prices: List[int]) -> int:
cur = sofar = 0
for i in range(1, len(prices)):
cur += prices[i] - prices[i-1]
cur = max(0, cur)
sofar = max(cur, sofar)
return sofar方法三：使用标准库的卡登算法。
def maxProfit(self, prices: List[int]) -> int:
from itertools import tee
cur = profit = 0
a, b = tee(prices)
next(b, None)
for before, today in zip(a, b):
cur += today - before
cur = max(0, cur)
profit = max(profit, cur)
return profit