第 208 场周赛回顾

前言

第一次满分（我有一个压线动作），激动！！！😁
虽然题目难度上确实有降低😅。

第一题：文件夹操作日志搜集器

题解一：模拟

• 遇到 ../ 深度-1
• 遇到 ./ 深度不变
• 遇到 ${文件名} 深度+1

  class Solution {
    public int minOperations(String[] logs) {
        int depth = 0;
        for (String str : logs) {
            switch (str) {
                case "../":
                    if (depth > 0) {
                        --depth;
                    }
                    break;
                case "./":
                    break;
                default:
                    depth++;
            }
        }
        return depth;
    }
  }

第二题：经营摩天轮的最大利润

题解一：模拟

题目描述比较复杂，但只需要模拟即可。我一开始还以为需要用到贪心什么的。

class Solution {
    public int minOperationsMaxProfit(int[] customers, int boardingCost, int runningCost) {
        final int capacity = 4;
        int maxProfit = -1;
        int ans = -1;
        int waitNum = 0;
        int index = 0;
        int profit = 0;
        int period = 0;
        while ((index < customers.length) || (waitNum > 0)) {
            ++period;
            // 新游客到达
            if (index < customers.length) {
                waitNum += customers[index++];
            }
            // 是否能满载
            if (waitNum >= capacity) {
                profit += capacity * boardingCost - runningCost;
                waitNum -= capacity;
            } else {
                profit += waitNum * boardingCost - runningCost;
                waitNum = 0;
            }
            // 更新最大利润
            if (profit > maxProfit) {
                maxProfit = profit;
                ans = period;
            }
        }
        if (maxProfit == -1) {
            return -1;
        } else {
            return ans;
        }
    }
}

第三题：皇位继承顺序

题解一：模拟

题目描述比较长，读懂后根据意思实现各个方法即可。会涉及大量查找操作，用Map来加速查找。

import java.util.*;
class ThroneInheritance {
    // 国王
    private Person king;
    // 人名->人物实例映射表
    private Map<String, Person> personMap;
    // 继承序列
    private List<Person> order;
    // 加速在继承序列中的查找效率
    private Map<String, Person> orderMap;
    public ThroneInheritance(String kingName) {
        king = new Person(null, kingName);
        personMap = new HashMap<>();
        personMap.put(kingName, king);
    }
    public void birth(String parentName, String childName) {
        Person parent = personMap.get(parentName);
        Person temp = new Person(parent, childName);
        parent.children.add(temp);
        personMap.put(childName, temp);
    }
    public void death(String name) {
        Person person = personMap.get(name);
        person.isLive = false;
    }
    public List<String> getInheritanceOrder() {
        order = new LinkedList<>();
        orderMap = new HashMap<>();
        for (Person cur = king; cur != null; cur = successor(cur)) {
            order.add(cur);
            orderMap.put(cur.name, cur);
        }
        List<String> ans = new ArrayList<>(order.size());
        for (Person i : order) {
            if (i.isLive) {
                ans.add(i.name);
            }
        }
        return ans;
    }
    /**
     * 寻找下一顺位继承人
     *
     * @param x 当前继承人
     * @return x的下一顺位继承人
     */
    private Person successor(Person x) {
        if ((x.children.size() == 0) || allIn(x)) {
            if (x.equals(king)) {
                return null;
            } else {
                return successor(x.parent);
            }
        } else {
            for (Person i : x.children) {
                if (!orderMap.containsKey(i.name)) {
                    return i;
                }
            }
        }
        return null;
    }
    /**
     * 判断x的所有孩子是否已经在继承序列中
     *
     * @param x 人
     * @return x的所有孩子均已在继承序列中则返回true, 否则返回false
     */
    private boolean allIn(Person x) {
        for (Person i : x.children) {
            if (!orderMap.containsKey(i.name)) {
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        ThroneInheritance obj = new ThroneInheritance("king");
        obj.birth("king", "andy");
        obj.birth("king", "bob");
        obj.birth("king", "catherine");
        List<String> param_3 = obj.getInheritanceOrder();
        System.out.print(param_3);
    }
}
class Person {
    String name;
    Person parent;
    List<Person> children;
    boolean isLive;
    Person(Person parent, String name) {
        this.name = name;
        this.parent = parent;
        this.children = new LinkedList<>();
        this.isLive = true;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return Objects.equals(name, person.name) && Objects.equals(parent, person.parent);
    }
}
/**
 * Your ThroneInheritance object will be instantiated and called as such:
 * ThroneInheritance obj = new ThroneInheritance(kingName);
 * obj.birth(parentName,childName);
 * obj.death(name);
 * List<String> param_3 = obj.getInheritanceOrder();
 */

第四题：最多可达成的换楼请求数目

题解一：暴搜

应该是一个图论的问题，选若干条边，满足所有点的入度等于出度。我图论还没开始练习。。。。
最后留给我的时间不多了，看了下数据范围 1 <= requests.length <= 16 ，直接暴搜的话，每条请求都考虑执行或不执行，2这个范围根本不大。然后就成了。。。

class Solution {
    private int max;
    public int maximumRequests(int n, int[][] requests) {
        max = 0;
        dfs(n, requests, 0, new int[n], new int[n], 0);
        return max;
    }
    private void dfs(int n, int[][] requests, int index, int[] in, int[] out, int ans) {
        if (index >= requests.length) {
            boolean flag = true;
            for (int i = 0; i < n; ++i) {
                if (in[i] != out[i]) {
                    flag = false;
                    return;
                }
            }
            max = Math.max(max, ans);
            return;
        }
        dfs(n, requests, index + 1, in, out, ans);
        int inNum = requests[index][0];
        int outNum = requests[index][1];
        in[inNum]++;
        out[outNum]++;
        dfs(n, requests, index + 1, in, out, ans + 1);
        in[inNum]--;
        out[outNum]--;
    }
}