2025年04月

第 154 场双周赛

Q1. 使数组和能被 K 整除的最少操作次数

给你一个整数数组 nums 和一个整数 k。你可以执行以下操作任意次：

• 选择一个下标 i，并将 nums[i] 替换为 nums[i] - 1。

返回使数组元素之和能被 k 整除所需的最小操作次数。

就是求数组和sum能被k整除需要执行的最小操作次数。

自己代码

class Solution {
    public int minOperations(int[] nums, int k) {
        int sum = 0;
        for (int x : nums) {
            sum += x;
        }
        int cnt = 0;
        while (sum % k != 0) {
            // -1
            sum--;
            cnt++;
        }
        return cnt;
    }
}

灵神代码

class Solution {
    public int minOperations(int[] nums, int k) {
        // 求和取模
        // 分类讨论，如果s就是k的倍数，就不用操作
        // 如果 s % k == 1， 那么操作一次，如果等于2那么操作两次
      	// 太强了，直接将题目转化成求和取余数 
        return Arrays.stream(nums).sum() % k;
    }
}

Q2. 不同 XOR 三元组的数目 I

给你一个长度为 n 的整数数组 nums，其中 nums 是范围 [1, n] 内所有数的 排列 。

XOR 三元组 定义为三个元素的异或值 nums[i] XOR nums[j] XOR nums[k]，其中 i <= j <= k。

返回所有可能三元组 (i, j, k) 中 不同 的 XOR 值的数量。

排列 是一个集合中所有元素的重新排列。

就是分类讨论，推倒出来的公式。

当n=1时，只有1，个数为1

当n=2时，只有1，2，个数为2

当n=3时，只有0，1，2，3，个数为4个

当n=4时，4的二进制100， 有0 ~7 一共8个数

API:

Integer.toBinaryString(n); 计算n的二进制字符串

String s = Integer.toBinaryString(8);  // s = 1000
int len = s.length();  // len = 4

Integer.numberOfLeadingZeros(n); 计算n二进制无符号最高有效为前面0的个数

int i = Integer.numberOfLeadingZeros(8);  // i = 28

自己代码

class Solution {
    public int uniqueXorTriplets(int[] nums) {
        // n>=1
        int n = nums.length;
        if (n <= 2) {
            return n;
        }
      	// 求长度n的二进制位数
        String s = Integer.toBinaryString(n);
        int len = s.length();
      	// 然后用n的二进制位数来求解，手动推出来的公式
      	// 当n>2的时候，xor值的数量就是： 二进制位数能表示的最大数+1
        int cnt = 0;
        for (int i = 0; i < len; i++) {
            cnt += Math.pow(2, i);
        }
        return cnt + 1;
    }
}

灵神代码

class Solution {
    public int uniqueXorTriplets(int[] nums) {
        int n = nums.length;
        // return n <= 2 ? n : (int) Math.pow(2, 32 - Integer.numberOfLeadingZeros(n));
        
        // Integer.numberOfLeadingZeros(n); 高效的计算出无符号整数最高有效位前面0的个数。
        return n <= 2?n: 1 << (32 - Integer.numberOfLeadingZeros(n));
    }
}

3514. 不同 XOR 三元组的数目 II

给你一个整数数组 nums 。

XOR 三元组 定义为三个元素的异或值 nums[i] XOR nums[j] XOR nums[k]，其中 i <= j <= k。

返回所有可能三元组 (i, j, k) 中 不同 的 XOR 值的数量。

优化三重循环到二重循环。

Java

class Solution {
    public int uniqueXorTriplets(int[] nums) {
        int mx = 0;
        for (int x : nums) {
            mx = Math.max(mx, x);
        }
        // 为什么要做这个操作？
        // 求1-n时最多的个数
        int u = 1 << (32 - Integer.numberOfLeadingZeros(mx));

        boolean[] has = new boolean[u];

        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                has[nums[i] ^ nums[j]] = true;
            }
        }
        boolean[] has3 = new boolean[u];
        for (int xy = 0; xy < u; xy++) {
            if (!has[xy]) {
                continue;
            }
            for (int z : nums) {
                has3[xy ^ z] = true;
            }
        }
        int ans = 0;
        for (boolean b : has3) {
            if (b) {
                ans++;
            }
        }
        return ans;
    }
}

