# # 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, i);
events.emplace_back(times[i], 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);
endpoints.emplace_back(segment);
}
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, r = segment, c = segment;
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
{"ft_lang_label":"__label__zh","ft_lang_prob":0.63591105,"math_prob":0.9905242,"size":3934,"snap":"2023-14-2023-23","text_gpt3_token_len":2100,"char_repetition_ratio":0.11501272,"word_repetition_ratio":0.3212928,"special_character_ratio":0.37493646,"punctuation_ratio":0.19028871,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9926808,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-06-08T08:15:30Z\",\"WARC-Record-ID\":\"<urn:uuid:a7929bf7-82ed-48c3-a2af-6c80aef2b104>\",\"Content-Length\":\"91048\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:6320fd48-0f46-4ed7-a271-1b7b970cdb34>\",\"WARC-Concurrent-To\":\"<urn:uuid:34f977ed-bce2-4fbc-b927-01d2aa36e53e>\",\"WARC-IP-Address\":\"76.76.21.123\",\"WARC-Target-URI\":\"https://cp-wiki.vercel.app/tutorial/leetcode/BC57/\",\"WARC-Payload-Digest\":\"sha1:STSXPJ32IBZWAT6ZGF4Z3VVP34NAK25G\",\"WARC-Block-Digest\":\"sha1:M3AYG54DFJ353BVXVBSXGTXSQA2FZEKN\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-23/CC-MAIN-2023-23_segments_1685224654606.93_warc_CC-MAIN-20230608071820-20230608101820-00636.warc.gz\"}"}