一、速算机器人
小扣在秋日市集发现了一款速算机器人。店家对机器人说出两个数字（记作 x 和 y），请小扣说出计算指令：
"A" 运算：使 x = 2 * x + y；"B" 运算：使 y = 2 * y + x。
在本次游戏中，店家说出的数字为 x = 1 和 y = 0，小扣说出的计算指令记作仅由大写字母 A、B 组成的字符串 s，字符串中字符的顺序表示计算顺序，请返回最终 x 与 y 的和为多少。
class Solution:
def calculate(self, s: str) -> int:
x,y=1,0
for i in s:
if i=='A': x=2*x+y
else: y=2*y+x
return x+y
二、早餐组合
小扣在秋日市集选择了一家早餐摊位，一维整型数组 staple 中记录了每种主食的价格，一维整型数组 drinks 中记录了每种饮料的价格。小扣的计划选择一份主食和一款饮料，且花费不超过 x 元。请返回小扣共有多少种购买方案。
注意：答案需要以 1e9 + 7 (1000000007) 为底取模，如：计算初始结果为：1000000008，请返回 1
class Solution:
def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:
mod=1000000007
staple.sort()
drinks.sort()
ans=0
for s in staple:
a=bisect.bisect_right(drinks,x-s)
if a:
ans+=bisect.bisect_right(drinks,x-s)
else:
break
return ans%mod
### bisect的二分，防止超时。
三、秋叶收藏集
小扣出去秋游，途中收集了一些红叶和黄叶，他利用这些叶子初步整理了一份秋叶收藏集 leaves， 字符串 leaves 仅包含小写字符 r 和 y， 其中字符 r 表示一片红叶，字符 y 表示一片黄叶。
出于美观整齐的考虑，小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等，但均需大于等于 1。每次调整操作，小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。
# 思路：
# 1. 动态规划
# 2. dp[i][0]表示全部为红需要修改几次
# dp[i][1]表示【红黄】需要修改几次
# dp[i][2]表示【红黄红】需要修改几次
class Solution:
def minimumOperations(self, leaves: str) -> int:
n=len(leaves)
dp=[[0 for i in range(3)] for _ in range(n)]
dp[0][0]= 0 if leaves[0]=='r' else 1
for i in range(1,n):
dp[i][0]=dp[i-1][0]+(0 if leaves[i]=='r' else 1)
dp[i][1]=dp[i-1][0]+(0 if leaves[i]=='y' else 1)
if i>1:
dp[i][1]=min(dp[i][1],dp[i-1][1]+(0 if leaves[i]=='y' else 1))
dp[i][2]=dp[i-1][1]+(0 if leaves[i]=='r' else 1)
if i>2:
dp[i][2]=min(dp[i][2],dp[i-1][2]+(0 if leaves[i]=='r' else 1))
return dp[n-1][2]
# 3种模式下的状态转移方程
# DP666
四、快速公交
小扣打算去秋日市集，由于游客较多，小扣的移动速度受到了人流影响：
小扣从 x 号站点移动至 x + 1 号站点需要花费的时间为 inc；
小扣从 x 号站点移动至 x - 1 号站点需要花费的时间为 dec。
现有 m 辆公交车，编号为 0 到 m-1。小扣也可以通过搭乘编号为 i 的公交车，从 x 号站点移动至 jump[i]*x 号站点，耗时仅为 cost[i]。小扣可以搭乘任意编号的公交车且搭乘公交次数不限。
假定小扣起始站点记作 0，秋日市集站点记作 target，请返回小扣抵达秋日市集最少需要花费多少时间。由于数字较大，最终答案需要对 1000000007 (1e9 + 7) 取模。
注意：小扣可在移动过程中到达编号大于 target 的站点。
from functools import lru_cache
class Solution:
def busRapidTransit(self, target: int, inc: int, dec: int, jump: List[int], cost: List[int]) -> int:
@lru_cache(None)
def min_cost(target):
if target == 0:
return 0
cur_cost = inc * target # 1.直接走回站点
for i in range(len(jump)):
if target % jump[i] == 0:
cur_cost = min(cur_cost, min_cost(target // jump[i]) + cost[i])
continue
# 2.刚好有公交
cur_cost = min(cur_cost, min_cost(target // jump[i]) + cost[i] + (target % jump[i]) * inc)
# 3.往前走再公交
if target > 1:
cur_cost = min(cur_cost, min_cost(target // jump[i] + 1) + cost[i] + (jump[i] - target % jump[i]) * dec)
# 4. 往后走再公交
return cur_cost
mod = 10 ** 9 + 7
return min_cost(target) % mod
# copy
# 核心思想：记忆化递归
# 从终点回到起点，4种方式
五、追逐游戏
秋游中的小力和小扣设计了一个追逐游戏。他们选了秋日市集景区中的 N 个景点，景点编号为 1~N。此外，他们还选择了 N 条小路，满足任意两个景点之间都可以通过小路互相到达，且不存在两条连接景点相同的小路。整个游戏场景可视作一个无向连通图，记作二维数组 edges，数组中以 [a,b] 形式表示景点 a 与景点 b 之间有一条小路连通。
小力和小扣只能沿景点间的小路移动。小力的目标是在最快时间内追到小扣，小扣的目标是尽可能延后被小力追到的时间。游戏开始前，两人分别站在两个不同的景点 startA 和 startB。每一回合，小力先行动，小扣观察到小力的行动后再行动。小力和小扣在每回合可选择以下行动之一：
- 移动至相邻景点
- 留在原地
如果小力追到小扣（即两人于某一时刻出现在同一位置），则游戏结束。若小力可以追到小扣，请返回最少需要多少回合；若小力无法追到小扣，请返回 -1。
注意：小力和小扣一定会采取最优移动策略。
class Solution:
def chaseGame(self, edges: List[List[int]], startA: int, startB: int) -> int:
def get_cycle(graph, start=startA):
cycle = set()
father = [-1 for i in range(n + 1)]
depth = [-1 for i in range(n + 1)]
father[start] = start
depth[start] = 0
queue = [start]
i = 0
while i < len(queue):
u = queue[i]
for v in graph[u]:
if depth[v] < 0:
depth[v] = depth[u] + 1
father[v] = u
queue.append(v)
else:
if father[u] == v:
continue
while depth[u] > depth[v]:
cycle.add(u)
u = father[u]
while depth[v] > depth[u]:
cycle.add(v)
v = father[v]
while u != v:
cycle.add(u)
cycle.add(v)
u = father[u]
v = father[v]
cycle.add(u)
return cycle
i += 1
def bfs(graph, cycle, start, n):
circle_pos = -1
min_arrival = float('inf')
arr = [-1 for i in range(n + 1)]
arr[start] = 0
queue = [start]
i = 0
while i < len(queue):
u = queue[i]
if u in cycle and arr[u] < min_arrival:
circle_pos = u
min_arrival = arr[u]
for v in graph[u]:
if arr[v] < 0:
arr[v] = arr[u] + 1
queue.append(v)
i += 1
return arr, circle_pos
n = len(edges)
graph = [[] for i in range(n + 1)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
cycle = get_cycle(graph)
arrA, posA = bfs(graph, cycle, startA, n)
arrB, posB = bfs(graph, cycle, startB, n)
# print(cycle)
# print(arrA, posA, arrA[posA])
# print(arrB, posB, arrB[posB])
if arrA[startB] <= 1:
return arrA[startB]
if arrA[posB] > arrB[posB] + 1 and len(cycle) >= 4:
return -1
ans = arrA[startB]
queue = [startB]
i = 0
arrived = set(queue)
while i < len(queue):
u = queue[i]
for v in graph[u]:
if v not in arrived and arrA[v] > arrB[v] + 1:
arrived.add(v)
queue.append(v)
ans = max(ans, arrA[v])
else:
ans = max(ans, arrA[v])
i += 1
return ans
# copy
