T1 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.length <= 100
• 1 <= nums[i] <= 100

解题思路：按要求排序即可

代码和提交结果如下：

class Solution {
    public int[] sortEvenOdd(int[] nums) {
        if(nums.length <= 2){
            return nums;
        }
        List<Integer> ji = new ArrayList<>();
        List<Integer> ou = new ArrayList<>();
        for(int i = 0 ; i < nums.length ;i++){
            if(i%2 == 0){
                ou.add(nums[i]);
            }else{
                ji.add(nums[i]);
            }
        }
        Collections.sort(ji);
        Collections.sort(ou);
        int jiS = ji.size()-1;
        int ouS = 0;
        
        for(int i = 0 ; i < nums.length ;i++){
            if(i%2 == 0){
                nums[i] = ou.get(ouS++);
            }else{
                nums[i] = ji.get(jiS--);
            }
        }
        return nums;
    }
}

 

T2 6001. 重排数字的最小值 

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

返回不含前导零且值最小的重排数字。

注意，重排各位数字后，num 的符号不会改变。

 

提示：

• - <= num <=

 解题思路：分三种情况进行讨论

① num > 0  将 num 的各个位置数字取出来按从小到大重排，需要返回的结果值最高位取非零的最小的数字，然后后面紧跟 所以的 0，剩余位置则是剩余数字从小到大排列。

② num = 0  返回的结果值直接返回 0 ；

③ num < 0 将 num 的各个位置数字取出来按从大到小重排，然后返回的结果为重排结果从左到右按顺序组合，最后乘 -1 即可。

代码和提交结果如下：

class Solution {
    public long smallestNumber(long num) {
        if(num == 0){
            return 0;
        }
        List<Long> list = new ArrayList<>();
        long temp = Math.abs(num);
        while(temp > 0){
            list.add(temp % 10);
            temp/=10;
        }
        Collections.sort(list);
        long res = 0;
        if(num < 0){
            for (int i = list.size()-1; i >= 0; i--) {
                if(list.get(i)!=0){
                    res = res*10+list.get(i);
                }else{
                    res = res*10;
                }
            }
            res = res * -1;
        }else{
            int count = 0;
            int index = 0;
            for (int i = 0; i < list.size(); i++) {
                if(list.get(i) == 0){
                    count++;
                }else{
                    index = i;
                    break;
                }
            }
            res = list.get(index);
            while(count > 0){
                res *= 10;
                count--;
            }
            for (int i = index+1; i < list.size(); i++) {
                res = res*10+list.get(i);
            }

        }
        return res;
    }
}

T3 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 方法外别的方法都不可以使用O（n）的时间复杂度，不然就会超时。

使用两个 HashSet 来对 0 和 1 的 index位置 进行存储，flip 方法则可以使用直接交换 HashSet 的方法来完成，稳得一批。

代码和提交结果如下：

 

class Bitset {
    HashSet<Integer> hashSet_one = new HashSet<>();
    HashSet<Integer> hashSet_zero = new HashSet<>();
    int size = 0;
    public Bitset(int size) {
        this.size = size;
        for (int i = 0; i < size; i++) {
            hashSet_zero.add(i);
        }
    }

    public void fix(int idx) {
        if(hashSet_zero.contains(idx)){
            hashSet_one.add(idx);
            hashSet_zero.remove(idx);
        }
            
        
    }

    public void unfix(int idx) {
        if(hashSet_one.contains(idx)){
            hashSet_zero.add(idx);
            hashSet_one.remove(idx);
        }
    }

    public void flip() {
        HashSet<Integer> hashSet = new HashSet<>();
        hashSet = hashSet_one;
        hashSet_one = hashSet_zero;
        hashSet_zero = hashSet;
    }

    public boolean all() {
        return hashSet_one.size() == size;
    }

    public boolean one() {
        return hashSet_one.size() > 0;
    }

    public int count() {
        return hashSet_one.size();
    }

