學習使用工具
劍指Offer http://itmyhome.com/sword-means-offer/sword-means-offer.pdf
LeetCode的劍指Offer題庫 https://leetcode.cn/problemset/all/
劍指 Offer 60. n個骰子的點數(shù)
把n個骰子扔在地上，所有骰子朝上一面的點數(shù)之和為s。輸入n政模，打印出s的所有可能的值出現(xiàn)的概率。
你需要用一個浮點數(shù)數(shù)組返回答案羡亩，其中第 i 個元素代表這 n 個骰子所能擲出的點數(shù)集合中第 i 小的那個的概率。
示例 1:
輸入: 1
輸出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
示例 2:
輸入: 2
輸出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
限制：
1 <= n <= 11
解法：
動態(tài)規(guī)劃。設輸入 n 個骰子的解為 ，其中點數(shù)和為 x 的概率為
配喳。有遞推公式：
def dicesProbability(self, n: int) -> List[float]:
dp = [1 / 6] * 6
for i in range(2, n + 1):
tmp = [0] * (5 * i + 1)
for j in range(len(dp)):
for k in range(6):
tmp[j + k] += dp[j] / 6
dp = tmp
return dp
劍指 Offer 62. 圓圈中最后剩下的數(shù)字
0,1,···,n-1這n個數(shù)字排成一個圓圈飘诗，從數(shù)字0開始，每次從這個圓圈里刪除第m個數(shù)字（刪除后從下一個數(shù)字開始計數(shù)）界逛。求出這個圓圈里剩下的最后一個數(shù)字。
例如纺座，0息拜、1、2净响、3少欺、4這5個數(shù)字組成一個圓圈，從數(shù)字0開始每次刪除第3個數(shù)字馋贤，則刪除的前4個數(shù)字依次是2赞别、0、4配乓、1仿滔，因此最后剩下的數(shù)字是3。
示例 1：
輸入: n = 5, m = 3
輸出: 3
示例 2：
輸入: n = 10, m = 17
輸出: 2
限制：
1 <= n <= 10^51 <= m <= 10^6
解法：
約瑟夫環(huán)問題犹芹。遞推公式：
表示崎页，N個人報數(shù)，每報到M時那個人出局腰埂，最終勝利者的編號
表示飒焦，N-1個人報數(shù)，每報到M時那個人出局屿笼，最終勝利者的編號
def lastRemaining(self, n: int, m: int) -> int:
ans = 0
for i in range(2, n + 1):
ans = (ans + m) % i
return ans
劍指 Offer 63. 股票的最大利潤
假設把某股票的價格按照時間先后順序存儲在數(shù)組中牺荠，請問買賣該股票一次可能獲得的最大利潤是多少？
示例 1:
輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價格 = 1）的時候買入驴一，在第 5 天（股票價格 = 6）的時候賣出休雌，最大利潤 = 6-1 = 5 。
注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格蛔趴。
示例 2:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0挑辆。
限制：
0 <= 數(shù)組長度 <= 10^5
解法：
維護一個當前最小值l，一個當前最大值r孝情，以及最大利潤值profit鱼蝉。初始，l和r都等于數(shù)組第一個元素箫荡，profit為0魁亦，遍歷數(shù)組：
- 如果當前數(shù)組元素小于l，則令l和r都等于當前元素羔挡；
- 如果當前數(shù)組元素大于r洁奈，則令r等于當前元素间唉，更新profit=max(profit, r-l)
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
l = prices[0]
r = prices[0]
profit = r - l
for i in range(len(prices)):
if prices[i] < l:
l = prices[i]
r = prices[i]
elif prices[i] > r:
r = prices[i]
profit = max(profit, r - l)
return profit
劍指 Offer 64. 求1+2+…+n
求 1+2+...+n ，要求不能使用乘除法利术、for呈野、while、if印叁、else被冒、switch、case等關鍵字及條件判斷語句（A?B:C）轮蜕。
示例 1：
輸入: n = 3
輸出: 6
示例 2：
輸入: n = 9
輸出: 45
限制：
1 <= n <= 10000
解法：
昨悼？什么意思
def sumNums(self, n: int) -> int:
return sum(range(1, n + 1))
原來是要遞歸代替循環(huán)，邏輯運算符代替if跃洛。
常見的邏輯運算符有三種率触，而其有重要的短路效應，如下所示：
本題需要實現(xiàn) “當 n=1 時終止遞歸” 的需求汇竭，可通過短路效應實現(xiàn)葱蝗。
n > 1 && sumNums(n - 1) // 當 n = 1 時 n > 1 不成立 ，此時 “短路” 韩玩，終止后續(xù)遞歸
class Solution:
def __init__(self):
self.res = 0
def sumNums(self, n: int) -> int:
n > 1 and self.sumNums(n - 1)
self.res += n
return self.res
