标签： 位运算

3289.数字小镇中的捣蛋鬼

目标

数字小镇 Digitville 中，存在一个数字列表 nums，其中包含从 0 到 n - 1 的整数。每个数字本应 只出现一次，然而，有 两个 顽皮的数字额外多出现了一次，使得列表变得比正常情况下更长。

为了恢复 Digitville 的和平，作为小镇中的名侦探，请你找出这两个顽皮的数字。

返回一个长度为 2 的数组，包含这两个数字（顺序任意）。

示例 1：

输入： nums = [0,1,1,0]
输出： [0,1]
解释：
数字 0 和 1 分别在数组中出现了两次。

示例 2：

输入： nums = [0,3,2,1,3,2]
输出： [2,3]
解释:
数字 2 和 3 分别在数组中出现了两次。

示例 3：

输入： nums = [7,1,5,4,3,4,6,0,9,5,8,2]
输出： [4,5]
解释:
数字 4 和 5 分别在数组中出现了两次。

说明：

  • 2 <= n <= 100
  • nums.length == n + 2
  • 0 <= nums[i] < n
  • 输入保证 nums 中 恰好 包含两个重复的元素。

思路

长度为 n + 2 的数组，其元素由 0 1 2 …… n - 1 n 个数字以及该范围内的两个任意数字组成，找出这两个重复数字。

简单的做法是对每个元素计数，找出出现次数为 2 的元素。但是空间复杂度为 O(n)。

进阶的做法是使用位运算得到这两个重复数字的异或值，这两个数字至少有一个 bit 位不同，根据该 bit 位分组，最终得到这两个数字。

代码


/**
 * @date 2025-10-31 9:05
 */
public class GetSneakyNumbers3289 {

    public int[] getSneakyNumbers(int[] nums) {
        int n = nums.length;
        int[] cnt = new int[n];
        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            cnt[num]++;
            if (cnt[num] == 2){
                list.add(num);
            }
        }
        int[] res = new int[2];
        for (int i = 0; i < 2; i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

性能

3370.仅含置位位的最小整数

目标

给你一个正整数 n。

返回 大于等于 n 且二进制表示仅包含 置位 位的 最小 整数 x 。

置位 位指的是二进制表示中值为 1 的位。

示例 1：

输入： n = 5
输出： 7
解释：
7 的二进制表示是 "111"。

示例 2：

输入： n = 10
输出： 15
解释：
15 的二进制表示是 "1111"。

示例 3：

输入： n = 3
输出： 3
解释：
3 的二进制表示是 "11"。

说明：

  • 1 <= n <= 1000

思路

返回大于等于 n 并且所有 bit 位均为 1 的最小整数。

代码


/**
 * @date 2025-10-29 8:40
 */
public class SmallestNumber3370 {

    public int smallestNumber(int n) {
        int l = 32 - Integer.numberOfLeadingZeros(n);
        return (1 << l) - 1;
    }

}

性能

3541.找到频率最高的元音和辅音

目标

给你一个由小写英文字母（'a' 到 'z'）组成的字符串 s。你的任务是找出出现频率 最高 的元音（'a'、'e'、'i'、'o'、'u' 中的一个）和出现频率最高的辅音（除元音以外的所有字母），并返回这两个频率之和。

注意：如果有多个元音或辅音具有相同的最高频率，可以任选其中一个。如果字符串中没有元音或没有辅音，则其频率视为 0。

一个字母 x 的 频率 是它在字符串中出现的次数。

示例 1：

输入: s = "successes"
输出: 6
解释:
元音有：'u' 出现 1 次，'e' 出现 2 次。最大元音频率 = 2。
辅音有：'s' 出现 4 次，'c' 出现 2 次。最大辅音频率 = 4。
输出为 2 + 4 = 6。

示例 2：

输入: s = "aeiaeia"
输出: 3
解释:
元音有：'a' 出现 3 次，'e' 出现 2 次，'i' 出现 2 次。最大元音频率 = 3。
s 中没有辅音。因此，最大辅音频率 = 0。
输出为 3 + 0 = 3。

说明:

  • 1 <= s.length <= 100
  • s 只包含小写英文字母

思路

计算字符串中辅音字母与元音字母的最高频率之和。

代码


/**
 * @date 2025-09-13 22:46
 */
public class MaxFreqSum3541 {

    public int maxFreqSum(String s) {
        int[] cnt = new int[26];
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (char c : s.toCharArray()) {
            int i = c - 'a';
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                cnt[i]--;
                min = Math.min(min, cnt[i]);
            } else {
                cnt[i]++;
                max = Math.max(max, cnt[i]);
            }
        }
        return Math.max(0, max) - Math.min(0, min);
    }
}

性能

2749.得到整数零需要执行的最少操作数

目标

给你两个整数：num1 和 num2 。

在一步操作中，你需要从范围 [0, 60] 中选出一个整数 i ，并从 num1 减去 2^i + num2 。

请你计算，要想使 num1 等于 0 需要执行的最少操作数，并以整数形式返回。

如果无法使 num1 等于 0 ，返回 -1 。

示例 1：

输入：num1 = 3, num2 = -2
输出：3
解释：可以执行下述步骤使 3 等于 0 ：
- 选择 i = 2 ，并从 3 减去 2^2 + (-2) ，num1 = 3 - (4 + (-2)) = 1 。
- 选择 i = 2 ，并从 1 减去 2^2 + (-2) ，num1 = 1 - (4 + (-2)) = -1 。
- 选择 i = 0 ，并从 -1 减去 2^0 + (-2) ，num1 = (-1) - (1 + (-2)) = 0 。
可以证明 3 是需要执行的最少操作数。

示例 2：

输入：num1 = 5, num2 = 7
输出：-1
解释：可以证明，执行操作无法使 5 等于 0 。

说明：

