LeetCode 190, 222, 990

---

190. 颠倒二进制位

题目链接

190. 颠倒二进制位

标签

位运算 分治

思路

左移运算

在某个数字的二进制数中，将全体的位向左移动指定位数，多余的位会被抛弃。例如 1001 0001 0001 0001 0001 0001 0001 0001 << 1 = 0010 0010 0010 0010 0010 0010 0010 0010，这里的 << 1 表示将指定 int (32 位) 数字向左移一位。

与运算

基础定义

对于 与运算，只需要看两个位是否同时为 1，如果同时为 1，则结果也为 1，其他情况全部为 0。例如 1010 & 1001 = 1000。这里的其他情况如下：

• 第一个位为 1，第二个位为 0。
• 第一个位为 0，第二个位为 1。
• 第一个位为 0，第二个位为 0。

结论

与运算有一个结论：对于 mask = 1 << i，如果 (n & mask) == mask，则 n 的第 i + 1 位为 1，否则为 0。以下举个例子验证它。

对于 n = 1111 0110

• 如果使用 1 << 5 = 0010 0000 和 n 进行与运算，会得到 1111 0110 & 0010 0000 = 0010 0000 这个二进制数，而这个二进制数恰好与 1 << 5 相等，并且 n 的第 5 + 1 = 6 位恰好为 1。
• 如果使用 1 << 0 = 0000 0001 和 n 进行与运算，会得到 1111 0110 & 0000 0001 = 0000 0000 这个二进制数，而这个二进制数恰好与 1 << 0 不相等，并且 n 的第 0 + 1 = 1 位恰好为 0。

或运算

基础定义

对于 或运算，只需要看两个位是否同时为 0，如果同时为 0，则结果也为 0，其他情况全部为 1。例如 1010 | 1001 = 1011。这里的其他情况如下：

• 第一个位为 1，第二个位为 0。
• 第一个位为 0，第二个位为 1。
• 第一个位为 1，第二个位为 1。

结论

或运算也有一个结论：对于 mask = 1 << i，如果使用 n | mask，则会得到 将 n 的第 i + 1 位设置为 1、其他位不变 的二进制数。以下举个例子验证它。

对于 n = 0010 0000，如果使用 1 << 0 = 0000 0001 和 n 进行或运算，会得到 0010 0000 | 0000 0001 = 0010 0001 这个二进制数，这个二进制数与 n 不同的一点是其第 0 + 1 = 1 位被设置为 1。

回到本题

本题针对 int(32 位) 数字的每一位进行操作，针对第 i + 1 位，有如下操作：

• 创建一个掩码 mask = 1 << i。
• 使用 与运算 & 获取 n 的二进制数中第 i + 1 位的值。
• 如果第 i + 1 位为 1，则使用 或运算 | 将 结果 的第 32 - i 位设置为 1。这一步就是颠倒操作。

例如对于 n = 1000 0100 0010 0001 1100 0110 0011 1110，它的反转操作如下：

首先定义结果为 res = 0对第一位 (i = 0) 进行操作：
n = 1000 0100 0010 0001 1100 0110 0011 1110^
mask = 0000 0000 0000 0000 0000 0000 0000 0001
因为 n & mask = 0000 0000 0000 0000 0000 0000 0000 0000，不等于 mask，所以不需要对 res 进行设置。
操作完毕后 res = 0000 0000 0000 0000 0000 0000 0000 0000对第二位 (i = 1) 进行操作：
n = 1000 0100 0010 0001 1100 0110 0011 1110^
mask = 0000 0000 0000 0000 0000 0000 0000 0010
因为 n & mask = 0000 0000 0000 0000 0000 0000 0000 0010，等于 mask，所以将 res 的第 32 - 1 = 31 位设置为 1。
操作完毕后 res = 0100 0000 0000 0000 0000 0000 0000 0000....对第三十位的操作完毕后，res = 0111 1100 0110 0011 1000 0100 0010 0000对第三十一位 (i = 30) 进行操作：
n = 1000 0100 0010 0001 1100 0110 0011 1110^
mask = 0100 0000 0000 0000 0000 0000 0000 0000
因为 n & mask = 0000 0000 0000 0000 0000 0000 0000 0000，不等于 mask，所以不需要对 res 进行设置。
操作完毕后 res = 0111 1100 0110 0011 1000 0100 0010 0000对第三十二位 (i = 31) 进行操作：
n = 1000 0100 0010 0001 1100 0110 0011 1110^
mask = 1000 0000 0000 0000 0000 0000 0000 0000
因为 n & mask = 1000 0000 0000 0000 0000 0000 0000 0000，等于 mask，所以将 res 的第 32 - 31 = 1 位设置为 1。
操作完毕后 res = 0111 1100 0110 0011 1000 0100 0010 0001

