windows搭建网站开发,南皮做网站的,龙泉建设有限公司网站,抖音代运营费用一年多少钱创作不易#xff0c;感谢三连支持#xff01;#xff01;
一、常见的位运算总结 标题 二、位1的个数
. - 力扣#xff08;LeetCode#xff09; 利用第七条特性#xff1a;n#xff08;n-1#xff09;干掉最后一个1#xff0c;然后每次都用count去统计#xff… 创作不易感谢三连支持
一、常见的位运算总结 标题 二、位1的个数
. - 力扣LeetCode 利用第七条特性nn-1干掉最后一个1然后每次都用count去统计直到变成0
class Solution {
public:int hammingWeight(uint32_t n) {int count0;while(n){n(n-1);count;} return count;}
}; 三、汉明距离
. - 力扣LeetCode 利用异或相同为0相异为1的特点x和y异或后不一样的位都会变成1这个时候再用nn-1去统计1个个数即为这两个数字的汉明距离
class Solution {
public:int hammingDistance(int x, int y) {//异或的特点相同为0相异为1 然后再利用n(n-1)统计1的个数int nx^y;int count0;while(n){n(n-1);count;}return count;}
}; 四、比特数记位典型dp 思路1每遍历一个数都用nn-1去数他一共有多少个1然后放心ans数组中
class Solution {
public:int countOnes(int x){int ones0;while(x){x(x-1);ones;}return ones;}//利用vectorint countBits(int n) {vectorint ret(n1);for(int i1;in;i) ret[i]countOnes(i);return ret;}
}; 思路2动态规划思想(本质是根据位运算的性质通过已经计算出来的状态去求未计算的状态) 即当计算 i 的「一比特数」时如果存在 0≤jij 的「一比特数」已知且 i和 j 相比i 的二进制表示只比j多了一个 1则可以快速得到 i 的「一比特数」。利用位运算的性质
1、设置最低位 对于nn-1本质上是将最右侧的1干掉所以一定会比原来的n小
因此bit[i]bit[i(i-1)]1 恒成立
class Solution {
public:vectorint countBits(int n) {vectorint ret(n1);for(int i1;in;i) ret[i]ret[i(i-1)]1;return ret;}
}; 2、最低有效位 对于正整数x来说如果是偶数的话右移一位正好就是x/2并且1的个数不会变所以偶数bit[i]bit[i/2] 对于奇数来说右移一位会丢掉后面的1所以要给他补上去所以奇数等于bit[i]bit[i/2]1 为了修正奇数多出来的1我们可以利用i1,如果是奇数就是1偶数就是0因此 bit[i]bit[i/2](i1) 恒成立
class Solution {
public:vectorint countBits(int n) {vectorint ret(n1);for(int i1;in;i) ret[i]ret[i/2](i1);return ret;}
};
3、最高有效位 对于正整数 x如果可以知道最大的正整数 y使得 y≤xy 是 2的整数次幂则 y的二进制表示中只有最高位是 1其余都是 0此时称 y 为 x 的「最高有效位」。令 zx−y显然 0≤zx则 bits[x]bits[z]1所以我们使用heightbit作为当前的最高有效位。如果ii-1为最高有效位就更新heightbiti 比 i−highBit的「一比特数」多 1 所以bit[i]bit[i-height]1 恒成立
class Solution {
public:vectorint countBits(int n) {vectorint ret(n1);int heightbit0;for(int i1;in;i) {if((i(i-1))0) heightbiti;ret[i]ret[i-heightbit]1;}return ret;}
};
五、只出现一次的数字1
. - 力扣LeetCode 思路利用异或的性质出现两次的数异或后为0出现一次的数异或0还是本身
class Solution {
public:int singleNumber(vectorint nums) {int n0;for(auto e:nums) n^e;return n;}
};
六、只出现一次的数字2
. - 力扣LeetCode class Solution {
public:int singleNumber(vectorint nums) {int ret0;for(int i0;i32;i){int sum0;for(int num:nums) if((numi)1) sum;//统计个数每一个1的比特位sum%3;//模3后代表ret当前bit位的值if(sum1) ret|(1i);//sum1就让ret该位置变成1}return ret;}
};
七、只出现一次的数字3 class Solution {
public:vectorint singleNumber(vectorint nums) {unsigned int temp0;//遇到INT_MIN会溢出10000……00for(int num:nums) temp^num;int xtemp(-temp);//x拿到最后一个1//int x (temp temp ? temp : temp (-temp));int type10,type20;for(int num:nums) if(numx) type1^num; else type2^num;return {type1,type2};}
};
八、丢失的数字
. - 力扣LeetCode 思路1利用等差数列和的公式-数组每一位数相加即可得到消失的数
class Solution {
public:int missingNumber(vectorint nums) {int nnums.size();return n*(n1)/2-accumulate(nums.begin(),nums.end(),0);}
}; 思路2利用异或的特点让0和数组所有数进行异或再对1-n异或出现两次的数都会被消去最后只会留下答案
class Solution {
public:int missingNumber(vectorint nums) {int ret0;for(int num:nums) ret^num;for(int i0;inums.size();i) ret^i;return ret;}
};
思路3暴力快排寻找下标和数字对应不上的数
class Solution {
public:int missingNumber(vectorint nums) {sort(nums.begin(),nums.end());int nnums.size();for(int i0;in;i) if(nums[i]!i) return i;return n;}
};
九、消失的两个数字
. - 力扣LeetCode 该题就是只出现一次数组1和 3的结合所以以上的思路去解答即可
class Solution {
public:vectorint missingTwo(vectorint nums) {int temp0;for(auto e:nums) temp^e;for(int i1;inums.size()2;i) temp^i;int xtemp(-temp);//拿到最右边的1int num10,num20;for(auto e:nums) if(ex) num1^e; else num2^e;for(int i1;inums.size()2;i) if(ix) num1^i; else num2^i;return {num1,num2};}
};
十、判定字符是否唯一
. - 力扣LeetCode class Solution {
public:bool isUnique(string astr) {if(astr.size()26) return false;//鸽巢原理做优化//利用位图的思想int bitmap0;for(auto ch:astr){int ich-a;//找到映射关系if((bitmapi)11) return false;//先判断该字符是否出现过 判断第i位是否是1//如果没出现过将第i位的0修改为1bitmap|(1i);}return true;}
};
十一、或运算的最小翻转次数
. - 力扣LeetCode class Solution {
public:int minFlips(int a, int b, int c) {int ret0;//记录翻转次数for(int i0;i31;i){//找到每一位进行判断int bit_a(ai)1;int bit_b(bi)1;int bit_c(ci)1;//情况1如果c为0的话那么a和b必须全是0 所以他们是多少就要翻转几次if(bit_c0) ret(bit_abit_b);//情况2如果c为1的话那么a和b至少要有一个为1 如果都为0翻转一次如果有1就不用翻转else ret(bit_abit_b0);}return ret;}
};
十二、两整数之和
. - 力扣LeetCode class Solution {
public:int getSum(int a, int b) {//要考虑-1因为-1的右移操作是没有定义的while(b){int xa^b;int carry(ab)1;ax;bcarry;}return a;}
};
