周赛 - 🏆 第 279 场力扣周赛 - 《学习笔记》

6000. 对奇偶下标分别排序
6001. 重排数字的最小值
6002. 设计位集
6003. 移除所有载有违禁货物车厢所需的最少时间

比较顺利的一次，没有罚时！！！

6000. 对奇偶下标分别排序

给你一个下标从 0 开始的整数数组 nums 。根据下述规则重排 nums 中的值：

按 非递增 顺序排列 nums 奇数下标 上的所有值。
- 举个例子，如果排序前 nums = [4,1,2,3] ，对奇数下标的值排序后变为 [4,3,2,1] 。奇数下标 1 和 3 的值按照非递增顺序重排。
按 非递减 顺序排列 nums 偶数下标 上的所有值。
- 举个例子，如果排序前 nums = [4,1,2,3] ，对偶数下标的值排序后变为 [2,1,4,3] 。偶数下标 0 和 2 的值按照非递减顺序重排。

返回重排 nums 的值之后形成的数组。

示例 1：
输入：nums = [4,1,2,3] 输出：[2,3,4,1] 解释： 首先，按非递增顺序重排奇数下标（1 和 3）的值。所以，nums 从 [4,1,2,3] 变为 [4,3,2,1] 。然后，按非递减顺序重排偶数下标（0 和 2）的值。所以，nums 从 [4,1,2,3] 变为 [2,3,4,1] 。因此，重排之后形成的数组是 [2,3,4,1] 。
示例 2：
输入：nums = [2,1] 输出：[2,1] 解释： 由于只有一个奇数下标和一个偶数下标，所以不会发生重排。形成的结果数组是 [2,1] ，和初始数组一样。

提示：

1 <= nums.length <= 100
1 <= nums[i] <= 100

思路：
分类排序再合并即可

class Solution {
    public int[] sortEvenOdd(int[] nums) {
        List<Integer> l1 = new ArrayList<>();
        List<Integer> l2 = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (i % 2 == 0) {
                l1.add(nums[i]);
            } else {
                l2.add(nums[i]);
            }
        }
        Collections.sort(l1);
        Collections.sort(l2, (o1, o2) -> (o2 - o1));
        for (int i = 0, j = 0; i < l1.size(); i++, j += 2)
            nums[j] = l1.get(i);
        for (int i = 0, j = 1; i < l2.size(); i++, j += 2)
            nums[j] = l2.get(i);
        return nums;
    }
}

6001. 重排数字的最小值

给你一个整数 num 。重排 num 中的各位数字，使其值 最小化 且不含任何前导零。
返回不含前导零且值最小的重排数字。
注意，重排各位数字后，num 的符号不会改变。

示例 1：
输入：num = 310 输出：103 解释：310 中各位数字的可行排列有：013、031、103、130、301、310 。不含任何前导零且值最小的重排数字是 103 。
示例 2：
输入：num = -7605 输出：-7650 解释：-7605 中各位数字的部分可行排列为：-7650、-6705、-5076、-0567。不含任何前导零且值最小的重排数字是 -7650 。

提示：

-1015 <= num <= 1015

思路：
正数，负数分别处理，0特判一下
如果是正数的话，所有0补充在第一个最小的非零数后即可，其余数从小到大跟在后面
如果是负数的话，所有0补充在最后即可，其余数从大到小放在前面

class Solution {
    public long smallestNumber(long num) {
        if (num == 0) return 0;
        boolean flag = num < 0 ? true : false;
        if (flag) {
            num = -num;
            List<Long> list = new ArrayList<>();
            int c0 = 0;
            while (num > 0) {
                long x = num % 10;
                if (x == 0) c0++;
                else list.add(x);
                num /= 10;
            }
            Collections.sort(list, (o1, o2) -> (int)(o2 - o1));
            long res = 0;
            for (long x : list) {
                res = res * 10 + x;
            }
            while (c0-- > 0) {
                res = res * 10;
            }
            return -res;
        } else {
            List<Long> list = new ArrayList<>();
            int c0 = 0;
            while (num > 0) {
                long x = num % 10;
                if (x == 0) c0++;
                else list.add(x);
                num /= 10;
            }
            Collections.sort(list);
            long res = 0;
            res = list.get(0);
            while (c0-- > 0)
                res = res * 10;
            for (int i = 1; i < list.size(); i++)
                res = res * 10 + list.get(i);
            return res;
        }
    }
}

6002. 设计位集

