跳到主要内容

第 63 场双周赛

Problem A - 使每位学生都有座位的最少移动次数

方法一:排序+贪心

座位和学生分别排序后,依次对应即可。

  • 时间复杂度O(NlogN)\mathcal{O}(N\log N)
  • 空间复杂度O(NlogN)\mathcal{O}(N\log N)
参考代码(Python 3)
class Solution:
def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
return sum(abs(seat - student) for seat, student in zip(sorted(seats), sorted(students)))

Problem B - 如果相邻两个颜色均相同则删除当前颜色

方法一:模拟

两个人的操作互不影响,所以计算出Alice和Bob各自最多操作的次数即可。

  • 时间复杂度为O(S)\mathcal{O}(|S|)
  • 空间复杂度O(1)\mathcal{O}(1)
参考代码(Python 3)
class Solution:
def winnerOfGame(self, colors: str) -> bool:
a = 0
b = 0
now = '$'
cnt = 0
for ch in colors + '#':
if ch == now:
cnt += 1
else:
if cnt > 0:
if now == 'A':
a += max(0, cnt - 2)
else:
b += max(0, cnt - 2)
now = ch
cnt = 1
return a > b

Problem C - 网络空闲的时刻

方法一:BFS

利用BFS计算出每个点到源点的距离,就可以计算出这个点最后一次发送报文的时间,从而求出它最后一次收到回复报文的时间。在所有点都收到最后的回复之后,网络就空闲了。

  • 时间复杂度O(V+E)\mathcal{O}(V+E)
  • 空间复杂度O(V+E)\mathcal{O}(V+E)
参考代码(C++)
const int INF = 0x3f3f3f3f;

class Solution {
public:
int networkBecomesIdle(vector<vector<int>>& edges, vector<int>& patience) {
int n = patience.size();
vector<vector<int>> adj(n);
for (auto &edge : edges) {
int u = edge[0], v = edge[1];
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> dist(n, INF);
dist[0] = 0;
queue<int> q;
q.emplace(0);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (dist[v] > dist[u] + 1) {
dist[v] = dist[u] + 1;
q.emplace(v);
}
}
}
int ans = 0;
for (int i = 1; i < n; ++i) {
int stop = dist[i] * 2;
int last_send = (stop - 1) / patience[i] * patience[i];
ans = max(ans, last_send + stop);
}
return ans + 1;
}
};

Problem D - 两个有序数组的第 K 小乘积

方法一:二分答案+双指针

显然不可能枚举所有的乘积。我们可以转换思路,将求第KK小乘积变为:给定一个乘积,求出有多少不大于它的乘积。这样我们就可以采用二分答案的方法求解本题。

因为数组中包含零和负数,所以我们这里分别考虑正数、零和负数。

下面我们需要解决的是:给定一个乘积,求出不大于它的乘积的个数。

显然,我们应该分负数、零和正数三种情况分别考虑:

  • 如果是一个负数,那么不大于它的乘积必然是由一正一负得来,这部分可以双指针求解。

  • 如果是零,那么不大于它的乘积包括所有的负数和零;

  • 如果是正数,那么不大于它的乘积包括所有的负数和零;以及两正和两负的情况,这部分可以双指针求解。

  • 时间复杂度O(NlogC)\mathcal{O}(N\log C)。其中CC是乘积上下界之差。

  • 空间复杂度O(NlogC)\mathcal{O}(N\log C)

参考代码(C++)
using ll = long long;

class Solution {
public:
ll kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, ll k) {
ll lo = -1e10, hi = 1e10;
int l1 = nums1.size(), l2 = nums2.size();

vector<int> pos1, pos2, neg1, neg2;
int zero1 = 0, zero2 = 0;
for (int num : nums1) {
if (num < 0) {
neg1.emplace_back(-num);
} else if (num == 0) {
zero1++;
} else {
pos1.emplace_back(num);
}
}
reverse(neg1.begin(), neg1.end());

for (int num : nums2) {
if (num < 0) {
neg2.emplace_back(-num);
} else if (num == 0) {
zero2++;
} else {
pos2.emplace_back(num);
}
}
reverse(neg2.begin(), neg2.end());

int p1 = pos1.size(), n1 = neg1.size(), p2 = pos2.size(), n2 = neg2.size();

while (lo <= hi) {
ll mid = (lo + hi) / 2;
ll cnt = 0;
if (mid > 0) {
cnt += 1LL * zero1 * l2 + 1LL * l1 * zero2 - 1LL * zero1 * zero2; // == 0
cnt += 1LL * p1 * n2 + 1LL * n1 * p2; // < 0
int ptr2 = p2 - 1;
for (int ptr1 = 0; ptr1 < p1 && ptr2 >= 0; ++ptr1) {
while (ptr2 >= 0 && 1LL * pos1[ptr1] * pos2[ptr2] > mid)
ptr2--;
cnt += ptr2 + 1;
}

ptr2 = n2 - 1;
for (int ptr1 = 0; ptr1 < n1 && ptr2 >= 0; ++ptr1) {
while (ptr2 >= 0 && 1LL * neg1[ptr1] * neg2[ptr2] > mid)
ptr2--;
cnt += ptr2 + 1;
}
} else if (mid < 0) {
ll amid = -mid;
int ptr2 = 0;
for (int ptr1 = p1 - 1; ptr1 >= 0 && ptr2 < n2; --ptr1) {
while (ptr2 < n2 && 1LL * pos1[ptr1] * neg2[ptr2] < amid)
ptr2++;
cnt += n2 - ptr2;
}

ptr2 = 0;
for (int ptr1 = n1 - 1; ptr1 >= 0 && ptr2 < p2; --ptr1) {
while (ptr2 < p2 && 1LL * neg1[ptr1] * pos2[ptr2] < amid)
ptr2++;
cnt += p2 - ptr2;
}
} else {
cnt += 1LL * zero1 * l2 + 1LL * l1 * zero2 - 1LL * zero1 * zero2; // == 0
cnt += 1LL * p1 * n2 + 1LL * n1 * p2; // < 0
}

if (cnt >= k) {
hi = mid - 1 ;
} else {
lo = mid + 1;
}
}
return lo;
}
};