网站改版怎么弄,做有网被视频网站有哪些,谷歌优化排名公司,drupal个人门户网站开发文章目录 一、算法原理常见的位运算总结 二、算法实战1. leetcode面试题01.01. 判断字符是否唯一2. leetcode268 丢失的数字3. leetcode371 两整数之和4. leetcode004 只出现一次的数字II5. leetcode面试题17.19. 消失的两个数字 三、总结 一、算法原理
计算机中的数据都以二进… 文章目录 一、算法原理常见的位运算总结 二、算法实战1. leetcode面试题01.01. 判断字符是否唯一2. leetcode268 丢失的数字3. leetcode371 两整数之和4. leetcode004 只出现一次的数字II5. leetcode面试题17.19. 消失的两个数字 三、总结 一、算法原理
计算机中的数据都以二进制形式存储和处理位运算直接对二进制位进行操作。常见的位运算符包括与、或|、异或^、取反~和左移、右移等。 常见的位运算总结
基础位运算 给一个数n确定它的二进制表示中第x位是0还是1 将一个数n的二进制表示的第x位修改成1 将一个数n的二进制表示的第x位修改成0 位图的思想 提取一个数(n)二进制表示中最右侧的1 干掉一个数(n)二进制表示中最右侧的1 位运算的优先级 能加括号就加括号异或(^)运算的运算律 二、算法实战
1. leetcode面试题01.01. 判断字符是否唯一 判断字符是否唯一 解题思路位图的思想
这道题目我们可以使用位图的思想来解决因为题目告诉我们字符串中只有小写字母所以我们只需要一个int类型的整数来充当位图的32个bit位即可。
首先将位图的所有bit位置为零默认字符串中的字符都未在位图中出现过。然后遍历整个字符串检测该字符是否在位图中出现过如果当前字符未在位图中出现过说明当前字符是第一次出现此时我们将其在位图中的位置当前字符-a置为1即可然后接着向后遍历字符串如果该字符再次出现我们就可以从位图中检测到该字符已经在出现过了。直接返回false即可否则继续向后遍历字符串如果遍历所有字符后发现都只出现一次则说明该字符串符合题意。
代码实现
class Solution {
public:bool isUnique(string astr) {int num 0;for(int i 0; i astr.size(); i){int index astr[i] - a;if(((numindex) 1) 1)return false;elsenum | 1 index;}return true;}
};2. leetcode268 丢失的数字 丢失的数字 解题思路异或运算
因为题目中告诉我们数组中【1~n】丢失了一个数字所以我们可以先将数组中的数字 ^ 起来然后在将这个 ^ 的结果与【1~n】中所有的数字异或因为按位 ^ 运算满足交换律和结合律所以按位 ^ 的结果中丢失的数字出现了一次其余的数字都出现了两次将这一堆数字异或起来结果即为丢失的数字。 代码实现
class Solution {
public:int missingNumber(vectorint nums) {int ret 0;for(auto e : nums)ret ^ e;for(int i 1; i nums.size(); i)ret ^ i;return ret;}
};3. leetcode371 两整数之和 两整数之和 解题思路异或运算-无进位相加
因为题目要求我们不能使用运算符和-来计算两整数之和因此我们可以将整数 a 和 b 的和拆分为 a 和 b 的无进位相加结果与进位结果的和无进位相加结果 我们可以使用两整数^来实现进位结果我们可以使用(a b) 1来实现。下面我们来举一个例子 每次将无进位相加结果与进位结果的和分别赋予a和b循环此过程直到进位为 0。最终a就是我们所要求的结果。当我们赋给无符号类型一个超出它表示范围的值时结果是初始值对无符号类型表示数值总数取模的余数。因此我们可以使用无符号类型来防止溢出。
代码实现
lass Solution {
public:int getSum(int a, int b) {while(b ! 0){int x a ^ b; // 先算出无进位相加的结果unsigned int carry (a b) 1; // 算出进位a x;b carry;}return a;}
};4. leetcode004 只出现一次的数字II 只出现一次的数字II 解题思路
数组中的每个元素的每一个二进制位不是1就是0而题目中又告诉我们只有一个元素出现一次其余元素都出现了三次所以对于数组中的每一个元素 x我们使用位运算 (x i) 1 得到 x 的第 i 个二进制位并将它们相加再对 3 取余得到的结果一定为 0 或 1即为答案的第 i 个二进制位。
所以答案的第 i 个二进制位就是数组中所有元素的第 i 个二进制位之和除以 3 的余数。可以先初始化一个ret 0然后根据余数的值来判断该数对应的二进制位应该置为0还是1如果余数为1我们则需要手动将该位置置为1ret | (1 i)否则则不需要处理。
代码实现
class Solution {
public:int singleNumber(vectorint nums) {int ret 0;for(int i 0; i 32; i){int cnt 0;for(auto e : nums)cnt ((ei)1);if(cnt % 3)ret | (1 i);}return ret;}
};5. leetcode面试题17.19. 消失的两个数字 消失的两个数字 解题思路
这道题目其实我们可以用力扣的第260题 只出现一次的数字III 的思想来做具体解决方式如下
因为数组中包含从 1 到 N 所有的整数但其中缺了两个数字现在数组的长度为n。所以数组中原本应该包含的数字是【1n 2】。我们可以将原来数组中的数字和【1n 2】组合到一起现在我们就可以将问题转化一下求数组中只出现一次的两个数字。
解决这个问题我们可以分为两步整体异或和分组异或。整体异或将题目给出的数组中的所有数字和【1n 2】中所包含的数字全部异或起来得到的结果就是只出现一次的两个数字的异或结果a^b。接下来我们需要提取出该数字二进制表示中最低位的1。假设该位置为第k位我们就可以把 所有数中的元素题目中给出的数字和【1n 2】的数字分成两类其中一类包含所有二进制表示的第 k 位为 0 的数另一类包含所有二进制表示的第 k 位为 1 的数。
对于任意一个在 所有元素中 出现两次的元素该元素的两次出现会被包含在同一类中对于任意一个在所有元素中只出现了一次的元素即 x1 和 x2 他们会被包含在不同的类中。
因此我们将这两类元素分别异或起来就可以得到不同的两个结果一个结果是x1另一个结果是x2这两个数字则是只出现一次的两个数字即本题中我们需要寻找的两个消失的数字。
代码实现
class Solution {
public:vectorint missingTwo(vectorint nums) {int ret 0;for(int i 1; i nums.size()2; i)ret ^ i;for(auto e : nums) ret ^ e;int lowbit ret -ret; // 找出最后一个不同的比特位int ret1 0, ret2 0;for(int i 1; i nums.size()2; i){ // 分组异或if(lowbit i) ret1 ^ i;else ret2 ^ i;}for(auto e : nums){if(lowbit e) ret1 ^ e;else ret2 ^ e;}return {ret1, ret2};}
};三、总结
位运算可以直接操控数字的二进制位节约内存使程序运行更快可靠性高。在算法中使用位运算可以大大降低算法的时间复杂度和空间复杂度恰当的位运算使用也能使程序变得更加简洁和优美。