位集 Bitset 是一种能以紧凑形式存储位的数据结构。
请你实现 Bitset 类。

Bitset(int size) 用 size 个位初始化 Bitset ，所有位都是 0 。
void fix(int idx) 将下标为 idx 的位上的值更新为 1 。如果值已经是 1 ，则不会发生任何改变。
void unfix(int idx) 将下标为 idx 的位上的值更新为 0 。如果值已经是 0 ，则不会发生任何改变。
void flip() 翻转 Bitset 中每一位上的值。换句话说，所有值为 0 的位将会变成 1 ，反之亦然。
boolean all() 检查 Bitset 中 每一位 的值是否都是 1 。如果满足此条件，返回 true ；否则，返回 false 。
boolean one() 检查 Bitset 中是否 至少一位 的值是 1 。如果满足此条件，返回 true ；否则，返回 false 。
int count() 返回 Bitset 中值为 1 的位的总数。
String toString() 返回 Bitset 的当前组成情况。注意，在结果字符串中，第 i 个下标处的字符应该与 Bitset 中的第 i 位一致。

示例：
输入 [“Bitset”, “fix”, “fix”, “flip”, “all”, “unfix”, “flip”, “one”, “unfix”, “count”, “toString”] [[5], [3], [1], [], [], [0], [], [], [0], [], []] 输出 [null, null, null, null, false, null, null, true, null, 2, “01010”] 解释 Bitset bs = new Bitset(5); // bitset = “00000”. bs.fix(3); // 将 idx = 3 处的值更新为 1 ，此时 bitset = “00010” 。 bs.fix(1); // 将 idx = 1 处的值更新为 1 ，此时 bitset = “01010” 。 bs.flip(); // 翻转每一位上的值，此时 bitset = “10101” 。 bs.all(); // 返回 False ，bitset 中的值不全为 1 。 bs.unfix(0); // 将 idx = 0 处的值更新为 0 ，此时 bitset = “00101” 。 bs.flip(); // 翻转每一位上的值，此时 bitset = “11010” 。 bs.one(); // 返回 True ，至少存在一位的值为 1 。 bs.unfix(0); // 将 idx = 0 处的值更新为 0 ，此时 bitset = “01010” 。 bs.count(); // 返回 2 ，当前有 2 位的值为 1 。 bs.toString(); // 返回 “01010” ，即 bitset 的当前组成情况。

提示：

1 <= size <= 105
0 <= idx <= size - 1
至多调用 fix、unfix、flip、all、one、count 和 toString 方法总共 105 次
至少调用 all、one、count 或 toString 方法一次
至多调用 toString 方法 5 次

思路：
用数组模拟一下即可
已经提示至多调用toString()5次，所以不用担心超时

class Bitset {
    int size;
    int[] f;
    int one, zero;
    public Bitset(int size) {
        this.size = size;
        f = new int[(size + 31) / 32];
        this.zero = size;
    }
    public void fix(int idx) {
        int x = idx / 32, y = idx % 32;
        if ((f[x] >> y & 1) == 1) return;
        f[x] |= (1 << y);
        one++;
        zero--;
    }
    public void unfix(int idx) {
        int x = idx / 32, y = idx % 32;
        if ((f[x] >> y & 1) == 0) return;
        f[x] ^= (1 << y);
        zero++;
        one--;
    }
    public void flip() {
        int t = zero;
        zero = one;
        one = t;
        for (int i = 0; i < f.length; i++)
            f[i] = ~f[i];
    }
    public boolean all() {
        return one == size;
    }
    public boolean one() {
        return one > 0;
    }
    public int count() {
        return one;
    }
    public String toString() {
        StringBuilder sb = new StringBuilder();
        // int len = size % 32;
        for (int i = 0; i < f.length; i++) {
            for (int j = 0; j < 32; j++) {
                sb.append(f[i] >> j & 1);
            }
        }
        return sb.toString().substring(0, size);
    }
}
/**
 * Your Bitset object will be instantiated and called as such:
 * Bitset obj = new Bitset(size);
 * obj.fix(idx);
 * obj.unfix(idx);
 * obj.flip();
 * boolean param_4 = obj.all();
 * boolean param_5 = obj.one();
 * int param_6 = obj.count();
 * String param_7 = obj.toString();
 */

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

