第279场周赛

第一题 2164. 对奇偶下标分别排序

题意

给你一个下标从 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 的值之后形成的数组。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/sort-even-and-odd-indices-independently
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

一个水题,但是我脑子嗡嗡的,写了半个小时。

我的思路是把奇数位的放入一个数组排序,然后把偶数位的放入一个数组排序。然后合并。

算法复杂度应该是O(N), 精确点就是2N。

代码

import java.util.*;
class Solution {
   public int[] sortEvenOdd(int[] nums) {
        if(nums.length <= 2) return nums;
        List<Integer> odd = new ArrayList<>();
        List<Integer> even = new ArrayList<>();
        for(int i = 0; i < nums.length; i++) {
            if(i % 2 != 0) {
                odd.add(nums[i]);
            } else {
                even.add(nums[i]);
            }
        }
        odd.sort((o1, o2) -> o2 - o1);
        Collections.sort(even);
        int oddIdx = 0;
        int evenIdx = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i % 2 != 0) {
                Integer val = odd.get(oddIdx++);
                nums[i] = val;
            } else {
                Integer val = even.get(evenIdx++);
                nums[i] = val;
            }
        }
        return nums;
    }
}

第二题 2165. 重排数字的最小值

题目

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

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

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/smallest-value-of-the-rearranged-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

  • 对于正整数我们只需要把每一位数字取出,如[3,1,0],然后对这个数组进行排序[0, 1, 3],如果发现前导为0,我们就寻找第一个不为0的数字和第一位交换。这里也就是0 <-> 1,最后变为[1, 0, 3]。

    • [4, 0, 0, 3, 2] ----排序---> [0, 0, 2, 3, 4] ---交换->[2, 0, 0, 3, 4]
  • 对于负数,我们取它的绝对值,然后要求调整位置使得这个绝对值最大,我们就可以把数字从大到小排序,这样就不会出现前导为0,我们直接算出就可以。注意最后要写成负数。

    • -[7, 6, 0, 5] ---->-[7,6,5,0]

代码

class Solution {
    public long smallestNumber(long num) {
        if(num == 0) return 0;
        List<Long> list = new ArrayList<>();
        long ans = 0;
        if (num < 0) {
            num = -num;
            long tmp = num;
            while (tmp > 0) {
                long remind = tmp % 10;
                tmp /= 10;
                list.add(remind);
            }
            list.sort((o1, o2) -> (int) (o2 - o1));
            long pow = 1;
            for (int i = list.size()-1; i >= 0; i--) {
                long n = list.get(i);
                ans += pow * n;
                pow *= 10;
            }
            ans = -ans;
        } else {
            long tmp = num;
            while (tmp > 0) {
                long remind = tmp % 10;
                tmp /= 10;
                list.add(remind);
            }
            Collections.sort(list);
            if (list.get(0) == 0) {
                int end = 0;
                for (int i = 0; i < list.size(); i++) {
                    if (list.get(i) != 0) {
                        end = i;
                        break;
                    }
                }
                long next = list.get(end);
                list.set(end, 0L);
                list.set(0, next);
            }
            long pow = 1;
            for (int i = list.size()-1; i >= 0; i--) {
                long n = list.get(i);
                ans += pow * n;
                pow *= 10;
            }
        }
        return ans;
    }
}

第三题 2166. 设计位集

题目

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/design-bitset
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

