网站建设捌金手指下拉十六基金网站建设网站

这里是Themberfue

上一篇文章讲完了常见位运算的技巧以及总结

那么本章则通过五道题来运用这些技巧 

判定字符是否唯一

        题目解析

本题要求判断给定字符串中的字符是否唯一，也就是每个字符是否只出现一次

        算法讲解

· 本题用哈希表遍历每一个字符也可以解决

· 如果这题使用位运算的技巧的做题的话，还需引入一个位图的概念：众所周知，int类型有32个bit位，每个bit位不是0就是1，那么便可利用这一性质。

· 将这32个bit位看成一个长度为32的boolean类型的数组，0表示假，1表示真

· 再用到 判断一个数字的某一位是否为0，以及，将一个数字的某一位的0改为1。运用这两个位运算技巧便可解出此题。

        编写代码 

class Solution {public boolean isUnique(String astr) {char[] s = astr.toCharArray();// 鸽巢原理if (s.length > 26) return false;// 位图的思想 => 使用比特位存储信息int bitMap = 0;for (char ch: s) {int x = ch - 'a';if (((bitMap >> x) & 1) == 1) {return false;}bitMap |= 1 << x;}return true;}
}

丢失的数字

        题目解析

本题要求寻找丢失的那个数字，我觉得看到示例解释应该就能看懂了

        算法讲解 

· 我们额外创建一个数组，其长度应该为给定数组长度加一：比如示例3中，n = 9，那么我们的创建数组的长度应该为10，我们需要初始化数组为包含 [0, 9] 中所有数字。

· 有了这一数组，不难发现，除了给定数组那个丢失的数字，加上我们创建的数组，每个数字肯定出现了两次。

· 根据异或(^)运算符的特性，相同的两个数异或的结果为0，所以我们将这两个数组都异或在一起。那么结果就是那个丢失的数字。

· 我们不需要关系异或顺序，因为异或好比乘法，先乘还是后乘都是一样的。

        编写代码 

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

两整数之和

        题目解析

本题就是求给定两个数的和，但是切记不能使用 + - 运算符，不然回去等通知吧

         算法讲解

· 重复下面这个步骤，直到 b 等于 0 ，那么此时的 a 就是结果。

· 异或( ^ )操作符的本质就是无进位相加，所以我们再获取二数实际需要在哪个地方的进位就可以

· (a & b) << 1完成的就是这个操作

        编写代码

class Solution {public int getSum(int a, int b) {while (b != 0) {int carry = (a & b) << 1;a = a ^ b;b = carry;}return a;}
}

只出现一次的数字 II 

        题目解析

 

        算法讲解 

        编写代码 

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

消失的两个数字

        题目解析

 

        算法讲解 

        编写代码 

class Solution {public int[] missingTwo(int[] nums) {// 将所有数字异或在一起int xorsum = 0;for (int num: nums) xorsum ^= num;for (int i = 1; i <= nums.length + 2; i++) xorsum ^= i;// 找出两个数字比特位不同的那位int lsb = 0;while (true) {if (((xorsum >> lsb) & 1) == 1) break;else lsb++;}int type1 = 0, type2 = 0;for (int num: nums) {if (((num >> lsb) & 1) == 1) type1 ^= num;else type2 ^= num;}for (int i = 1; i <= nums.length + 2; i++) {if (((i >> lsb) & 1) == 1) type1 ^= i;else type2 ^= i;}return new int[]{type1, type2};}
}