标签： 位运算

目标

给你一个整数数组 nums 。

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

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

示例 1：

输入： nums = [1,3]
输出： 2
解释：
所有可能的 XOR 三元组值为：
(0, 0, 0) → 1 XOR 1 XOR 1 = 1
(0, 0, 1) → 1 XOR 1 XOR 3 = 3
(0, 1, 1) → 1 XOR 3 XOR 3 = 1
(1, 1, 1) → 3 XOR 3 XOR 3 = 3
不同的 XOR 值为 {1, 3} 。因此输出为 2 。

示例 2：

输入： nums = [6,7,8,9]
输出： 4
解释：
不同的 XOR 值为 {6, 7, 8, 9} 。因此输出为 4 。

说明：

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

思路

有一个正整数数组 nums，从中取三个数（可重复）的异或值 XOR，求不同的 XOR 值有多少个。

暴力枚举。

代码

/**
 * @date 2026-07-24 9:12
 */
public class UniqueXorTriplets3514 {

    public int uniqueXorTriplets(int[] nums) {
        int n = nums.length;
        int max = 0;
        for (int num : nums) {
            max = Math.max(max, num);
        }
        int upper = 1 << (32 - Integer.numberOfLeadingZeros(max));
        boolean[] tmp = new boolean[upper];
        boolean[] arr = new boolean[upper];
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                tmp[nums[i] ^ nums[j]] = true;
            }
        }
        for (int i = 0; i < upper; i++) {
            if (tmp[i]) {
                for (int num : nums) {
                    arr[num ^ i] = true;
                }
            }
        }
        int res = 0;
        for (boolean b : arr) {
            if (b) {
                res++;
            }
        }
        return res;
    }

}

性能

目标

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

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

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

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

示例 1：

输入： nums = [1,2]
输出： 2
解释：
所有可能的 XOR 三元组值为：
(0, 0, 0) → 1 XOR 1 XOR 1 = 1
(0, 0, 1) → 1 XOR 1 XOR 2 = 2
(0, 1, 1) → 1 XOR 2 XOR 2 = 1
(1, 1, 1) → 2 XOR 2 XOR 2 = 2
不同的 XOR 值为 {1, 2}，因此输出为 2。

示例 2：

输入： nums = [3,1,2]
输出： 4
解释：
可能的 XOR 三元组值包括：
(0, 0, 0) → 3 XOR 3 XOR 3 = 3
(0, 0, 1) → 3 XOR 3 XOR 1 = 1
(0, 0, 2) → 3 XOR 3 XOR 2 = 2
(0, 1, 2) → 3 XOR 1 XOR 2 = 0
不同的 XOR 值为 {0, 1, 2, 3}，因此输出为 4。

说明：

• 1 <= n == nums.length <= 10^5
• 1 <= nums[i] <= n
• nums 是从 1 到 n 的整数的一个排列。

思路

有一个 1 ~ n 的排列，从中取三个数（可重复）的异或值 XOR，求不同的 XOR 值有多少个。

可以构造出 0 ~ 2^(k + 1) - 1 之间的任意数字，其中 k 是从右向左的最高位（从 0 开始）。

代码

/**
 * @date 2026-07-23 9:55
 */
public class UniqueXorTriplets3513 {

    public int uniqueXorTriplets(int[] nums) {
        int n = nums.length;
        return n <= 2 ? n : 1 << (32 - Integer.numberOfLeadingZeros(n));
    }
}

性能

目标

给你一个二维整数数组 descriptions ，其中 descriptions[i] = [parenti, childi, isLefti] 表示 parenti 是 childi 在 二叉树 中的 父节点，二叉树中各节点的值 互不相同 。此外：

• 如果 isLefti == 1 ，那么 childi 就是 parenti 的左子节点。
• 如果 isLefti == 0 ，那么 childi 就是 parenti 的右子节点。

请你根据 descriptions 的描述来构造二叉树并返回其 根节点 。

测试用例会保证可以构造出 有效 的二叉树。

示例 1：

输入：descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]
输出：[50,20,80,15,17,19]
解释：根节点是值为 50 的节点，因为它没有父节点。
结果二叉树如上图所示。

示例 2：

输入：descriptions = [[1,2,1],[2,3,0],[3,4,1]]
输出：[1,2,null,null,3,4]
解释：根节点是值为 1 的节点，因为它没有父节点。 
结果二叉树如上图所示。 

说明：

• 1 <= descriptions.length <= 10^4
• descriptions[i].length == 3
• 1 <= parenti, childi <= 10^5
• 0 <= isLefti <= 1
• descriptions 所描述的二叉树是一棵有效二叉树

思路