代码

public class Solution {public int reverseBits(int n) {int res = 0;for (int i = 0; i < 32; i++) { // 对第 i + 1 位进行操作int mask = 1 << i; // 掩码，用于获取第 i + 1 位的值if ((n & mask) == mask) { // 如果 n 的第 i + 1 位的值为 1res |= 1 << (31 - i); // 则将 res 的第 32 - i 位设置为 1}}return res;}
}

222. 完全二叉树的节点个数

题目链接

222. 完全二叉树的节点个数

标签

位运算 树 二分查找 二叉树

简单题

思路

这道题是一道“简单题”，那就先想简单的解决方法：使用 深度优先搜索 获取一个节点的左、右子树中的节点数，然后加上当前节点的个数（1 个），即可得到 以当前节点为根节点的二叉树 的节点数。遇到当前节点为 null 的情况时，返回 0 表示没有节点即可。这种方法不针对完全二叉树，对所有的二叉树都适用，由于需要遍历每个节点，所以时间复杂度为 $O(n)$。

代码

class Solution {// 获取 以 curr 为根节点的二叉树 的节点数public int countNodes(TreeNode curr) {if (curr == null) { // 如果当前节点为 nullreturn 0; // 则返回 0}return countNodes(curr.left) // 获取左子树的节点数+ countNodes(curr.right) // 获取右子树的节点数+ 1; // 再加上本节点，就是 以 curr 为根节点的二叉树 的节点数}
}

困难题

思路

完全二叉树的三条规律

本题也可以是一道“困难题”，因为 完全二叉树 的规律和 数学 紧密相关，可以使用 完全二叉树 的以下三条规律：

规律一：完全二叉树的节点数被层数限制

结论：若一棵完全二叉树有 $h$ 层，那么它的节点数在区间 $[2^h,2^{h+1}-1]$ 内。

证明：

完全二叉树的前 $h-1$ 层都满了，共有
$$2^0+2^1+2^2+\cdots +2^{h-1}=\frac{1-2^{h-1}}{1-2}=2^{h-1}-1$$ 个节点，第 $h$ 层第节点数在区间 $[1,2^{h-1}]$ 内，所以加起来就是总节点数在区间 $[2^h,2^{h+1}-1]$ 内。

规律二：一直往左子节点找就能得到完全二叉树的层数

因为完全二叉树的底层（最下面一层）的节点都集中在 该层最左边的若干位置。如果底层只有一个节点，那么这个节点就在底层的最左边，如下面的二叉树所示：

