# # Leetcode 第216场周赛题解

## # Problem A - 检查两个字符串数组是否相等 (opens new window)

• 时间复杂度$O(\sum|word1|+\sum|word2|)$
• 空间复杂度$O(\sum|word1|+\sum|word2|)$

class Solution:
def arrayStringsAreEqual(self, word1: List[str], word2: List[str]) -> bool:
return ''.join(word1) == ''.join(word2)

1
2
3

## # Problem B - 具有给定数值的最小字符串 (opens new window)

• 时间复杂度$O(N)$
• 空间复杂度$O(N)$

class Solution {
public:
string getSmallestString(int n, int k) {
string s;
while (n > 0) {
if ((k - 1) <= 26 * (n - 1))
s.push_back('a'), k--;
else {
char c = 'a' + k - 1 - 26 * (n - 1);
s.push_back(c);
k -= c - 'a' + 1;
}
n--;
}
return s;
}
};

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

## # Problem C - 生成平衡数组的方案数 (opens new window)

• 时间复杂度$O(N)$
• 空间复杂度$O(N)$

class Solution {
public:
int waysToMakeFair(vector<int>& nums) {
int ans = 0;
int n = nums.size();
vector<int> odd(n + 1), even(n + 1);
for (int i = 0; i < n; ++i) {
even[i + 1] = even[i], odd[i + 1] = odd[i];
if (i % 2 == 0)
even[i + 1] += nums[i];
else
odd[i + 1] += nums[i];
}
for (int i = 0; i < n; ++i) {
int osum, esum;
if (i % 2 == 0) {
osum = odd[i + 1] + even[n] - even[i + 1];
esum = even[i] + odd[n] - odd[i + 1];
} else {
osum = odd[i] + even[n] - even[i + 1];
esum = even[i] + odd[n] - odd[i + 1];
}
if (osum == esum)
ans++;
}
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

## # Problem D - 完成所有任务的最少初始能量 (opens new window)

• 时间复杂度$O(N\log N)$。我们进行了排序。
• 空间复杂度$O(1)$。我们只使用了常数的额外空间。

class Solution {
public:
int minimumEffort(vector<vector<int>>& tasks) {
int n = tasks.size();
sort(tasks.begin(), tasks.end(), [](vector<int> &p, vector<int> &q) {
return p[1] - p[0] > q[1] - q[0] || (p[1] - p[0] == q[1] - q[0] && p[1] > q[1]);
});
int ans = 0, curr = 0;
for (auto &task : tasks) {
if (curr < task[1]) {
ans += task[1] - curr;
curr = task[1];
}
curr -= task[0];
}
return ans;
}
};

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