# # Leetcode 第57场双周赛题解

## # Problem A - 检查是否所有字符出现次数相同 (opens new window)

### # 方法一：计数

• 时间复杂度$\mathcal{O}(|S|)$
• 空间复杂度$\mathcal{O}(|\sum|)$

class Solution:
def areOccurrencesEqual(self, s: str) -> bool:
return len(set(collections.Counter(s).values())) == 1

1
2
3

## # Problem B - 最小未被占据椅子的编号 (opens new window)

### # 方法一：排序+优先队列

• 时间复杂度为$\mathcal{O}(N\log N)$
• 空间复杂度$\mathcal{O}(N)$

class Solution {
public:
int smallestChair(vector<vector<int>>& times, int targetFriend) {
int n = times.size();
priority_queue<int, vector<int>, greater<>> available;
for (int i = 0; i < n; ++i)
available.emplace(i);
vector<tuple<int, int, int>> events;
for (int i = 0; i < n; ++i) {
events.emplace_back(times[i][1], -1, i);
events.emplace_back(times[i][0], 1, i);
}
sort(events.begin(), events.end());
vector<int> seats(n);

for (auto [_time, event_type, idx] : events) {
if (event_type == 1) {
seats[idx] = available.top();
if (idx == targetFriend)
return seats[idx];
available.pop();
} else {
available.emplace(seats[idx]);
}
}

return -1; // Should not return from here
}
};

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

## # Problem C - 描述绘画结果 (opens new window)

### # 方法一：离散化+差分数组

• 时间复杂度$\mathcal{O}(|S|)$
• 空间复杂度$\mathcal{O}(1)$

class Solution {
public:
vector<vector<long long>> splitPainting(vector<vector<int>>& segments) {
vector<int> endpoints;
for (auto &segment : segments) {
endpoints.emplace_back(segment[0]);
endpoints.emplace_back(segment[1]);
}
sort(endpoints.begin(), endpoints.end());
endpoints.resize(unique(endpoints.begin(), endpoints.end()) - endpoints.begin());
map<int, int> mp;
int idx = 1;
for (int endpoint : endpoints)
mp[endpoint] = idx++;

vector<long long> diff(idx);
for (auto &segment : segments) {
int l = segment[0], r = segment[1], c = segment[2];
diff[mp[l]] += c, diff[mp[r]] -= c;
}

vector<vector<long long>> ans;
long long now = 0;
for (int i = 1; i < idx; ++i) {
now += diff[i];
if (now != 0)
ans.push_back({endpoints[i - 1], endpoints[i], now});
}

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
29
30
31
32

## # Problem D - 队列中可以看到的人数 (opens new window)

### # 方法一：单调栈

[2,8,7,3,4,6,9]

• 时间复杂度$\mathcal{O}(N)$
• 空间复杂度$\mathcal{O}(N)$

class Solution {
public:
vector<int> canSeePersonsCount(vector<int>& heights) {
int n = heights.size();
vector<int> ans(n), R(n, n);
stack<int> st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && heights[st.top()] < heights[i]) {
R[st.top()] = i;
st.pop();
}
st.push(i);
}
for (int i = n - 2; i >= 0; --i) {
int r = i + 1;
while (r < n && heights[r] < heights[i]) {
ans[i]++;
r = R[r];
}
if (r != n)
ans[i]++;
}
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

class Solution {
public:
vector<int> canSeePersonsCount(vector<int>& heights) {
int n = heights.size();
vector<int> ans(n);
stack<int> st;
for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && heights[st.top()] < heights[i]) {
st.pop();
ans[i]++;
}
if (!st.empty())
ans[i]++;
st.push(i);
}
return ans;
}
};

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