# # Leetcode 第50场双周赛题解

## # Problem A - 最少操作使数组递增 (opens new window)

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

class Solution {
public:
int minOperations(vector<int>& nums) {
int ans = 0, last = nums[0];
for (int i = 1; i < nums.size(); ++i) {
int target = max(nums[i], last + 1);
ans += target - nums[i];
last = target;
}
return ans;
}
};

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

## # Problem B - 统计一个圆中点的数目 (opens new window)

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

class Solution {
public:
vector<int> countPoints(vector<vector<int>>& points, vector<vector<int>>& queries) {
vector<int> ans;
for (auto &query: queries) {
int x = query[0], y = query[1], r = query[2];
int cnt = 0;
for (auto &point : points) {
int dx = x - point[0], dy = y - point[1];
if (dx * dx + dy * dy <= r * r)
cnt++;
}
ans.emplace_back(cnt);
}
return ans;
}
};

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

## # Problem C - 每个查询的最大异或值 (opens new window)

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

class Solution {
public:
vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {
vector<int> ans;
int val = 0, msk = (1 << maximumBit) - 1;
for (int num : nums)
val ^= num;
while (!nums.empty()) {
ans.emplace_back(msk ^ val);
val ^= nums.back();
nums.pop_back();
}
return ans;
}
};

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

## # Problem D - 使字符串有序的最少操作次数 (opens new window)

### # 方法一：枚举更小排列的数目

• 时间复杂度$\mathcal{O}(N(|\sum|+\log M))$。其中$|\sum|$为字典大小，$M=10^9+7-2=10^9+5$
• 空间复杂度$\mathcal{O}(N+|\sum|)$

using ll = long long;
const ll MOD = 1e9 + 7;

ll fexp(ll x, ll y) {
ll ans = 1;
while (y) {
if (y & 1)
ans = ans * x % MOD;
x = x * x % MOD;
y >>= 1;
}
return ans;
}

ll inv(ll x) {
return fexp(x, MOD - 2);
}

class Solution {
public:
int makeStringSorted(string s) {
ll ans = 0;
int n = s.size();
vector<int> cnt(26);
for (char c : s)
cnt[c - 'a']++;
vector<ll> fac(n + 1), invfac(n + 1);
fac[0] = invfac[0] = 1;
for (int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * i % MOD;
invfac[i] = inv(fac[i]);
}

for (int i = 0; i < n; ++i) {
ll tot = fac[n - 1 - i];
for (int k = 0; k < 26; ++k)
tot = tot * invfac[cnt[k]] % MOD;
for (int j = 0; j < s[i] - 'a'; ++j) {
if (cnt[j])
ans = (ans + tot * cnt[j] % MOD) % MOD;
}
cnt[s[i] - 'a']--;
}

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47