  • 1 <= num1 <= 10^9
  • -10^9 <= num2 <= 10^9

思路

已知整数 num1 和 num2，每次操作需要从 0 ~ 60 选一个整数 i，并将 num1 -= 2^i + num2，返回将 num1 变为 0 的最小操作次数，如果无法完成返回 -1。

假设最少需要操作 k 次，那么 num1 - k * num2 = 2^i1 + 2^i2 + …… + 2^ik，其中 ik 表示第 k 次选择的 i。

问题转换为 num1 - k * num2 能否用 k 个 2 的幂表示。

二进制中 1 的个数就是最少的 k 的个数，它自身的值就是最多可以拆分的个数 ，也就是说 num = num1 - k * num2 的二进制表示中 1 的个数应小于等于 k 并且 num >= k。

代码


/**
 * @date 2025-09-05 8:46
 */
public class MakeTheIntegerZero2749 {

    public int makeTheIntegerZero(int num1, int num2) {
        for (int i = 0; i < 61; i++) {
            long num = num1 - (long) i * num2;
            if (num <= 0) {
                return -1;
            } else if (Long.bitCount(num) <= i && num >= i) {
                return i;
            }
        }
        return -1;
    }

}

性能

342.4的幂

目标

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4^x

示例 1：

输入：n = 16
输出：true

示例 2：

输入：n = 5
输出：false

示例 3：

输入：n = 1
输出：true

说明：

  • -2^31 <= n <= 2^31 - 1

进阶：你能不使用循环或者递归来完成本题吗？

思路

判断一个整数是否是 4 的幂。

参考 231.2的幂。

负数的二进制表示中前导零的个数为 0，而 4 的幂的前导零个数为奇数，恰好排除掉了负数。

代码


/**
 * @date 2025-08-15 8:43
 */
public class IsPowerOfFour342 {

    public boolean isPowerOfFour(int n) {
        return (n & (n - 1)) == 0 && Integer.numberOfLeadingZeros(n) % 2 == 1;
    }

}

性能

231.2的幂

目标

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

示例 1：

输入：n = 1
输出：true
解释：20 = 1

示例 2：

输入：n = 16
输出：true
解释：24 = 16

示例 3：

输入：n = 3
输出：false

提示：

  • -2^31 <= n <= 2^31 - 1

进阶：你能够不使用循环/递归解决此问题吗？

思路

判断数字是不是 2 的幂。

提前预处理 2 的幂。

进阶做法是判断 n & (n - 1) == 0。

代码


/**
 * @date 2025-08-09 20:33
 */
public class IsPowerOfTwo231 {

    static Set<Integer> set = new HashSet<>();