    1/ \2   3/
4

规律三：可以通过位运算判断一个节点是否存在

结论：如果第 k 个节点位于第 h 层，则 k 的二进制数包含 h 位，其中最高位是 1，其余各位从 高位 到 低位 表示从 根节点 到 第 k 个节点 的路径，0 表示移动到左子节点，1 表示移动到右子节点。其中，第 k 个节点中的 k 是按照 层序遍历 的结果计算的。

举例：

这条规律证明起来比较麻烦，举个例子来验证它：

例如上面这棵完全二叉树，对于第 h = 3 层的节点 4，它是第 k = 4 个节点，k 的二进制数为 0100，第 h = 3 位（最高位）为 1，从第二位到第一位表示从根节点到这个节点的路径：第二位为 0，表示向左子节点走；第一位为 0，表示向左子节点走。即可走到节点 4。

如何使用这三条规律

我们可以使用 二分枚举答案 的思路来解决本题，答案的区间就可以使用第一条规律得到：$left=2^h,right=2^{h+1}-1$，其中 $h$ 是完全二叉树的层数，可以通过第二条规律得到。

枚举答案，猜想存在 mid = left + (right - left + 1 >> 1) 个节点，对其进行验证，如果存在，则扩大猜想值；否则缩小猜想值。这里的验证就可以使用第三条规律，通过判断第 mid 个节点是否存在，来判断是否存在 mid 个节点。

代码

class Solution {public int countNodes(TreeNode root) {if (root == null) {return 0;}int h = getCompleteTreeLevel(root);int left = 1 << h, right = (1 << (h + 1)) - 1;while (left < right) {int mid = left + (right - left + 1 >> 1); // 猜想节点数if (exists(root, h, mid)) { // 如果至少存在 猜想的节点数left = mid; // 扩大猜想的节点数} else { // 如果不存在 猜想的节点数right = mid - 1; // 则缩小猜想的节点数}}return left;}// 获取完全二叉树的层数private int getCompleteTreeLevel(TreeNode root) {int h = 0;TreeNode curr = root;while (curr.left != null) { // 直到左子节点为 nullcurr = curr.left; // 一直向左子节点遍历h++;}return h;}// 判断第 k 个节点是否存在，如果存在，则表示至少有 k 个节点private boolean exists(TreeNode root, int h, int k) {// 检测比第 h 位更低的 h - 1 位int bits = 1 << (h - 1); // 标记位（只有一位为 1，其余位全部为 0），用于获取移动的方向TreeNode curr = root;while (curr != null && bits > 0) { // 直到 curr 为 null，或者 标记位 为 0int dir = bits & k; // 获取本次移动的方向if (dir == 0) { // 0 表示移动到左子节点curr = curr.left;} else { // 1 表示移动到右子节点curr = curr.right;}bits >>= 1; // 让标记为向右移动一位，获取下一次移动的方向}return curr != null; // 如果 curr 为 null，则不存在 k 个节点；否则存在}
}

990. 等式方程的可满足性

题目链接

990. 等式方程的可满足性

标签

并查集 图 数组 字符串

思路

本题使用了 并查集 这个数据结构，分为以下三步：

1. 初始化 26 个小写字母组成的并查集。
2. 构建 相等字母 组成的并查集。
3. 查询不相等的字母是否属于同一个集合，如果属于，则矛盾，返回 false，否则在判断完毕后返回 true。

代码

class Solution {public boolean equationsPossible(String[] equations) {UnionFind uf = new UnionFind(26); // 为 26 个小写字母初始化一个并查集// 构建 相等字母 组成的并查集for (String equation : equations) {if (equation.charAt(1) == '=') {int x = equation.charAt(0) - 'a',y = equation.charAt(3) - 'a';uf.union(x, y);}}// 查询 不相等的字母 是否属于同一个集合，如果属于，则矛盾，返回 falsefor (String equation : equations) {if (equation.charAt(1) == '!') {int x = equation.charAt(0) - 'a',y = equation.charAt(3) - 'a';if (uf.find(x) == uf.find(y)) {return false;}}}return true; // 不矛盾，返回 true}private static class UnionFind {private final int[] parent; // parent[i] 表示第 i 个元素的父节点// 初始化并查集public UnionFind(int size) {parent = new int[size];for (int i = 0; i < size; i++) {parent[i] = i; // 初始时，每个元素的父节点都是自己}}// 查找 x 的根节点public int find(int x) {if (x != parent[x]) { // 如果 x 不是根节点return find(parent[x]); // 则寻找 x 的根节点并返回}return x; // 否则直接返回 x 自己}// 合并两个节点所在的集合public void union(int x, int y) {parent[find(x)] = find(y); // 让 x 的根节点 指向 y 的根节点}}
}