LeetCode Go · 位运算（2）

返回题库与筛选 · 收录范围与使用说明

来源与许可

题目版权归 LeetCode；题解来自 Doocs/leetcode，按 CC BY-SA 4.0 共享。补充 Go 代码来自灵茶山艾府、halfrost，保留 MIT 许可及逐题署名。本站提取 Go、调整分类及折叠排版；标注“本站整理”的 Go 解法依据题意与参考思路补写，按 CC BY-SA 4.0 共享。收录日期：2026-10-31；主题源版本：91ef8c241a5e。

本卷 30 题 · 点击题目展开，先独立思考，再查看解法。

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

简单1 种解法

标签：位运算、数组

题目、示例与约束

给定一个二进制数组 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 <= 105 
• nums[i] 仅为 0 或 1

方法一：模拟 · Go 实现

思考

每个前缀对应的整数可直接算出再判断能否被 $5$ 整除，但 $n\le {10}^5$ 时数值高达 $2^{{10}^5}$，不能真的保存。可整除性只需要模 $5$。

新前缀等于旧值左移一位再或上当前位，即 $x\leftarrow (2x+v)mod5$。

按此递推每个前缀的余数，余数为 $0$ 则该前缀合法。

我们用一个变量 $x$ 来表示当前的二进制前缀，然后遍历数组 $nums$，对于每个元素 $v$，我们将 $x$ 左移一位，然后加上 $v$，再对 $5$ 取模，判断是否等于 $0$，如果等于 $0$，则说明当前的二进制前缀可以被 $5$ 整除，我们将 $\mathit{\text{true}}$ 加入答案数组，否则将 $\mathit{\text{false}}$ 加入答案数组。

时间复杂度 $O(n)$，忽略答案数组的空间消耗，空间复杂度 $O(1)$。

func prefixesDivBy5(nums []int) (ans []bool) {
	x := 0
	for _, v := range nums {
		x = (x<<1 | v) % 5
		ans = append(ans, x == 0)
	}
	return
}

力扣原题 · Doocs 题解来源

1177. 构建回文串检测

中等1 种解法

标签：位运算、数组、哈希表、字符串、前缀和

题目、示例与约束

给你一个字符串 s，请你对 s 的子串进行检测。

每次检测，待检子串都可以表示为 queries[i] = [left, right, k]。我们可以 重新排列 子串 s[left], ..., s[right]，并从中选择 最多 k 项替换成任何小写英文字母。 

如果在上述检测过程中，子串可以变成回文形式的字符串，那么检测结果为 true，否则结果为 false。

返回答案数组 answer[]，其中 answer[i] 是第 i 个待检子串 queries[i] 的检测结果。

注意：在替换时，子串中的每个字母都必须作为 独立的 项进行计数，也就是说，如果 s[left..right] = "aaa" 且 k = 2，我们只能替换其中的两个字母。（另外，任何检测都不会修改原始字符串 s，可以认为每次检测都是独立的）

 

示例：

输入：s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
输出：[true,false,false,true,true]
解释：
queries[0] : 子串 = "d"，回文。
queries[1] : 子串 = "bc"，不是回文。
queries[2] : 子串 = "abcd"，只替换 1 个字符是变不成回文串的。
queries[3] : 子串 = "abcd"，可以变成回文的 "abba"。 也可以变成 "baab"，先重新排序变成 "bacd"，然后把 "cd" 替换为 "ab"。
queries[4] : 子串 = "abcda"，可以变成回文的 "abcba"。

 

提示：

• 1 <= s.length, queries.length <= 10^5
• 0 <= queries[i][0] <= queries[i][1] < s.length
• 0 <= queries[i][2] <= s.length
• s 中只有小写英文字母

方法一：前缀和 · Go 实现

思考

子串经至多 $k$ 次替换成回文，本质是奇数次字符的个数：每次替换可消掉两个奇数（或把一个奇数改成另一个）。查询多，不宜每次重扫子串。 $26$ 维前缀计数给出区间奇偶，奇数个数的一半与 $k$ 比较即可。

我们先考虑一个子串能否在经过最多 $k$ 次替换后变成回文串，显然，我们需要统计子串中每个字符出现的次数，这可以通过前缀和来实现。对于出现偶数次的字符，我们不需要进行替换，对于出现奇数次的字符，我们需要进行替换，替换的次数为 $\lfloor \frac{x}{2}\rfloor$，其中 $x$ 为出现奇数次的字符的个数。如果 $\lfloor \frac{x}{2}\rfloor \le k$，那么这个子串就可以变成回文串。

因此，我们定义一个前缀和数组 $ss$，其中 $ss[i][j]$ 表示字符串 $s$ 的前 $i$ 个字符中，字符 $j$ 出现的次数。那么对于一个子串 $s[l..r]$，我们可以通过 $ss[r+1][j]-ss[l][j]$ 得到子串中字符 $j$ 出现的次数。我们遍历所有的查询，对于每个查询 $[l,r,k]$，我们统计子串 $s[l..r]$ 中出现奇数次的字符的个数 $x$，如果 $\lfloor \frac{x}{2}\rfloor \le k$，那么这个子串就可以变成回文串。

时间复杂度 $O((n+m)\times C)$，空间复杂度 $O(n\times C)$，其中 $n$ 和 $m$ 分别为字符串 $s$ 和查询数组的长度；而 $C$ 为字符集的大小，本题中字符集为小写英文字母，因此 $C=26$。

func canMakePaliQueries(s string, queries [][]int) (ans []bool) {
	n := len(s)
	ss := make([][26]int, n+1)
	for i := 1; i <= n; i++ {
		for j := 0; j < 26; j++ {
			ss[i][j] = ss[i-1][j]
		}
		ss[i][s[i-1]-'a']++
	}
	for _, q := range queries {
		l, r, k := q[0], q[1], q[2]
		x := 0
		for j := 0; j < 26; j++ {
			x += (ss[r+1][j] - ss[l][j]) & 1
		}
		ans = append(ans, x/2 <= k)
	}
	return
}

力扣原题 · Doocs 题解来源

1256. 加密数字 🔒

中等1 种解法

标签：位运算、数学、字符串

题目、示例与约束

给你一个非负整数 num ，返回它的「加密字符串」。

加密的过程是把一个整数用某个未知函数进行转化，你需要从下表推测出该转化函数：

 

示例 1：

输入：num = 23
输出："1000"

示例 2：

输入：num = 107
输出："101100"

 

提示：

• 0 <= num <= 10^9

方法一：位运算 · Go 实现

思考

编码表按 $0,1,00,01,\dots$ 排列，即所有二进制串的字典序。 $num+1$ 的二进制去掉最高位的 $1$，剩下的恰是第 $num$ 个这样的串。 $num$ 达 ${10}^9$，不能列表，位运算一次完成。

我们将 $num$ 加一，然后将其转换为二进制字符串，去掉最高位的 $1$ 即可。

时间复杂度 $O(\log n)$，空间复杂度 $O(\log n)$。其中 $n$ 为 $num$ 的大小。

func encode(num int) string {
	num++
	s := strconv.FormatInt(int64(num), 2)
	return s[1:]
}

力扣原题 · Doocs 题解来源

1310. 子数组异或查询

中等1 种解法

标签：位运算、数组、前缀和

题目、示例与约束

有一个正整数数组 arr，现给你一个对应的查询数组 queries，其中 queries[i] = [Li, Ri]。

对于每个查询 i，请你计算从 Li 到 Ri 的 XOR 值（即 arr[Li] xor arr[Li+1] xor ... xor arr[Ri]）作为本次查询的结果。

并返回一个包含给定查询 queries 所有结果的数组。

 

示例 1：

输入：arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
输出：[2,7,14,8] 
解释：
数组中元素的二进制表示形式是：
1 = 0001 
3 = 0011 
4 = 0100 
8 = 1000 
查询的 XOR 值为：
[0,1] = 1 xor 3 = 2 
[1,2] = 3 xor 4 = 7 
[0,3] = 1 xor 3 xor 4 xor 8 = 14 
[3,3] = 8

示例 2：

输入：arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
输出：[8,0,4,4]

 

提示：

• 1 <= arr.length <= 3 * 10^4
• 1 <= arr[i] <= 10^9
• 1 <= queries.length <= 3 * 10^4
• queries[i].length == 2
• 0 <= queries[i][0] <= queries[i][1] < arr.length

方法一：前缀异或 · Go 实现

思考

每次询问一段异或。若现场从 $l$ 异或到 $r$，在询问数较多时为平方级。异或满足 $x\oplus x=0$，故前缀异或 $s[i]=\mathit{\text{arr}}[0]\oplus \cdots \oplus \mathit{\text{arr}}[i-1]$ 之后，区间 $[l,r]$ 等于 $s[r+1]\oplus s[l]$。先线性建前缀，再对每个询问 $O(1)$ 作答。

我们可以用一个长度为 $n+1$ 的前缀异或数组 $s$ 来存储数组 $\mathit{\text{arr}}$ 的前缀异或结果，其中 $s[i]=s[i-1]\oplus \mathit{\text{arr}}[i-1]$，即 $s[i]$ 表示 $\mathit{\text{arr}}$ 的前 $i$ 个元素的异或结果。

那么对于一个查询 $[l,r]$，我们可以得到：

$$\begin{array}{rl}\mathit{\text{arr}}[l]\oplus \mathit{\text{arr}}[l+1]\oplus \cdots \oplus \mathit{\text{arr}}[r]& =(\mathit{\text{arr}}[0]\oplus \mathit{\text{arr}}[1]\oplus \cdots \oplus \mathit{\text{arr}}[l-1])\oplus (\mathit{\text{arr}}[0]\oplus \mathit{\text{arr}}[1]\oplus \cdots \oplus \mathit{\text{arr}}[r])\\ & =s[l]\oplus s[r+1]\end{array}$$

时间复杂度 $O(n+m)$，空间复杂度 $O(n)$。其中 $n$ 和 $m$ 分别是数组 $\mathit{\text{arr}}$ 的长度和查询数组 $\mathit{\text{queries}}$ 的长度。

func xorQueries(arr []int, queries [][]int) (ans []int) {
	n := len(arr)
	s := make([]int, n+1)
	for i, x := range arr {
		s[i+1] = s[i] ^ x
	}
	for _, q := range queries {
		l, r := q[0], q[1]
		ans = append(ans, s[r+1]^s[l])
	}
	return
}

力扣原题 · Doocs 题解来源

1318. 或运算的最小翻转次数

中等1 种解法

标签：位运算

题目、示例与约束

给你三个正整数 a、b 和 c。

你可以对 a 和 b 的二进制表示进行位翻转操作，返回能够使按位或运算   a OR b == c  成立的最小翻转次数。

「位翻转操作」是指将一个数的二进制表示任何单个位上的 1 变成 0 或者 0 变成 1 。

 

示例 1：

输入：a = 2, b = 6, c = 5
输出：3
解释：翻转后 a = 1 , b = 4 , c = 5 使得 a OR b == c

示例 2：

输入：a = 4, b = 2, c = 7
输出：1

示例 3：

输入：a = 1, b = 2, c = 3
输出：0

 

提示：

• 1 <= a <= 10^9
• 1 <= b <= 10^9
• 1 <= c <= 10^9