    static {
        for (int i = 0; i < 31; i++) {
            set.add(1 << i);
        }
    }

    public boolean isPowerOfTwo(int n) {
        return set.contains(n);
    }

}

性能

3307.找出第K个字符II

目标

Alice 和 Bob 正在玩一个游戏。最初，Alice 有一个字符串 word = "a"。

给定一个正整数 k 和一个整数数组 operations，其中 operations[i] 表示第 i 次操作的类型。

现在 Bob 将要求 Alice 按顺序执行 所有 操作：

  • 如果 operations[i] == 0，将 word 的一份 副本追加 到它自身。
  • 如果 operations[i] == 1，将 word 中的每个字符 更改 为英文字母表中的 下一个 字符来生成一个新字符串，并将其 追加 到原始的 word。例如，对 "c" 进行操作生成 "cd"，对 "zb" 进行操作生成 "zbac"。

在执行所有操作后，返回 word 中第 k 个字符的值。

注意，在第二种类型的操作中，字符 'z' 可以变成 'a'。

示例 1:

输入：k = 5, operations = [0,0,0]
输出："a"
解释：
最初，word == "a"。Alice 按以下方式执行三次操作：
将 "a" 附加到 "a"，word 变为 "aa"。
将 "aa" 附加到 "aa"，word 变为 "aaaa"。
将 "aaaa" 附加到 "aaaa"，word 变为 "aaaaaaaa"。

示例 2:

输入：k = 10, operations = [0,1,0,1]
输出："b"
解释：
最初，word == "a"。Alice 按以下方式执行四次操作：
将 "a" 附加到 "a"，word 变为 "aa"。
将 "bb" 附加到 "aa"，word 变为 "aabb"。
将 "aabb" 附加到 "aabb"，word 变为 "aabbaabb"。
将 "bbccbbcc" 附加到 "aabbaabb"，word 变为 "aabbaabbbbccbbcc"。

说明：

  • 1 <= k <= 10^14
  • 1 <= operations.length <= 100
  • operations[i] 可以是 0 或 1。
  • 输入保证在执行所有操作后，word 至少有 k 个字符。

思路

开始的时候有一个字符 a，根据操作数组 operations 执行以下操作：

  • 当 operations[i] == 0 时，将现有的所有字母拼接到当前字符后面。
  • 当 operations[i] == 1 时，将现有的所有字母替换为它在字母表中的下一个字母（z 的下一个字母为 a），拼接到当前字符后面。

返回执行所有操作之后的第 k 个字母。

计算 tail = ceil(log2(k)) 表示操作次数的上界，如果 k <= 1 << tail，说明在左半边无需操作，否则在右半边，需要操作，它是从左半边的第 k - (1 << tail) 个元素转移而来，需要根据 operations[tail] 来确定字母是否变化。按照这个逻辑递归，直到 tail < 0，返回字母 a。

代码


/**
 * @date 2025-07-04 9:19
 */
public class KthCharacter3307 {

    public char kthCharacter(long k, int[] operations) {
        return kthCharacter(k, operations, 63 - Long.numberOfLeadingZeros(k - 1));
    }

    public char kthCharacter(long k, int[] operations, int tail) {
        if (tail < 0) {
            return 'a';
        }
        long p = 1L << tail;
        if (k <= p) {
            return (char) ('a' + ((kthCharacter(k, operations, tail - 1) - 'a') % 26));
        }
        return (char) ('a' + (kthCharacter(k - p, operations, tail - 1) - 'a' + operations[tail]) % 26);
    }

}

性能

2716.最小化字符串长度

目标

给你一个下标从 0 开始的字符串 s ，重复执行下述操作 任意 次：