    public String toString() {
        char[] ch = new char[size];
        Arrays.fill(ch, '0');
        for (int k : hashSet_one) {
            ch[k] = '1';
        }
        return new String(ch);
    }
}

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

给你一个下标从 0 开始的二进制字符串 s ，表示一个列车车厢序列。s[i] = '0' 表示第 i 节车厢 不 含违禁货物，而 s[i] = '1' 表示第 i 节车厢含违禁货物。

作为列车长，你需要清理掉所有载有违禁货物的车厢。你可以不限次数执行下述三种操作中的任意一个：

从列车 左 端移除一节车厢（即移除 s[0]），用去 1 单位时间。
从列车 右 端移除一节车厢（即移除 s[s.length - 1]），用去 1 单位时间。
从列车车厢序列的 任意位置 移除一节车厢，用去 2 单位时间。
返回移除所有载有违禁货物车厢所需要的 最少 单位时间数。

注意，空的列车车厢序列视为没有车厢含违禁货物。

 

 

提示：

• 1 <= s.length <= 2 * 105
• s[i] 为 '0' 或 '1'

解题思路：DP + 枚举分割点

定义 left[i] 表示移除前 i 节车厢中的所有违禁货物车厢所花费的最少时间。

定义 right[i] 表示移除后  车厢总数 - i 节车厢中的所有违禁货物车厢所花费的最少时间。

当 s.charAt(i) == 1时，可以单独移除第 i 节车厢，也可以移除前 i + 1 个车厢，二者取最小值，既left[i] = Math.min(left[i-1]+2 , i+1)。

当 s.charAt(i) == 0时，不用进行移除，left[i] = left[i-1]。

right[] 数组的初始化和 left[] 相似。只不过需要从后往前进行 初始化。

当 s.charAt(i) == 0时，不用进行移除，right[i] = right[i+1];

当 s.charAt(i) == 1时，可以单独移除第 i 节车厢，也可以移除后 s.length()-i 车厢，二者取最小值，right[i] = Math.min(right[i+1]+2 , s.length()-i);

可以自己根据 left 的思路 捋 right，没必要直接看。​    

然后枚举分割点，计算所有 left[i]+right[i+1]、left[left.length - 1] 和 right[0]的最小值 ，即为答案。（我使用了一个 res 数组来进行寻找最小值）

left[left.length - 1] 和 right[0] 分别为 直接从左往右删完整个车厢 和 从右往左 删完整个车厢。

代码和提交结果如下：

class Solution {
    public int minimumTime(String s) {
        int left[] = new int[s.length()];
        int right[] = new int[s.length()];
        if(s.charAt(0) == '0'){
            left[0] = 0;
        }else{
            left[0] = 1;
        }
        if(s.charAt(s.length() - 1) == '0'){
            right[s.length()-1] = 0;
        }else{
            right[s.length()-1] = 1;
        }
        for(int i = 1 ; i < s.length() ; i++){
            if(s.charAt(i) == '0'){
                left[i] = left[i-1];
            }else{
                left[i] = Math.min(left[i-1]+2 , i+1);
            }
        }
        for(int i = s.length()-2 ; i >= 0 ; i--){
            if(s.charAt(i) == '0'){
                right[i] = right[i+1];
            }else{
                right[i] = Math.min(right[i+1]+2 , s.length()-i);
            }
        }
        int res[] = new int[s.length()+1];
        res[0] = right[0];
        res[res.length-1] = left[left.length-1];
        for(int i = 1 ; i < res.length-1 ; i++){
            res[i] = left[i-1] + right[i];
        }
        int min = Integer.MAX_VALUE;
        for(int i = 0 ; i < res.length ; i++){
            if(res[i] < min){
                min = res[i];
            }
        }
        return min;
    }
}

总结：这次周赛，因为之前设计题写的比较少又懒得读题，所以 T3 压根就没看（结束后悔死了），T4 开始以为是贪心，因为和之前做过的一道中等题特别像。2091. 从数组中移除最大值和最小值  最后 5 分钟发现方法错了。直接嘎了，明天更新双周赛题解。