有一个二维数组 descriptions，descriptions[i] = [parenti, childi, left or right] 描述了二叉树中的一对父子关系，即 parenti 是 childi 的父节点，childi 是 parenti 的左或者右孩子（取决于 1 或者 0）。重建二叉树并返回根节点。题目保证描述的是有效二叉树，且节点值不重复。

使用哈希表保存树节点，根据描述关系将节点连接起来，最终需要找出根节点，可以将孩子节点存到哈希集合中，返回不在该集合的节点即可。

代码

/**
 * @date 2026-06-08 11:34
 */
public class CreateBinaryTree2196 {

    public TreeNode createBinaryTree(int[][] descriptions) {
        Map<Integer, TreeNode> map = new HashMap<>();
        Set<Integer> childKeySet = new HashSet<>();
        for (int[] description : descriptions) {
            int parentKey = description[0];
            map.putIfAbsent(parentKey, new TreeNode(parentKey));
            TreeNode parent = map.get(parentKey);
            int childKey = description[1];
            childKeySet.add(childKey);
            map.putIfAbsent(childKey, new TreeNode(childKey));
            TreeNode child = map.get(childKey);
            if (description[2] == 1) {
                parent.left = child;
            } else {
                parent.right = child;
            }
        }
        for (int[] description : descriptions) {
            int parentKey = description[0];
            if (!childKeySet.contains(parentKey)) {
                return map.get(parentKey);
            }
        }
        return null;
    }
}

性能

目标

给你一个整数 mass ，它表示一颗行星的初始质量。再给你一个整数数组 asteroids ，其中 asteroids[i] 是第 i 颗小行星的质量。

你可以按 任意顺序 重新安排小行星的顺序，然后让行星跟它们发生碰撞。如果行星碰撞时的质量 大于等于 小行星的质量，那么小行星被 摧毁 ，并且行星会 获得 这颗小行星的质量。否则，行星将被摧毁。

如果所有小行星 都 能被摧毁，请返回 true ，否则返回 false 。

示例 1：

输入：mass = 10, asteroids = [3,9,19,5,21]
输出：true
解释：一种安排小行星的方式为 [9,19,5,3,21] ：
- 行星与质量为 9 的小行星碰撞。新的行星质量为：10 + 9 = 19
- 行星与质量为 19 的小行星碰撞。新的行星质量为：19 + 19 = 38
- 行星与质量为 5 的小行星碰撞。新的行星质量为：38 + 5 = 43
- 行星与质量为 3 的小行星碰撞。新的行星质量为：43 + 3 = 46
- 行星与质量为 21 的小行星碰撞。新的行星质量为：46 + 21 = 67
所有小行星都被摧毁。

示例 2：

输入：mass = 5, asteroids = [4,9,23,4]
输出：false
解释：
行星无论如何没法获得足够质量去摧毁质量为 23 的小行星。
行星把别的小行星摧毁后，质量为 5 + 4 + 9 + 4 = 22 。
它比 23 小，所以无法摧毁最后一颗小行星。

说明：

• 1 <= mass <= 10^5
• 1 <= asteroids.length <= 10^5
• 1 <= asteroids[i] <= 10^5

思路

有一颗行星质量为 mass，还有一些小行星 asteroids，asteroids[i] 表示第 i 颗小行星的质量。可以让小行星以任意顺序碰撞行星，如果行星质量大于等于小行星，那么小行星被摧毁，行星获得其质量，否则行星被摧毁。判断是否所有小行星都可以被摧毁。

使用有序集合，每次获得比行星质量小的所有小行星质量。

代码

/**
 * @date 2026-06-01 10:14
 */
public class AsteroidsDestroyed2126 {

    public boolean asteroidsDestroyed(int mass, int[] asteroids) {
        TreeMap<Long, Integer> ts = new TreeMap<>();
        for (int a : asteroids) {
            ts.merge((long) a, 1, Integer::sum);
        }
        long m = mass;
        Long next = ts.floorKey(m);
        while (!ts.isEmpty() && next != null) {
            m += next * ts.get(next);
            ts.remove(next);
            next = ts.floorKey(m);
        }
        return ts.isEmpty();
    }

}

性能

目标

给你一个字符串 word。如果 word 中同时出现某个字母 c 的小写形式和大写形式，并且 每个 小写形式的 c 都出现在第一个大写形式的 c 之前，则称字母 c 是一个 特殊字母 。

返回 word 中 特殊字母 的数量。

示例 1:

输入：word = "aaAbcBC"
输出：3
解释：
特殊字母是 'a'、'b' 和 'c'。

示例 2:

输入：word = "abc"
输出：0
解释：
word 中不存在特殊字母。

示例 3:

输入：word = "AbBCab"
输出：0
解释：
word 中不存在特殊字母。

说明：

• 1 <= word.length <= 2 * 10^5
• word 仅由小写和大写英文字母组成。

思路

有一个字符串 word，返回其中大小写同时存在，且 所有小写都在其大写之前出现 的的字母个数。

