【LeetCode】妙用位运算解题

ゝ一纸荒年。 2022-11-09 14:24 224阅读 0赞

## 【LeetCode】妙用位运算解题 ##

### 文章目录 ###

*   *  【LeetCode】妙用位运算解题
     *   *  交替位二进制数★
         *  插入★
         *  数字范围按位与★★
         *  比特位计数★★
         *  下一个数★★
         *  消失的两个数字★★★
         *  修改后的最大二进制字符串★★

详细位运算知识见往期总结 [♢位运算♢常用公式及练习详解][Link 1]

> 注：★为easy，★★为medium，★★★为hard

### 交替位二进制数★ ###

[693. 交替位二进制数][693.]

【**题目**】给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。

**提示：**

*  `1 <= n <= 231 - 1`

【**示例**】

输入：n = 5
    输出：true
    解释：5 的二进制表示是：101
    -----------------------------
    输入：n = 5
    输出：true
    解释：5 的二进制表示是：101

【**解题思路**】

取相邻两位比较是否相同即可

class Solution {
        
        public boolean hasAlternatingBits(int n) {
        
            while (n > 0) {
        
                if ((n & 1) == ((n >> 1) & 1)) {
        
                    return false;
                }
                n >>= 1;
            }
            return true;
        }
    }

递归版

class Solution {
        
        public boolean hasAlternatingBits(int n) {
        
            return n == 0 || (n & 1) != ((n >> 1) & 1) && hasAlternatingBits(n >> 1);
        }
    }

--------------------

### 插入★ ###

[面试题 05.01. 插入][05.01.]

【**题目**】给定两个整型数字 `N` 与 `M`，以及表示比特位置的 `i` 与 `j`（`i <= j`，且从 0 位开始计算）。

编写一种方法，使 `M` 对应的二进制数字插入 `N` 对应的二进制数字的第 `i ~ j` 位区域，不足之处用 `0` 补齐。具体插入过程如图所示。

![在这里插入图片描述][20210315194529424.gif_pic_center]

题目保证从 `i` 位到 `j` 位足以容纳 `M`， 例如： `M = 10011`，则 `i～j` 区域至少可容纳 5 位。

【**示例**】

输入：N = 1024(10000000000), M = 19(10011), i = 2, j = 6
     输出：N = 1100(10001001100)
    ------------------------------------------------------------------
     输入： N = 0, M = 31(11111), i = 0, j = 4
     输出：N = 31(11111)

【**解题思路**】

将结果区间分为三部分：

*  插入区间左边
 *  插入区间
 *  插入区间右边

最后将得到的三部分区间相与即可

> 注意：java里面32位整数n左移32位的结果是n循环左移而不是置零，由于测试用例存在j=31，代码 `1<<j+1`应改为 `1<<j<<1`

class Solution {
        
        public int insertBits(int N, int M, int i, int j) {
        
            return (N >> j >> 1 << j << 1) | (N ^ ((N >> i) << i)) | (M << i);
        }
    }

--------------------

### 数字范围按位与★★ ###

[201. 数字范围按位与][201.]

【**题目**】给你两个整数 `left` 和 `right` ，表示区间 `[left, right]` ，返回此区间内所有数字 **按位与** 的结果（包含 `left` 、`right` 端点）。

**提示：**

*  `0 <= left <= right <= 231 - 1`

【**示例**】

输入：left = 5, right = 7
    输出：4

【**解题思路**】

如果有一位是0，区间内所有数字这一位相与（&）都为0。

寻找最长公共前缀。

class Solution {
        
        public int rangeBitwiseAnd(int left, int right) {
        
            int k = 0;
            while (left != right) {
        
                left >>= 1;
                right >>= 1;
                k++;
            }
            return left << k;
        }
    }

改进版，每次去掉最后一个1

class Solution {
        