方法一：位运算 · Go 实现

思考

按位或等于 $c$ 的最少翻转。位与位独立，不必枚举整数。对每一位：若 $c$ 该位为 $0$，则 $a$、 $b$ 中每一个 $1$ 都要翻掉；若为 $1$，则仅当 $a$、 $b$ 该位都为 $0$ 时需要翻一次。累加 $32$ 位即可。

我们可以枚举 $a$, $b$, $c$ 的二进制表示的每一位，分别记为 $x$, $y$, $z$。如果 $x$ 和 $y$ 的按位或运算结果与 $z$ 不同，此时我们判断 $x$ 和 $y$ 是否都是 $1$，如果是，则需要翻转两次，否则只需要翻转一次。我们将所有需要翻转的次数累加即可。

时间复杂度 $O(\log M)$，其中 $M$ 是题目中数字的最大值。空间复杂度 $O(1)$。

func minFlips(a int, b int, c int) (ans int) {
	for i := 0; i < 32; i++ {
		x, y, z := a>>i&1, b>>i&1, c>>i&1
		if z == 0 {
			ans += x + y
		} else if x == 0 && y == 0 {
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1342. 将数字变成 0 的操作次数

简单2 种解法

标签：位运算、数学

题目、示例与约束

给你一个非负整数 num ，请你返回将它变成 0 所需要的步数。 如果当前数字是偶数，你需要把它除以 2 ；否则，减去 1 。

 

示例 1：

输入：num = 14
输出：6
解释：
步骤 1) 14 是偶数，除以 2 得到 7 。
步骤 2） 7 是奇数，减 1 得到 6 。
步骤 3） 6 是偶数，除以 2 得到 3 。
步骤 4） 3 是奇数，减 1 得到 2 。
步骤 5） 2 是偶数，除以 2 得到 1 。
步骤 6） 1 是奇数，减 1 得到 0 。

示例 2：

输入：num = 8
输出：4
解释：
步骤 1） 8 是偶数，除以 2 得到 4 。
步骤 2） 4 是偶数，除以 2 得到 2 。
步骤 3） 2 是偶数，除以 2 得到 1 。
步骤 4） 1 是奇数，减 1 得到 0 。

示例 3：

输入：num = 123
输出：12

 

提示：

• 0 <= num <= 10^6

方法一 · Go 实现

思考

偶数除以 $2$，奇数减 $1$，问到 $0$ 的步数。 $\mathit{\text{num}}\le {10}^6$，直接模拟即可：奇数则减一，否则右移，计数直到变为 $0$。

func numberOfSteps(num int) int {
	ans := 0
	for num != 0 {
		if (num & 1) == 1 {
			num--
		} else {
			num >>= 1
		}
		ans++
	}
	return ans
}

方法二 · Go 实现

思考

同一规则也可写成递归：偶数递归 $n/2$，奇数递归 $n-1$，每层加一； $n=0$ 停止。语义与循环一致，只是用调用栈表达过程。

func numberOfSteps(num int) int {
	if num == 0 {
		return 0
	}
	if (num & 1) == 0 {
		return 1 + numberOfSteps(num>>1)
	}
	return 1 + numberOfSteps(num-1)
}

力扣原题 · Doocs 题解来源

1356. 根据数字二进制下 1 的数目排序

简单1 种解法

标签：位运算、数组、计数、排序

题目、示例与约束

给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。

如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。

请你返回排序后的数组。

 

示例 1：

输入：arr = [0,1,2,3,4,5,6,7,8]
输出：[0,1,2,4,8,3,5,6,7]
解释：[0] 是唯一一个有 0 个 1 的数。
[1,2,4,8] 都有 1 个 1 。
[3,5,6] 有 2 个 1 。
[7] 有 3 个 1 。
按照 1 的个数排序得到的结果数组为 [0,1,2,4,8,3,5,6,7]

示例 2：

输入：arr = [1024,512,256,128,64,32,16,8,4,2,1]
输出：[1,2,4,8,16,32,64,128,256,512,1024]
解释：数组中所有整数二进制下都只有 1 个 1 ，所以你需要按照数值大小将它们排序。

示例 3：

输入：arr = [10000,10000]
输出：[10000,10000]

示例 4：

输入：arr = [2,3,5,7,11,13,17,19]
输出：[2,3,5,17,7,11,13,19]

示例 5：

输入：arr = [10,100,1000,10000]
输出：[10,100,10000,1000]

 

提示：

• 1 <= arr.length <= 500
• 0 <= arr[i] <= 10^4

方法一：自定义排序 · Go 实现

思考

先按二进制中 $1$ 的个数升序，个数相同再按数值升序。自定义排序键 $(x.\mathrm{bit}\mathrm{\_}\mathrm{count}(),x)$ 一次比较即可同时满足两级次序。

我们将数组 $arr$ 按照题目要求排序，即按照二进制表示中数字 $1$ 的数目升序排序，如果存在多个数字二进制中 $1$ 的数目相同，则必须将它们按照数值大小升序排列。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $arr$ 的长度。

func sortByBits(arr []int) []int {
	for i, v := range arr {
		arr[i] += bits.OnesCount(uint(v)) * 100000
	}
	sort.Ints(arr)
	for i := range arr {
		arr[i] %= 100000
	}
	return arr
}

力扣原题 · Doocs 题解来源

1371. 每个元音包含偶数次的最长子字符串

中等1 种解法

标签：位运算、哈希表、字符串、前缀和

题目、示例与约束

给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 'a'，'e'，'i'，'o'，'u' ，在子字符串中都恰好出现了偶数次。

 

示例 1：

输入：s = "eleetminicoworoep"
输出：13
解释：最长子字符串是 "leetminicowor" ，它包含 e，i，o 各 2 个，以及 0 个 a，u 。

示例 2：

输入：s = "leetcodeisgreat"
输出：5
解释：最长子字符串是 "leetc" ，其中包含 2 个 e 。

示例 3：

输入：s = "bcbcbc"
输出：6
解释：这个示例中，字符串 "bcbcbc" 本身就是最长的，因为所有的元音 a，e，i，o，u 都出现了 0 次。

 

提示：

• 1 <= s.length <= 5 x 10^5
• s 只包含小写英文字母。

方法一：前缀异或 + 数组或哈希表 · Go 实现

思考

最长子串使五个元音各出现偶数次。 $n\le 5\times {10}^5$，不能枚举两端。偶数次等价于两端前缀的奇偶状态相同。用五位掩码表示当前前缀各元音奇偶，记下每种掩码首次出现的位置，再次出现时用 $i-j$ 更新最长长度。

根据题目描述，如果我们用一个数字表示字符串 $\mathit{\text{s}}$ 的某个前缀中每个元音字母出现的次数的奇偶性，那么当两个前缀的这个数字相同时，这两个前缀的交集就是一个符合条件的子字符串。

我们可以用一个二进制数的低五位分别表示五个元音字母的奇偶性，其中第 $i$ 位为 $1$ 表示该元音字母在子字符串中出现了奇数次，为 $0$ 表示该元音字母在子字符串中出现了偶数次。

我们用 $\mathit{\text{mask}}$ 表示这个二进制数，用一个数组或哈希表 $\mathit{\text{d}}$ 记录每个 $\mathit{\text{mask}}$ 第一次出现的位置。初始时，我们将 $\mathit{\text{d}}[0]=-1$，表示空字符串的开始位置为 $-1$。

遍历字符串 $\mathit{\text{s}}$，如果遇到元音字母，就将 $\mathit{\text{mask}}$ 的对应位取反。接下来，我们判断 $\mathit{\text{mask}}$ 是否在之前出现过，如果出现过，那么我们就找到了一个符合条件的子字符串，其长度为当前位置减去 $\mathit{\text{mask}}$ 上一次出现的位置。否则，我们将 $\mathit{\text{mask}}$ 的当前位置存入 $\mathit{\text{d}}$。

遍历结束后，我们就找到了最长的符合条件的子字符串。

时间复杂度 $O(n)$，其中 $n$ 为字符串 $\mathit{\text{s}}$ 的长度。空间复杂度 $O(1)$。

func findTheLongestSubstring(s string) (ans int) {
    vowels := "aeiou"
    d := [32]int{}
    for i := range d {
        d[i] = 1 << 29
    }
    d[0] = 0
    mask := 0
    for i := 1; i <= len(s); i++ {
        c := s[i-1]
        for j := 0; j < 5; j++ {
            if c == vowels[j] {
                mask ^= 1 << j
                break
            }
        }
        ans = max(ans, i-d[mask])
        d[mask] = min(d[mask], i)
    }
    return
}

力扣原题 · Doocs 题解来源

1404. 将二进制表示减到 1 的步骤数

中等1 种解法

标签：位运算、字符串、模拟

题目、示例与约束

给你一个以二进制形式表示的数字 s 。请你返回按下述规则将其减少到 1 所需要的步骤数：

• 如果当前数字为偶数，则将其除以 2 。

• 如果当前数字为奇数，则将其加上 1 。

题目保证你总是可以按上述规则将测试用例变为 1 。

 

示例 1：

输入：s = "1101"
输出：6
解释："1101" 表示十进制数 13 。
Step 1) 13 是奇数，加 1 得到 14 
Step 2) 14 是偶数，除 2 得到 7
Step 3) 7  是奇数，加 1 得到 8
Step 4) 8  是偶数，除 2 得到 4  
Step 5) 4  是偶数，除 2 得到 2 
Step 6) 2  是偶数，除 2 得到 1  

示例 2：

输入：s = "10"
输出：1
解释："10" 表示十进制数 2 。
Step 1) 2 是偶数，除 2 得到 1 

示例 3：

输入：s = "1"
输出：0

 

提示：

• 1 <= s.length <= 500
• s 由字符 '0' 或 '1' 组成。
• s[0] == '1'

方法一：模拟 · Go 实现

思考

按题意反复对整数做「奇数加一、偶数右移」， $s$ 最长 $500$，若每次在二进制串上做加法并处理进位，最坏每次加一可能扫过整串。

从最低位向前看：当前位为 $0$ 时只需一次右移；为 $1$ 时先加一变成偶数再右移，加一产生的进位会向高位传播。因此不必改写字符串，用布尔 $\mathit{\text{carry}}$ 记录尚未消化的加一即可。

自右向左扫描 $s[1:]$（最高位单独处理），遇 $1$ 则步数加二并置位进位，遇 $0$ 则步数加一。扫描结束后若进位仍在，最高位还需再计一步。

我们模拟操作 $1$ 和 $2$，同时维护一个进位 $\mathit{\text{carry}}$ 来表示当前是否有进位，初始时 $\mathit{\text{carry}}=\text{false}$。

我们从字符串 $s$ 的末尾开始向前遍历：

• 如果 $\mathit{\text{carry}}$ 为 $\text{true}$，则当前位 $c$ 需要加 $1$，如果 $c$ 是 $0$，则加 $1$ 后变为 $1$，同时 $\mathit{\text{carry}}$ 变为 $\text{false}$；如果 $c$ 是 $1$，则加 $1$ 后变为 $0$，同时 $\mathit{\text{carry}}$ 保持为 $\text{true}$。
• 如果 $c$ 是 $1$，则需要执行操作 $1$，即加 $1$，同时 $\mathit{\text{carry}}$ 变为 $\text{true}$。
• 此时 $c$ 是 $0$，则需要执行操作 $2$，即除以 $2$。

