⭐️寒假新坑——代码之狐的每日做题笔记

⭐️解题思路

1. 按下标奇偶分组保存，分别排序处理
2. 获取每一位数字，排序，根据正负分类处理（负数要求重排后的正数最大，正数要求最小且没有前导零）
3. 难点是考虑优化反转操作——保存一个反转数组，反转操作不用重新处理每一位，只是将反转数组和当前数组交换即可，不然超时
4. DP，使用L[i]保存只考虑从左处理完i节点的最小花费，R[i]同理，然后再次历遍一次，判断L[i]+R[i+1]是否最小花费（注意L[n]和R[0]单独判断，表示只从左往右处理或从右往左处理）；求DP数组L和R的思路：由于只有两种操作——对于一个有问题车厢——边缘移除操作（要求前面全部移除，花费为包含该车厢和前面车厢的个数），中间移除操作（花费为之前一个车厢处理完的最小值+2，之前一个车厢什么操作完全不影响当前车厢操作）；对于一个正常车厢——直接集成之前车厢花费即可

6000. 对奇偶下标分别排序-第 279 场周赛题1

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

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

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

class Solution {
    public int[] sortEvenOdd(int[] nums) {
        List<Integer> j=new ArrayList<>();
        List<Integer> o=new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            if(i%2==0){
                o.add(nums[i]);
            }
            else{
                j.add(nums[i]);
            }
        }
        
        Collections.sort(o);
        Collections.sort(j,(a,b)->(b-a));
        
        for(int i=0;i<nums.length;i++){
            if(i%2==0){
                nums[i]=o.get(i/2);
            }
            else{
                nums[i]=j.get(i/2);
            }
        }
        return nums;
    }
}

6001. 重排数字的最小值-Mid-第 279 场周赛题2

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

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

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

class Solution {
    public long smallestNumber(long num) {
        if(num==0){
            return 0;
        }
        
        boolean T=false;
        if(num>0){
            T=true;
        }
        else{
            num=-num;
        }
        
        List<Long> l=new ArrayList<>();
        while(num!=0){
            l.add(num%10);
            num/=10;
        }
        
        Collections.sort(l);
        if(T==false){
            int c=l.size()-1;
            while(c>=0){
                num=num*10+l.get(c);
                c--;
            }
            return -num;
        }
        else{
            int c=0;
            while(l.get(c)==0){
                c++;
            }
            num+=l.get(c);
            c++;
            for(int i=0;i<c-1;i++){
                num*=10;
            }
            while(c<l.size()){
                num=num*10+l.get(c);
                c++;
            }
            return num;
        }
    }
}

6002. 设计位集-Mid-第 279 场周赛题3

位集 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 位一致。

class Bitset {
    boolean[] bits;
    boolean[] bit;
    int count_all;
    int count_1;
    public Bitset(int size) {
        bits=new boolean[size];
        bit=new boolean[size];
        count_all=size;
        for(int i=0;i<count_all;i++){
            bit[i]=true;
        }
        
        count_1=0;
    }
    
    public void fix(int idx) {
        if(!bits[idx]){
            bits[idx]=true;
            count_1++;
        }
        bit[idx]=false;
    }
    
    public void unfix(int idx) {
        if(bits[idx]){
            bits[idx]=false;
            count_1--;
        }
        bit[idx]=true;
    }
    
    public void flip() {
        count_1=count_all-count_1;
        
        boolean[] mid=bits;
        bits=bit;
        bit=mid;
    }
    
    public boolean all() {
        return count_1==count_all;
    }
    
    public boolean one() {
        return count_1>=1;
    }
    
    public int count() {
        return count_1;
    }
    
    public String toString() {
        StringBuffer res=new StringBuffer();
        for(int i=0;i<count_all;i++){
            if(bits[i])
                res.append(1);
            else{
                res.append(0);
            }
        }
        return res.toString();
    }
}

/**
 * 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. 移除所有载有违禁货物车厢所需的最少时间-Hard-第 279 场周赛题4

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

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

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

返回移除所有载有违禁货物车厢所需要的 最少 单位时间数。

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

class Solution {
    public int minimumTime(String s) {
        int n=s.length();
        int[][] l=new int[n][2];
        if(s.charAt(0)=='1'){
            l[0][1]=2;
            l[0][0]=1;
        }
        
        for(int i=1;i<n;i++){
            if(s.charAt(i)=='1'){
                l[i][0]=i+1;
                l[i][1]=Math.min(l[i-1][0],l[i-1][1])+2;
            }
            else{
                l[i][0]=l[i-1][0];
                l[i][1]=l[i-1][1];
            }
        }
        
        int[][] r=new int[n][2];
        if(s.charAt(n-1)=='1'){
            r[n-1][1]=2;
            r[n-1][0]=1;
        }
        
        for(int i=n-2;i>=0;i--){
            if(s.charAt(i)=='1'){
                r[i][0]=n-(i);
                r[i][1]=Math.min(r[i+1][0],r[i+1][1])+2;
            }
            else{
                r[i][0]=r[i+1][0];
                r[i][1]=r[i+1][1];
            }
        }
        
        for(int i=0;i<n;i++){
            r[i][0]=Math.min(r[i][0],r[i][1]);
            l[i][0]=Math.min(l[i][0],l[i][1]);
        }
        
        int ans=Math.min(l[n-1][0],r[0][0]);
        
        for(int i=0;i<n-1;i++){
            if(ans>(l[i][0]+r[i+1][0])){
                ans=(l[i][0]+r[i+1][0]);
            }
        }
        
        return ans;
    }
}

结尾

题目来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems

⭐️关注作者，带你刷题，从简单的算法题了解最常用的算法技能（寒假每日一题）
⭐️关注作者刷题——简单到进阶，让你不知不觉成为无情的刷题机器，有问题请私信