【LeetCode】位运算 bit manipulation（共32题）

发布时间：2020-12-14 04:23:58 所属栏目：大数据来源：网络整理

导读：【78】Subsets ? 给了一个 distinct 的数组，返回它所有的子集。 Example:Input: nums = [ 1 , 2 , 3 ]Output:[ [ 3 ],[ 1 ],[ 2 ],[ 1 , 3 ],[ 2 , 2 ],[]] ? 题解：我是直接dfs（backtracking）了，有个小地方写错了(dfs那里)，至少调整了十多分钟，下次不

【78】Subsets?

给了一个 distinct 的数组，返回它所有的子集。

Example:
Input: nums = [1,2,3]
Output:
[
  [3],[1],[2],[1,3],[2,2],[]
]

?题解：我是直接dfs（backtracking）了，有个小地方写错了(dfs那里)，至少调整了十多分钟，下次不要写错了。

 1 class Solution {
 2 public:
 3     vector<vector<int>> subsets(vector<int>& nums) {
 4         n = nums.size();
 5         vector<int> visit(n,0);
 6         vector<int> temp;
 7         if (n == 0) { return ans; }
 8         dfs(nums,visit,temp,0);
 9         return ans;
10     }
11     void dfs(const vector<int>& nums,vector<int>& visit,vector<int>& temp,int cur_idx) {
12         ans.push_back(temp);
13         if (cur_idx == n) { return; }
14         for (int i = cur_idx; i < n; ++i) {
15             if (!visit[i]) {
16                 visit[i] = 1;
17                 temp.push_back(nums[i]);
18                 dfs(nums,i + 1); //一开始写成了 dfs(nums,cur_idx + 1) 挂了半天
19                 visit[i] = 0;
20                 temp.pop_back();
21             }
22         }
23         return;
24     }
25     vector<vector<int>> ans;
26     int n;
27 };

backtracking

我看分类是位运算，学习一下位运算解法。https://leetcode.com/problems/subsets/discuss/27288/My-solution-using-bit-manipulation

题解的解释参考：https://www.mathsisfun.com/sets/power-set.html?（有点像状态压缩的感觉）

 1 //bit manipulation,我认为是状态压缩的最简单的题.
 2 class Solution {
 3 public:
 4     vector<vector<int>> subsets(vector<int>& nums) {
 5         const int n = nums.size();
 6         if (n == 0) { return vector<vector<int>>{}; }
 7         // n 个元素一共有 2^n 个子集。
 8         int tot = pow(2,n);
 9         vector<vector<int>> ans(tot,vector<int>{});
10         // 然后用二进制一个一个往里面塞
11         for (int i = 0; i < n; ++i) {
12             for (int j = 0; j < tot; ++j) {
13                 if (j >> i & 1) {
14                     ans[j].push_back(nums[i]);
15                 }
16             }
17         }
18         return ans;
19     }
20 
21 };

bit manipulation

【136】Single Number?（2018年11月4日）（剑指offer上有个变种题，有两个数只出现了一次，求出出现一次的这两个数）

给了一个数组，说数组里面除了一个数只出现了一次，其他数都出现了两次。找出只出现一次的那个数。

题解：出现两次的数取异或之后为0，把全部数字异或起来，最后结果就是要求的那个数。

 1 class Solution {
 2 public:
 3     int singleNumber(vector<int>& nums) {
 4         int ans = 0;
 5         for (int i = 0; i < nums.size(); ++i) {
 6             ans ^= nums[i];
 7         }
 8         return ans;
 9     }
10 };

View Code

【137】Single Number II?

【169】Majority Element?

【187】Repeated DNA Sequences?

【190】Reverse Bits?

【191】Number of 1 Bits?（2018年11月4日，无聊做的）

给了一个数的 hamming weight，返回它的二进制中? 1 的个数。

题解：方法同 231， n & (n-1) 这个表达式能消除 n 的二进制表达中最右边的一个 1.?

 1 class Solution {
 2 public:
 3     int hammingWeight(uint32_t n) {
 4         int cnt = 0;
 5         while (n) {
 6             cnt++;
 7             n = n & (n-1);
 8         }
 9         return cnt;
10     }
11 };

