[Leetcode/Python3] 第208场周赛

P1 文件夹操作日志搜集器

每当用户执行变更文件夹操作时，LeetCode 文件系统都会保存一条日志记录。

下面给出对变更操作的说明：

“…/” ：移动到当前文件夹的父文件夹。如果已经在主文件夹下，则 继续停留在当前文件夹 。

“./” ：继续停留在当前文件夹。

“x/” ：移动到名为 x 的子文件夹中。题目数据 保证总是存在文件夹 x 。

给你一个字符串列表 logs ，其中 logs[i] 是用户在 ith 步执行的操作。

文件系统启动时位于主文件夹，然后执行 logs 中的操作。

执行完所有变更文件夹操作后，请你找出 返回主文件夹所需的最小步数 。

class Solution:
    def minOperations(self, logs: List[str]) -> int:
        ans = 0
        for log in logs:
            if log == "./":
                continue
            elif log == "../":
                ans = max(0, ans - 1)
            else:    
                ans += 1
        return ans  
           

P2 经营摩天轮的最大利润

你正在经营一座摩天轮，该摩天轮共有 4 个座舱 ，每个座舱 最多可以容纳 4 位游客 。你可以 逆时针 轮转座舱，但每次轮转都需要支付一定的运行成本 runningCost 。摩天轮每次轮转都恰好转动 1 / 4 周。

给你一个长度为 n 的数组 customers ， customers[i] 是在第 i 次轮转（下标从 0 开始）之前到达的新游客的数量。这也意味着你必须在新游客到来前轮转 i 次。每位游客在登上离地面最近的座舱前都会支付登舱成本 boardingCost ，一旦该座舱再次抵达地面，他们就会离开座舱结束游玩。

你可以随时停下摩天轮，即便是 在服务所有游客之前 。如果你决定停止运营摩天轮，为了保证所有游客安全着陆，将免费进行所有后续轮转 。注意，如果有超过 4 位游客在等摩天轮，那么只有 4 位游客可以登上摩天轮，其余的需要等待 下一次轮转 。

返回最大化利润所需执行的 最小轮转次数 。 如果不存在利润为正的方案，则返回 -1 。

class Solution:
    def minOperationsMaxProfit(self, customers: List[int], a: int, b: int) -> int:
        if 4*a<= b: return -1
        w, gain, max_gain, cnt, mi = 0, 0, 0, 0, 0
        idx, n = 0,  len(customers)
        while w > 0 or idx < n:
            x = customers[idx] if idx < n else 0
            idx += 1
            w += x
            gain += a* min(w, 4) - b
            w -= min(w, 4)
            cnt += 1
            if gain > max_gain:
                max_gain = gain
                mi = cnt 
        return mi
           

P3 皇位继承顺序

一个王国里住着国王、他的孩子们、他的孙子们等等。每一个时间点，这个家庭里有人出生也有人死亡。

这个王国有一个明确规定的皇位继承顺序，第一继承人总是国王自己。我们定义递归函数

Successor(x, curOrder)

，给定一个人 x 和当前的继承顺序，该函数返回 x 的下一继承人。

Successor(x, curOrder)

:

如果

x

没有孩子或者所有

x

的孩子都在

curOrder

中：

如果

x

是国王，那么返回

null

否则，返回

Successor(x 的父亲, curOrder)

否则，返回

x 不在 curOrder 中最年长的孩子

比方说，假设王国由国王，他的孩子 Alice 和 Bob （Alice 比 Bob 年长）和 Alice 的孩子 Jack 组成。

• 一开始，

  curOrder

  为

  ["king"].

• 调用

  Successor(king, curOrder)

  ，返回

  Alice

  ，所以我们将 Alice 放入

  curOrder

  中，得到

  ["king", "Alice"]

  。
• 调用

  Successor(Alice, curOrder)

  ，返回

  Jack

  ，所以我们将 Jack 放入

  curOrder

  中，得到

  ["king", "Alice", "Jack"]

  。
• 调用

  Successor(Jack, curOrder)

  ，返回

  Bob

  ，所以我们将 Bob 放入

  curOrder

  中，得到

  ["king", "Alice", "Jack", "Bob"]

  。
• 调用

  Successor(Bob, curOrder)

  ，返回

  null

  。最终得到继承顺序为

  ["king", "Alice", "Jack", "Bob"]

  。

  通过以上的函数，我们总是能得到一个唯一的继承顺序。

请你实现

ThroneInheritance

类：

• ThroneInheritance(string kingName)

  初始化一个

  ThroneInheritance

  类的对象。国王的名字作为构造函数的参数传入。

• void birth(string parentName, string childName)

  表示 p

  arentName

  新拥有了一个名为

  childName

  的孩子。

• void death(string name)

  表示名为

  name

  的人死亡。一个人的死亡不会影响

  Successor

  函数，也不会影响当前的继承顺序。你可以只将这个人标记为死亡状态。

  string[] getInheritanceOrder()

  返回 除去 死亡人员的当前继承顺序列表。

代码

class ThroneInheritance:

    def __init__(self, kingName: str):
        self.dead = set()
        self.chd = collections.defaultdict(list)
        self.fa = collections.defaultdict(str)
        self.root = kingName
        


    def birth(self, parentName: str, childName: str) -> None:
        self.chd[parentName].append(childName)
        self.fa[childName] = parentName

    def death(self, name: str) -> None:
        self.dead.add(name)


    def getInheritanceOrder(self) -> List[str]:
        ret = []
        def dfs(root):
            nonlocal ret
            if root not in self.dead:
                ret.append(root)
            for x in self.chd[root]:
                dfs(x)    
        dfs(self.root)        
        return ret 
           

P4 最多可达成的换楼请求数目

我们有 n 栋楼，编号从 0 到 n - 1 。每栋楼有若干员工。由于现在是换楼的季节，部分员工想要换一栋楼居住。

给你一个数组 requests ，其中 requests[i] = [fromi, toi] ，表示一个员工请求从编号为 fromi 的楼搬到编号为 toi 的楼。

一开始 所有楼都是满的，所以从请求列表中选出的若干个请求是可行的需要满足 每栋楼员工净变化为 0 。意思是每栋楼 离开 的员工数目 等于 该楼 搬入 的员工数数目。比方说 n = 3 且两个员工要离开楼 0 ，一个员工要离开楼 1 ，一个员工要离开楼 2 ，如果该请求列表可行，应该要有两个员工搬入楼 0 ，一个员工搬入楼 1 ，一个员工搬入楼 2 。

请你从原请求列表中选出若干个请求，使得它们是一个可行的请求列表，并返回所有可行列表中最大请求数目。

代码

class Solution:
    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:
        m = len(requests)
        ans = 0
        for i in range(1 << m):
            tmp = [0]*n
            cnt = 0
            for k in range(m):
                if (i & (1 << k )) != 0:
                    cnt += 1
                    a, b = requests[k]
                    tmp[a] += 1
                    tmp[b] -= 1
            if tmp == [0] * n:        
                ans = max(ans, cnt)
                
        return ans