第 153 场双周赛

灵神视频讲解

还没想好以什么形式记录周赛的题目，暂时每场周赛一个文件吧。

记录做题过程中的思考的问题。

Q1. 字符串的反转度

给你一个字符串s，计算其反转度。

反转度的计算方法如下：

1.对每个字符，将其在反转字母表中的位置（'a'=26, 'b'=25...'z'=1），与其字符串中的位置（下标从1开始）相乘。

2.将这些乘积加起来，就得到了字符串中所有字符的和。

返回反转度。

就是用反转字母表中字符的位置 * 字符的位置之和。

在解题的时候，想不到如何维护字母表，就用map来维护了，但是后更好的方式，就是 26 - (s.charAt(i)-'a')就是字符在字母表中的位置。

使用a来维护字母表

class Solution {
    public int reverseDegree(String s) {
      	// 主要是维护字母表
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            int reverse = 26 - (s.charAt(i) - 'a');
            res += reverse * (i + 1);
        }
        return res;
    }
}©leetcode

使用z来维护字母表

class Solution {
    public int reverseDegree(String s) {
        // 主要是维护字母表
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            int cnt = (('z' - s.charAt(i)) + 1) * (i + 1);
            ans += cnt;
        }
        return ans;
    }
}

遇到的问题：

1、a z的ascll码是多少？

• a 97， z 122， A 65， Z 90

2、java中如何将ascll与字符进行转换？

• // 将数字转成字符
  int num = 97;
  char x = (char) num;  // sout -> x = a
  // 将字符转成数字
  int s = x;  // sout -> s = 97

3、java中将的api

• s.toCharArray(), s.charAt(idx)

Q2. 操作后最大活跃区段数 I

给你一个长度为 n 的二进制字符串 s，其中：

• '1' 表示一个 活跃 区段。
• '0' 表示一个 非活跃 区段。

你可以执行 最多一次操作 来最大化 s 中的活跃区段数量。在一次操作中，你可以：

• 将一个被 '0' 包围的连续 '1' 区块转换为全 '0'。
• 然后，将一个被 '1' 包围的连续 '0' 区块转换为全 '1'。

返回在执行最优操作后，s 中的 最大 活跃区段数。

**注意：**处理时需要在 s 的两侧加上 '1' ，即 t = '1' + s + '1'。这些加上的 '1' 不会影响最终的计数。

python

class Solution:
    def maxActiveSectionsAfterTrade(self, s: str) -> int:
        ans = mx = cnt = 0
        pre0 = -inf

        for i, b in enumerate(s):
            cnt += 1
            if i == len(s) - 1 or b != s[i + 1]:
                if b == "1":
                    ans += cnt
                else:
                    mx = max(mx, pre0 + cnt)
                    pre0 = cnt
                cnt = 0
        return ans + mx

Q4. 操作后最大活跃区段数 II

给你一个长度为 n 的二进制字符串 s ，其中：

• '1' 表示一个 活跃 区域。
• '0' 表示一个 非活跃 区域。

你最多可以进行一次 操作 来最大化 s 中活跃区间的数量。在一次操作中，你可以：

• 将一个被 '0' 包围的连续 '1' 区域转换为全 '0'。
• 然后，将一个被 '1' 包围的连续 '0' 区域转换为全 '1'。

此外，你还有一个 二维数组 queries，其中 queries[i] = [li, ri] 表示子字符串 s[li...ri]。

对于每个查询，确定在对子字符串 s[li...ri] 进行最优交换后，字符串 s 中 可能的最大 活跃区间数。

返回一个数组 answer，其中 answer[i] 是 queries[i] 的结果。

注意

• 对于每个查询，仅对 s[li...ri] 处理时，将其看作是在两端都加上一个 '1' 后的字符串，形成 t = '1' + s[li...ri] + '1'。这些额外的 '1' 不会对最终的活跃区间数有贡献。
• 各个查询相互独立。

Changelog

5/7/25, 10:15 AM

View All Changelog

• 8c7c5-feat(wiki): java: 基本数据结构源代码on 5/7/25