View Code

【201】Bitwise AND of Numbers Range?

【231】Power of Two?（相关题目 342 Power of Four）（2018年11月4日，无聊做的）

给了一个数，判断它是不是2的幂。

题解：2的幂的二进制中只有一个1，所以我们用 num&(num-1) == 0 判断是不是2的幂次。?

1 class Solution {
2 public:
3     bool isPowerOfTwo(int n) {
4         return n > 0 && (n & (n-1)) == 0;
5     }
6 };

View Code

另外，还有判断一个数是不是3的幂的(326)，一个数是不是4的幂的(342)。?

【260】Single Number III? (2018年11月24日，算法群)?

题解：本题剑指offer书上好像是有的。

【268】Missing Number?

【318】Maximum Product of Word Lengths?

【320】Generalized Abbreviation?

【338】Counting Bits?

【342】Power of Four?（231题的升级版，判断是不是4的幂）（2018年11月4日，无聊做的）

给了一个数，判断这个数是不是4的幂。

题解：可能是负数，所以先把负数排除。一个数是4的幂的前提条件是它的2的幂，2的幂的二进制中只有一个1，所以用 num&(num-1) == 0 判断是不是 2 的幂。（这个方法也用在数一个数的二进制中有几个1用到了，【191】题，Number of 1 Bits）。然后增加判断它是不是 4 的幂，就是如果一个数是 2 的幂，那么增加一个条件， num % 3 == 1，满足这个条件，它就是 4 的幂。

1 //一个数是4的幂次，首先它要是2的幂次，2的幂次怎么求，2的幂次二进制中只有一个1.
2 class Solution {
3 public:
4     bool isPowerOfFour(int num) {
5         return num > 0 && (num&(num-1))==0 && num % 3 == 1;
6     }
7 };

View Code

?discuss中还有 & 一堆5的，那个要研究一下。

【371】Sum of Two Integers? (2018年11月26日)

返回 a + b 的答案，不能用 +。

题解：位运算。为啥我也还没搞懂。先写着。

https://leetcode.com/problems/sum-of-two-integers/discuss/84278/A-summary:-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently

 1 class Solution {
 2 public:
 3     int getSum(int a,int b) {
 4         do {
 5             int sum = a ^ b;
 6             int carry = (a & b) << 1;
 7             a = sum,b = carry;
 8         } while (b != 0);
 9         return a;
10     }
11 };

View Code

【389】Find the Difference?

【393】UTF-8 Validation?

【397】Integer Replacement?

【401】Binary Watch?

【405】Convert a Number to Hexadecimal?

【411】Minimum Unique Word Abbreviation?

【421】Maximum XOR of Two Numbers in an Array?

【461】Hamming Distance?(2019年2月16日)

两个整数对应二进制位置不同的个数叫做hamming distance。给了两个正整数 x 和 y，计算他们的hamming distance。

题解：我这里想强调下左移右移。左移低位补0，相当于乘以2，右移，如果是正数的话，高位补0，如果是负数的话，低位补0.

 1 class Solution {
 2 public:
 3     int hammingDistance(int x,int y) {
 4         int res = 0;
 5         while (x || y) {
 6             res += (x & 1) ^ (y & 1);
 7             x >>= 1; y >>= 1;
 8         }
 9         return res;
10     }
11 };

View Code

【476】Number Complement?（2019年2月16日）

返回一个正整数的补码。

The complement strategy is to flip the bits of its binary representation.

题解：我们用一个unsigned mask，mask一开始是～0 = FFFFFFFF，然后我们把 mask 尾部跟 number 有重叠的部分全 set 成 0。然后返回 ~num & ~mask

1 class Solution {
2 public:
3     int findComplement(int num) {
4         unsigned mask = ~0;
5         while (num & mask) {mask <<= 1;}
6         return ~num & ~mask;
7     }
8 };

View Code

【477】Total Hamming Distance?

【693】Binary Number with Alternating Bits?

【751】IP to CIDR?

【756】Pyramid Transition Matrix?

【762】Prime Number of Set Bits in Binary Representation?

【784】Letter Case Permutation?

【898】Bitwise ORs of Subarrays

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!