[LeetCode/Python] LCCUP 20 参赛题解_Python

P1 速算机器人

小扣在秋日市集发现了一款速算机器人。店家对机器人说出两个数字（记作 x 和 y），请小扣说出计算指令：

“A” 运算：使 x = 2 * x + y；
“B” 运算：使 y = 2 * y + x。
在本次游戏中，店家说出的数字为 x = 1 和 y = 0，小扣说出的计算指令记作仅由大写字母 A、B 组成的字符串 s，字符串中字符的顺序表示计算顺序，请返回最终 x 与 y 的和为多少。

模拟(AC)

class Solution:
    def calculate(self, s: str) -> int:
        x = 1
        y = 0
        for ch in s:
            if ch == 'A':
                x = 2 * x + y
            if ch == 'B':
                y = 2 * y + x 
        return x + y

数学(AC)

这个方法是赛后想到的，我们用函数式编程来做
$f (x, y, a n s) = f (x + a n s, y, a n s + a n s) o r f (x, a n s + y, a n s + a n s)$
对A，B两种操作：
$x = x + (x + y)$
$y = y + (x + y)$
每次操作都是将ans加倍。

class Solution:
    def calculate(self, s: str) -> int:
        return 1 << len(s)

P2 早餐组合

小扣在秋日市集选择了一家早餐摊位，一维整型数组 staple 中记录了每种主食的价格，一维整型数组 drinks 中记录了每种饮料的价格。小扣的计划选择一份主食和一款饮料，且花费不超过 x 元。请返回小扣共有多少种购买方案。

注意：答案需要以 1e9 + 7 (1000000007) 为底取模，如：计算初始结果为：1000000008，请返回 1

双指针(AC)

class Solution:
    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:
        A = sorted(staple)
        B = sorted(drinks)
        n, m = len(A), len(B)
        mod = 10**9 + 7
        i = 0
        j = m -1
        ans = 0
        while i < n and j >= 0:
            while j >= 0 and A[i] + B[j] > x:
                j -= 1
            ans = (ans + j+1) % mod    
            i += 1
        return ans

P3 秋叶收藏集

小扣出去秋游，途中收集了一些红叶和黄叶，他利用这些叶子初步整理了一份秋叶收藏集 leaves，字符串 leaves 仅包含小写字符 r 和 y，其中字符 r 表示一片红叶，字符 y 表示一片黄叶。
出于美观整齐的考虑，小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等，但均需大于等于 1。每次调整操作，小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。

DP (AC)

维护三个状态:

0 -> [RRRR]
1 -> [RRRRYYY]
2 -> [RRRYYYRR]
状态转移 $\rightarrow\{0,1\}, 1 \rightarrow \{1,2\}, 2 \rightarrow \{2\}$
初始化：根据第一个字符。

class Solution:
    def minimumOperations(self, leaves: str) -> int:
        n = len(leaves)
        inf = n
        cost = [[inf] * n for _ in range(3)]
        #initial 0
        if leaves[0] == 'r':
            cost[0][0] = 0
        else:
            cost[0][0] = 1
        for i in range(1,n):
            if leaves[i] == 'r':
                cost[0][i] = cost[0][i-1]
                cost[1][i] = min(cost[0][i-1] + 1, cost[1][i-1] + 1) 
                cost[2][i] = min(cost[2][i-1], cost[1][i-1])
            if leaves[i] == 'y':
                cost[0][i] = cost[0][i-1] + 1
                cost[1][i] = min(cost[1][i-1], cost[0][i-1])  
                cost[2][i] = min(cost[2][i-1] + 1, cost[1][i-1] + 1)
        #for x in cost: print(x)        
        return cost[2][-1]

P4 快速公交

小扣打算去秋日市集，由于游客较多，小扣的移动速度受到了人流影响：

小扣从 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 的站点。
提示：

1 <= target <= 10^9
1 <= jump.length, cost.length <= 10
2 <= jump[i] <= 10^6
1 <= inc, dec, cost[i] <= 10^6

DP (AC)

Jump数组比较小可以直接遍历。
避免出现死循环，对小Jump的跳跃，要特殊处理。