当遍历结束后，如果 $\mathit{\text{carry}}$ 仍然为 $\text{true}$，则需要再执行一次操作 $1$。

时间复杂度 $O(n)$，其中 $n$ 是字符串 $s$ 的长度。空间复杂度 $O(1)$。

func numSteps(s string) int {
	ans := 0
	carry := false
	for i := len(s) - 1; i > 0; i-- {
		c := s[i]
		if carry {
			if c == '0' {
				c = '1'
				carry = false
			} else {
				c = '0'
			}
		}
		if c == '1' {
			ans++
			carry = true
		}
		ans++
	}
	if carry {
		ans++
	}
	return ans
}

力扣原题 · Doocs 题解来源

1442. 形成两个异或相等数组的三元组数目

中等1 种解法

标签：位运算、数组、哈希表、数学、前缀和

题目、示例与约束

给你一个整数数组 arr 。

现需要从数组中取三个下标 i、j 和 k ，其中 (0 <= i < j <= k < arr.length) 。

a 和 b 定义如下：

• a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
• b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]

注意：^ 表示 按位异或 操作。

请返回能够令 a == b 成立的三元组 (i, j , k) 的数目。

 

示例 1：

输入：arr = [2,3,1,6,7]
输出：4
解释：满足题意的三元组分别是 (0,1,2), (0,2,2), (2,3,4) 以及 (2,4,4)

示例 2：

输入：arr = [1,1,1,1,1]
输出：10

示例 3：

输入：arr = [2,3]
输出：0

示例 4：

输入：arr = [1,3,5,7,9]
输出：3

示例 5：

输入：arr = [7,11,12,9,5,2,7,17,22]
输出：8

 

提示：

• 1 <= arr.length <= 300
• 1 <= arr[i] <= 10^8

方法一：枚举 · Go 实现

思考

$a=b$ 等价于区间 $[i,k]$ 的异或为 $0$，此时 $j$ 可在 $(i,k]$ 中任取，共 $k-i$ 种。 $n\le 300$，枚举左端 $i$ 与右端 $k$ 并维护异或前缀即可。

根据题目描述，要找到满足 $a=b$ 的三元组 $(i,j,k)$，即满足 $s=a\oplus b=0$，我们只需要枚举左端点 $i$，然后计算以 $k$ 为右端点的区间 $[i,k]$ 的前缀异或和 $s$，如果 $s=0$，那么对于任意 $j\in [i+1,k]$，都满足 $a=b$，即 $(i,j,k)$ 是一个满足条件的三元组，一共有 $k-i$ 个，我们将其累加到答案中即可。

枚举结束后，返回答案即可。

时间复杂度 $O(n^2)$，其中 $n$ 是数组 $\mathit{\text{arr}}$ 的长度。空间复杂度 $O(1)$。

