第二题 WA 了一次，其他都能一次 AC。这次拖慢速度的竟然不是手速，而是阅读速度。。。排名150左右。

第一题Crawler Log Folder

给定一系列类似于 cd 的操作，问最后的文件路径深度是多少。

模拟题，因为只需要知道深度，所以我们并不关心文件夹的名字，只考虑对深度影响 ../ -> -1，./ -> 0，其他 -> +1 。

class Solution:
    def minOperations(self, logs: List[str]) -> int:
        depth = 0
        for path in logs:
            if path == '../':
                depth = max(0, depth - 1)
            elif path == './':
                pass
            else:
                depth += 1
        return depth

第二题Maximum Profit of Operating a Centennial Wheel

在这题里我们是一个操作有四个仓位（？）的摩天轮的管理人员！每个仓位最多能坐四个人，每次转一下都有一个 runningCost，上一个人则收费 boardingCost。我们的顾客人数在 customers 数组中，但是 customers[i] 中的顾客需要我们转 i 次才出现。问能达到最大利润的最少操作次数。

也是一题模拟题，带有点贪心的味道。基本思路就是每次尽量让 4 个人上。

class Solution:
    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:
        if 4 * boardingCost <= runningCost:
            return -1
        cnt = profit = 0
        total = 0
        cprofit = ccnt = 0
        for i, c in enumerate(customers):
            if ccnt < i:
                cprofit += total * boardingCost - (i - ccnt) * runningCost
                ccnt = i
                total = 0
            total += c
            t = total // 4
            cprofit += (4 * boardingCost - runningCost) * t
            ccnt += t
            total %= 4
            if cprofit > profit:
                profit, cnt = cprofit, ccnt
        if total > 0:
            cprofit += (total * boardingCost - runningCost)
            ccnt += 1
        if cprofit > profit:
            profit, cnt = cprofit, ccnt
        if cprofit > 0:
            return cnt
        return -1

第三题Throne Inheritance

树的前序遍历。

题目很长，但是看下来就是树的前序遍历：初始化给定根节点的名字，birth 给出一个节点的子节点，death 标记一个节点让其不出现前序遍历中，getInheritanceOrder 前序遍历当前的树。

class ThroneInheritance:

    def __init__(self, kingName: str):
        self.king = kingName
        self.children = collections.defaultdict(list)
        self.deaths = set()


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


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


    def getInheritanceOrder(self) -> List[str]:
        ans = []
        deaths = self.deaths
        children = self.children
        def dfs(root):
            if root not in deaths:
                ans.append(root)
            for c in children[root]:
                dfs(c)
        dfs(self.king)
        return ans

第四题Maximum Number of Achievable Transfer Requests

给定一个无向图，我们需要找出每个点出度和入度都相同的子图的最大边数。

看到题目我一点头绪都没有，但是看了一下数据规模：图的最大边数是16。果断暴力枚举所有子图。如果一条边是一个环，那么最大边数的子图必然包含这条边，所以我们可以做一个简单的优化：去除所有的环。

class Solution:
    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:
        ans = [0]
        reqs = []
        for a, b in requests:
            if a == b:
                ans[0] += 1
            else:
                reqs.append([a, b])

        def dfs(i, cnt, deg):
            if i == len(reqs):
                if all(v == 0 for v in deg.values()):
                    ans[0] = max(ans[0], cnt)
            else:
                dfs(i + 1, cnt, deg)
                a, b = reqs[i]
                deg[a] -= 1
                deg[b] += 1
                dfs(i + 1, cnt + 1, deg)
                deg[a] += 1
                deg[b] -= 1

        dfs(0, ans[0], collections.Counter())
        return ans[0]
leetcode contest