【专题五】位运算（2）

📝前言说明：

• 本专栏紧张记载本人的基础算法学习以及LeetCode刷题记载，按专题分别
  
• 每题紧张记载：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）字斟句酌，更好的解法和独特的头脑（假如有的话）
  
• 文章中的明白仅为个人明白。如有错误，感谢纠错
  

   🎬个人简介：积极学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习条记，Linux
🎀CSDN主页 愚润泽
  

---

面试题 01.01. 判断字符是否唯一

标题链接：https://leetcode.cn/problems/is-unique-lcci/description/

个人解

思绪：

• 不利用额外的数据布局，但是我们可以用一个整型的比特位来存储
  
• a 存在第 0 个bit位，也就是：hash >> 0
  
• 0 代表没有出现过，1 代表出现过了
  
• 每个字符本质是一个 ASCII 的一个整型
  
• 留意优先级 == 优先级高于 >>, 发起多加括号
  

用时：10:00
屎山代码：

1. class Solution {
2. public:
3.     bool isUnique(string astr) {
4.         int n = astr.size(), hash = 0;
5.         if(n > 26)
6.             return false;
7.         for(auto c: astr)
8.         {
9.             int location = c - 'a';
10.             if(((hash >> location) & 1) == 0)
11.                 hash |= (1 << location); // 对应位置为 0 ，改为 1
12.             else
13.                 return false;
14.         }
15.         return true;
16.     }
17. };

复制代码

时间复杂度：O(n)
空间复杂度：O(1)

---

268. 丢失的数字

标题链接：https://leetcode.cn/problems/missing-number/description/

个人解

思绪：

• “创建” 一个包罗 0 - n全部元素的数组（没必要真的创建）
  
• 然后两个数组的全部元素做 ^ 运算
  
• 因为 a ^ a == 0，以是末了得到的就是没有出现的数
  
• 固然，这道题排序 + 二分也行（但是排序时间复杂度 ： O(nlogn)）
  

用时：5:00
屎山代码：

1. class Solution {
2. public:
3.     int missingNumber(vector<int>& nums) {
4.         int n = nums.size(), ans = 0;
5.         for(auto x:nums)
6.             ans ^= x;
7.         for(int i = 0; i <= n; i++)
8.             ans ^= i;
9.         return ans;
10.     }
11. };

复制代码

时间复杂度：O(n)
空间复杂度：O(1)

---

371. 两整数之和

标题链接：https://leetcode.cn/problems/sum-of-two-integers/description/

---

这道题没写出来
优质解

思绪：

• 不能利用+和-，那么就利用位运算
  
• 对于每一位：异或运算（a ^ b）==无进位相加（就是不管进位，只生存当前为相加效果），那么进位怎么处理惩罚呢？
  
• 因为只有1 1的时间才有进位，以是我们可以用 &
  
• 对于每一个相加的位：当且仅有1 & 1 == 1，这时间就代表有进位
  
• 留意进位是往前进位，以是要 << 1，即：(a & b) << 1得到进位
  
• 无进位 + 进位就是答案，但是，因为有大概这两个数相加的时间也出现进位，以是要重复上面的操纵，直到进位为0
  

代码：

1. class Solution {
2. public:
3.     int getSum(int a, int b)
4.     {
5.         int carry = (a & b) << 1; // 进位
6.         int s = a ^ b; // 无进位相加
7.         while(carry != 0)
8.         {
9.             int newcarry = (s & carry) << 1; // 进位（在 s 改变前，算出本次进位）
10.             s ^= carry; // 加上进位
11.             carry = newcarry;
12.         }
13.         return s;
14.     }
15. };

复制代码

时间复杂度：O(log(max_int))
空间复杂度：O(1)

---

137. 只出现一次的数字 II

标题链接：https://leetcode.cn/problems/single-number-ii/description/

个人解

思绪：

• 把每个数的每个比特位拿出来看，依次盘算答案的每一个比特位
  
• 对于非答案数：因为每个比特位出现三次且雷同，即：3个0，大概3个1，%3 == 0
  
• 以是我们只必要将全部输数的比特位相加，然后%3得到的就是答案的当前比特位的值
  

代码：

1. class Solution {
2. public:
3.     int singleNumber(vector<int>& nums) {
4.         int ans = 0;
5.         for(int i = 0; i < 32; i++)
6.         {
7.             int s = 0; // 当前比特位所有数相加的结果
8.             for(auto x: nums)
9.             {
10.                 s += (x >> i) & 1;
11.             }
12.             ans |= ((s % 3) << i);
13.         }
14.         return ans;
15.     }
16. };

复制代码

时间复杂度：O(n)
空间复杂度：O(1)

---

面试题 17.19. 消散的两个数字

标题链接：https://leetcode.cn/problems/missing-two-lcci/description/

个人解

思绪：

• 这道题就即是：第268题 + 第260题。这两道题都写过，我就不多说了。
  

用时：15:00
屎山代码：

1. class Solution {
2. public:
3.     vector<int> missingTwo(vector<int>& nums) {
4.         int s = 0, n = nums.size();
5.         for(auto x: nums)
6.             s ^= x;
7.         for(int i = 1; i <= n + 2; i++)
8.             s ^= i;
9.         // 此时 s == a ^ b
10.         unsigned int lowbit = s & (-s);
11.         int a = 0, b = 0;
12.         for(auto x: nums)
13.         {
14.             if(x & lowbit)
15.                 a ^= x;
16.             else
17.                 b ^= x;
18.         }
19.         for(int i = 1; i <= n + 2; i++)
20.         {
21.             if(i & lowbit)
22.                 a ^= i;
23.             else
24.                 b ^= i;
25.         }
26.         return {a, b};
27.     }
28. };

复制代码

时间复杂度：O(n)
空间复杂度：O(1)

---

优质解

和我的思绪大差不差。

---

   🌈我的分享也就到此竣事啦🌈
要是我的分享也能对你的学习起到资助，那简直是太酷啦！
若有不敷，还请大家多多指正，我们一起学习交换！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能心满意足，每天开心！！！