  • 在字符串中选出一个下标 i ，并使 c 为字符串下标 i 处的字符。并在 i 左侧（如果有）和 右侧（如果有）各 删除 一个距离 i 最近 的字符 c 。

请你通过执行上述操作任意次，使 s 的长度 最小化 。

返回一个表示 最小化 字符串的长度的整数。

示例 1：

输入：s = "aaabc"
输出：3
解释：在这个示例中，s 等于 "aaabc" 。我们可以选择位于下标 1 处的字符 'a' 开始。接着删除下标 1 左侧最近的那个 'a'（位于下标 0）以及下标 1 右侧最近的那个 'a'（位于下标 2）。执行操作后，字符串变为 "abc" 。继续对字符串执行任何操作都不会改变其长度。因此，最小化字符串的长度是 3 。

示例 2：

输入：s = "cbbd"
输出：3
解释：我们可以选择位于下标 1 处的字符 'b' 开始。下标 1 左侧不存在字符 'b' ，但右侧存在一个字符 'b'（位于下标 2），所以会删除位于下标 2 的字符 'b' 。执行操作后，字符串变为 "cbd" 。继续对字符串执行任何操作都不会改变其长度。因此，最小化字符串的长度是 3 。

示例 3：

输入：s = "dddaaa"
输出：2
解释：我们可以选择位于下标 1 处的字符 'd' 开始。接着删除下标 1 左侧最近的那个 'd'（位于下标 0）以及下标 1 右侧最近的那个 'd'（位于下标 2）。执行操作后，字符串变为 "daaa" 。继续对新字符串执行操作，可以选择位于下标 2 的字符 'a' 。接着删除下标 2 左侧最近的那个 'a'（位于下标 1）以及下标 2 右侧最近的那个 'a'（位于下标 3）。执行操作后，字符串变为 "da" 。继续对字符串执行任何操作都不会改变其长度。因此，最小化字符串的长度是 2 。

说明：

  • 1 <= s.length <= 100
  • s 仅由小写英文字母组成

思路

每次操作可以从字符串 s 中任选一个字符 c，同时删除其左侧与右侧距离最近的相同字符。求执行操作任意次后字符串的最小长度。

由于选中的字符不会被删除，本质是返回字符串中不同字符的个数。

代码


/**
 * @date 2025-03-28 0:20
 */
public class MinimizedStringLength2716 {

    /**
     * 位运算，将出现过的字符保存到 mask 中
     */
    public int minimizedStringLength_v1(String s) {
        int n = s.length();
        int mask = 0;
        for (int i = 0; i < n; i++) {
            mask |= 1 << (s.charAt(i) - 'a');
        }
        return Integer.bitCount(mask);
    }

    public int minimizedStringLength(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            set.add(s.charAt(i));
        }
        return set.size();
    }
}

性能

2711.对角线上不同值的数量差

目标

给你一个下标从 0 开始、大小为 m x n 的二维矩阵 grid ，请你求解大小同样为 m x n 的答案矩阵 answer 。

矩阵 answer 中每个单元格 (r, c) 的值可以按下述方式进行计算：

  • 令 topLeft[r][c] 为矩阵 grid 中单元格 (r, c) 左上角对角线上 不同值 的数量。
  • 令 bottomRight[r][c] 为矩阵 grid 中单元格 (r, c) 右下角对角线上 不同值 的数量。

然后 answer[r][c] = |topLeft[r][c] - bottomRight[r][c]| 。

返回矩阵 answer 。

矩阵对角线 是从最顶行或最左列的某个单元格开始，向右下方向走到矩阵末尾的对角线。

如果单元格 (r1, c1) 和单元格 (r, c) 属于同一条对角线且 r1 < r ，则单元格 (r1, c1) 属于单元格 (r, c) 的左上对角线。类似地，可以定义右下对角线。

示例 1：

输入：grid = [[1,2,3],[3,1,5],[3,2,1]]
输出：[[1,1,0],[1,0,1],[0,1,1]]
解释：第 1 个图表示最初的矩阵 grid 。 
第 2 个图表示对单元格 (0,0) 计算，其中蓝色单元格是位于右下对角线的单元格。
第 3 个图表示对单元格 (1,2) 计算，其中红色单元格是位于左上对角线的单元格。
第 4 个图表示对单元格 (1,1) 计算，其中蓝色单元格是位于右下对角线的单元格，红色单元格是位于左上对角线的单元格。
- 单元格 (0,0) 的右下对角线包含 [1,1] ，而左上对角线包含 [] 。对应答案是 |1 - 0| = 1 。
- 单元格 (1,2) 的右下对角线包含 [] ，而左上对角线包含 [2] 。对应答案是 |0 - 1| = 1 。
- 单元格 (1,1) 的右下对角线包含 [1] ，而左上对角线包含 [1] 。对应答案是 |1 - 1| = 0 。
其他单元格的对应答案也可以按照这样的流程进行计算。

