leetcode 第279场周赛

T1 对奇偶下标分别排序

水题

T2 重排数字的最小值

题意

给出一个整数，重排 $num$ 中的各位数字，使其值最小化且不含 任何前导零。

做法

对于负数，对所有位降序排序。对于正数，升序排序，之后找到第一个非零值，交换到第一个位置。

代码

class Solution {
public:
    long long smallestNumber(long long num) {
        using ll = long long;
        bool neg = (num < 0);
        
        vector<ll> v;
        if (neg) num = -num;
        
        while (num)
        {
            v.push_back(num % 10);
            num /= 10;
        }
        
        ll ans = 0, p = 1;
        if (!neg)
        {
            sort(v.begin(), v.end());
            for (int i = 0; i < v.size(); i++)
            {
                if (v[i] != 0)
                {
                    swap(v[i], v[0]);
                    break;
                }
            }
            for (int i = v.size() - 1; i >= 0; i--)
            {
                ans += v[i] * p;
                p *= 10;
            }
        }
        else
        {
            sort(v.begin(), v.end(), greater<ll>());
            for (int i = v.size() - 1; i >= 0; i--)
            {
                ans += v[i] * p;
                p *= 10;
            }
            ans = -ans;
        }
        return ans;
    }
};

T3 设计位集

题意

设计 $bitset$ 类，支持操作：单点置零置一，翻转所有位，统计一的个数等。

做法

维护标记是否处于翻转态，再分类讨论，正确维护一的计数器即可。

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

题意

给出一个 $01$ 字符串，每一位表示这一节车厢有无违禁品。现在需要将所有包含违禁品的车厢去掉。从左端或者右端移除第一节车厢代价为 $1$ ，移除中间某一节车厢代价为 $2$ 。求出最小代价。

做法

将列车分成左右两部分，枚举分割点，分别计算两半段的代价，取最小值。
维护 $pre[i]$ 表示移除前 $i$ 节车厢中的所有违禁货物车厢所花费的最少时间。当 $s[i]=0$ 时，无需移除车厢，则有 $pre[i]=pre[i-1]$ 。当 $s[i]=1$ 时，可以单独移除第 $i$ 节车厢，也可以移除前 $i$ 个车厢，二者取最小值，即 $pre[i]=\min(pre[i-1]+2,\ i+1)$ ， $i+1$ 是因为下标从 $0$ 开始。对于右半部分，维护 $suf[\ ]$ ，同理。最后取 $\min(pre[i]+suf[i+1])$ 为答案。

计算 $pre[\ ]$ 可以和枚举分割点相结合，所以可以先计算 $suf[\ ]$ 。
考虑到 $pre[i]$ 只和前一个 $pre[i-1]$ 有关，可以只用一个变量 $pre$ 表示。

代码

class Solution {
public:
    int minimumTime(string s) {
        int n = s.size();
        vector<int> suf(n + 1, 0);
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == '1') {
                suf[i] = min(suf[i + 1] + 2, n - i);
            }
            else suf[i] = suf[i + 1];
        }
        
        // 注意左半段为空的情况，ans := suf[0]
        int ans = suf[0]; 
        int pre = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '1') {
                pre = min(pre + 2, i + 1);
                ans = min(ans, pre + suf[i + 1]);
            }
        }
        return ans;
    }
};