# # Leetcode 第42场双周赛题解

## # Problem A - 无法吃午餐的学生数量 (opens new window)

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

class Solution {
public:
int countStudents(vector<int>& students, vector<int>& sandwiches) {
stack<int> st;
for (int i = (int)sandwiches.size() - 1; i >= 0; --i)
st.push(sandwiches[i]);
vector<int> t(2);
for (int student : students)
t[student]++;
while (!st.empty() && t[st.top()]) {
t[st.top()]--;
st.pop();
}
return st.size();
}
};

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

## # Problem B - 平均等待时间 (opens new window)

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

class Solution:
def averageWaitingTime(self, customers: List[List[int]]) -> float:
n = len(customers)
cook = 0
wait = 0
for arrival, duration in customers:
if arrival >= cook:
wait += duration
else:
wait += cook + duration - arrival
cook = max(cook, arrival) + duration
return wait / n

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

## # Problem C - 修改后的最大二进制字符串 (opens new window)

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

class Solution {
public:
string maximumBinaryString(string binary) {
int n = binary.size();
int front = 0;
while (binary[front] == '1' && front < n)
front++;
if (front == n)
return binary;
int rest = 0;
for (int i = front; i < n; ++i)
if (binary[i] == '1')
rest++;
string ans(n - rest - 1, '1');
if (front != n)
ans.push_back('0');
ans += string(rest, '1');
return ans;
}
};

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

## # Problem D - 得到连续 K 个 1 的最少相邻交换次数 (opens new window)

### # 对等效坐标的简单说明

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

typedef long long ll;

class Solution {
public:
int minMoves(vector<int>& nums, int k) {
vector<ll> one;
for (int i = 0; i < nums.size(); ++i)
if (nums[i] == 1)
one.emplace_back(i - (int)one.size());
vector<ll> pre{0};
for (int i : one)
pre.emplace_back(pre.back() + i);
ll ans = 1e10;
for (int l = 1; l + k - 1 <= one.size(); ++l) {
int r = l + k - 1;
int mid = (l + r) >> 1;
ll left = one[mid - 1] * (mid - l) - pre[mid - 1] + pre[l - 1];
ll right = pre[r] - pre[mid] - one[mid - 1] * (r - mid);
ans = min(ans, left + right);
}
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