欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页  >  IT编程

[LeetCode/Python] LCCUP 20 参赛题解

程序员文章站 2022-04-16 19:48:25
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: s...

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 ) f(x,y,ans) = f(x + ans, y , ans + ans) or f(x, ans + y, ans + ans) f(x,y,ans)=f(x+ans,y,ans+ans)orf(x,ans+y,ans+ans)
对A，B两种操作：
x = x + ( x + y ) x = x + (x + y) x=x+(x+y)
y = y + ( x + y ) y = y + (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]
    状态转移 0 → { 0 , 1 } , 1 → { 1 , 2 } , 2 → { 2 } 0 \rightarrow\{0,1\}, 1 \rightarrow \{1,2\}, 2 \rightarrow \{2\} 0→{0,1},1→{1,2},2→{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)

  1. Jump数组比较小可以直接遍历。
  2. 避免出现死循环， 对小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

难点在于正确分析题意：

  1. n n n条边n个顶点组成的图，有且只有一个环。
  2. 判断胜负条件：
    如果后手可以提前到达环，则后手赢，这里还需要满足环的大小大于3。
  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

小结

  1. P1 到 P3基本是打卡的题
  2. P4其实不难解法很常规， 但是在inc和dec的计算时，搞错了顺序。
  3. P5比赛时，没做出来。 赛后看了下确实是很难， 因为不但少判了环的大小， 还超时了。 找环的时候没写剥洋葱法， 写了个dfs超时的。

本文地址：https://blog.csdn.net/weixin_42227482/article/details/108572942

相关标签： python3 leetcode周赛

上一篇： 4599元游戏利器！AMD RX 6800开箱图赏

下一篇： 用Java编写猜数字小游戏

推荐阅读