LeetCode 208 周赛

1. 文件夹操作日志搜集器

简单模拟

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

2. 经营摩天轮的最大利润

模拟

class Solution:
    def minOperationsMaxProfit(self, customers: List[int],
                               boardingCost: int, runningCost: int) -> int:
        ans = 0
        res = 0
        p = 0
        w = 0
        i = 0
        for c in customers:
            i += 1
            w += c
            b = min(w, 4)
            w -= b
            p += b * boardingCost - runningCost
            if p > res:
                res = p
                ans = i
        while w:
            i += 1
            b = min(w, 4)
            w -= b
            p += b * boardingCost - runningCost
            if p > res:
                res = p
                ans = i
        return ans if ans else -1

3. 皇位继承顺序

树节点的设计，和dfs先序遍历

class TreeNode:
    def __init__(self, name):
        self.name = name
        self.children = []
        self.is_death = False


class ThroneInheritance:

    def __init__(self, kingName: str):
        self.root = TreeNode(kingName)
        self.mem = {kingName: self.root}

    def birth(self, parentName: str, childName: str) -> None:
        p_node = self.mem[parentName]
        c_node = TreeNode(childName)
        p_node.children.append(c_node)
        self.mem[childName] = c_node

    def death(self, name: str) -> None:
        node = self.mem[name]
        node.is_death = True

    def getInheritanceOrder(self) -> List[str]:
        res = []
        stack = [self.root]
        while stack:
            node = stack.pop()
            if not node.is_death:
                res.append(node.name)
            for child in reversed(node.children):
                stack.append(child)
        return res

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

状态压缩dp，以及了解图中任何一个节点入度与出度相等时，就满足净变化为0

class Solution {
    int tot[25];
public:
    int maximumRequests(int n, vector<vector<int>> &req) {
        int ans = 0;
        int m = req.size();
        int lim = (1 << m) - 1;
        for (int i = 1; i <= lim; ++i) {
            for (int j = 0; j < n; ++j) tot[j] = 0;
            int cnt = 0;
            for (int j = 0, k = 1; j < m; ++j, k <<= 1)
                if (i & k) {
                    ++tot[req[j][1]], --tot[req[j][0]];
                    ++cnt;
                }
            bool flag = true;
            for (int j = 0; j < n; ++j) {
                if (tot[j] != 0) {
                    flag = false;
                    break;
                }
            }
            if (flag) ans = max(ans, cnt);
        }
        return ans;
    }
};