0%

leetcode-208场周赛

Posted on In ,

第208场周赛

##文件夹操作日志搜集器

image1

如果进入子文件夹最小步数就要+1，如果是回退符就-1，如果最小步数等于0，那么碰到回退符也不-1。

1
class Solution {
2
    public int minOperations(String[] logs) {
3
        int ans = 0;
4
        int n = logs.length;
5
        for(int i=0; i<n; i++){
6
            if(logs[i].equals("../")){
7
                if(ans > 0){
8
                    ans--;
9
                }else{
10
                    continue;
11
                }
12
            }else if(logs[i].equals("./")){
13
                continue;
14
            }else{
15
                ans++;
16
            }
17
        }
18
        return ans;
19
    }
20
}

经营摩天轮的最大利润

image2

image3

每一次轮转最多上4人，多的人数就要进入等待。记录每一次轮转后的利润和轮次数，如果利润高于最大利润，就更新最大利润和轮次数。遍历完顾客数组后如果还有剩余等待的人，那么就继续轮转，直到所有顾客都上摩天轮。而且轮转结束不需要所有顾客都下摩天轮，只需要都上摩天轮即可。

1
class Solution {
2
    public int minOperationsMaxProfit(int[] customers, int boardingCost, int runningCost) {
3
        int ans = 0,turn = 0,sum = 0,remain = 0;
4
        int profit = -(int)1e5;
5
        int n = customers.length;
6
        for(int i=0; i<n; i++){
7
            turn++;
8
            remain += customers[i];
9
            int num = Math.min(4, remain);
10
            sum += num*boardingCost - runningCost;
11
            if(sum > profit){
12
                profit = sum;
13
                ans = turn;
14
            }
15
            remain -= num;
16
        }
17
        while(remain > 0){
18
            turn++;
19
            int num = Math.min(4, remain);
20
            sum += num*boardingCost - runningCost;
21
            if(sum > profit){
22
                profit = sum;
23
                ans = turn;
24
            }
25
            remain -= num;
26
        }
27
        return profit>0 ? ans:-1;
28
    }
29
}

皇位继承顺序

image4

image5

多叉树的先序遍历。同时记录一个死亡名单集合，在得到顺序的时候，如果该名字在死亡名单中，就不加入继承列表。继承列表顺序就是多叉树的先序遍历顺序。

1
class ThroneInheritance {
2
    Map<String, List<String>> map = new HashMap<>();
3
    Set<String> dead = new HashSet<>();
4
    String kingName;
5
    public ThroneInheritance(String kingName) {
6
        this.kingName = kingName;
7
        map.put(kingName, new ArrayList<String>());
8
    }
9
    
10
    public void birth(String parentName, String childName) {
11
        if(map.containsKey(parentName)){
12
            map.get(parentName).add(childName);
13
        }else{
14
            List<String> temp = new ArrayList<String>();
15
            temp.add(childName);
16
            map.put(parentName, temp);
17
        }
18
    }
19
    
20
    public void death(String name) {
21
        dead.add(name);
22
    }
23
    
24
    public List<String> getInheritanceOrder() {
25
        List<String> res = new ArrayList<>();
26
        if(!dead.contains(kingName)){
27
            res.add(kingName);
28
        }
29
        dfs(kingName, res);
30
        return res;
31
    }
32
33
    public void dfs(String name, List<String> res){
34
        if(!map.containsKey(name)){
35
            return;
36
        }
37
        List<String> list = map.get(name);
38
        for(String a : list){
39
            if(!dead.contains(a)){
40
                res.add(a);
41
            }
42
            dfs(a, res);
43
        }
44
    }
45
}
46
47
/**
48
 * Your ThroneInheritance object will be instantiated and called as such:
49
 * ThroneInheritance obj = new ThroneInheritance(kingName);
50
 * obj.birth(parentName,childName);
51
 * obj.death(name);
52
 * List<String> param_3 = obj.getInheritanceOrder();
53
 */

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

image6

image7

一共有m个请求，那么就有$2^m$种请求情况，数据规模不是很大，那么就可以暴力枚举每一种请求情况，判断是否可以满足。如何判断该种请求情况是否可以满足，使用一个数组delta来记录每幢楼的换入换出情况，换入就++，换出就–，最后等于0就说明可以满足，否则不可以。使用状态压缩即$[0,2^m-1]$中的数字还表示每一种请求情况，数字中$1$表示该请求被允许，$0$表示不被允许，每次与$1$做$&$操作判断，之后再右移1位。

1
class Solution {
2
    public int maximumRequests(int n, int[][] requests) {
3
        int m = requests.length;
4
        int ans = 0;
5
        for(int state=0; state<(1<<m); state++){
6
            ans = Math.max(ans, solve(state, n, requests));
7
        }
8
        return ans;
9
    }
10
11
    public int solve(int state, int n, int[][] requests){
12
        int[] delta = new int[n];
13
        Arrays.fill(delta, 0);
14
        int index = 0, res = 0;
15
        while(state != 0){
16
            if((state&1) == 1){
17
                delta[requests[index][0]]--;
18
                delta[requests[index][1]]++;
19
                res++;
20
            }
21
            state = state>>1;
22
            index++;
23
        }
24
        for(int i=0; i<n; i++){
25
            if(delta[i] != 0){
26
                return -1;
27
            }
28
        }
29
        return res;
30
    }
31
}