【Java 刷题记录】位运算

位运算

33. 位1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中

设置位

的个数（也被称为汉明重量）。

示例 1：

输入：n = 11
输出：3
解释：输入的二进制串 1011 中，共有 3 个设置位。

示例 2：

输入：n = 128
输出：1
解释：输入的二进制串 10000000 中，共有 1 个设置位。

示例 3：

输入：n = 2147483645
输出：30
解释：输入的二进制串 11111111111111111111111111111101 中，共有 30 个设置位。

提示：

• 1 <= n <= 2³¹ - 1

进阶：

• 如果多次调用这个函数，你将如何优化你的算法？

class Solution {public int hammingWeight(int n) {int count = 0;while(n != 0) {count++;n &= n - 1;}return count;}
}

34. 比特位计数

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1：

输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10

示例 2：

输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

提示：

• 0 <= n <= 10⁵

进阶：

• 很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
• 你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）

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

35. 汉明距离

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

示例 1：

输入：x = 1, y = 4
输出：2
解释：
1   (0 0 0 1)
4   (0 1 0 0)↑   ↑
上面的箭头指出了对应二进制位不同的位置。

示例 2：

输入：x = 3, y = 1
输出：1

提示：

• 0 <= x, y <= 2³¹ - 1

class Solution {public int hammingDistance(int x, int y) {int n = x ^ y;int count = 0;while(n != 0) {count++;n &= n - 1;}return count;}
}

36. 只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

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

示例 2 ：

输入：nums = [4,1,2,1,2]
输出：4

示例 3 ：

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

提示：

• 1 <= nums.length <= 3 * 10⁴
• -3 * 10⁴ <= nums[i] <= 3 * 10⁴
• 除了某个元素只出现一次以外，其余每个元素均出现两次。

class Solution {public int singleNumber(int[] nums) {int n = nums.length;int ret = 0;for(int i = 0; i < n; i++) {ret ^= nums[i];}return ret;}
}

37. 只出现一次的数字 III

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

示例 1：

输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

示例 2：

输入：nums = [-1,0]
输出：[-1,0]

示例 3：

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

提示：

• 2 <= nums.length <= 3 * 10⁴
• -2³¹ <= nums[i] <= 2³¹ - 1
• 除两个只出现一次的整数外，nums 中的其他数字都出现两次

class Solution {public int[] singleNumber(int[] nums) {int x = 0;int n = nums.length;for(int i = 0; i < n; i++) {x ^= nums[i];}// 找到一个标志位（可以是任意一个，但是必须是准确的）int flag = x == Integer.MIN_VALUE ? x : x & (-x);// 根据标志位划分两个部分int ret1 = 0;int ret2 = 0;for(int i = 0; i < n; i++) {int number = nums[i];if((number & flag) == 0) {ret1 ^= number;}else {ret2 ^= number;}}return new int[]{ret1, ret2};}
}

38. 判定字符是否唯一

实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

示例 1：

输入: s = "leetcode"
输出: false 

示例 2：

输入: s = "abc"
输出: true

限制：

• 0 <= len(s) <= 100
• s[i]仅包含小写字母
• 如果你不使用额外的数据结构，会很加分。

class Solution {public boolean isUnique(String str) {int len = str.length();if(len > 26) return false;int bitMap = 0;for(int i = 0; i < len; i++) {int change = 1 << (str.charAt(i) - 'a');if((change & bitMap) == 0) bitMap |= change;else return false;}return true;}
}

39. 丢失的数字

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1：

输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 2：

输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 3：

输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。

示例 4：

输入：nums = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。

提示：

• n == nums.length
• 1 <= n <= 10⁴
• 0 <= nums[i] <= n
• nums 中的所有数字都 独一无二

class Solution {public int missingNumber(int[] nums) {int ret = 0;int n = nums.length;for(int i = 0; i < n; i++) {ret ^= i ^ nums[i];}return ret ^ n;}
}

40. 两整数之和

给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和。

示例 1：

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

示例 2：

输入：a = 2, b = 3
输出：5

提示：

• -1000 <= a, b <= 1000

class Solution {public int getSum(int a, int b) {while(b != 0) {int tmp = a;a ^= b; // 无进位相加b = (tmp & b) << 1; // 进位 carry}return a;}
}

41. 只出现一次的数字 II

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 **三次 。**请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

示例 1：

输入：nums = [2,2,3,2]
输出：3

示例 2：

输入：nums = [0,1,0,1,0,1,99]
输出：99

提示：

• 1 <= nums.length <= 3 * 10⁴
• -2³¹ <= nums[i] <= 2³¹ - 1
• nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

class Solution {public int singleNumber(int[] nums) {int ret = 0;for(int i = 0; i < 32; i++) {int sum = 0;for(int num : nums) {sum += (num >>> i) & 1;}ret |= (sum % 3) << i;}return ret;}
}

42. 消失的两个数字

给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？

以任意顺序返回这两个数字均可。

示例 1:

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

示例 2:

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

提示：

• nums.length <= 30000

class Solution {public int[] missingTwo(int[] nums) {int x = 0;int n = nums.length;for(int num : nums) {x ^=  num;}for(int i = 1; i <= n + 2; i++) {x ^= i;}int flag = x == Integer.MIN_VALUE ? x : (x & (-x));int lose1= 0;int lose2 = 0;for(int num : nums) {if((num & flag) == 0) lose1 ^= num;else lose2 ^= num;}for(int i = 1; i <= n + 2; i++) {if((i & flag) == 0) lose1 ^= i;else lose2 ^= i;}return new int[]{lose1, lose2};}
}