第279场周赛

6000. 对奇偶下标分别排序

class Solution {
public:
    vector<int> sortEvenOdd(vector<int>& nums) {
        vector<int> vec1, vec2;
        for (int i = 0; i < nums.size(); i ++) {
            if (i % 2 == 0) vec1.push_back(nums[i]); // 偶数
            else vec2.push_back(nums[i]); // 奇数
        }
        sort(vec1.begin(), vec1.end());
        sort(vec2.begin(), vec2.end(), greater<int>());
        vector<int> res;
        for (int i = 0, j = 0, k = 0; i < nums.size(); i ++) {
            if (i % 2 == 0) res.push_back(vec1[j ++]);
            else res.push_back(vec2[k ++]);
        }
        return res;
    }
};

6001. 重排数字的最小值

class Solution {
public:
    
    vector<int> getNum(long long num) {
        vector<int> a;
        while(num) {
            a.push_back(num % 10);
            num /= 10;
        }
        return a;
    }
    
    long long smallestNumber(long long num) {
        long long res = 0;
        if (num > 0) {
            auto a = getNum(num);
            sort(a.begin(), a.end());
            int i = 0, n =a.size(), k = 0;
            bool flag = true;
            vector<int> vec;
            for (int i = 0; i < n; i ++) {
                if (a[i] != 0 && flag){
                    k = i, flag = !flag;
                    continue;
                } 
                vec.push_back(a[i]);
            }
            res += a[k] * pow(10, n - 1);
            int cnt = vec.size() - 1;
            for (int i = 0; i < vec.size(); i ++) {
                res += vec[i] * pow(10, cnt);
                cnt --;
            }
        } else {
            long long n1 = -num;
            auto a = getNum(n1);
            sort(a.begin(), a.end(), greater<int>());
            int cnt = a.size() - 1;
            for (int i = 0; i < a.size(); i ++) {
                res += a[i] * pow(10, cnt);
                cnt --;
            }
            res = -res;
        }
        return res;
    }
};

6002. 设计位集

class Bitset {
public:
    
    string bst, fbst;
    int cnt;
    bool flipped; // 判断是否翻转
    
    Bitset(int size) {
        bst = string(size, '0');
        fbst = string(size, '1');
        cnt = 0;
        flipped = false;
    }
    
    void fix(int idx) {
        if (!flipped) {
            if (bst[idx] == '0') cnt ++;
            bst[idx] = '1';
            fbst[idx] = '0';
        } else {
            if (bst[idx] == '1') cnt ++; // 如果翻转了，则是fbit，那么翻转前是1，翻转后是0，fix设置fbit，则加1
            bst[idx] = '0';
            fbst[idx] = '1';    
        }
    }
    
    void unfix(int idx) {
        if (!flipped) {
            if (bst[idx] == '1') cnt --;
            bst[idx] = '0';
            fbst[idx] = '1';
        } else {
            if (bst[idx] == '0') cnt --; 
            bst[idx] = '1';
            fbst[idx] = '0';    
        }
    }
    
    void flip() {
        flipped = !flipped;
        cnt = bst.size() - cnt;
    }
    
    bool all() {
        return cnt == bst.size();
    }
    
    bool one() {
        return cnt > 0;
    }
    
    int count() {
        return cnt;
    }
    
    string toString() {
        if (!flipped) return bst;
        else return fbst;
    }
};

/**
 * 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();
 */ 

6003. 移除所有载有违禁货物车厢所需的最少时间

前后缀分解 + DP - 移除所有载有违禁货物车厢所需的最少时间

class Solution {
public:
    /*
        考虑左半部分的最少时间。
        当s[i] == '0' pre[i] = pre[i - 1]
        当s[i] == '1' pre[i] = min(pre[i - 1] + 2, i + 1)
        考虑右半部分的最少时间
        s[i] == '0' , suf[i] = suf[i + 1]
        s[i] == '1' , suf[i] = min(suf[i + 1] + 2, n - i)
    */
    int minimumTime(string s) {
        int n = s.length();
        vector<int> suf(n + 1, 0); // 移除后i个载有违禁货物车所需的最少单位时间数
        for (int i = n - 1; i >= 0; i --) {
            suf[i] = s[i] == '0' ? suf[i + 1] : min(suf[i + 1] + 2, n - i);
        }

        // 枚举分割点
        int pre = 0, ans = suf[0];  // pre使用滚动数组优化
        for (int i = 0; i < n; i ++) {
            if (s[i] == '1') pre = min(pre + 2, i + 1);
            ans = min(ans, pre + suf[i]);
        } 
        return ans;
    }
};