1 颠倒二进制位
分析:c++的bitset中封装了对二进制的操作:构造函数可以直接将整型转为其二进制表示,to_string()可将其二进制转为字符串形式,to_ulong()转为整数形式。
代码:
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
bitset<32> x(n);
string s = x.to_string();
reverse(s.begin(), s.end());
bitset<32> y(s);
uint32_t res = y.to_ulong();
return res;
}
};
分析:两个相同的数异或为0,任何数与0异或为本身,所以数组中所有数的异或即为只出现一次的数。
代码:
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;
for (auto e: nums) ret ^= e;
return ret;
}
};
方法一:同样利用bitset,将其二进制表示转为字符串形式,然后统计其中1的个数。
代码:
class Solution {
public:
int hammingWeight(uint32_t n) {
bitset<32> x(n);
int res = 0;
string s = x.to_string();
for(int i = 0; i < 32; i++) {
if(s[i] == '1') {
res++;
}
}
return res;
}
};
方法二:n & (n - 1)其运算结果恰为把n的二进制位中的最低位的1变为0之后的结果,所以依次将n的最低位的1变为0,在这个过程中计数,直到n为0即可。
代码:
class Solution {
public:
int hammingWeight(uint32_t n) {
int ret = 0;
while (n) {
n &= n - 1;
ret++;
}
return ret;
}
};
分析:n如果是2的幂,则n是正整数并且n的二进制表示中只有1个1。第一个方法采用了前面提到的n & (n - 1),该式可以将n最低位的1变成0,如果最低位变成0后n为0,则n满足要求。第二个方法采用了n & -n,该式可以直接获取到最低位的1,实际上就是n的最高位,如果n & -n后n不变,则n满足要求。
代码:
class Solution {
public:
bool isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
};
class Solution {
public:
bool isPowerOfTwo(int n) {
return n > 0 && (n & -n) == n;
}
};
分析:典型的dfs例题,背模板。
代码:
class Solution {
public:
vector<int> temp;
vector<vector<int>> ans;
void dfs(int cur, int n, int k) {
if(temp.size() + (n - cur + 1) < k) {
return;
}
if(temp.size() == k) {
ans.push_back(temp);
return;
}
temp.push_back(cur);
dfs(cur + 1, n, k);
temp.pop_back();
dfs(cur + 1, n, k);
}
vector<vector<int>> combine(int n, int k) {
dfs(1, n, k);
return ans;
}
};