LeetCode第 279 场周赛题解

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 ，所有位都是 。

• void fix(int idx)

  将下标为

  idx

  的位上的值更新为

  1

  。如果值已经是

  1

  ，则不会发生任何改变。

• void unfix(int idx)

  idx

• void flip()

  翻转 Bitset 中每一位上的值。换句话说，所有值为 的位将会变成

  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\)个字符结尾的最小代价，其转移方程为：

\[f_i =

\begin{cases}

f_{i - 1} & s_i = 0\\

min(i , f_{i - 1} + 2) & s_i = 1

\end{cases}

\]

考虑两边就再定义状态\(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);
    }
};