把这个网站重新用起来的动机，是感觉自己明明做了很多，但总觉得什么都没做。所以计划强迫自己记录下来，以防自己真的什么都没干。
先把最近的一些活动，列下来
- 头发
- 游泳
- 滑雪
- 健身房
- 阅读笔记
Daily Leetcode
1220. 统计元音字母序列的数目
线性DP 矩阵快速幂
首先要定义一个 $ f[i][j] $ 为考虑长度为i的字符串，其末尾是j的方案数。
j 代表 ['a', 'e', 'i', 'o', 'u']定义转移方程
根据题目给出的条件
- 每个元音 'a' 后面都只能跟着 'e'
f[i+1][1] += f[i][0] - 每个元音 'e' 后面只能跟着 'a' 或者是 'i'
f[i+1][0] += f[i][1] & f[i+1][2] += f[i][1] - 每个元音 'i' 后面 不能 再跟着另一个 'i'
f[i+1][j] += f[i][2](j 不为2，及 j不代表i) - 每个元音 'o' 后面只能跟着 'i' 或者是 'u'
f[i+1][2] +=f[i][3] & f[i+1][4] += f[i][3] - 每个元音 'u' 后面只能跟着 'a'
f[i+1][0] += f[i][4]
- 每个元音 'a' 后面都只能跟着 'e'
然后作出反推,
i = i-11
2
3
4
5
6
7
8dp = [[0] * 5 for i in range(n)]
dp[0] = [1] * 5
for i in range(1, n):
dp[i][0] = dp[i-1][1] % MOD
dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % MOD
dp[i][2] = ((((dp[i-1][0] + dp[i-1][1]) % MOD + dp[i-1][3]) % MOD) + dp[i-1][4]) % MOD
dp[i][3] = (dp[i-1][2] + dp[i-1][4]) % MOD
dp[i][4] = dp[i-1][0] % MOD- 要注意随时都可能超MOD, 所以要在每次求和之间都要%MOD
快速矩阵幂
// TODO 矩阵快速幂の三部曲
539. 最小时间差
排序；首尾相接
排序之后，首尾相接处理边界情况
模拟；哈希
利用一天最多1440个时间点，可以使得处理的数据没有上限。因为一旦数超过1440个 就肯定会有重复的时间点。扩展当天和下一天时间。这样规避边界情况。
219. 存在重复元素 II
Hash 表
Key: 数字的值，value：下标，只用记最后一次出现的下标。
没有这个key -- 存下
有这个key 看差值是否在范围内。是返回True， 查到结尾没有 返回False
- set + 滑动窗 超过窗口的从set里remove。
2029. 石子游戏 IX
博弈论 数学题
注意 取完的情况下按A输
先把石头都按3取余， 得到0类， 1类， 2类的数目。 分情况讨论。
当 value[0] 是偶数时
- 如果value[1] == 0 时， A必输
- 如果value[2] == 0 时， A必输
- vlaue[1] & value[2]都不为0 A胜
当 value[0] 为奇数时 相当于有一次换手机会
什么情况下会降低A的胜率呢
value[1] value[2] 两者数量差不超过2。 会导致B通过换手使A必败。
838. 推多米诺
模拟
关键在 在左右引入两个虚拟节点。
然后分情况讨论
左右分别向两边 中间 . 就不改变
左右向里， 中间 . 根据数量 看最中间是不是竖直
左右同向 就会是将. 变成一个方向
**注意最后保存的时候不要用到一开始设定的虚拟节点。