func countTriplets(arr []int) (ans int) {
	for i, x := range arr {
		s := x
		for k := i + 1; k < len(arr); k++ {
			s ^= arr[k]
			if s == 0 {
				ans += k - i
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1461. 检查一个字符串是否包含所有长度为 K 的二进制子串

中等2 种解法

标签：位运算、哈希表、字符串、有向无环图、哈希函数、滚动哈希

题目、示例与约束

给你一个二进制字符串 s 和一个整数 k 。如果所有长度为 k 的二进制字符串都是 s 的子串，请返回 true ，否则请返回 false 。

 

示例 1：

输入：s = "00110110", k = 2
输出：true
解释：长度为 2 的二进制串包括 "00"，"01"，"10" 和 "11"。它们分别是 s 中下标为 0，1，3，2 开始的长度为 2 的子串。

示例 2：

输入：s = "0110", k = 1
输出：true
解释：长度为 1 的二进制串包括 "0" 和 "1"，显然它们都是 s 的子串。

示例 3：

输入：s = "0110", k = 2
输出：false
解释：长度为 2 的二进制串 "00" 没有出现在 s 中。

 

提示：

• 1 <= s.length <= 5 * 105
• s[i] 不是'0' 就是 '1'
• 1 <= k <= 20

方法一：哈希表 · Go 实现

思考

长度为 $k$ 的二进制串共 $2^k$ 种， $k\le 20$。若 $s$ 的 $k$ 子串个数不足 $2^k$，直接失败；否则把所有子串放入集合，看是否凑满。

首先，对于一个长度为 $n$ 的字符串 $s$，长度为 $k$ 的子串的个数为 $n-k+1$，如果 $n-k+1<2^k$，则一定存在长度为 $k$ 的二进制串不是 $s$ 的子串，返回 false。

接下来，我们遍历字符串 $s$，将所有长度为 $k$ 的子串存入集合 $ss$，最后判断集合 $ss$ 的大小是否等于 $2^k$。

时间复杂度 $O(n\times k)$，空间复杂度 $O(n)$。其中 $n$ 是字符串 $s$ 的长度。

func hasAllCodes(s string, k int) bool {
	n, m := len(s), 1<<k
	if n-k+1 < m {
		return false
	}
	ss := map[string]bool{}
	for i := 0; i+k <= n; i++ {
		ss[s[i:i+k]] = true
	}
	return len(ss) == m
}

方法二：滑动窗口 · Go 实现

思考

方法一每个窗口复制 $k$ 个字符。把窗口看成整数，滑入新位、滑出最高位，插入集合的代价降为 $O(1)$。

方法一中，我们存储了所有长度为 $k$ 的不同子串，子串的处理需要 $O(k)$ 的时间，我们可以改用滑动窗口，每次添加最新字符时，删除窗口最左边的字符。此过程中用一个整型数字 $x$ 来存放子串。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是字符串 $s$ 的长度。

func hasAllCodes(s string, k int) bool {
	n, m := len(s), 1<<k
	if n-k+1 < m {
		return false
	}
	ss := make([]bool, m)
	x, _ := strconv.ParseInt(s[:k], 2, 64)
	ss[x] = true
	for i := k; i < n; i++ {
		a := int64(s[i-k]-'0') << (k - 1)
		b := int64(s[i] - '0')
		x = (x-a)<<1 | b
		ss[x] = true
	}
	for _, v := range ss {
		if !v {
			return false
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

1486. 数组异或操作

简单1 种解法

标签：位运算、数学

题目、示例与约束

给你两个整数，n 和 start 。

数组 nums 定义为：nums[i] = start + 2*i（下标从 0 开始）且 n == nums.length 。

请返回 nums 中所有元素按位异或（XOR）后得到的结果。

 

示例 1：

输入：n = 5, start = 0
输出：8
解释：数组 nums 为 [0, 2, 4, 6, 8]，其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 。
     "^" 为按位异或 XOR 运算符。

示例 2：

输入：n = 4, start = 3
输出：8
解释：数组 nums 为 [3, 5, 7, 9]，其中 (3 ^ 5 ^ 7 ^ 9) = 8.

示例 3：

输入：n = 1, start = 7
输出：7

示例 4：

输入：n = 10, start = 5
输出：2

 

提示：

• 1 <= n <= 1000
• 0 <= start <= 1000
• n == nums.length

方法一：模拟 · Go 实现

思考

$n\le 1000$，按下标生成 $start+2i$ 并依次异或即可。

我们可以直接模拟算出数组中所有元素的异或结果。

时间复杂度 $O(n)$，其中 $n$ 为数组长度。空间复杂度 $O(1)$。

func xorOperation(n int, start int) (ans int) {
	for i := 0; i < n; i++ {
		ans ^= start + 2*i
	}
	return
}

力扣原题 · Doocs 题解来源

1542. 找出最长的超赞子字符串

困难1 种解法

标签：位运算、哈希表、字符串

题目、示例与约束

给你一个字符串 s 。请返回 s 中最长的 超赞子字符串 的长度。

「超赞子字符串」需满足满足下述两个条件：

• 该字符串是 s 的一个非空子字符串
• 进行任意次数的字符交换后，该字符串可以变成一个回文字符串

 

示例 1：

输入：s = "3242415"
输出：5
解释："24241" 是最长的超赞子字符串，交换其中的字符后，可以得到回文 "24142"

示例 2：

输入：s = "12345678"
输出：1

示例 3：

输入：s = "213123"
输出：6
解释："213123" 是最长的超赞子字符串，交换其中的字符后，可以得到回文 "231132"

示例 4：

输入：s = "00"
输出：2

 

提示：

• 1 <= s.length <= 10^5
• s 仅由数字组成

方法一：状态压缩 + 前缀和思想 · Go 实现

思考

超赞子串重排后能成回文，即最多一个数字出现奇数次。 $n\le {10}^5$，不能枚举子串再统计。数字只有 $0$– $9$，奇偶可用 $10$ 位掩码表示。

前缀掩码 $st$ 记录每种数字的奇偶。子串 $s[j+1..i]$ 合法，当且仅当 $s{t}_i$ 与 $s{t}_j$ 至多一位不同。哈希表记下每种掩码首次出现的位置：相等掩码给出全偶数段，翻转一位后命中则给出恰一个奇数。取最长即可。

根据题目描述，“超赞子字符串”中的字符可以通过交换得到回文字符串，因此，“超赞子字符串”中最多有一个数字字符出现奇数次，其余数字字符出现偶数次。

我们可以用一个整数 $st$ 来表示当前前缀字符串中数字字符出现的奇偶性，其中 $st$ 的第 $i$ 位表示数字字符 $i$ 出现的奇偶性，即 $st$ 的第 $i$ 位为 $1$ 表示数字字符 $i$ 出现奇数次，为 $0$ 表示数字字符 $i$ 出现偶数次。

而如果子字符串 $s[j,..i]$ 是“超赞字符串”，那么前缀字符串 $s[0,..i]$ 的状态 $st$ 与前缀字符串 $s[0,..j-1]$ 的状态 $s{t}^{\prime }$ 的二进制位中，最多只有一位不同。这是因为，二进制位不同，表示奇偶性不同，而奇偶性不同，就意味着子字符串 $s[j,..i]$ 中该数字出现的次数为奇数次。

所以，我们可以用哈希表或数组记录所有状态 $st$ 第一次出现的位置。若当前前缀字符串的状态 $st$ 在哈希表中已经存在，那么说明当前前缀字符串的状态 $st$ 与前缀字符串 $s[0,..j-1]$ 的状态 $s{t}^{\prime }$ 的二进制位中，所有位都相同，即子字符串 $s[j,..i]$ 是“超赞字符串”，更新答案的最大值。或者，我们可以枚举每一位，将当前前缀字符串的状态 $st$ 的第 $i$ 位取反，即 $st\oplus 2^i$，然后判断 $st\oplus 2^i$ 是否在哈希表中，若在，那么说明当前前缀字符串的状态 $st$ 与前缀字符串 $s[0,..j-1]$ 的状态 $s{t}^{\prime }\oplus 2^i$ 的二进制位中，只有第 $i$ 位不同，即子字符串 $s[j,..i]$ 是“超赞字符串”，更新答案的最大值。

最后，返回答案即可。

时间复杂度 $O(n\times C)$，空间复杂度 $O(2^C)$。其中 $n$ 和 $C$ 分别为字符串 $s$ 的长度和数字字符的种类数。

func longestAwesome(s string) int {
	d := [1024]int{}
	d[0] = 1
	st, ans := 0, 1
	for i, c := range s {
		i += 2
		st ^= 1 << (c - '0')
		if d[st] > 0 {
			ans = max(ans, i-d[st])
		} else {
			d[st] = i
		}
		for v := 0; v < 10; v++ {
			if d[st^(1<<v)] > 0 {
				ans = max(ans, i-d[st^(1<<v)])
			}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1680. 连接连续二进制数字

中等2 种解法

标签：位运算、数学、模拟

题目、示例与约束

给你一个整数 n ，请你将 1 到 n 的二进制表示连接起来，并返回连接结果对应的 十进制 数字对 109 + 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 。
对 109 + 7 取余后，结果为 505379714 。

 

提示：

• 1 <= n <= 105

方法一：位运算 · Go 实现

思考

把 $1$ 到 $n$ 的二进制依次拼接再模 ${10}^9+7$， $n$ 达 ${10}^5$，不能真的拼字符串。接到 $i$ 时，相当于把已有结果左移 $i$ 的二进制位数再或上 $i$。

循环中 $\mathit{\text{ans}}=(\mathit{\text{ans}}\ll i.\mathtt{\text{bit\_length()}}\mid i)mod({10}^9+7)$。

观察数字的连接规律，我们可以发现，当连接到第 $i$ 个数时，实际上是将前 $i-1$ 个数连接而成的结果 $ans$ 往左移动一定的位数，然后再加上 $i$ 这个数，移动的位数是 $i$ 中二进制的位数。

时间复杂度 $O(n)$，其中 $n$ 为给定的整数。空间复杂度 $O(1)$。

func concatenatedBinary(n int) (ans int) {
	const mod = 1e9 + 7
	for i := 1; i <= n; i++ {
		ans = (ans<<bits.Len(uint(i)) | i) % mod
	}
	return
}

方法二：位运算（优化） · Go 实现

思考

方法一每次调用 $\mathtt{\text{bit\_length}}$。位数只在 $i$ 越过 $2$ 的幂时加一，用变量 $\mathit{\text{shift}}$ 在 $i$ 为 $2$ 的幂时自增即可少做位长计算。

在方法一中，我们每次都需要计算 $i$ 的二进制位数，这样会增加一些额外的计算。我们可以通过一个变量 $\mathit{\text{shift}}$ 来记录当前需要移动的位数，当 $i$ 是 $2$ 的幂时， $\mathit{\text{shift}}$ 需要增加 $1$。

时间复杂度 $O(n)$，其中 $n$ 为给定的整数。空间复杂度 $O(1)$。

func concatenatedBinary(n int) (ans int) {
	const mod = 1e9 + 7
	shift := 0
	for i := 1; i <= n; i++ {
		if i&(i-1) == 0 {
			shift++
		}
		ans = (ans<<shift | i) % mod
	}
	return
}

力扣原题 · Doocs 题解来源

1684. 统计一致字符串的数目

简单2 种解法

标签：位运算、数组、哈希表、字符串、计数

题目、示例与约束

给你一个由不同字符组成的字符串 allowed 和一个字符串数组 words 。如果一个字符串的每一个字符都在 allowed 中，就称这个字符串是 一致字符串 。

请你返回 words 数组中 一致字符串 的数目。

 

示例 1：

输入：allowed = "ab", words = ["ad","bd","aaab","baa","badab"]
输出：2
解释：字符串 "aaab" 和 "baa" 都是一致字符串，因为它们只包含字符 'a' 和 'b' 。

示例 2：

输入：allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"]
输出：7
解释：所有字符串都是一致的。

示例 3：

输入：allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"]
输出：4
解释：字符串 "cc"，"acd"，"ac" 和 "d" 是一致字符串。

 

提示：

• 1 <= words.length <= 104
• 1 <= allowed.length <= 26
• 1 <= words[i].length <= 10
• allowed 中的字符 互不相同 。
• words[i] 和 allowed 只包含小写英文字母。

方法一：哈希表或数组 · Go 实现

思考

一致串的每个字符都出现在 $\mathit{\text{allowed}}$ 中。把 $\mathit{\text{allowed}}$ 放进集合，对每个单词检查字符是否都在集合内。

一种比较直接的思路是，用哈希表或数组 $s$ 记录 allowed 中的字符。然后遍历 words 数组，对于每个字符串 $w$，判断其是否由 allowed 中的字符组成。若是，答案加一。

时间复杂度 $O(m)$，空间复杂度 $O(C)$。其中 $m$ 为所有字符串的总长度，而 $C$ 为 allowed 字符集的大小。本题中 $C\le 26$。

func countConsistentStrings(allowed string, words []string) (ans int) {
	s := [26]bool{}
	for _, c := range allowed {
		s[c-'a'] = true
	}
	check := func(w string) bool {
		for _, c := range w {
			if !s[c-'a'] {
				return false
			}
		}
		return true
	}
	for _, w := range words {
		if check(w) {
			ans++
		}
	}
	return ans
}

方法二：位运算 · Go 实现

思考

方法一用哈希集合。字母只有 $26$ 个，可用整数位掩码表示出现集合：单词掩码与 $\mathit{\text{allowed}}$ 掩码按位或后若仍等于后者，则单词被包含。

我们也可以仅用一个整数来表示每个字符串中字符的出现情况。其中，整数的二进制表示中的每一位表示一个字符是否出现。

我们简单地定义一个函数 $f(w)$，这个函数可以将一个字符串 $w$ 转换为一个整数。整数的二进制表示中的每一位表示一个字符是否出现。例如，字符串 ab 可以转换为整数 $3$，即二进制表示为 $11$。字符串 abd 可以转换为整数 $11$，即二进制表示为 $1011$。

回到题目上，判断一个字符串 $w$ 是否由 allowed 中的字符组成，就可以转换为：判断 $f(allowed)$ 和 $f(w)$ 进行按位或运算后的结果是否等于 $f(allowed)$。若是，答案加一。

时间复杂度 $O(m)$，其中 $m$ 为所有字符串的总长度。空间复杂度 $O(1)$。

func countConsistentStrings(allowed string, words []string) (ans int) {
	f := func(w string) (mask int) {
		for _, c := range w {
			mask |= 1 << (c - 'a')
		}
		return
	}

	mask := f(allowed)
	for _, w := range words {
		if (mask | f(w)) == mask {
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1720. 解码异或后的数组

简单1 种解法

标签：位运算、数组

题目、示例与约束

未知 整数数组 arr 由 n 个非负整数组成。

经编码后变为长度为 n - 1 的另一个整数数组 encoded ，其中 encoded[i] = arr[i] XOR arr[i + 1] 。例如，arr = [1,0,2,1] 经编码后得到 encoded = [1,2,3] 。

给你编码后的数组 encoded 和原数组 arr 的第一个元素 first（arr[0]）。

请解码返回原数组 arr 。可以证明答案存在并且是唯一的。

 

示例 1：

输入：encoded = [1,2,3], first = 1
输出：[1,0,2,1]
解释：若 arr = [1,0,2,1] ，那么 first = 1 且 encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]

示例 2：

输入：encoded = [6,2,7,3], first = 4
输出：[4,2,0,7,4]

 

提示：

• 2 <= n <= 104
• encoded.length == n - 1
• 0 <= encoded[i] <= 105
• 0 <= first <= 105

方法一：位运算 · Go 实现

思考

$\mathit{\text{encoded}}[i]=\mathit{\text{arr}}[i]\oplus \mathit{\text{arr}}[i+1]$，且首元 $\mathit{\text{first}}$ 已知。异或两边再异或 $\mathit{\text{arr}}[i]$ 即得后一项。

从 $\mathit{\text{first}}$ 出发依次做 $\mathit{\text{arr}}[i+1]=\mathit{\text{arr}}[i]\oplus \mathit{\text{encoded}}[i]$，线性还原整个数组。

根据题目描述，有：

$$\mathit{\text{encoded}}[i]=\mathit{\text{arr}}[i]\oplus \mathit{\text{arr}}[i+1]$$

如果我们将等式两边同时异或上 $\mathit{\text{arr}}[i]$，那么就会得到：

$$\mathit{\text{arr}}[i]\oplus \mathit{\text{arr}}[i]\oplus \mathit{\text{arr}}[i+1]=\mathit{\text{arr}}[i]\oplus \mathit{\text{encoded}}[i]$$

即：

$$\mathit{\text{arr}}[i+1]=\mathit{\text{arr}}[i]\oplus \mathit{\text{encoded}}[i]$$

根据上述推导，我们可以从 $\mathit{\text{first}}$ 开始，依次计算出数组 $\mathit{\text{arr}}$ 的每一个元素。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组的长度。

func decode(encoded []int, first int) []int {
	ans := []int{first}
	for i, x := range encoded {
		ans = append(ans, ans[i]^x)
	}
	return ans
}

力扣原题 · Doocs 题解来源

1734. 解码异或后的排列

中等1 种解法

标签：位运算、数组

题目、示例与约束

给你一个整数数组 perm ，它是前 n 个正整数的排列，且 n 是个 奇数 。

它被加密成另一个长度为 n - 1 的整数数组 encoded ，满足 encoded[i] = perm[i] XOR perm[i + 1] 。比方说，如果 perm = [1,3,2] ，那么 encoded = [2,1] 。

给你 encoded 数组，请你返回原始数组 perm 。题目保证答案存在且唯一。

 

示例 1：

输入：encoded = [3,1]
输出：[1,2,3]
解释：如果 perm = [1,2,3] ，那么 encoded = [1 XOR 2,2 XOR 3] = [3,1]

示例 2：

输入：encoded = [6,5,4,6]
输出：[2,4,1,5,3]

 

提示：

• 3 <= n < 105
• n 是奇数。
• encoded.length == n - 1

方法一：位运算 · Go 实现

思考

$\mathit{\text{perm}}$ 是 $1..n$ 的排列且 $n$ 为奇数， $\mathit{\text{encoded}}[i]=\mathit{\text{perm}}[i]\oplus \mathit{\text{perm}}[i+1]$。缺一个起始值便无法递推。

$1\oplus \cdots \oplus n$ 可知。把 $\mathit{\text{encoded}}$ 的偶数下标异或起来，恰好比全集少了 $\mathit{\text{perm}}[n-1]$，因此能还原末元。

从末元逆序用 $\mathit{\text{perm}}[i]=\mathit{\text{encoded}}[i]\oplus \mathit{\text{perm}}[i+1]$ 推出整个排列。

我们注意到，数组 $perm$ 是前 $n$ 个正整数的排列，因此 $perm$ 的所有元素的异或和为 $1\oplus 2\oplus \cdots \oplus n$，记为 $a$。而 $encode[i]=perm[i]\oplus perm[i+1]$，如果我们将 $encode[0],encode[2],\cdots ,encode[n-3]$ 的所有元素的异或和记为 $b$，则 $perm[n-1]=a\oplus b$。知道了 $perm$ 的最后一个元素，我们就可以通过逆序遍历数组 $encode$ 求出 $perm$ 的所有元素。

时间复杂度 $O(n)$，其中 $n$ 为数组 $perm$ 的长度。忽略答案数组的空间消耗，空间复杂度 $O(1)$。

func decode(encoded []int) []int {
	n := len(encoded) + 1
	a, b := 0, 0
	for i := 0; i < n-1; i += 2 {
		a ^= encoded[i]
	}
	for i := 1; i <= n; i++ {
		b ^= i
	}
	perm := make([]int, n)
	perm[n-1] = a ^ b
	for i := n - 2; i >= 0; i-- {
		perm[i] = encoded[i] ^ perm[i+1]
	}
	return perm
}

力扣原题 · Doocs 题解来源

1829. 每个查询的最大异或值

中等2 种解法

标签：位运算、数组、前缀和

题目、示例与约束

给你一个 有序 数组 nums ，它由 n 个非负整数组成，同时给你一个整数 maximumBit 。你需要执行以下查询 n 次：

1. 找到一个非负整数 k < 2maximumBit ，使得 nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k 的结果 最大化 。k 是第 i 个查询的答案。
2. 从当前数组 nums 删除 最后 一个元素。

请你返回一个数组 answer ，其中 answer[i]是第 i 个查询的结果。

 

示例 1：

输入：nums = [0,1,1,3], maximumBit = 2
输出：[0,3,2,3]
解释：查询的答案如下：
第一个查询：nums = [0,1,1,3]，k = 0，因为 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3 。
第二个查询：nums = [0,1,1]，k = 3，因为 0 XOR 1 XOR 1 XOR 3 = 3 。
第三个查询：nums = [0,1]，k = 2，因为 0 XOR 1 XOR 2 = 3 。
第四个查询：nums = [0]，k = 3，因为 0 XOR 3 = 3 。

示例 2：

输入：nums = [2,3,4,7], maximumBit = 3
输出：[5,2,6,5]
解释：查询的答案如下：
第一个查询：nums = [2,3,4,7]，k = 5，因为 2 XOR 3 XOR 4 XOR 7 XOR 5 = 7。
第二个查询：nums = [2,3,4]，k = 2，因为 2 XOR 3 XOR 4 XOR 2 = 7 。
第三个查询：nums = [2,3]，k = 6，因为 2 XOR 3 XOR 6 = 7 。
第四个查询：nums = [2]，k = 5，因为 2 XOR 5 = 7 。

示例 3：

输入：nums = [0,1,2,2,5,7], maximumBit = 3
输出：[4,3,6,4,6,7]

 

提示：

• nums.length == n
• 1 <= n <= 105
• 1 <= maximumBit <= 20
• 0 <= nums[i] < 2maximumBit
• nums​​​ 中的数字已经按 升序 排好序。

方法一：位运算 + 枚举 · Go 实现

思考

每次要选 $k<2^{\mathit{\text{maximumBit}}}$ 使当前前缀异或与 $k$ 的异或最大，再删掉末尾元素。若对每个查询重新扫描数组，时间为 $O(n^2)$。 $n\le {10}^5$，无法通过。

先求出全数组异或 $xs$。从后往前删除时， $k$ 应在 $maximumBit$ 位内尽量把 $xs$ 的 $0$ 翻成 $1$。按位检查 $xs$ 即可构造 $k$，再用 $xs\oplus x$ 回退末尾。

我们先预处理出数组 nums 的异或和 $xs$，即 $xs=nums[0]\oplus nums[1]\oplus \cdots \oplus nums[n-1]$。

接下来，我们从后往前枚举数组 nums 中的每个元素 $x$，当前的异或和为 $xs$，我们需要找到一个数 $k$，使得 $xs\oplus k$ 的值尽可能大，并且 $k<2^{maximumBit}$。

也即是说，我们从 $xs$ 的第 $maximumBit-1$ 位开始，往低位枚举，如果 $xs$ 的某一位为 $0$，那么我们就将 $k$ 的对应位设置为 $1$，否则我们就将 $k$ 的对应位设置为 $0$。这样，最终得到的 $k$ 就是每一次查询的答案。然后，我们将 $xs$ 更新为 $xs\oplus x$，继续枚举下一个元素。

时间复杂度 $O(n\times m)$，其中 $n$ 和 $m$ 分别是数组 nums 和 maximumBit 的值。忽略答案数组的空间消耗，空间复杂度 $O(1)$。

func getMaximumXor(nums []int, maximumBit int) (ans []int) {
	xs := 0
	for _, x := range nums {
		xs ^= x
	}
	for i := range nums {
		x := nums[len(nums)-i-1]
		k := 0
		for j := maximumBit - 1; j >= 0; j-- {
			if xs>>j&1 == 0 {
				k |= 1 << j
			}
		}
		ans = append(ans, k)
		xs ^= x
	}
	return
}

方法二：枚举优化 · Go 实现

思考

方法一按位构造 $k$，内层循环依赖 $maximumBit$。注意到目标是让 $xs\oplus k$ 在低 $maximumBit$ 位全为 $1$，故 $k=xs\oplus (2^{\mathit{\text{maximumBit}}}-1)$。一次异或即可，总时间降为线性。

与方法一类似，我们先预处理出数组 nums 的异或和 $xs$，即 $xs=nums[0]\oplus nums[1]\oplus \cdots \oplus nums[n-1]$。

接下来，我们算出 $2^{maximumBit}-1$，即 $2^{maximumBit}$ 减去 $1$，记为 $mask$。然后，我们从后往前枚举数组 nums 中的每个元素 $x$，当前的异或和为 $xs$，那么 $k=xs\oplus mask$ 就是每一次查询的答案。然后，我们将 $xs$ 更新为 $xs\oplus x$，继续枚举下一个元素。

时间复杂度 $O(n)$，其中 $n$ 是数组 nums 的长度。忽略答案数组的空间消耗，空间复杂度 $O(1)$。

func getMaximumXor(nums []int, maximumBit int) (ans []int) {
	xs := 0
	for _, x := range nums {
		xs ^= x
	}
	mask := (1 << maximumBit) - 1
	for i := range nums {
		x := nums[len(nums)-i-1]
		k := xs ^ mask
		ans = append(ans, k)
		xs ^= x
	}
	return
}

力扣原题 · Doocs 题解来源

1835. 所有数对按位与结果的异或和

困难1 种解法

标签：位运算、数组、数学

题目、示例与约束

列表的 异或和（XOR sum）指对所有元素进行按位 XOR 运算的结果。如果列表中仅有一个元素，那么其 异或和 就等于该元素。

• 例如，[1,2,3,4] 的 异或和 等于 1 XOR 2 XOR 3 XOR 4 = 4 ，而 [3] 的 异或和 等于 3 。

给你两个下标 从 0 开始 计数的数组 arr1 和 arr2 ，两数组均由非负整数组成。

根据每个 (i, j) 数对，构造一个由 arr1[i] AND arr2[j]（按位 AND 运算）结果组成的列表。其中 0 <= i < arr1.length 且 0 <= j < arr2.length 。

返回上述列表的 异或和 。

 

示例 1：

输入：arr1 = [1,2,3], arr2 = [6,5]
输出：0
解释：列表 = [1 AND 6, 1 AND 5, 2 AND 6, 2 AND 5, 3 AND 6, 3 AND 5] = [0,1,2,0,2,1] ，
异或和 = 0 XOR 1 XOR 2 XOR 0 XOR 2 XOR 1 = 0 。

示例 2：

输入：arr1 = [12], arr2 = [4]
输出：4
解释：列表 = [12 AND 4] = [4] ，异或和 = 4 。

 

提示：

• 1 <= arr1.length, arr2.length <= 105
• 0 <= arr1[i], arr2[j] <= 109

方法一：位运算 · Go 实现

思考

要求 $\underset{i,j}{⨁}(arr1[i]\wedge arr2[j])$。若枚举全部数对， $n,m$ 达 ${10}^5$ 时不可行。

按位看，与运算相当于乘法、异或相当于不进位加法，因而整个式子等于 $(⨁arr1)\wedge (⨁arr2)$。分别求两数组的异或再取与即可。

假设数组 $arr1$ 的元素分别为 $a_1,a_2,\cdots ,a_n$，数组 $arr2$ 的元素分别为 $b_1,b_2,\cdots ,b_m$，那么题目答案为：

$$\begin{array}{rl}\mathit{\text{ans}}& =(a_1\wedge b_1)\oplus (a_1\wedge b_2)...(a_1\wedge b_m)\\ & \oplus (a_2\wedge b_1)\oplus (a_2\wedge b_2)...(a_2\wedge b_m)\\ & \oplus \cdots \\ & \oplus (a_n\wedge b_1)\oplus (a_n\wedge b_2)...(a_n\wedge b_m)\end{array}$$

由于布尔代数中，异或运算就是不进位的加法，与运算就是乘法，所以上式可以简化为：

$$\mathit{\text{ans}}=(a_1\oplus a_2\oplus \cdots \oplus a_n)\wedge (b_1\oplus b_2\oplus \cdots \oplus b_m)$$

即，数组 $arr1$ 的异或和与数组 $arr2$ 的异或和的与运算结果。

时间复杂度 $O(n+m)$，其中 $n$ 和 $m$ 分别为数组 $arr1$ 和 $arr2$ 的长度。空间复杂度 $O(1)$。

func getXORSum(arr1 []int, arr2 []int) int {
	var a, b int
	for _, v := range arr1 {
		a ^= v
	}
	for _, v := range arr2 {
		b ^= v
	}
	return a & b
}

力扣原题 · Doocs 题解来源

1915. 最美子字符串的数目

中等1 种解法

标签：位运算、哈希表、字符串、前缀和

题目、示例与约束

如果某个字符串中 至多一个 字母出现 奇数 次，则称其为 最美 字符串。

• 例如，"ccjjc" 和 "abab" 都是最美字符串，但 "ab" 不是。

给你一个字符串 word ，该字符串由前十个小写英文字母组成（'a' 到 'j'）。请你返回 word 中 最美非空子字符串 的数目。如果同样的子字符串在 word 中出现多次，那么应当对 每次出现 分别计数。

子字符串 是字符串中的一个连续字符序列。

 

示例 1：

输入：word = "aba"
输出：4
解释：4 个最美子字符串如下所示：
- "aba" -> "a"
- "aba" -> "b"
- "aba" -> "a"
- "aba" -> "aba"

示例 2：

输入：word = "aabb"
输出：9
解释：9 个最美子字符串如下所示：
- "aabb" -> "a"
- "aabb" -> "aa"
- "aabb" -> "aab"
- "aabb" -> "aabb"
- "aabb" -> "a"
- "aabb" -> "abb"
- "aabb" -> "b"
- "aabb" -> "bb"
- "aabb" -> "b"

示例 3：

输入：word = "he"
输出：2
解释：2 个最美子字符串如下所示：
- "he" -> "h"
- "he" -> "e"

 

提示：

• 1 <= word.length <= 105
• word 由从 'a' 到 'j' 的小写英文字母组成

方法一：前缀异或 + 计数 · Go 实现

思考

「至多一个字母出现奇数次」若对每个子串统计频次，时间为 $O(n^2\cdot \mathrm{\Sigma })$， $n\le {10}^5$ 不可行。

字母仅 $10$ 个，奇偶可用 $10$ 位掩码表示。前缀异或相等则区间全部为偶；相差恰好一位则恰有一个字母为奇。

扫到位置 $i$ 时，答案累加历史中与当前掩码相同或只差一位的前缀个数，再把当前掩码计入哈希。

由于字符串中只包含 $10$ 个小写字母，因此可以用一个长度为 $10$ 的二进制数表示字符串中每个字母的奇偶性，其中第 $i$ 位为 $1$ 表示第 $i$ 个字母出现了奇数次，为 $0$ 表示第 $i$ 个字母出现了偶数次。

我们遍历字符串的每个字符，用一个变量 $st$ 维护当前字符串的前缀异或值，用一个数组 $cnt$ 维护每个前缀异或值出现的次数，初始时 $st=0$, $cnt[0]=1$。

对于当前遍历到的字符，我们更新其前缀异或值。如果当前的前缀异或值出现了 $cnt[st]$ 次，也就意味着有 $cnt[st]$ 个子字符串满足所有字母的出现次数均为偶数，因此我们将答案增加 $cnt[st]$。此外，对于 $0\le i<10$，如果当前的前缀异或值 $st$ 的第 $i$ 位为 $1$，那么我们还可以找到一个字母出现了奇数次，我们将答案增加 $cnt[st\oplus (1<<i)]$。最后，我们将 $st$ 出现的次数增加 $1$。继续遍历下一个字符，直到遍历完整个字符串。

时间复杂度 $O(n\times \mathrm{\Sigma })$，空间复杂度 $O(2^{\mathrm{\Sigma }})$，其中 $\mathrm{\Sigma }=10$，而 $n$ 为字符串的长度。

相似题目：

• 1371. 每个元音包含偶数次的最长子字符串

func wonderfulSubstrings(word string) (ans int64) {
	cnt := [1024]int{1}
	st := 0
	for _, c := range word {
		st ^= 1 << (c - 'a')
		ans += int64(cnt[st])
		for i := 0; i < 10; i++ {
			ans += int64(cnt[st^(1<<i)])
		}
		cnt[st]++
	}
	return
}

力扣原题 · Doocs 题解来源

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

中等1 种解法

标签：位运算、哈希表、字符串、前缀和

题目、示例与约束

给你一个字符串 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 <= 105
• s 仅由小写英文字母组成

方法一：枚举两端字符 + 哈希表 · Go 实现

思考

长度为 $3$ 的回文子序列形如 $c\mathrm{\_}c$，中间字符任意。 $n\le {10}^5$，枚举全部三元组不可行。

字母仅 $26$ 种，两端字符可枚举。对固定 $c$，取其首次与末次出现之间的不同字符个数，即为以 $c$ 为两端的不同回文个数。

$\mathtt{\text{find}}/\mathtt{\text{rfind}}$ 定位两端，中间用集合去重，总时间 $O(n|\mathrm{\Sigma }|)$。

由于字符串中只包含小写字母，因此我们可以直接枚举所有的两端字符。对于每一对两端字符 $c$，我们找出它们在字符串中第一次和最后一次出现的位置 $l$ 和 $r$，如果 $r-l>1$，说明找到了满足条件的回文序列，我们将 $[l+1,..r-1]$ 之间的字符去重后统计个数，即为以 $c$ 为两端字符的回文序列个数，加入答案中。

枚举结束后，即可得到答案。

时间复杂度 $O(n\times |\mathrm{\Sigma }|)$，其中 $n$ 为字符串长度，而 $\mathrm{\Sigma }$ 为字符集大小，本题中 $|\mathrm{\Sigma }|=26$。空间复杂度 $O(|\mathrm{\Sigma }|)$ 或 $O(1)$。

func countPalindromicSubsequence(s string) (ans int) {
	for c := 'a'; c <= 'z'; c++ {
		l, r := strings.Index(s, string(c)), strings.LastIndex(s, string(c))
		mask := 0
		for i := l + 1; i < r; i++ {
			j := int(s[i] - 'a')
			if mask>>j&1 == 0 {
				mask |= 1 << j
				ans++
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2032. 至少在两个数组中出现的值

简单2 种解法

标签：位运算、数组、哈希表

题目、示例与约束

给你三个整数数组 nums1、nums2 和 nums3 ，请你构造并返回一个 元素各不相同的 数组，且由 至少 在 两个 数组中出现的所有值组成。数组中的元素可以按 任意 顺序排列。

 

示例 1：

输入：nums1 = [1,1,3,2], nums2 = [2,3], nums3 = [3]
输出：[3,2]
解释：至少在两个数组中出现的所有值为：
- 3 ，在全部三个数组中都出现过。
- 2 ，在数组 nums1 和 nums2 中出现过。

示例 2：

输入：nums1 = [3,1], nums2 = [2,3], nums3 = [1,2]
输出：[2,3,1]
解释：至少在两个数组中出现的所有值为：
- 2 ，在数组 nums2 和 nums3 中出现过。
- 3 ，在数组 nums1 和 nums2 中出现过。
- 1 ，在数组 nums1 和 nums3 中出现过。

示例 3：

输入：nums1 = [1,2,2], nums2 = [4,3,3], nums3 = [5]
输出：[]
解释：不存在至少在两个数组中出现的值。

 

提示：

• 1 <= nums1.length, nums2.length, nums3.length <= 100
• 1 <= nums1[i], nums2[j], nums3[k] <= 100

方法一：数组 + 枚举 · Go 实现

思考

值域仅 $[1,100]$，三个数组长度也 $\le 100$。先各自去重，再枚举 $1..100$，看它落入几个集合。出现不少于两次即加入答案。

实现不依赖位运算，与约束完全吻合。

我们可以先将每个数组中的元素放入数组中，然后枚举 $1$ 到 $100$ 中的每个数 $i$，判断 $i$ 是否在至少两个数组中出现过。若是，则将 $i$ 加入答案数组中。

时间复杂度 $O(n_1+n_2+n_3)$，空间复杂度 $O(n_1+n_2+n_3)$。其中 $n_1,n_2,n_3$ 分别为数组 nums1、nums2 和 nums3 的长度。

func twoOutOfThree(nums1 []int, nums2 []int, nums3 []int) (ans []int) {
	get := func(nums []int) (s [101]int) {
		for _, v := range nums {
			s[v] = 1
		}
		return
	}
	s1, s2, s3 := get(nums1), get(nums2), get(nums3)
	for i := 1; i <= 100; i++ {
		if s1[i]+s2[i]+s3[i] > 1 {
			ans = append(ans, i)
		}
	}
	return
}

方法二：哈希表 + 位运算 · Go 实现

思考

方法一固定枚举 $1..100$，换值域便失效。用掩码记录每个数出现在哪些数组：第 $i$ 个数组置第 $i$ 位。

v & (v-1) 非零当且仅当至少两位为 $1$，即至少两个数组含该数。一次遍历即可，不依赖值域上界。

我们可以用一个哈希表 $\mathit{\text{mask}}$ 来记录每个数在哪些数组中出现过。对于每个数组，我们将其中的元素加入哈希表中，并将对应的位设置为 $1$。例如，如果是第一个数组，则将对应的位设置为 $1$；如果是第二个数组，则将对应的位设置为 $2$；如果是第三个数组，则将对应的位设置为 $4$。

最后，我们枚举哈希表中的每个数，判断其对应的值对应的二进制位中是否至少有两位为 $1$，如果是，则将该数加入答案数组中。

时间复杂度 $O(n_1+n_2+n_3)$，空间复杂度 $O(n_1+n_2+n_3)$。其中 $n_1,n_2,n_3$ 分别为数组 $\mathit{\text{nums1}}$, $\mathit{\text{nums2}}$ 和 $\mathit{\text{nums3}}$ 的长度。

func twoOutOfThree(nums1 []int, nums2 []int, nums3 []int) (ans []int) {
	mask := make(map[int]int)
	for i, nums := range [][]int{nums1, nums2, nums3} {
		for _, x := range nums {
			mask[x] |= 1 << i
		}
	}
	for x, m := range mask {
		if m&(m-1) != 0 {
			ans = append(ans, x)
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2128. 通过翻转行或列来去除所有的 1 🔒

中等1 种解法

标签：位运算、数组、数学、矩阵

题目、示例与约束

给你一个大小为 m x n 的二进制矩阵 grid。

每次操作，你可以选择 任意 一行 或者 一列，然后将其中的所有值翻转（0 变成 1， 1变成 0）。

如果经过 任意次 操作，你能将矩阵中所有的 1 去除，那么返回 true；否则返回 false。

 

示例 1:

输入: grid = [[0,1,0],[1,0,1],[0,1,0]]
输出: true
解释: 一种去除所有 1 的可行方法是:
- 翻转矩阵的中间的行
- 翻转矩阵的中间的列

示例 2:

输入: grid = [[1,1,0],[0,0,0],[0,0,0]]
输出: false
解释: 不可能去除矩阵中所有的 1。

示例 3:

输入: grid = [[0]]
输出: true
解释: 矩阵中不存在 1，已经符合要求。

 

提示:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] 是 0 或者 1.

方法一：哈希表 · Go 实现

思考

行翻转与列翻转各做一次或零次，最终要变成全零。两行若能同时被同一组列翻转清零，则它们要么完全相同，要么处处相反。枚举 $2^{m+n}$ 种翻转方案在规模较大时不可行。

把每行按与第一行首元是否相同规范化到以 $0$ 开头的等价类后，合法矩阵至多对应一种行模式。哈希表中若出现第二种模式，则无法用统一的列翻转消去。

遍历各行，与 $\mathit{\text{grid}}[0][0]$ 不同则整行取反，将元组放入集合，集合大小为 $1$ 当且仅当可行。

我们观察发现，如果矩阵中的两行满足以下条件之一，则它们可以通过翻转某些列的方式得到相等的行：

1. 两行的对应位置元素相等，即如果其中一行元素为 $1,0,0,1$，则另一行元素也为 $1,0,0,1$；
2. 两行的对应位置元素相反，即如果其中一行元素为 $1,0,0,1$，则另一行元素为 $0,1,1,0$。

我们称满足以上条件之一的两行元素为“等价行”，那么题目所求的答案即为矩阵中最多包含等价行的行数。

因此，我们可以遍历矩阵的每一行，将每一行转换成第一个元素为 $0$ 的“等价行”。具体做法如下：

• 如果当前行的第一个元素为 $0$，那么当前行的元素保持不变；
• 如果当前行的第一个元素为 $1$，那么我们将当前行的每个元素进行翻转，即 $0$ 变成 $1$, $1$ 变成 $0$。也就是说，我们将以 $1$ 开头的行翻转成以 $0$ 开头的“等价行”。

这样一来，我们只需要用一个哈希表来统计转换后的每一行，如果最后哈希表只有一个元素，那么说明我们可以通过翻转行或列，将矩阵中所有的 $1$ 去除。

时间复杂度 $O(m\times n)$，空间复杂度 $O(m)$。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

相似题目：

• 1072. 按列翻转得到最大值等行数

func removeOnes(grid [][]int) bool {
	s := map[string]bool{}
	for _, row := range grid {
		t := []byte{}
		for _, x := range row {
			if row[0] == 1 {
				x ^= 1
			}
			t = append(t, byte(x)+'0')
		}
		s[string(t)] = true
	}
	return len(s) == 1
}

力扣原题 · Doocs 题解来源

2135. 统计追加字母可以获得的单词数

中等1 种解法

标签：位运算、数组、哈希表、字符串、排序

题目、示例与约束

给你两个下标从 0 开始的字符串数组 startWords 和 targetWords 。每个字符串都仅由 小写英文字母 组成。

对于 targetWords 中的每个字符串，检查是否能够从 startWords 中选出一个字符串，执行一次 转换操作 ，得到的结果与当前 targetWords 字符串相等。

转换操作 如下面两步所述：

1. 追加 任何 不存在 于当前字符串的任一小写字母到当前字符串的末尾。
   • 例如，如果字符串为 "abc" ，那么字母 'd'、'e' 或 'y' 都可以加到该字符串末尾，但 'a' 就不行。如果追加的是 'd' ，那么结果字符串为 "abcd" 。
2. 重排 新字符串中的字母，可以按 任意 顺序重新排布字母。
   • 例如，"abcd" 可以重排为 "acbd"、"bacd"、"cbda"，以此类推。注意，它也可以重排为 "abcd" 自身。

找出 targetWords 中有多少字符串能够由 startWords 中的 任一 字符串执行上述转换操作获得。返回 targetWords 中这类 字符串的数目 。

注意：你仅能验证 targetWords 中的字符串是否可以由 startWords 中的某个字符串经执行操作获得。startWords  中的字符串在这一过程中 不 发生实际变更。

 

示例 1：

输入：startWords = ["ant","act","tack"], targetWords = ["tack","act","acti"]
输出：2
解释：
- 为了形成 targetWords[0] = "tack" ，可以选用 startWords[1] = "act" ，追加字母 'k' ，并重排 "actk" 为 "tack" 。
- startWords 中不存在可以用于获得 targetWords[1] = "act" 的字符串。
  注意 "act" 确实存在于 startWords ，但是 必须 在重排前给这个字符串追加一个字母。
- 为了形成 targetWords[2] = "acti" ，可以选用 startWords[1] = "act" ，追加字母 'i' ，并重排 "acti" 为 "acti" 自身。

示例 2：

输入：startWords = ["ab","a"], targetWords = ["abc","abcd"]
输出：1
解释：
- 为了形成 targetWords[0] = "abc" ，可以选用 startWords[0] = "ab" ，追加字母 'c' ，并重排为 "abc" 。
- startWords 中不存在可以用于获得 targetWords[1] = "abcd" 的字符串。

 

提示：

• 1 <= startWords.length, targetWords.length <= 5 * 104
• 1 <= startWords[i].length, targetWords[j].length <= 26
• startWords 和 targetWords 中的每个字符串都仅由小写英文字母组成
• 在 startWords 或 targetWords 的任一字符串中，每个字母至多出现一次

方法一：哈希表 + 位运算 · Go 实现

思考

每个单词字母互异且为小写，目标串由某个起始串加一个字母并重排得到。若对每个目标枚举删除一个字母再与起始串排序比较，字符串操作偏多，但仍与 $26$ 成正比。

字母集合可用 $26$ 位掩码表示，起始串的掩码放入哈希集合。目标掩码去掉其中一位后若落在集合中，则该目标合法。

先把 $\mathit{\text{startWords}}$ 压成集合，再对每个目标试删除每个字母对应的比特。

我们注意到，题目中给定的字符串只包含小写字母，并且每个字符串的字母至多出现一次。因此，我们可以用一个长度为 $26$ 的二进制数表示一个字符串，其中第 $i$ 位为 $1$ 表示字符串中包含第 $i$ 个小写字母，为 $0$ 表示字符串中不包含第 $i$ 个小写字母。

我们可以将字符串数组 $\mathit{\text{startWords}}$ 中的每个字符串转换为一个二进制数，并将这些二进制数存储到一个集合 $\mathit{\text{s}}$ 中。对于字符串数组 $\mathit{\text{targetWords}}$ 中的每个字符串，我们首先将其转换为一个二进制数，然后枚举这个字符串中的每个字母，将这个字母从二进制数中去掉，再检查是否存在一个二进制数在集合 $\mathit{\text{s}}$ 中，使得这个二进制数与去掉的字母的二进制数的异或结果在集合 $\mathit{\text{s}}$ 中，如果存在，那么这个字符串可以由 $\mathit{\text{startWords}}$ 中的某个字符串执行转换操作获得，答案加一。然后我们跳过这个字符串，继续处理下一个字符串。

时间复杂度 $O(n\times |\mathrm{\Sigma }|)$，空间复杂度 $O(n)$。其中 $n$ 为字符串数组 $\mathit{\text{targetWords}}$ 的长度，而 $|\mathrm{\Sigma }|$ 为字符串中的字符集大小，本题中 $|\mathrm{\Sigma }|=26$。

func wordCount(startWords []string, targetWords []string) (ans int) {
	s := map[int]bool{}
	for _, w := range startWords {
		x := 0
		for _, c := range w {
			x |= 1 << (c - 'a')
		}
		s[x] = true
	}
	for _, w := range targetWords {
		x := 0
		for _, c := range w {
			x |= 1 << (c - 'a')
		}
		for _, c := range w {
			if s[x^(1<<(c-'a'))] {
				ans++
				break
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2206. 将数组划分成相等数对

简单1 种解法

标签：位运算、数组、哈希表、计数

题目、示例与约束

给你一个整数数组 nums ，它包含 2 * n 个整数。

你需要将 nums 划分成 n 个数对，满足：

• 每个元素 只属于一个 数对。
• 同一数对中的元素 相等 。

如果可以将 nums 划分成 n 个数对，请你返回 true ，否则返回 false 。

 

示例 1：

输入：nums = [3,2,3,2,2,2]
输出：true
解释：
nums 中总共有 6 个元素，所以它们应该被划分成 6 / 2 = 3 个数对。
nums 可以划分成 (2, 2) ，(3, 3) 和 (2, 2) ，满足所有要求。

示例 2：

输入：nums = [1,2,3,4]
输出：false
解释：
无法将 nums 划分成 4 / 2 = 2 个数对且满足所有要求。

 

提示：

• nums.length == 2 * n
• 1 <= n <= 500
• 1 <= nums[i] <= 500

方法一：计数 · Go 实现

思考

长度为 $2n$ 的数组要分成 $n$ 对相等元素。配对方案不必输出，只需判断是否存在。若枚举所有配对， $n\le 500$ 仍会陷入组合搜索。

一对相等元素会消耗该值两次，因此每个值的出现次数必须为偶数。用计数器统计频率，检查是否全部为偶数即可。 $n$ 很小，哈希表一次遍历足够。

根据题目描述，只要数组中每个元素出现的次数都是偶数次，就可以将数组划分成 $n$ 个数对。

因此，我们可以用一个哈希表或者数组 $\mathit{\text{cnt}}$ 记录每个元素出现的次数，然后遍历 $\mathit{\text{cnt}}$，如果有任何一个元素出现的次数是奇数次，就返回 $\mathit{\text{false}}$，否则返回 $\mathit{\text{true}}$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是数组 $\mathit{\text{nums}}$ 的长度。

func divideArray(nums []int) bool {
	cnt := [510]int{}
	for _, x := range nums {
		cnt[x]++
	}
	for _, v := range cnt {
		if v%2 != 0 {
			return false
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

2220. 转换数字的最少位翻转次数

简单1 种解法

标签：位运算

题目、示例与约束

一次 位翻转 定义为将数字 x 二进制中的一个位进行 翻转 操作，即将 0 变成 1 ，或者将 1 变成 0 。

• 比方说，x = 7 ，二进制表示为 111 ，我们可以选择任意一个位（包含没有显示的前导 0 ）并进行翻转。比方说我们可以翻转最右边一位得到 110 ，或者翻转右边起第二位得到 101 ，或者翻转右边起第五位（这一位是前导 0 ）得到 10111 等等。

给你两个整数 start 和 goal ，请你返回将 start 转变成 goal 的 最少位翻转 次数。

 

示例 1：

输入：start = 10, goal = 7
输出：3
解释：10 和 7 的二进制表示分别为 1010 和 0111 。我们可以通过 3 步将 10 转变成 7 ：
- 翻转右边起第一位得到：1010 -> 1011 。
- 翻转右边起第三位：1011 -> 1111 。
- 翻转右边起第四位：1111 -> 0111 。
我们无法在 3 步内将 10 转变成 7 。所以我们返回 3 。

示例 2：

输入：start = 3, goal = 4
输出：3
解释：3 和 4 的二进制表示分别为 011 和 100 。我们可以通过 3 步将 3 转变成 4 ：
- 翻转右边起第一位：011 -> 010 。
- 翻转右边起第二位：010 -> 000 。
- 翻转右边起第三位：000 -> 100 。
我们无法在 3 步内将 3 变成 4 。所以我们返回 3 。

 

提示：

• 0 <= start, goal <= 109

 

注意：本题与 461. 汉明距离 相同。

方法一：位运算 · Go 实现

思考

一次翻转改变 $start$ 的某一比特，要使它变成 $goal$。两个整数至多约 $30$ 位，枚举翻转集合可以，但每位独立：只有 $start$ 与 $goal$ 不同的位才需要翻。

异或 $start\oplus goal$ 恰在这些位上为 $1$，统计二进制中 $1$ 的个数即为最少翻转次数。

根据题目描述，我们只需要计算 $\mathit{\text{start}}\oplus \mathit{\text{goal}}$ 的二进制表示中有多少个 1 即可。

时间复杂度 $O(\log n)$，其中 $n$ 是题目中整数的大小。空间复杂度 $O(1)$。

func minBitFlips(start int, goal int) int {
	return bits.OnesCount(uint(start ^ goal))
}

力扣原题 · Doocs 题解来源

2275. 按位与结果大于零的最长组合

中等1 种解法

标签：位运算、数组、哈希表、计数

题目、示例与约束

对数组 nums 执行 按位与 相当于对数组 nums 中的所有整数执行 按位与 。

• 例如，对 nums = [1, 5, 3] 来说，按位与等于 1 & 5 & 3 = 1 。
• 同样，对 nums = [7] 而言，按位与等于 7 。

给你一个正整数数组 candidates 。计算 candidates 中的数字每种组合下 按位与 的结果。

返回按位与结果大于 0 的 最长 组合的长度。

 

示例 1：

输入：candidates = [16,17,71,62,12,24,14]
输出：4
解释：组合 [16,17,62,24] 的按位与结果是 16 & 17 & 62 & 24 = 16 > 0 。
组合长度是 4 。
可以证明不存在按位与结果大于 0 且长度大于 4 的组合。
注意，符合长度最大的组合可能不止一种。
例如，组合 [62,12,24,14] 的按位与结果是 62 & 12 & 24 & 14 = 8 > 0 。

示例 2：

输入：candidates = [8,8]
输出：2
解释：最长组合是 [8,8] ，按位与结果 8 & 8 = 8 > 0 。
组合长度是 2 ，所以返回 2 。

 

提示：

• 1 <= candidates.length <= 105
• 1 <= candidates[i] <= 107

方法一：位运算 · Go 实现

思考

子集的按位与大于 $0$，当且仅当存在某一比特在子集中全为 $1$。要子集尽量大，等价于某一比特上 $1$ 的个数的最大值。 $n\le {10}^5$，枚举子集不可行。

对每一位 $i$，统计 $x>>i\mathrm{\&}1$ 的个数，取最大。位数由最大值决定，不超过 $24$。

题目需要找到按位与结果大于 $0$ 的数字组合的最大长度，那么说明一定存在某个二进制位，所有数字在这个二进制位上都是 $1$。因此，我们可以枚举每个二进制位，统计所有数字在这个二进制位上的 $1$ 的个数，最后取最大值即可。

时间复杂度 $O(n\times \log M)$，其中 $n$ 和 $M$ 分别是数组 $\mathit{\text{candidates}}$ 的长度和数组中的最大值。空间复杂度 $O(1)$。

func largestCombination(candidates []int) (ans int) {
	mx := slices.Max(candidates)
	m := bits.Len(uint(mx))
	for i := 0; i < m; i++ {
		cnt := 0
		for _, x := range candidates {
			cnt += (x >> i) & 1
		}
		ans = max(ans, cnt)
	}
	return
}

力扣原题 · Doocs 题解来源

2306. 公司命名

困难1 种解法

标签：位运算、数组、哈希表、字符串、枚举

题目、示例与约束

给你一个字符串数组 ideas 表示在公司命名过程中使用的名字列表。公司命名流程如下：

1. 从 ideas 中选择 2 个 不同 名字，称为 ideaA 和 ideaB 。
2. 交换 ideaA 和 ideaB 的首字母。
3. 如果得到的两个新名字 都 不在 ideas 中，那么 ideaA ideaB（串联 ideaA 和 ideaB ，中间用一个空格分隔）是一个有效的公司名字。
4. 否则，不是一个有效的名字。

返回 不同 且有效的公司名字的数目。

 

示例 1：

输入：ideas = ["coffee","donuts","time","toffee"]
输出：6
解释：下面列出一些有效的选择方案：
- ("coffee", "donuts")：对应的公司名字是 "doffee conuts" 。
- ("donuts", "coffee")：对应的公司名字是 "conuts doffee" 。
- ("donuts", "time")：对应的公司名字是 "tonuts dime" 。
- ("donuts", "toffee")：对应的公司名字是 "tonuts doffee" 。
- ("time", "donuts")：对应的公司名字是 "dime tonuts" 。
- ("toffee", "donuts")：对应的公司名字是 "doffee tonuts" 。
因此，总共有 6 个不同的公司名字。

下面列出一些无效的选择方案：
- ("coffee", "time")：在原数组中存在交换后形成的名字 "toffee" 。
- ("time", "toffee")：在原数组中存在交换后形成的两个名字。
- ("coffee", "toffee")：在原数组中存在交换后形成的两个名字。

示例 2：

输入：ideas = ["lack","back"]
输出：0
解释：不存在有效的选择方案。因此，返回 0 。

 

提示：

• 2 <= ideas.length <= 5 * 104
• 1 <= ideas[i].length <= 10
• ideas[i] 由小写英文字母组成
• ideas 中的所有字符串 互不相同

方法一：枚举计数 · Go 实现

思考

合法公司名由两个不同想法互换首字母得到，且互换后两串均不在原集合中。两两配对需 $O(n^2)$， $n\le 5\times {10}^4$ 不可行。

首字母只有 $26$ 种，后缀是否冲突决定一对能否互换。用集合判重后，统计「以字母 $i$ 开头、换成 $j$ 后不在集合中」的个数 $f[i][j]$。再次遍历时，一个义项换成 $j$ 合法，则它可与 $f[j][i]$ 个对方配对，从而在线性于 $n|\mathrm{\Sigma }|$ 的时间内计数。

我们定义 $f[i][j]$ 表示 $\mathit{\text{ideas}}$ 中以第 $i$ 个字母开头，替换为第 $j$ 个字母后，不在 $\mathit{\text{ideas}}$ 中的字符串的个数。初始时 $f[i][j]=0$。另外，用一个哈希表 $s$ 记录 $\mathit{\text{ideas}}$ 中的字符串，方便我们快速判断某个字符串是否在 $\mathit{\text{ideas}}$ 中。

接下来，我们遍历 $\mathit{\text{ideas}}$ 中字符串，对于当前遍历到的字符串 $v$，我们枚举替换后的第一个字母 $j$，如果 $v$ 替换后的字符串不在 $\mathit{\text{ideas}}$ 中，那么我们就更新 $f[i][j]=f[i][j]+1$。

最后，我们再次遍历 $\mathit{\text{ideas}}$ 中字符串，对于当前遍历到的字符串 $v$，我们枚举替换后的第一个字母 $j$，如果 $v$ 替换后的字符串不在 $\mathit{\text{ideas}}$ 中，那么我们就更新答案 $\mathit{\text{ans}}=\mathit{\text{ans}}+f[j][i]$。

最终答案即为 $\mathit{\text{ans}}$。

时间复杂度 $O(n\times m\times |\mathrm{\Sigma }|)$，空间复杂度 $O(|\mathrm{\Sigma }{|}^2)$。其中 $n$ 和 $m$ 分别是 $\mathit{\text{ideas}}$ 中字符串的个数和字符串的最大长度，而 $|\mathrm{\Sigma }|$ 是字符串中出现的字符集，本题中 $|\mathrm{\Sigma }|\le 26$。

func distinctNames(ideas []string) (ans int64) {
	s := map[string]bool{}
	for _, v := range ideas {
		s[v] = true
	}
	f := [26][26]int{}
	for _, v := range ideas {
		i := int(v[0] - 'a')
		t := []byte(v)
		for j := 0; j < 26; j++ {
			t[0] = 'a' + byte(j)
			if !s[string(t)] {
				f[i][j]++
			}
		}
	}

	for _, v := range ideas {
		i := int(v[0] - 'a')
		t := []byte(v)
		for j := 0; j < 26; j++ {
			t[0] = 'a' + byte(j)
			if !s[string(t)] {
				ans += int64(f[j][i])
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2317. 操作后的最大异或和

中等1 种解法

标签：位运算、数组、数学

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums 。一次操作中，选择 任意 非负整数 x 和一个下标 i ，更新 nums[i] 为 nums[i] AND (nums[i] XOR x) 。

注意，AND 是逐位与运算，XOR 是逐位异或运算。

请你执行 任意次 更新操作，并返回 nums 中所有元素 最大 逐位异或和。

 

示例 1：

输入：nums = [3,2,4,6]
输出：7
解释：选择 x = 4 和 i = 3 进行操作，num[3] = 6 AND (6 XOR 4) = 6 AND 2 = 2 。
现在，nums = [3, 2, 4, 2] 且所有元素逐位异或得到 3 XOR 2 XOR 4 XOR 2 = 7 。
可知 7 是能得到的最大逐位异或和。
注意，其他操作可能也能得到逐位异或和 7 。

示例 2：

输入：nums = [1,2,3,9,2]
输出：11
解释：执行 0 次操作。
所有元素的逐位异或和为 1 XOR 2 XOR 3 XOR 9 XOR 2 = 11 。
可知 11 是能得到的最大逐位异或和。

 

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 108

方法一：位运算 · Go 实现

思考

一次操作能把 $nums[i]$ 的若干 $1$ 变成 $0$，不能凭空制造 $1$。 $n\le {10}^5$，需要 $O(n)$ 或接近线性的结论。

逐位异或的最大值在某一比特上为 $1$，当且仅当原数组中该位至少出现一次 $1$（可只保留其中一个）。因此答案等于全体元素的按位或。

在一次操作中，我们可以把 $\mathit{\text{nums}}[i]$ 更新为 $\mathit{\text{nums}}[i]\text{ AND }(\mathit{\text{nums}}[i]\text{ XOR }x)$。由于 $x$ 是任意非负整数，因此 $\mathit{\text{nums}}[i]\oplus x$ 的结果是一个任意值，再与 $\mathit{\text{nums}}[i]$ 逐位与运算，可以把 $\mathit{\text{nums}}[i]$ 的二进制表示中的若干位 $1$ 变为 $0$。

而题目中要获取的是 $\mathit{\text{nums}}$ 所有元素的最大逐位异或和，对于一个二进制位，只要在 $\mathit{\text{nums}}$ 中存在一个元素对应的二进制位为 $1$，那么这个二进制位对于最大逐位异或和的贡献就是 $1$。因此答案就是 $\mathit{\text{nums}}$ 中所有元素的逐位或运算的结果。

时间复杂度 $O(n)$，其中 $n$ 为 $\mathit{\text{nums}}$ 的长度。空间复杂度 $O(1)$。

func maximumXOR(nums []int) (ans int) {
	for _, x := range nums {
		ans |= x
	}
	return
}

力扣原题 · Doocs 题解来源

2351. 第一个出现两次的字母

简单2 种解法

标签：位运算、哈希表、字符串、计数

题目、示例与约束

给你一个由小写英文字母组成的字符串 s ，请你找出并返回第一个出现 两次 的字母。

注意：

• 如果 a 的 第二次 出现比 b 的 第二次 出现在字符串中的位置更靠前，则认为字母 a 在字母 b 之前出现两次。
• s 包含至少一个出现两次的字母。

 

示例 1：

输入：s = "abccbaacz"
输出："c"
解释：
字母 'a' 在下标 0 、5 和 6 处出现。
字母 'b' 在下标 1 和 4 处出现。
字母 'c' 在下标 2 、3 和 7 处出现。
字母 'z' 在下标 8 处出现。
字母 'c' 是第一个出现两次的字母，因为在所有字母中，'c' 第二次出现的下标是最小的。

示例 2：

输入：s = "abcdd"
输出："d"
解释：
只有字母 'd' 出现两次，所以返回 'd' 。

 

提示：

• 2 <= s.length <= 100
• s 由小写英文字母组成
• s 包含至少一个重复字母

方法一：数组或哈希表 · Go 实现

思考

求第一次使某字母累计两次的字符。 $s$ 很短且保证有解，扫一遍计数即可。

哈希表或数组累加出现次数，某键变为 $2$ 时立刻返回。

遍历字符串 $s$，用数组或哈希表 cnt 记录每个字母出现的次数，当某个字母出现两次时，返回该字母。

时间复杂度 $O(n)$，空间复杂度 $O(C)$。其中 $n$ 为字符串 $s$ 的长度，而 $C$ 为字符集大小。本题中 $C=26$。

func repeatedCharacter(s string) byte {
	cnt := [26]int{}
	for i := 0; ; i++ {
		cnt[s[i]-'a']++
		if cnt[s[i]-'a'] == 2 {
			return s[i]
		}
	}
}

方法二：位运算 · Go 实现

思考

方法一占用与字母表同阶的计数空间。只需「是否出现过」，一个整型掩码的对应位即可，空间为常数。

我们也可以用一个整数 mask 记录每个字母是否出现过，其中 mask 的第 $i$ 位表示第 $i$ 个字母是否出现过。当某个字母出现两次时，返回该字母。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为字符串 $s$ 的长度。

func repeatedCharacter(s string) byte {
	mask := 0
	for i := 0; ; i++ {
		if mask>>(s[i]-'a')&1 == 1 {
			return s[i]
		}
		mask |= 1 << (s[i] - 'a')
	}
}

力扣原题 · Doocs 题解来源