与 3120_统计特殊字母的数量I 相比，本题多了顺序条件。

使用两个数组标记字母（无论大小写，统一用 0 ~ 25 表示）是否被计数以及是否被删除：

• 如果当前字母是大写：
  • 之前大小写都已出现（计数 或者 删除都已经处理过了），直接跳过
  • 对应的小写已经出现，计数（上面的条件保证了不会重复计数），并标记为已计数
• 如果当前字母是小写：
  • 之前大小写都已出现，且已计数（不一定被计数，因为小写可能后出现）未被标记为已删除，则计数减一，并标记为已删除
  • 注意如果之前只出现过大写，不用处理，因为没有被计数

代码

/**
 * @date 2026-05-26 9:06
 */
public class NumberOfSpecialChars3121 {

    /**
     * A(65):  1000001
     * Z(90):  1011010
     * a(97):  1100001
     * z(122): 1111010
     * 31: 0011111
     * 32: 0100000
     */
    public int numberOfSpecialChars_v1(String word) {
        Set<Integer> set = new HashSet<>();
        int n = word.length();
        boolean[] rm = new boolean[26];
        boolean[] add = new boolean[26];
        int res = 0;
        for (int i = 0; i < n; i++) {
            int c = word.charAt(i);
            // 将字母映射到 0 ~ 25，不区分大小写
            int index = (c & 31) - 1;
            // flag 为 0 表示大写字母，为 1 是小写字母
            int flag = c & 32;
            // 如果之前已经遇到过字母的大小写
            if (set.contains(c) && set.contains(c ^ (1 << 5))) {
                // 如果当前是大写，无需处理，因为需要加的话前面已经加了，需要减的前面已经减了
                if (flag == 0){
                    continue;
                }
                // 如果当前是小写，计数过且没减过，计数减一，并标记
                // 注意，如果之前只遇到过大写，不用处理，因为不满足条件没有被计数
                if (!rm[index] && add[index]){
                    rm[index] = true;
                    res--;
                }
            }
            // 如果当前是大写并且之前出现过小写，标记并计数
            if (flag == 0 && set.contains(c + 32)){
                add[index] = true;
                res++;
            }
            set.add(c);
        }
        return res;
    }

}

性能

目标

给你两个下标从 0 开始长度为 n 的整数排列 A 和 B 。

A 和 B 的 前缀公共数组 定义为数组 C ，其中 C[i] 是数组 A 和 B 到下标为 i 之前公共元素的数目。

请你返回 A 和 B 的 前缀公共数组 。

如果一个长度为 n 的数组包含 1 到 n 的元素恰好一次，我们称这个数组是一个长度为 n 的 排列 。

示例 1：

输入：A = [1,3,2,4], B = [3,1,2,4]
输出：[0,2,3,4]
解释：i = 0：没有公共元素，所以 C[0] = 0 。
i = 1：1 和 3 是两个数组的前缀公共元素，所以 C[1] = 2 。
i = 2：1，2 和 3 是两个数组的前缀公共元素，所以 C[2] = 3 。
i = 3：1，2，3 和 4 是两个数组的前缀公共元素，所以 C[3] = 4 。

示例 2：

输入：A = [2,3,1], B = [3,1,2]
输出：[0,1,3]
解释：i = 0：没有公共元素，所以 C[0] = 0 。
i = 1：只有 3 是公共元素，所以 C[1] = 1 。
i = 2：1，2 和 3 是两个数组的前缀公共元素，所以 C[2] = 3 。

说明：

• 1 <= A.length == B.length == n <= 50
• 1 <= A[i], B[i] <= n
• 题目保证 A 和 B 两个数组都是 n 个元素的排列。

思路

有两个长度为 n 的整数排列 A 和 B，整数 1 ~ n 恰好出现一次，C[i] 表示 A[0, i] 和 B[0, i] 中的公共元素个数（注意不是公共前缀长度），返回 C。

直接依题意模拟，使用哈希表（或者数组计数），A 中元素 +1， B 中元素 -1，然后累加出现次数为 0 的元素个数即可。注意元素相同时避免重复累加，并且当前位置公共元素的个数应该以前一个位置公共元素的个数为基础再加上新增公共元素的个数。

网友题解使用的是位运算，注意到 n <= 50，可以使用两个 long 型变量来记录元素是否出现，将这两个变量相与然后 bitcount 就是公共元素个数。

代码

/**
 * @date 2026-05-20 8:58
 */
public class FindThePrefixCommonArray2657 {