一开始沙比Σ(☉▽☉"a,没看数据的范围

  • 1 <= size <= 105
  • 0 <= idx <= size - 1

然后直接用char(16bit)做直接爆了,然后才看了下官方的做法。

错误的方法,用char进行位运算直接做

错误的做法如下。

class Bitset {
    int size;
    char bitSet;
    public Bitset(int size) {
        this.size = size;
        this.bitSet = 0;
    }

    public void fix(int idx) {
        int change = (int) Math.pow(2, this.size - idx - 1);
        this.bitSet = (char) (this.bitSet | change);
    }

    public void unfix(int idx) {
        int change = ~(int) Math.pow(2, this.size - idx - 1);
        this.bitSet = (char) (this.bitSet & change);
    }

    public void flip() {
        this.bitSet = (char) ((~this.bitSet));
    }

    public boolean all() {
        int tmp = this.bitSet;
        int cnt = 0;
        while (cnt < this.size) {
            if ((tmp & 1) != 1) {
                return false;
            }
            cnt++;
            tmp >>= 1;
        }
        return true;
    }

    public boolean one() {
        int tmp = this.bitSet;
        int cnt = 0;
        while (cnt < this.size) {
            if ((tmp & 1) == 1) {
                return true;
            }
            cnt++;
            tmp >>= 1;
        }
        return false;
    }

    public int count() {
        int cnt = 0;
        int tmp = this.bitSet;
        int p = 0;
        while (p < this.size) {
            if ((tmp & 1) == 1) {
                cnt++;
            }
            p++;
            tmp >>= 1;
        }
        return cnt;
    }

    public String toString() {
        int tmp = this.bitSet;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < this.size; i++) {
            int remind =tmp % 2;
            tmp /= 2;
            sb.append(remind);
        }
        sb.reverse();
        return sb.toString();
    }
}

正确的方法,用数组模拟bit位进行运算

我们需要知道如果经过偶数次的flip,二进制数不变,所以我们用一个reversed的二进制位来表示是奇数次还是偶数次, flip()函数不真正改变arr[]里面的数字,而是在需要运算的时候才使用。

public void fix(int idx) {
        // 如果它arr[idx]通过反转后为0的话
        if ((arr[idx] ^ reversed) == 0) {
            // 那么就把这个位数变为1. 异或的规则是同0异1,也就是 0^1=1, 1^1=0, 0^0=0, 1^0=1
            arr[idx] ^= 1;
            ++cnt;
        }
}
public void unfix(int idx) {
        // 如果它arr[idx]通过反转后为1的话
        if ((arr[idx] ^ reversed) == 1) {
            // 把这个变成0
            arr[idx] ^= 1;
            --cnt;
        }
 }
public void flip() {
        // 记录反转次数, 0 异或 1 = 1 -> 1 异或 1 = 0
        // 仅记录反转次数,不参与计算
        reversed ^= 1;
        cnt = arr.length - cnt;
}
public boolean all() {
        return cnt == arr.length;
}

public boolean one() {
    return cnt > 0;
}

public int count() {
    return cnt;
}
public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arr.length; i++) {
            // 最后输出的时候把反转加上
            sb.append(arr[i] ^ reversed);
        }
        sb.reverse();
        return sb.toString();
}

代码

class Bitset {
    int[] arr;
    int cnt ;
    int reversed;
    public Bitset(int size) {
        arr = new int[size];
        this.cnt = 0;
        this.reversed = 0;
    }

    public void fix(int idx) {
        // 如果它arr[idx]通过反转后为0的话
        if ((arr[idx] ^ reversed) == 0) {
            arr[idx] ^= 1;
            ++cnt;
        }
    }

    public void unfix(int idx) {
        // 如果它arr[idx]通过反转后为1的话
        if ((arr[idx] ^ reversed) == 1) {
            arr[idx] ^= 1;
            --cnt;
        }
    }

    public void flip() {
        // 记录反转次数, 0 异或 1 = 1 -> 1 异或 1 = 0
        reversed ^= 1;
        cnt = arr.length - cnt;
    }

        public boolean all() {
            return cnt == arr.length;
        }

        public boolean one() {
            return cnt > 0;
        }

        public int count() {
            return cnt;
        }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arr.length; i++) {
            sb.append(arr[i] ^ reversed);
        }
        sb.reverse();
        return sb.toString();
    }
}
最后修改:2022 年 03 月 03 日
如果觉得我的文章对你有用,请随意赞赏