兰州公司做网站,建设网站有哪些公司,zzcms网站开发,如何做营销活动这里是Themberfue 上一篇文章讲完了常见位运算的技巧以及总结 那么本章则通过五道题来运用这些技巧 判定字符是否唯一 题目解析 本题要求判断给定字符串中的字符是否唯一#xff0c;也就是每个字符是否只出现一次 算法讲解 本题用哈希表遍历每一个字符也可以解决 如果这题使… 这里是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};}
}
