2020秋季个人赛


第一题:https://leetcode-cn.com/contest/season/2020-fall/problems/nGK0Fy/
第二题:https://leetcode-cn.com/contest/season/2020-fall/problems/2vYnGI/
第三题:https://leetcode-cn.com/contest/season/2020-fall/problems/UlBDOe/
第四题:https://leetcode-cn.com/contest/season/2020-fall/problems/meChtZ/
第五题:https://leetcode-cn.com/contest/season/2020-fall/problems/Za25hA/

一、速算机器人

小扣在秋日市集发现了一款速算机器人。店家对机器人说出两个数字(记作 xy),请小扣说出计算指令:

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

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 仅包含小写字符 ry, 其中字符 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种模式下的状态转移方程,可以的
# DP厉害啊,从无到有

四、快速公交

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

小扣从 x 号站点移动至 x + 1 号站点需要花费的时间为 inc
小扣从 x 号站点移动至 x - 1 号站点需要花费的时间为 dec

现有 m 辆公交车,编号为 0m-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
        
# from copy
# 核心思想:记忆化递归
# 从终点回到起点,4种方式

五、追逐游戏

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

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

  • 移动至相邻景点
  • 留在原地

如果小力追到小扣(即两人于某一时刻出现在同一位置),则游戏结束。若小力可以追到小扣,请返回最少需要多少回合;若小力无法追到小扣,请返回 -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

# from copy

小结

二题选手,要好好努力了

多跟大佬学习,多刷知识


文章作者: ╯晓~
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ╯晓~ !
评论
  目录