位运算 – shelterofly

1018.可被5整除的二进制前缀

目标

给定一个二进制数组 nums ( 索引从0开始 )。

我们将 xi 定义为其二进制表示形式为子数组 nums[0..i] (从最高有效位到最低有效位)。

例如，如果 nums =[1,0,1] ，那么 x0 = 1, x1 = 2, 和 x2 = 5。

返回布尔值列表 answer，只有当 xi 可以被 5 整除时，答案 answer[i] 为 true，否则为 false。

示例 1：

输入：nums = [0,1,1]
输出：[true,false,false]
解释：
输入数字为 0, 01, 011；也就是十进制中的 0, 1, 3 。只有第一个数可以被 5 整除，因此 answer[0] 为 true 。

示例 2：

输入：nums = [1,1,1]
输出：[false,false,false]

说明：

1 <= nums.length <= 10^5
nums[i] 仅为 0 或 1

思路

有一个二进制数组 nums，定义 xi 为二进制表示为子数组 [0, i] 的数字，判断 x0 ~ x_(n-1) 能否被 5 整除。

模拟存在的问题是左移多次会溢出。假设 num = k * 5 + mod，左移 1 位相当于乘以 2，2 * num = k * 10 + 2 * mod，能否被 5 整除只需考虑 2 * mod | nums[i]。

代码


/**
 * @date 2025-11-24 8:52
 */
public class PrefixesDivBy5_1018 {

    public List<Boolean> prefixesDivBy5_v1(int[] nums) {
        List<Boolean> res = new ArrayList<>();
        int mod = 0;
        for (int num : nums) {
            mod = (mod << 1) % 5 + num;
            res.add(mod % 5 == 0);
        }
        return res;
    }

}

性能

1930.长度为3的不同回文子序列

目标

给你一个字符串 s ，返回 s 中长度为 3 的不同回文子序列的个数。

即便存在多种方法来构建相同的子序列，但相同的子序列只计数一次。

回文是正着读和反着读一样的字符串。

子序列是由原字符串删除其中部分字符（也可以不删除）且不改变剩余字符之间相对顺序形成的一个新字符串。

例如，"ace" 是 "abcde" 的一个子序列。

示例 1：

输入：s = "aabca"
输出：3
解释：长度为 3 的 3 个回文子序列分别是：
- "aba" ("aabca" 的子序列)
- "aaa" ("aabca" 的子序列)
- "aca" ("aabca" 的子序列)

示例 2：

输入：s = "adc"
输出：0
解释："adc" 不存在长度为 3 的回文子序列。

示例 3：

输入：s = "bbcbaba"
输出：4
解释：长度为 3 的 4 个回文子序列分别是：
- "bbb" ("bbcbaba" 的子序列)
- "bcb" ("bbcbaba" 的子序列)
- "bab" ("bbcbaba" 的子序列)
- "aba" ("bbcbaba" 的子序列)

说明：

3 <= s.length <= 10^5
s 仅由小写英文字母组成

思路

求长度为 3 的不同回文子序列个数。

枚举中间元素，同时枚举 a - z 作为左右两侧的字母，判断是否前后都存在。

对字母计数，在枚举过程中记录前面出现字母的次数，结合总次数可以快速判断后面是否存在相同的字母。注意，如果前面出现的字母与枚举的中间字母相同需要将次数减 1。

代码


/**
 * @date 2025-11-21 8:44
 */
public class CountPalindromicSubsequence1930 {

    public int countPalindromicSubsequence_v1(String s) {
        int[] total = new int[26];
        char[] chars = s.toCharArray();
        for (char c : chars) {
            total[c - 'a']++;
        }
        boolean[][] visited = new boolean[26][26];
        int[] prefix = new int[26];
        int res = 0;
        for (char c : chars) {
            prefix[c - 'a']++;
            for (int j = 0; j < 26; j++) {
                if (!visited[j][c - 'a'] && total[j] > prefix[j] && ((j == c - 'a' && prefix[j] > 1) || j != c - 'a' && prefix[j] > 0)) {
                    visited[j][c - 'a'] = true;
                    res++;
                }
            }
        }
        return res;
    }

}

性能

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();
    }
}

2025 年 12 月
一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31