    public int[] findThePrefixCommonArray_v1(int[] A, int[] B) {
        int n = A.length;
        int[] cnt = new int[n + 1];
        int[] C = new int[n];
        cnt[A[0]]++;
        cnt[B[0]]--;
        if (A[0] == B[0]) {
            C[0] = 1;
        }
        for (int i = 1; i < n; i++) {
            cnt[A[i]]++;
            cnt[B[i]]--;
            C[i] = C[i - 1];
            if (cnt[A[i]] == 0) {
                C[i]++;
            }
            if (A[i] != B[i] && cnt[B[i]] == 0) {
                C[i]++;
            }
        }
        return C;
    }

}

性能

目标

给你一个二进制字符串 s 。你可以按任意顺序执行以下两种操作任意次：

• 类型 1 ：删除 字符串 s 的第一个字符并将它 添加 到字符串结尾。
• 类型 2 ：选择 字符串 s 中任意一个字符并将该字符 反转 ，也就是如果值为 '0' ，则反转得到 '1' ，反之亦然。

请你返回使 s 变成 交替 字符串的前提下， 类型 2 的 最少 操作次数 。

我们称一个字符串是 交替 的，需要满足任意相邻字符都不同。

• 比方说，字符串 "010" 和 "1010" 都是交替的，但是字符串 "0100" 不是。

示例 1：

输入：s = "111000"
输出：2
解释：执行第一种操作两次，得到 s = "100011" 。
然后对第三个和第六个字符执行第二种操作，得到 s = "101010" 。

示例 2：

输入：s = "010"
输出：0
解释：字符串已经是交替的。

示例 3：

输入：s = "1110"
输出：1
解释：对第二个字符执行第二种操作，得到 s = "1010" 。

说明：

• 1 <= s.length <= 10^5
• s[i] 要么是 '0' ，要么是 '1' 。

思路

有一个二进制字符串 s，每次操作：1.可以将首字母移动到末尾；2.或者将任意字符反转，求将 s 变为交替字符串所需的最小反转次数，即最少的操作 2 次数。

由于不考虑首尾移动的次数，可以将首尾相接，考虑字符串 s + s。交替字符串就两种，可以使用长度为 s.length 的滑动窗口计算反转的最小次数。

可以只考虑交替字符串 010101...，假设所需的反转次数为 k，那么 10101010... 所需的反转次数为 n - k，参考 1758.生成交替二进制字符串的最少操作数。

010101... 这种交替字符串可以用下标的奇偶性来表示。移出窗口时，如果下标的奇偶性与元素值的奇偶性不同，说明差异个数减一。移入窗口同理，操作次数加一。

代码

/**
 * @date 2026-03-09 11:42
 */
public class MinFlips1888 {

    public int minFlips(String s) {
        int n = s.length();
        char[] chars = s.toCharArray();
        int ops = 0;
        for (int i = 0; i < n; ++i) {
            ops += (chars[i] ^ i) & 1;
        }
        int res = Math.min(ops, n - ops);
        if ((n & 1) == 0) {
            // 如果长度为偶数，操作1不会改变下标的奇偶性，比如 i，i + n 的奇偶性相同，后面循环中 ops 并不会发生变化
            return res;
        }
        for (int i = 0; i < n; ++i) {
            ops -= (chars[i] ^ i) & 1;
            ops += (chars[i] ^ (n + i)) & 1;
            res = Math.min(res, Math.min(ops, n - ops));
        }
        return res;
    }

}

性能

目标

给你一个整数 n ，请你将 1 到 n 的二进制表示连接起来，并返回连接结果对应的 十进制 数字对 10^9 + 7 取余的结果。

示例 1：

输入：n = 1
输出：1
解释：二进制的 "1" 对应着十进制的 1 。

示例 2：

输入：n = 3
输出：27
解释：二进制下，1，2 和 3 分别对应 "1" ，"10" 和 "11" 。
将它们依次连接，我们得到 "11011" ，对应着十进制的 27 。

示例 3：

输入：n = 12
输出：505379714
解释：连接结果为 "1101110010111011110001001101010111100" 。
对应的十进制数字为 118505380540 。
对 10^9 + 7 取余后，结果为 505379714 。

说明：

• 1 <= n <= 10^5

思路

拼接 1 ~ n 的二进制表示，将结果对应的十进制数对 10^9 + 7 取模。

遍历 1 ~ n 模拟拼接过程，将之前拼接的数字左移当前数字的 bitLength 并对 mod 取模。拼接 a b c 可以视为 (a * 2^bitLength(b) + b) * 2^bitLength(c) + c，可以先对括号内的运算取模，即 (a << bitLength(b)) + b ) % mod。

代码

/**
 * @date 2026-02-28 9:18
 */
public class ConcatenatedBinary1680 {

    public int concatenatedBinary(int n) {
        int mod = 1000000007;
        long res = 0L;
        for (int i = 1; i <= n; i++) {
            int bl = 32 - Integer.numberOfLeadingZeros(i);
            res = ((res << bl) + i) % mod;
        }
        return (int) res;
    }

}

性能