示例 2：

输入：grid = [[1]]
输出：[[0]]
解释：- 单元格 (0,0) 的右下对角线包含 [] ，左上对角线包含 [] 。对应答案是 |0 - 0| = 0 。

说明：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n, grid[i][j] <= 50

思路

计算矩阵元素左上对角线的不同元素个数与右下对角线的不同元素个数的差的绝对值。即将元素所在的左上右下对角线，以当前元素为分界点（不包括当前元素），分成左上与右下两部分，计算每部分不同元素的个数，取差的绝对值。

暴力解法是枚举每个格子的左上右下元素，每一对角线都要遍历它所包含的元素个数次。

可以直接按对角线遍历，先记录前缀中的不同元素个数，然后再倒着遍历，计算差值的绝对值。

网友提到由于元素值不大，可以将其保存到 long 型数字中。

代码


/**
 * @date 2025-03-25 0:12
 */
public class DifferenceOfDistinctValues2711 {

    public int[][] differenceOfDistinctValues(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] res = new int[m][n];
        for (int i = 0; i < m + n - 1; i++) {
            int row = i / n < 1 ? 0 : i - n + 1 % m;
            int col = row > 0 ? 0 : n - 1 - i;
            Set<Integer> set = new HashSet<>();
            while (row < m && col < n){
                res[row][col] = set.size();
                set.add(grid[row][col]);
                row++;
                col++;
            }
            row--;
            col--;
            set.clear();
            while (row >= 0 && col >= 0){
                res[row][col] = Math.abs(res[row][col] - set.size());
                set.add(grid[row][col]);
                row--;
                col--;
            }
        }
        return res;
    }

}

性能

2680.最大或值

目标

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 k 。每一次操作中，你可以选择一个数并将它乘 2 。

你最多可以进行 k 次操作，请你返回 nums[0] | nums[1] | ... | nums[n - 1] 的最大值。

a | b 表示两个整数 a 和 b 的 按位或 运算。

示例 1：

输入：nums = [12,9], k = 1
输出：30
解释：如果我们对下标为 1 的元素进行操作，新的数组为 [12,18] 。此时得到最优答案为 12 和 18 的按位或运算的结果，也就是 30 。

示例 2：

输入：nums = [8,1,2], k = 2
输出：35
解释：如果我们对下标 0 处的元素进行操作，得到新数组 [32,1,2] 。此时得到最优答案为 32|1|2 = 35 。

说明：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= 15

思路

有一个整数数组 nums，最多可以对它执行 k 次操作，每次操作可以任选一个数将其左移 1 位。求操作后数组所有元素的最大或值。

操作集中到同一个数上可以将最高有效位移到最高，少一次操作最高位就低一位。问题的关键在于，如果所有数字都有相同的最高有效位，移哪个是不确定的。

这时就需要枚举操作数了，每选择一个操作数就需要重新计算其余元素的或值。由于或运算没有逆运算，我们无法撤销已经或进去的值。

直接的想法是计算或前缀、后缀，枚举所有元素，将其左移 k 次，然后与前后缀进行或运算，取最大值。

网友提供了另一种基于位运算的解法，计算全体元素的或值，同时计算所有 bit 位上存在重复 1 的位置，通过异或运算将当前元素对或值的贡献抵消，然后补上重复位置上的 1。

代码


/**
 * @date 2025-03-21 0:08
 */
public class MaximumOr2680 {

    public long maximumOr_v1(int[] nums, int k) {
        int n = nums.length;
        int or = 0;
        int multiBits = 0;
        for (int i = 0; i < n; i++) {
            multiBits = multiBits | or & nums[i];
            or = or | nums[i];
        }
        long res = 0L;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, or ^ nums[i] | multiBits | ((long) nums[i] << k));
        }
        return res;
    }

    public long maximumOr(int[] nums, int k) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
        int[] suffix = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] | nums[i - 1];
            suffix[n - i] = suffix[n - i + 1] | nums[n - i];
        }
        long res = 0L;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, prefix[i] | suffix[i + 1] | ((long) nums[i] << k));
        }
        return res;
    }

}

性能