A
class Solution {
public:
vector<int> sortEvenOdd(vector<int>& nums) {
vector<int> a, b, v;
for (int i = 0; i < nums.size(); i ++ )
if (i % 2 == 0) a.push_back(nums[i]);
else b.push_back(nums[i]);
sort(a.begin(), a.end());
sort(b.begin(), b.end());
reverse(b.begin(), b.end());
for (int i = 0; i < min(a.size(), b.size()); i ++ )
v.push_back(a[i]), v.push_back(b[i]);
if (a.size() > b.size())
v.push_back(a[a.size() - 1]);
return v;
}
};
B
class Solution {
public:
int cnt[10];
long long smallestNumber(long long num) {
if (num >= 0) {
while (num) {
cnt[num % 10] ++;
num /= 10;
}
long long res = 0;
for (int i = 1; i <= 9; i ++ ) {
if (cnt[i]) {
res = i;
cnt[i] --;
break;
}
}
while (cnt[0] -- )
res = res * 10;
for (int i = 1; i <= 9; i ++ ) {
while (cnt[i]) {
res = res * 10 + i;
cnt[i] --;
}
}
return res;
}
else {
num *= -1;
long long res = 0;
while (num) {
cnt[num % 10] ++;
num /= 10;
}
for (int i = 9; i >= 0; i -- ) {
while (cnt[i]) {
res = res * 10 + i;
cnt[i] --;
}
}
return res * -1;
}
}
};
C
class Bitset {
public:
int len, cnt = 0, tot = 0;
int a[100010] = {0};
Bitset(int size) {
len = size;
}
void fix(int idx) {
if (a[idx] == 0 && tot % 2 == 0) cnt ++, a[idx] = 1;
if (a[idx] == 1 && tot % 2 == 1) cnt ++, a[idx] = 0;
}
void unfix(int idx) {
if (a[idx] == 1 && tot % 2 == 0) cnt --, a[idx] = 0;
if (a[idx] == 0 && tot % 2 == 1) cnt --, a[idx] = 1;
}
void flip() {
cnt = len - cnt;
tot ++;
}
bool all() {
if (cnt == len) return true;
else return false;
}
bool one() {
if (cnt >= 1) return true;
else return false;
}
int count() {
return cnt;
}
string toString() {
string s;
for (int i = 0; i < len; i ++ ) {
if (tot & 1) {
if (a[i]) s += "0";
else s += "1";
}
else {
if (a[i]) s += "1";
else s += "0";
}
}
return s;
}
};
D
从两个方向DP,分别记作\(f1,f2\),那么答案就为\(min\{f1[i]+f2[i + 1]\}\)
class Solution {
public:
char s[200010];
int f1[200010], f2[200010];
int minimumTime(string ss) {
int n = ss.size();
memset(f1, 0x3f, sizeof f1);
memset(f2, 0x3f, sizeof f2);
for (int i = 0; i < ss.size(); i ++ ) s[i + 1] = ss[i];
f1[0] = f2[n + 1] = 0;
for (int i = 1; i <= n; i ++ ) {
f1[i] = f1[i - 1];
if (s[i] == '1') {
f1[i] = min(i, f1[i] + 2);
}
}
for (int i = n; i >= 1; i -- ) {
f2[i] = f2[i + 1];
if (s[i] == '1') {
f2[i] = min(n - i + 1, f2[i + 1] + 2);
}
}
int res = 0x3f3f3f3f;
for (int i = 0; i <= n; i ++ ) {
res = min(res, f1[i] + f2[i + 1]);
}
return res;
}
};