6000. 对奇偶下标分别排序
题目描述：给你一个数组，将数组中奇数下标上的值按照非递增排序，将偶数下标上的值按照非递减排序，并返回排序后的数组。
思路：根据题意模拟即可。
时间复杂度：\(O(nlogn)\)
参考代码：
class Solution {
public:
vector<int> sortEvenOdd(vector<int>& nums) {
vector<int>lr , rs;
int n = nums.size();
for(int i = 0 ; i < n ; ++i){
if(i % 2 == 0) lr.push_back(nums[i]);
else rs.push_back(nums[i]);
}
sort(rs.begin() , rs.end() , [&](const int& a , const int& b){
return a > b;
});
sort(lr.begin() , lr.end());
vector<int>res;
int p = 0 , q = 0;
while(p < lr.size() || q < rs.size()){
if(p < lr.size()) res.push_back(lr[p]);
if(q < rs.size()) res.push_back(rs[q]);
++p;++q;
}
return res;
}
};
6001. 重排数字的最小值
题目描述：给你一个整数\(-10^{15} \leq num \leq 10^{15}\)，将整数中的数字重排并且不允许有前导\(0\)，求重排后的最小值。
思路：根据题意模拟即可。
时间复杂度：\(O(n)\)，\(n\)为数字的位数
参考代码：
class Solution {
private:
long long solve(long long num , int flag){
if(num == 0) return num;
string s = to_string(num);
sort(s.begin() , s.end());
vector<int>cnt(10 , 0);
for(auto c : s) cnt[c - '0']++;
long long res = 0;
if(flag == 1){
for(int i = 1 ; i < 10 ; ++i){
if(cnt[i] == 0) continue;
res = i;
--cnt[i];
break;
}
for(int i = 0 ; i < 10 ; ++i){
while(cnt[i]){
res = res * 10 + i;
--cnt[i];
}
}
}
else{
for(int i = 9 ; i >= 0 ; --i){
while(cnt[i]){
--cnt[i];
res = res * 10 + i;
}
}
}
return res;
}
public:
long long smallestNumber(long long num) {
if(num < 0) return -1* solve(-num , 0);
return solve(num , 1);
}
};
6002. 设计位集
题目描述：设计一个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位一致。
思路：根据需要toString方法，所以考虑使用string类型作为底层。然后使用flag标记flip操作，并使用变量存储字符串中字符1的出现次数，只在toString且flag为1的时候实际翻转。
时间复杂度：\(O(n)\),\(n\)为操作次数
参考代码：
class Bitset {
private:
string s;
int cnt , flag, sz;
public:
Bitset(int size) {
s = string(size , '0');
flag = 0;
cnt = 0;
sz = size;
}
void fix(int idx) {
if(s[idx] == '1'){
if(flag) s[idx] = '0' , ++cnt;
else ;
}
else{
if(flag) ;
else s[idx] = '1' , ++cnt;
}
return ;
}
void unfix(int idx) {
if(s[idx] == '0'){
if(flag) --cnt , s[idx] = '1';
else ;
}
else{
if(flag);
else s[idx] = '0' , --cnt;
}
}
void flip() {
flag^= 1;
cnt = sz - cnt;
}
bool all() {
return cnt == sz;
}
bool one() {
return cnt != 0;
}
int count() {
return cnt;
}
string toString() {
if(flag == 0) return s;
cnt = 0; flag ^= 1;
for(auto& c : s){
if(c == '0') c = '1' , ++cnt;
else c = '0';
}
return s;
}
};
6003. 移除所有载有违禁货物车厢所需的最少时间
题目描述：给你一个长度为\(n\)的01串，你需要将字符串中的\(1\)全部删去，从字符串的左边或者右边删去一个字符代价为1，从中间删去一个字符的代价为2。问最小代价。
思路：比较显然的dp。考虑一边，定义状态\(f_i\)表示到第\(i\)个字符结尾的最小代价，其转移方程为：
考虑两边就再定义状态\(g_i\)表示从右到左第\(i\)个字符的最小代价。最终答案为：
\[\mathop{min}\limits_{i = 1}^{n + 1} f_{i - 1} + g_i \]时间复杂度：\(O(n)\)
参考代码：
class Solution {
private:
int solve(string& s){
int cnt = 0;
for(auto c : s) cnt += c == '1';
if(cnt == 0) return 0;
int n = s.size();
vector<int> f(n + 1 , 0) , g(n + 2 , 0);
for(int i = 1 ; i <= n ; ++ i){
if(s[i - 1] == '0') f[i] = f[i - 1];
else f[i] = min(f[i - 1] + 2 , i);
}
for(int i = n ; i >= 1 ; --i){
if(s[i - 1] == '0') g[i] = g[i + 1];
else g[i] = min(g[i + 1] + 2 , n - i + 1);
}
int res = INT_MAX;
for(int i = 1 ; i <= n + 1; ++i){
res = min(res , f[i - 1] + g[i]);
}
return res;
}
public:
int minimumTime(string s) {
return solve(s);
}
};