03二进制特性
# 03 二进制特性
利用二进制的一些特性,可以把位运算使用到更多问题上。例如,可以利用二进制和位运算输出一个数组的所有子集。假设有一个长度为 n 的数组,可以生成长度为 n 的所有二进制,1 表示选取该数字,0 表示不选取。这样就获得了 2^n
个子集。
# 342 4的幂 (opens new window)
给定一个整数,判断它是否是 4 的次方。
输入是一个整数,输出是一个布尔值,表示判断结果。
输入:n = 16 输出:true
解析:
本题可以采用按位与运算简单实现判断数是否为4的幂。如果 n 是 4 的幂,那么 n 的二进制表示中有且仅有一个 1 ,且其位置必须为奇数位,例如16 = (10000)
,从右向左且从1开始计数的话,16的二进制表示中 1 位于第5位。根据此规律可以将 n 和二进制01010101010101010101010101010101
或者十六进制的0x55555555
做按位与,如果得到的结果不为零,那么说明这个数可能是 4 的幂。
为什么说是可能呢?可以看出上述条件是充分条件而非充要条件,1 与0x55555555
做按位与的结果也是非0的。
所以需要进一步考虑该数 n 也是 2 的幂,才能保证上述条件判断结果为该数是 4 的幂。如果 n 是 2 的幂,那么 n 的二进制表示中也有且仅有一个 1,假设其位置为 pos ;那么 n - 1 二进制表示由第 1 位到第 pos-1 位全部为 1构成。例如16 = 10000; 15 = 01111
,所以可以得出:如果 n & (n - 1) == 0
,那么 n 是 2 的幂。
最终得到:如果(n&(n-1))==0 && (n & 0x55555555)!=0
,那么n 是 4 的幂。
class Solution {
public:
bool isPowerOfFour(int n) {
return n > 0 && !(n&(n-1)) && (n&0x55555555);
}
};
当然,本题也可以采用类似求 326. 3的幂 (opens new window)的方法直接使用对数函数的换底公式构造log4(n)
,然后使用fmod()
函数判断该值是否为整数,进而判断 n 是否是 4 的幂。
class Solution {
public:
bool isPowerOfFour(int n) {
return fmod(log10(n)/log10(4),1) == 0;
}
};
# 318 最大单词长度乘积 (opens new window)
给定多个字母串,求其中任意两个字母串的长度乘积的最大值,且这两个字母串不能含有相同字母。
输入一个包含多个字母串的一维数组,输出一个整数,表示长度乘积的最大值。
输入: ["a","ab","abc","d","cd","bcd","abcd"] 输出: 4 解释: 这两个单词为 "ab", "cd"。
解析:
怎样快速判断两个字母串是否含有重复数字呢?可以为每个字母串建立一个长度为 26 的二进制数字 mask,用于表示从右到左每个位置表示是否存在a-z
对应的字母。例如abc:111, abd:1011
,如果两个字母串含有重复数字,那它们的二进制表示的按位与不为 0,例如abc,adbe
存在相同的字母,将它们按位与的结果是1011!=0
。
怎么实现对字符串的编号记录呢?也可以通过位运算实现:首先将 mask 置为 0,然后遍历字符串的所有字符,每一次遍历中计算当前字符串所处的位置,然后使用算术左移,将标识 1 移动到指定位置,移动完成后将其与mask按位与运算,将位置记录在mask中。
为了求长度乘积的最大值,可以建立一个哈希表记录字符串与其自身的长度。在计算长度乘积最大值时,遍历哈希表将不存在相同字母的字符串长度相乘并取最大值。
class Solution {
public:
int maxProduct(vector<string>& words) {
unordered_map<int,int> hash;
int ans = 0;
for(const auto& word: words){
int mask = 0;
int wordLen = word.length();
// 为当前字符串编码
for(const auto c:word){
// 考虑字符串中每一个字符时,将 1 左移 (c-'a') 位
int cPos = 1 << (c-'a');
// 与mask按位与,将当前字符的位置保存到mask中,如果当前字符已经存在不影响mask
mask = mask | cPos;
}
// 更新mask对应的长度时要考虑到:字符串中元素重复出现的情况,这种情况下字符串长度不一致
hash[mask] = max(hash[mask],wordLen);
// 遍历所有已经记录的字符串,如果有不存在相同字符 (mask & h_mask)== 0 的字符串计算当前长度乘积
for(const auto& [h_mask,h_len]: hash){
if(!(mask & h_mask)){
ans = max(ans,wordLen*h_len);
}
}
}
return ans;
}
};
# 338 比特位计数 (opens new window)
给定一个非负整数 n,求从 0 到 n 的所有数字的二进制表达中,分别有多少个 1。
输入是一个非负整数 n,输出是长度为 n + 1 的非负整数数组,每个位置 m 表示 m 的二进制里有多少个 1。
输入:n = 5 输出:[0,1,1,2,1,2] 解释:0 --> 0, 1 --> 1, 2 --> 10, 3 --> 11, 4 --> 100, 5 --> 101
解析:
本题如果使用双层循环逐个统计每个数二进制表示中1的个数会出现超时的情况。为了优化可以考虑使用动态规划来解题。
设置状态:使用一个一维数组dp[i]
表示第 i 个数的二进制表示中 1 的个数
状态转移方程:对于第 i 个数字,如果该数为奇数即其二进制表示的末位为1,那么该数二进制表示中 1 的个数直接与前一个偶数相关为dp[i]=dp[i-1]+1
;如果该数为偶数即其二进制表示的末位为0,那么该数二进制表示中 1 的个数与其算术右移一位结果相同,因为其算术右移一位将末位0移出后与对应数的二进制表示一致,即dp[i]=dp[i>>1]
边界条件:当 n = 0时,dp[0]=0
class Solution {
public:
vector<int> countBits(int n) {
vector<int> dp(n+1,0);
for(int i=1;i<=n;++i){
if(i&1){
dp[i] = dp[i-1] + 1;
}else{
dp[i] = dp[i>>1];
}
}
return dp;
}
};