位运算专题——常见位运算位图的使用力扣实战应用

本文主要是介绍位运算专题——常见位运算位图的使用力扣实战应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

1、常见位运算

2、算法应用【leetcode】

2.1 判断字符是否唯一【面试题 】

 2.1.1 算法思想【位图】

 2.1.2 算法代码

2.2 只出现一次的数字 III

2.2.1 算法思想

2.2.2 算法代码

2.3 丢失的数字

2.3.1 算法思想

2.3.2 算法代码

2.4 两整数之和

2.4.1 算法思想

2.4.2 算法代码

2.5 只出现一次的数字 II

2.5.1 算法思想

2.5.2 算法代码

2.6 消失的两个数字【面试题】(leetcode难度:困难)

2.6.1 算法思想

2.6.2 算法代码

---

1、常见位运算

想要灵活使用位运算，基础的位运算操作是我们必须掌握的，常见位运算操作如下：

1. 基础位运算操作符
2. 判断某一数二进制表示中第x位是0还是1
3. 如何将某一数其二进制表示中第x位修改为1
4. 如何将某一数其二进制表示中第x位修改为0
5. 掌握位图思想
6. 提取某一数二进制表示中最右侧的1
7. 干掉某一数二进制表示中最右侧的1(将右侧的1修改为0)
8. 位运算符的优先级
9. 异或(^)的使用

大家可以先思考，尽可能的多想，答案总结我放在下图中。 

---

2、算法应用【leetcode】

2.1 判断字符是否唯一【面试题 】

. - 力扣（LeetCode）

 2.1.1 算法思想【位图】

本题解法具有多种，可以使用哈希表，也可以使用位图，这里给出最优的位图解法(节省空间消耗)。

因为字符均为小写字母，共有26个不同字符，而位图最多有32个bit位，故可使用位图。

1. 每个字符占一个bit位
2. 遍历字符串，将出现的字符其位图中的位置设置为1
3. 设置前先查看位图，若为0，则设置为1；若为1，则说明该字符已经出现过了，为重复字符，返回false。

 2.1.2 算法代码

class Solution {public boolean isUnique(String astr) {//鸽巢原理if(astr.length() > 26) return false;//位图int bitMap = 0;for(int i = 0; i < astr.length(); i++) {//确定该字符在位图中的位置int bit = astr.charAt(i) - 'a';//该字符已经出现过了if((bitMap & (1 << bit)) != 0) return false;//该字符没有出现过，设置为1else bitMap |= (1 << bit);}return true;}
}

---

2.2 只出现一次的数字 III

. - 力扣（LeetCode）

2.2.1 算法思想

1. 因为数组中恰好有两个元素只出现一次，其余所有元素均出现两次，故我们可以利用异或(^)运算符“消消乐”的特性，将全部元素异或，得到的结果就是这两个不同的元素相异或的结果x
2. 因为这两个元素不同，故x一定不为0，其二进制表示中一定有某一bit位为1，而我们可以使用"x & (-x)"提取出最右侧的1
3. 而这两个不同的元素中的这一bit位一定是不相同的，根据这个特性，将数组中的元素分为两组，一组为元素二进制的这一位为0，一组为元素二进制的这一位为1，将不同组中的元素相异或，(重复元素再次消去)就得到这两个单独出现的元素

2.2.2 算法代码

class Solution {public int[] singleNumber(int[] nums) {int x = 0;for (int num : nums) {x ^= num;}int last1 = x & -x;int[] ret = new int[2]; for(int num : nums) {ret[(num & last1) == 0 ? 0 : 1] ^= num;}/**for (int num : nums) {int val = num & last1;if (val == 0) {ret[0] ^= num;} else {ret[1] ^= num;}} */return  ret;}
}

---

2.3 丢失的数字

. - 力扣（LeetCode）

2.3.1 算法思想

解题思想很简单，只需将数组中的数据和原应出现的数据相异或，得到的就是确实的数据。

注意：不需额外创建数组来表示[0，n]中原应出现的数据，只需在遍历原数组的同时，异或上下标i即可。

2.3.2 算法代码

class Solution {public int missingNumber(int[] nums) {//异或位运算int x = 0;int len = nums.length;for(int i = 0; i < len; i++) {x ^= (nums[i] ^ i);}return x ^ len;}
}

---

2.4 两整数之和

. - 力扣（LeetCode）

2.4.1 算法思想

解决本题，我们需要充分的了解异或运算符(^)的特性——无进位相加。

1. 我们可以通过异或得到两数无进位相加的结果res
2. 接着使用 & 得到两数相加的进位结果，因为是进位的结果，所以还要左移一位，得到carry
3. 将carry和res相加就得到最终结果(因为不能使用+，所以要循环以上过程，直至进位为0)

2.4.2 算法代码

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

---

2.5 只出现一次的数字 II

. - 力扣（LeetCode）

2.5.1 算法思想

1.  因为每一个重复出现的元素的次数都是相等的(n)，所以每个相同元素的某一bit位之和也是n的倍数。
2. 所以我们可以进行取模运算(%)得到单独出现的那个元素的bit位数值。
3. 循环32次，便能得到该元素的准确数值

2.5.2 算法代码

class Solution {public int singleNumber(int[] nums) {int ret = 0;for(int x = 0; x <32; x++) {int bitSum = 0;for(int n : nums) {bitSum += (n >> x) & 1;}//得到单独出现元素的比特位数值//bit %= n;bitSum %= 3;ret |= (bitSum << x);}return ret;}
}

---

2.6 消失的两个数字【面试题】(leetcode难度:困难)

2.6.1 算法思想

虽然力扣为本题标注的难度为困难级别，实际上也并不困难。

本题解法非常简单，其实就是上文 丢失的数字+只出现一次的数字III 两题思想的结合，如果你跟着本文一步一步的学习下来，那解决本题就是分分钟钟的事，非常的简单。

1. 将应出现的完整数据和数组数据进行整体异或，得到缺失的两个数字的异或结果。
2. 提取最右侧的1，并将应出现的完整数据和数组数据进行分组异或，就得到所消失的两个数字。

2.6.2 算法代码

class Solution {public int[] missingTwo(int[] nums) {//丢失的数字 + 只出现一次的数字IIIint n = nums.length;int[] ret = new int[2];int x = 0;//得到两数异或结果for(int i = 1; i <= n + 2; i++) x ^= i;for(int i = 0; i < n; i++) x ^= nums[i];//提取最右侧1int check = x & (-x);//分组异或 --> 得到结果for(int num : nums) ret[(num & check) == 0 ? 0 : 1] ^= num;for(int i = 1; i <= n + 2; i++) ret[(i & check) == 0 ? 0 : 1] ^= i;return ret;}
}

---

END

这篇关于位运算专题——常见位运算位图的使用力扣实战应用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---