        public int rangeBitwiseAnd(int left, int right) {
        
            while (right > left) {
        
                right = right & (right - 1);
            }
            return right;
        }
    }

--------------------

### 比特位计数★★ ###

[338. 比特位计数][338.]

【**题目**】给定一个非负整数 **num**。对于 **0 ≤ i ≤ num** 范围中的每个数字 **i** ，计算其二进制数中的 1 的数目并将它们作为数组返回。  
**进阶**:

给出时间复杂度为`O(n*sizeof(integer))`的解答非常容易。但你可以在线性时间`O(n)`内用一趟扫描做到吗？  
要求算法的空间复杂度为O`(n)`。  
你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 \_\_builtin\_popcount）来执行此操作。

【**示例**】

输入: 5
    输出: [0,1,1,2,1,2]

【**解题思路**】

方法一：库函数

class Solution {
        
        public int[] countBits(int num) {
        
            int[] res = new int[num + 1];
            for (int i = 0; i <= num; i++) {
        
                res[i] = Integer.bitCount(i);
            }
            return res;
        }
    }

方法二：动态规划

class Solution {
        
        public int[] countBits(int num) {
        
            int[] res = new int[num + 1];
            for (int i = 1; i <= num; i++) {
        
                res[i] = res[i & (i - 1)] + 1;
            }
            return res;
        }
    }

方法三：动态规划

class Solution {
        
        public int[] countBits(int num) {
        
            int[] res = new int[num + 1];
            for (int i = 1; i <= num; i++) {
        
                res[i] = res[i >> 1] + (i & 1);
            }
            return res;
        }
    }

--------------------

### 下一个数★★ ###

[面试题 05.04. 下一个数][05.04.]

【**题目**】下一个数。给定一个正整数，找出与其二进制表达式中1的个数相同且大小最接近的那两个数（一个略大，一个略小）。

**提示:**

1.  `num`的范围在`[1, 2147483647]`之间；
2.  如果找不到前一个或者后一个满足条件的正数，那么输出 `-1`。

【**示例**】

输入：num = 2（或者0b10）
     输出：[4, 1] 或者（[0b100, 0b1]）
    ---------------------------------------
     输入：num = 1
     输出：[2, -1]

【**解题思路**】

求最大值，

*  使用公式`num & -num`得到二进制位的最后一个1即`lastOne`(1000110 -> 10)
 *  将`lastOne`与`num`相加得到左边1的位置（消除右边连续1,比num稍大）（1000110 + 10 -> 1001000）
 *  然后将剩余连续1放在末尾即可（1001000 + 1 = 1001001）

求最小值，

调用函数连续取反即可（可拿示例自己推算）

class Solution {
        
        public int[] findClosedNumbers(int num) {
        
            if (num == 1) return new int[]{
        2, -1};
            if (num == 2147483647) return new int[]{
        -1, -1};
            int big = nextMax(num);
            int small = ~nextMax(~num);
            return new int[]{
        big, small};
        }
    
        private int nextMax(int num) {
        
            int lastOne = num & -num;
            int left = num + lastOne;
            return left | (num & ~left) / lastOne >> 1;
            //return left + ((num & ~left) / lastOne >> 1);
        }
    }

--------------------

### 消失的两个数字★★★ ###

[面试题 17.19. 消失的两个数字][17.19.]

【**题目**】给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？以任意顺序返回这两个数字均可。

**提示：**

*  `nums.length <= 30000`

【**示例**】

输入: [2,3]
    输出: [1,4]

【**解题思路**】

方法一：求和

class Solution {
        
        public int[] missingTwo(int[] nums) {
        
            int n = nums.length + 2;
            int sum = 0;
            for (int x : nums) sum += x;
            int sumTwo = n * (n + 1) / 2 - sum;
            int limit = sumTwo / 2;
            sum = 0;
            for (int i = 0; i < nums.length; i++) {
        
                if (nums[i] <= limit) sum += nums[i];
            }
            int one = limit * (limit + 1) / 2 - sum;
            int two = sumTwo - one;
            return new int[]{
        one, two};
        }
    }

