正文
【LeetCode】位运算 bit manipulation（共32题）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
p.p1 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica}
【78】Subsets
给了一个 distinct 的数组，返回它所有的子集。
Example:
Input: nums = [,,]
Output:
[
[],
[],
[],
[,,],
[,],
[,],
[,],
[]
]
题解：我是直接dfs（backtracking）了，有个小地方写错了(dfs那里)，至少调整了十多分钟，下次不要写错了。
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
n = nums.size();
vector<int> visit(n, );
vector<int> temp;
if (n == ) { return ans; }
dfs(nums, visit, temp, );
return ans;
}
void dfs(const vector<int>& nums, vector<int>& visit, vector<int>& temp, int cur_idx) {
ans.push_back(temp);
if (cur_idx == n) { return; }
for (int i = cur_idx; i < n; ++i) {
if (!visit[i]) {
visit[i] = ;
temp.push_back(nums[i]);
dfs(nums, visit, temp, i + ); //一开始写成了 dfs(nums, visit, temp, cur_idx + 1) 挂了半天
visit[i] = ;
temp.pop_back();
}
}
return;
}
vector<vector<int>> ans;
int n;
};
backtracking
我看分类是 位运算，学习一下位运算解法。https://leetcode.com/problems/subsets/discuss/27288/My-solution-using-bit-manipulation
题解的解释参考：https://www.mathsisfun.com/sets/power-set.html （有点像状态压缩的感觉）
//bit manipulation, 我认为是状态压缩的最简单的题.
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
const int n = nums.size();
if (n == ) { return vector<vector<int>>{}; }
// n 个元素一共有 2^n 个子集。
int tot = pow(, n);
vector<vector<int>> ans(tot, vector<int>{});
// 然后用二进制一个一个往里面塞
for (int i = ; i < n; ++i) {
for (int j = ; j < tot; ++j) {
if (j >> i & ) {
ans[j].push_back(nums[i]);
}
}
}
return ans;
} };
bit manipulation
【136】Single Number （2018年11月4日）（剑指offer上有个变种题，有两个数只出现了一次，求出出现一次的这两个数）
给了一个数组，说数组里面除了一个数只出现了一次，其他数都出现了两次。找出只出现一次的那个数。
题解：出现两次的数取异或之后为0，把全部数字异或起来，最后结果就是要求的那个数。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = ;
for (int i = ; i < nums.size(); ++i) {
ans ^= nums[i];
}
return ans;
}
};
【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.
class Solution {
public:
int hammingWeight(uint32_t n) {
int cnt = ;
while (n) {
cnt++;
n = n & (n-);
}
return cnt;
}
};
【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的幂次。
class Solution {
public:
bool isPowerOfTwo(int n) {
return n > && (n & (n-)) == ;
}
};
另外，还有判断一个数是不是3的幂的(326)，一个数是不是4的幂的(342)。
【260】Single Number III (2018年11月24日，算法群)
题解：本题剑指offer书上好像是有的。
【268】Missing Number
【318】Maximum Product of Word Lengths （2019年3月26日）
给了一组wordlist，返回里面两个单词的长度的乘积最大是多少。要求这两个单词里面不能有重复的字母。题目中给定所有单词都是小写字母。
题解：因为已经说明了每个单词的字母都是小写字母，所以我们可以用一个32位整数来编码当前单词是否出现过这个字母。重要代码如下：
x = words[i][j] - 'a'
code |= ( << x)
然后判断两个单词是否有相同字母，使用如下语句判断： code[i] & code[j] == 0
class Solution {
public:
int maxProduct(vector<string>& words) {
const int n = words.size();
vector<int> codes(n, );
for (int i = ; i < n; ++i) {
for (int j = ; j < words[i].size(); ++j) {
int x = words[i][j] - 'a';
codes[i] |= ( << x);
}
}
int res();
for (int i = ; i < n; ++i) {
for (int j = i + ; j < n; ++j) {
if (codes[i] & codes[j]) {continue;}
int length = (int)words[i].size() * words[j].size();
res = max(res, length);
}
}
return res;
}
};
【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 的幂。
//一个数是4的幂次，首先它要是2的幂次，2的幂次怎么求，2的幂次二进制中只有一个1.
class Solution {
public:
bool isPowerOfFour(int num) {
return num > && (num&(num-))== && num % == ;
}
};
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
class Solution {
public:
int getSum(int a, int b) {
do {
int sum = a ^ b;
int carry = (a & b) << ;
a = sum, b = carry;
} while (b != );
return a;
}
};
【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.
class Solution {
public:
int hammingDistance(int x, int y) {
int res = ;
while (x || y) {
res += (x & ) ^ (y & );
x >>= ; y >>= ;
}
return res;
}
};
【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
class Solution {
public:
int findComplement(int num) {
unsigned mask = ~;
while (num & mask) {mask <<= ;}
return ~num & ~mask;
}
};
【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