from functools import lru_cache
class Solution:
    def busRapidTransit(self, target: int, inc: int, dec: int, jump: List[int], cost: List[int]) -> int:
        inc, dec = dec, inc
        inf = 10 ** 15
        mod = 10 ** 9 + 7
        n = len(jump)
        @lru_cache(None)
        def dp(x):
            if x == 0: return 0
            ret = x * dec 
            for i in range(n):
                if x % jump[i] == 0:
                    ret = min(ret, cost[i] + dp(x // jump[i]))
                elif x < jump[i]:    
                    ret = min(ret, x * dec , (jump[i] - x) * inc + cost[i] + dec)
                else:    
                    p = x % jump[i]
                    q = x // jump[i]
                    ret = min(ret, cost[i] + dp(q) + p * dec, cost[i] + dp(q+1) + (jump[i] - p) * inc)
            return ret        
        ans = dp(target)
        #print(ans, mod, ans % mod)
        return ans % mod

P5 追逐游戏

秋游中的小力和小扣设计了一个追逐游戏。他们选了秋日市集景区中的 N 个景点，景点编号为 1~N。此外，他们还选择了 N 条小路，满足任意两个景点之间都可以通过小路互相到达，且不存在两条连接景点相同的小路。整个游戏场景可视作一个无向连通图，记作二维数组 edges，数组中以 [a,b] 形式表示景点 a 与景点 b 之间有一条小路连通。

小力和小扣只能沿景点间的小路移动。小力的目标是在最快时间内追到小扣，小扣的目标是尽可能延后被小力追到的时间。游戏开始前，两人分别站在两个不同的景点 startA 和 startB。每一回合，小力先行动，小扣观察到小力的行动后再行动。小力和小扣在每回合可选择以下行动之一：

移动至相邻景点
留在原地

如果小力追到小扣（即两人于某一时刻出现在同一位置），则游戏结束。若小力可以追到小扣，请返回最少需要多少回合；若小力无法追到小扣，请返回 -1。

注意：小力和小扣一定会采取最优移动策略。

无向图找环 + DFS

难点在于正确分析题意：

$n$ 条边n个顶点组成的图，有且只有一个环。
判断胜负条件：
如果后手可以提前到达环，则后手赢，这里还需要满足环的大小大于3。
计算后手失败时，先手需要付出的最大代价。后手能优先于先手达到的点中，先手最远的点。

class Solution:
    def chaseGame(self, edges: List[List[int]], startA: int, startB: int) -> int:
        # find the cycle
        # edges == n, only one cycle
        n = len(edges)
        startA, startB = startA - 1, startB - 1
        graph = collections.defaultdict(list)
        for a, b in edges:
            a, b = a - 1, b - 1
            graph[a].append(b)
            graph[b].append(a)
            if (a == startA and b == startB) or (a == startB and b == startA): return 1
        cycle = self.find_cycle(n, edges, graph)
        pa = self.min_path(n, startA, graph)
        pb = self.min_path(n, startB, graph)
        #print(pa)
        #print(pb)
        #print(cycle)
        ans = 0
        for i in range(n):
            if pa[i] > pb[i] + 1: 
                ans = max(ans, pa[i])
                if i in cycle and len(cycle) > 3:
                    return -1
        return ans
    def find_cycle(self, n, edges, graph):
        deg = [0] * n
        for a, b in edges:
            a, b = a-1, b-1
            deg[a] += 1
            deg[b] += 1
        Q = [i for i in range(n) if deg[i] == 1]    
        while Q:
            h = Q.pop()
            deg[h] -= 1
            for x in graph[h]:
                deg[x] -= 1
                if deg[x] == 1:
                    Q.append(x)
        return set([i for i in range(n) if deg[i] == 2])
    def min_path(self, n, u, graph):
        A = [-1] * n
        A[u], Q = 0, [u]
        while Q:
            q = Q[0]
            del Q[0]
            for x in graph[q]:
                if A[x] == -1:
                    A[x] = A[q] + 1
                    Q.append(x)
                
        return A