方法二：位运算

class Solution {
        
        public int[] missingTwo(int[] nums) {
        
            int n = nums.length + 2;
            int e = 0;
            for (int x : nums) {
        
                e ^= x;
            }
            for (int i = 1; i <= n; i++) {
        
                e ^= i;
            }
            int t = e & (-e), eo = e;
            for (int x : nums) {
        
                if ((x & t) != 0) {
        
                    eo ^= x;
                }
            }
            for (int i = 1; i <= n; i++) {
        
                if ((i & t) != 0) {
        
                    eo ^= i;
                }
            }
            return new int[]{
        eo, e ^ eo};
        }
    }

--------------------

附加题型（顺便把这道好题总结下哈哈哈）

### 修改后的最大二进制字符串★★ ###

[1702. 修改后的最大二进制字符串][1702.]

【**题目**】给你一个二进制字符串 `binary` ，它仅有 `0` 或者 `1` 组成。你可以使用下面的操作任意次对它进行修改：

操作 1 ：如果二进制串包含子字符串 “`00`” ，你可以用 “`10`” 将其替换。  
比方说， `"00010" -> "10010"`  
操作 2 ：如果二进制串包含子字符串 “`10`” ，你可以用 “`01`” 将其替换。  
比方说， `"00010" -> "00001"`  
请你返回执行上述操作任意次以后能得到的 最大二进制字符串 。如果二进制字符串 x 对应的十进制数字大于二进制字符串 y 对应的十进制数字，那么我们称二进制字符串 x 大于二进制字符串 y 。

**提示：**

*  `1 <= binary.length <= 105`
 *  `binary` 仅包含 `'0'` 和 `'1'` 。

【**示例**】

输入：binary = "000110"
    输出："111011"
    解释：一个可行的转换为：
    "000110" -> "000101" 
    "000101" -> "100101" 
    "100101" -> "110101" 
    "110101" -> "110011" 
    "110011" -> "111011"

【**解题思路**】

智力题，

`10->01`，可以将1移动至最右边，左边都为0，`00->10`，可以把最后一位变为0，其余位为1，若字符串都为1，则最大；若只有一个0，则不作变换；其他情况可以把字符串变为只有一个0的情况

*  使用begin标记第一个0出现的位置
 *  使用count记录共有多少个0出现
 *  若count <2，则不做变换
 *  若count>=2，则使用1赋值res\[n\]，然后将res\[begin + count - 1\]置为0，即将0最后右移至此位置了

class Solution {
        
        public String maximumBinaryString(String binary) {
        
            int n = binary.length();
            int begin = (int)1e6, count = 0;
            for (int i = 0; i < n; i++) {
        
                if (binary.charAt(i) == '0') {
        
                    count++;
                    begin = Math.min(begin, i);
                }
            }
            if (count < 2) return binary;
            char[] res = new char[binary.length()];
            Arrays.fill(res, '1');
            res[begin + count - 1] = '0';
            return new String(res);
        }
    }

[Link 1]: https://blog.csdn.net/weixin_44368437/article/details/111089587
[693.]: https://leetcode-cn.com/problems/binary-number-with-alternating-bits/
[05.01.]: https://leetcode-cn.com/problems/insert-into-bits-lcci/
[20210315194529424.gif_pic_center]: /images/20221023/93cb2396949342bebc4f77910a2133d3.png
[201.]: https://leetcode-cn.com/problems/bitwise-and-of-numbers-range/
[338.]: https://leetcode-cn.com/problems/counting-bits/
[05.04.]: https://leetcode-cn.com/problems/closed-number-lcci/
[17.19.]: https://leetcode-cn.com/problems/missing-two-lcci/
[1702.]: https://leetcode-cn.com/problems/maximum-binary-string-after-change/