# # Leetcode 第208场周赛题解

## # Problem A - 文件夹操作日志搜集器 (opens new window)

class Solution {
public:
int minOperations(vector<string>& logs) {
int depth = 0;
for (auto s : logs) {
if (s == "./")
continue;
if (s == "../")
depth = max(0, depth - 1);
else
depth++;
}
return depth;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

## # Problem B - 经营摩天轮的最大利润 (opens new window)

class Solution {
public:
int minOperationsMaxProfit(vector<int>& customers, int boardingCost, int runningCost) {
int hi = INT_MIN;
int profit = 0, rem = 0, idx = -1;
int turn = 0;
for (int c : customers) {
turn++;
profit -= runningCost;
rem += c;
int b = min(4, rem);
profit += b * boardingCost;
rem -= b;
if (hi < profit) {
hi = profit;
idx = turn;
}
}
while (rem) {
turn++;
int b = min(4, rem);
rem -= b;
profit += b * boardingCost - runningCost;
if (hi < profit) {
hi = profit;
idx = turn;
}
}
return hi > 0 ? idx : -1;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

## # Problem C - 皇位继承顺序 (opens new window)

• birth$O(1)$
• death$O(1)$
• getInheritanceOrder$O(N)$

class ThroneInheritance {
unordered_map<string, vector<string>> children;
string king;
vector<string> order;
void dfs(string u) {
order.emplace_back(u);
for (string v : children[u])
dfs(v);
}
public:
ThroneInheritance(string kingName) {
king = kingName;
children[kingName] = {};
}

void birth(string parentName, string childName) {
children[parentName].emplace_back(childName);
}

void death(string name) {
}

vector<string> getInheritanceOrder() {
order.clear();
dfs(king);
return order;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

## # Problem D - 最多可达成的换楼请求数目 (opens new window)

class Solution {
public:
int maximumRequests(int n, vector<vector<int>>& requests) {
int m = requests.size();
int ans = 0;
for (int i = 1; i < (1 << m); ++i) {
int c = __builtin_popcount(i);
if (c <= ans)
continue;
vector<int> delta(n);
for (int j = 0; j < m; ++j) {
if (!(i & (1 << j)))
continue;
delta[requests[j][0]]--;
delta[requests[j][1]]++;
}
bool ok = true;
for (int j : delta)
if (j != 0) {
ok = false;
break;
}
if (ok)
ans = max(ans, c);
}
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28