给你一个下标从 0 开始的二进制字符串 s ，表示一个列车车厢序列。s[i] = ‘0’ 表示第 i 节车厢不含违禁货物，而 s[i] = ‘1’ 表示第 i 节车厢含违禁货物。
作为列车长，你需要清理掉所有载有违禁货物的车厢。你可以不限次数执行下述三种操作中的任意一个：

从列车左端移除一节车厢（即移除 s[0]），用去 1 单位时间。
从列车右端移除一节车厢（即移除 s[s.length - 1]），用去 1 单位时间。
从列车车厢序列的 任意位置 移除一节车厢，用去 2 单位时间。

返回移除所有载有违禁货物车厢所需要的最少单位时间数。
注意，空的列车车厢序列视为没有车厢含违禁货物。

示例 1：
输入：s = “11_00101“ 输出：5 解释： 一种从序列中移除所有载有违禁货物的车厢的方法是： - 从左端移除一节车厢 2 次。所用时间是 2 1 = 2 。 - 从右端移除一节车厢 1 次。所用时间是 1 。 - 移除序列中间位置载有违禁货物的车厢。所用时间是 2 。总时间是 2 + 1 + 2 = 5 。一种替代方法是： - 从左端移除一节车厢 2 次。所用时间是 2 1 = 2 。 - 从右端移除一节车厢 3 次。所用时间是 3 1 = 3 。总时间也是 2 + 3 = 5 。 5 是移除所有载有违禁货物的车厢所需要的最少单位时间数。没有其他方法能够用更少的时间移除这些车厢。
示例 2：
*输入：s = “001_0” 输出：2 解释： 一种从序列中移除所有载有违禁货物的车厢的方法是： - 从左端移除一节车厢 3 次。所用时间是 3 1 = 3 。总时间是 3. 另一种从序列中移除所有载有违禁货物的车厢的方法是： - 移除序列中间位置载有违禁货物的车厢。所用时间是 2 。总时间是 2. 另一种从序列中移除所有载有违禁货物的车厢的方法是： - 从右端移除一节车厢 2 次。所用时间是 2 1 = 2 。总时间是 2. 2 是移除所有载有违禁货物的车厢所需要的最少单位时间数。没有其他方法能够用更少的时间移除这些车厢。

提示：

1 <= s.length <= 2 * 105
s[i] 为 ‘0’ 或 ‘1’

思路：
DP
每个违禁车厢要么是从左边被删除，要么从中间直接被删除，要么从右边被删除
状态表示：f[i][j]表示前i个车厢的所有违禁车厢全部被删除，且第i个车厢被删除的方式是j（0表示从左边被删，1表示从右边被删）的所有删除方式的集和
集和属性：最小代价
状态转移：考虑第i个车厢是否为违禁车厢
是：f[i][0] = f[i - 1][0] + 1
f[i][1] = Math.min(f[i - 1][0], f[i - 1][1]) + 2
否：f[i][0] = f[i - 1][0] + 1
f[i][1] = Math.min(f[i - 1][0], f[i - 1][1])
g[i][j]倒着再DP一次，同理
然后枚举左右删除的分界点即可
res = Math.min(res, Math.min(f[i][0], f[i][1]) + Math.min(g[i + 1][0], g[i + 1][1]))

class Solution {
    public int minimumTime(String s) {
        int n = s.length();
        char[] c = s.toCharArray();
        int[][] f = new int[n + 2][2];
        int[][] g = new int[n + 2][2];
        // 左 中
        for (int i = 1; i <= n; i++) {
            char ch = c[i - 1];
            if (ch == '1') {
                f[i][0] = f[i - 1][0] + 1;
                f[i][1] = Math.min(f[i - 1][0], f[i - 1][1]) + 2;
            } else {
                f[i][0] = f[i - 1][0] + 1;
                f[i][1] = Math.min(f[i - 1][0], f[i - 1][1]);
            }
        }
        // 右 中
        for (int i = n; i > 0; i--) {
            char ch = c[i - 1];
            if (ch == '1') {
                g[i][0] = g[i + 1][0] + 1;
                g[i][1] = Math.min(g[i + 1][0], g[i + 1][1]) + 2;
            } else {
                g[i][0] = g[i + 1][0] + 1;
                g[i][1] = Math.min(g[i + 1][0], g[i + 1][1]);
            }
        }
        int sum = 0x3f3f3f3f;
        for (int i = 0; i <= n; i++) {
            sum = Math.min(sum, Math.min(f[i][0], f[i][1]) + Math.min(g[i + 1][0], g[i + 1][1]));
        }
        return sum;
    }
}