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);
    }
};