LeetCode官方举办！279场周赛题解合集
LeetCode官方举办！279场周赛题解合集
作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，我是梁唐。
今天我们来看上周日进行的LeetCode第279场周赛，这也是LeetCode官方举办的招聘周赛。
前500的选手可以获得LeetCode简历免筛的资格。
本场比赛的题难度适中，质量不错，感兴趣的同学不妨练习一下。
对奇偶下标排序
难度：Easy
给你一个下标从 0 开始的整数数组 nums 。根据下述规则重排 nums 中的值：
- 按 非递增 顺序排列 nums 奇数下标 上的所有值。
- 举个例子，如果排序前 nums = [4,1,2,3] ，对奇数下标的值排序后变为 [4,3,2,1] 。奇数下标 1 和 3 的值按照非递增顺序重排。
- 按 非递减 顺序排列 nums 偶数下标 上的所有值。
- 举个例子，如果排序前 nums = [4,1,2,3] ，对偶数下标的值排序后变为 [2,1,4,3] 。偶数下标 0 和 2 的值按照非递减顺序重排。
返回重排 nums 的值之后形成的数组。
解法
模拟题，只需要把数组当中的元素按照奇偶位置分类后再分别按照递增和递减的顺序排序后合并即可。
注意一下边界情况。
AC代码：
class Solution {
public:
vector<int> sortEvenOdd(vector<int>& nums) {
int n = nums.size();
// 使用两个vector分别存储奇位置和偶位置的元素
vector<int> odd, even;
for (int i = 0; i < n; i += 2) {
odd.push_back(nums[i]);
if (i+1 < n) even.push_back(nums[i+1]);
}
// 奇位置递增排序，偶位置递减排序
sort(odd.begin(), odd.end());
sort(even.begin(), even.end(), greater<int>());
vector<int> ret;
for (int i = 0; i < n/2; i++) {
ret.push_back(odd[i]);
ret.push_back(even[i]);
}
if (n % 2) ret.push_back(odd[n/2]);
return ret;
}
};
重排数字的最小值
难度：Medium
给你一个整数 num 。重排 num 中的各位数字，使其值 最小化 且不含 任何 前导零。
返回不含前导零且值最小的重排数字。
注意，重排各位数字后，num 的符号不会改变。
解法
不难发现num是正数和负数的处理逻辑不同，当num是正数时，我们要排列出尽量小的数，而num为负数时则相反。
要重组得到尽量大的数很简单，我们拿到num的每一位数字倒排即可。如301的数字是[3, 0, 1]，倒排重组得到310。而由于前导零的存在，我们无法直接得到最小的数，可以先按递增顺序排，再找到第一位不为0的元素和首个0交换。如310，排序之后得到的是013，第一个不是0的数是1，我们将它和0交换，得到103。
依然是模拟题，难度不大。
AC代码如下：
class Solution {
public:
long long smallestNumber(long long num) {
if (num == 0) return 0;
long long ret = 0;
vector<int> nums;
long long cur = abs(num);
// 拆解num的每一位数字
while (cur > 0) {
nums.push_back(cur % 10);
cur /= 10;
}
// 根据num正负分情况处理
if (num < 0) {
sort(nums.begin(), nums.end(), greater<int>());
for (int i = 0; i < nums.size(); i++) {
ret = ret * 10 + nums[i];
}
return -ret;
}
sort(nums.begin(), nums.end());
if (nums[0] == 0) {
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == 0) continue;
swap(nums[0], nums[i]);
break;
}
}
for (int i = 0; i < nums.size(); i++) {
ret = ret * 10 + nums[i];
}
return ret;
}
};
设计位集
难度：Medium
位集 Bitset 是一种能以紧凑形式存储位的数据结构。
请你实现 Bitset 类。
- Bitset(int size) 用 size 个位初始化 Bitset ，所有位都是 0 。
- void fix(int idx) 将下标为 idx 的位上的值更新为 1 。如果值已经是 1 ，则不会发生任何改变。
- void unfix(int idx) 将下标为 idx 的位上的值更新为 0 。如果值已经是 0 ，则不会发生任何改变。
- void flip() 翻转 Bitset 中每一位上的值。换句话说，所有值为 0 的位将会变成 1 ，反之亦然。
- boolean all() 检查 Bitset 中 每一位 的值是否都是 1 。如果满足此条件，返回 true ；否则，返回 false 。
- boolean one() 检查 Bitset 中 是否 至少一位 的值是 1 。如果满足此条件，返回 true ；否则，返回 false 。
- int count() 返回 Bitset 中值为 1 的位的 总数 。
- String toString() 返回 Bitset 的当前组成情况。注意，在结果字符串中，第 i 个下标处的字符应该与 Bitset 中的第 i 位一致。
解法
这是一道数据结构实现题，实现题目要求的数据结构。
单纯从逻辑上来说，bitset的原理并不难，我们直接模拟实现非常容易。但仔细分析之后，很容易发现问题，如果我们采用模拟的方法实现，当进行flip操作时，需要遍历整个set，将其中的每一位翻转，这个操作的时间复杂度是O(n) 。由于最多会进行1e5次翻转，那么一定会导致超时。
所以实现bitset的逻辑不是重点，真正的难点在解决多次flip复杂度的问题。
怎么解决这个问题呢？这里要用到懒惰标记的小技巧，当我们执行flip的时候并不是真正地去遍历翻转每一个元素，这太耗时，而是更新一个标记，表示当前的元素是否是翻转的。在我们进行toString,count等其他操作的时候把当前是否翻转加入考量，保证结果的正确，这样我们就把一个O(n) 的操作简化成了O(1) ，就不用担心超时了。
同样，count也是一个O(n) 的操作，不过好在count处理的逻辑比较简单，我们只需要在fix,unfix和flip这种会改变1的数量的操作当中更新为1的数量就可以了。很容易想到，当我们执行flip的时候，0变成1,1变成0，如果翻转之前1的数量是cnt，那么翻转之后会变成 n - cnt。
我们只需要把这些逻辑整合一下即可，更多细节参考代码。
class Bitset {
public:
int cnt = 0, _size = 0;
vector<int> bits;
bool _flip = false;
Bitset(int size) {
// bitset初始化
bits = vector(size, 0);
_size = size;
}
void fix(int idx) {
// fix操作是将idx位置为1
// 如果没有翻转，那么bits[idx] = 0时操作
// 如果翻转了，bits[idx] = 1 时操作
if (!bits[idx] && !_flip || bits[idx] && _flip) {
bits[idx] = !_flip;
// 如果没有翻转，1的数量增加
// 否则1的数量减少
if (!_flip) cnt++;
else cnt--;
}
}
void unfix(int idx) {
// unfix将idx位置置为0
// 如果没有翻转，bits[idx] = 1时操作，否则bits[idx] = 0时操作
if (bits[idx] && !_flip || !bits[idx] && _flip) {
bits[idx] = _flip;
// 如果翻转了，从0置为1，所以1的数量增加
if (_flip) cnt++;
// 否则，从1置为0,1的数量减小
else cnt--;
}
}
void flip() {
_flip = !_flip;
}
bool all() {
return count() == _size;
}
bool one() {
return count() > 0;
}
int count() {
return _flip ? _size - cnt : cnt;
}
string toString() {
string s = "";
for (int i = 0; i < _size; i++) {
if (bits[i] & !_flip || !bits[i] && _flip) s.push_back('1');
else s.push_back('0');
}
return s;
}
};
/**
* Your Bitset object will be instantiated and called as such:
* Bitset* obj = new Bitset(size);
* obj->fix(idx);
* obj->unfix(idx);
* obj->flip();
* bool param_4 = obj->all();
* bool param_5 = obj->one();
* int param_6 = obj->count();
* string param_7 = obj->toString();
*/
移除所有载有违禁货物车厢所需要的最小时间
难度：Hard
给你一个下标从 0 开始的二进制字符串 s ，表示一个列车车厢序列。s[i] = '0' 表示第 i 节车厢 不 含违禁货物，而 s[i] = '1' 表示第 i 节车厢含违禁货物。
作为列车长，你需要清理掉所有载有违禁货物的车厢。你可以不限次数执行下述三种操作中的任意一个：
- 从列车 左 端移除一节车厢（即移除 s[0]），用去 1 单位时间。
- 从列车 右 端移除一节车厢（即移除 s[s.length - 1]），用去 1 单位时间。
- 从列车车厢序列的 任意位置 移除一节车厢，用去 2 单位时间。
返回移除所有载有违禁货物车厢所需要的 最少 单位时间数。
注意，空的列车车厢序列视为没有车厢含违禁货物。
解法
这是经典的动态规划问题。
由于要移除所有违禁品，我们可以考虑同时维护从左到右和从右到左两个状态。对于位置i来说，如果从左到i和从右到i都没有违禁品，那么我们就可以认为所有位置都没有违禁品。
我们用left[i]表示清除从0到i所有违禁品所需要的开销，right[i]表示清除从i到n所有违禁品需要的开销。那么最小的left[i] + right[i+1]就是答案。
由于明确了维护的方向，我们可以很容易写出状态转移方程：
为了更好处理边界情况，我们可以将字符串s往右移动一位，保证下标从1开始。
AC代码如下：
class Solution {
public:
int minimumTime(string s) {
if (s == "0") return 0;
int n = s.size();
// 将s字符串往右移动一位
s = "$" + s + "#";
vector<int> left(n+2, 0), right(n+2, 0);
// 维护从左往右清除违禁品的开销
for (int i = 1; i <= n; i++) {
if (s[i] == '0') left[i] = left[i-1];
else left[i] = min(i, left[i-1] + 2);
}
int ret = n;
// 维护从右往左清除违禁品的开销
for (int i = n; i > 0; i--) {
if (s[i] == '0') right[i] = right[i+1];
else right[i] = min(n-i+1, right[i+1] + 2);
}
// 找到最优值
for (int i = 1; i < n; i++) {
ret = min(ret, left[i] + right[i+1]);
}
return ret;
}
};
感谢大家的阅读，祝大家日拱一卒，每天都有进步。