一、异或操作
/*
* 异或的特性:
* x ^ 0 = x
* x ^ 111...111 = ~x
* x ^ x = 0 //应用比较多,常用于找数目为奇数个的那个数。
* x ^ ~x = 111...1111
* a ^ b = c ==> a ^ c = b ==> b ^ c = a
* (a ^ b ) ^ c = a ^ (b ^ c)
*/
//leetcode136(在成对的数中找一个单的数)
namespace lt136 {
int singleNumber(vector<int>& nums)
{
int result = 0;
for (auto elem : nums)
{
result ^= elem; //如果相同的数异或会为0,而0和别的数异或是它自身,因此可以选出个数为一的数
}
return result;
}
}
namespace lt268 {
int missingNumber(vector<int>& nums)
{
unsigned int result = 0, i = 0;
for (auto elem : nums)
{
result = result ^ i ^ elem; //数组里的数是0-i,而下标也是0-i,然后找缺失的,跟上面的题一样
i ++;
}
return result ^ i;
}
}
//leetcode
namespace lt389 {
char findTheDifference(string s, string t)
{
int len = s.size();
unsigned int i, result = 0;
for (i = 0; i < len; i ++)
{
result = result ^ s[i] ^ t[i];
}
return result ^ t[i];
}
}
关于字典树的详解:https://blog.csdn.net/weixin_39778570/article/details/81990417
下面有关字典树的在二进制上的应用:
leetcode421 数组中两个数的最大异或值:https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/
//求最大的异或值,众所周知,越高位的1越多,那么对应的数越大,而对于异或最大,也就是两个数越高位不一样的,
//则,这两个数异或的值就越大,可以用字典树,从最高位开始存数字,因为最高为32为,所以设置树高为32
//比如5就存在0000 0000 0000 0000 0000 0000 0000 0101这条路径上;
//到时候找最大异或值,从最高位开始找,每次走与目标数不同的路径(如果存在的话)
namespace lt421 {
//二进制字典树
class Trie
{
private:
Trie* next[2]={nullptr};
public:
void insert(int x) //把数组的树存到树里
{
Trie *root=this;
int u;
for(int i=31;i>=0;i--)
{
u=x>>i&1;
if(!root->next[u])root->next[u]=new Trie();
root=root->next[u];
}
}
int srearch(int x)
{
Trie *root=this;
int u;
int res=0;
for(int i=31;i>=0;i--)
{
u=x>>i&1;
if(root->next[!u]){root=root->next[!u];res=res*2+!u;}
else {root=root->next[u];res=res*2+u;}
}
res^=x;
return res;
}
};
int findMaximumXOR(vector<int>& nums) {
Trie *root=new Trie();
for(auto x:nums)root->insert(x);
int res=0;
for(auto x:nums)
res=max(res,root->srearch(x));
return res;
}
}
字符串字典树的模板如下:
class Trie1
{
private:
bool is_string=false;
Trie1 *next[26]={nullptr};
public:
void insert(const string& word)//插入单词
{
Trie1 *root=this;
for(const auto& w:word){
if(root->next[w-'a']==nullptr)root->next[w-'a']=new Trie1();
root=root->next[w-'a'];
}
root->is_string=true;
}
bool search(const string& word)//查找单词
{
Trie1* root=this;
for(const auto& w:word){
if(root->next[w-'a']==nullptr)return false;
root=root->next[w-'a'];
}
return root->is_string;
}
bool startsWith(string prefix)//查找前缀
{
Trie1* root=this;
for(const auto& p:prefix){
if(root->next[p-'a']==nullptr)return false;
root=root->next[p-'a'];
}
return true;
}
};
/*
* 获取x的第n的位值:(x >> n) & 1;
* 获取x的第n的幂值:(1 << (n - 1)) & x;
* 将x的最右边的n为清为0:x & (~0 << n);
* 仅将第n的位置置为1:x | (1 << n)
* 仅将第n的位置置为0:x & (~(1 << n))
* 将 x 最高位至第 n 位(含)清零,x & ((1 << n) - 1)
* 将第 n 位至第 0 位(含)清零,x & (~((1 << (n + 1)) - 1))
* X & 1 == 1 判断是否是奇数(偶数)
* X & = (X - 1) 将最低位(LSB)的 1 清零
* X & -X 得到最低位(LSB)的 1
* X & ~X = 0
*/
其中:
为必会的操作
https://leetcode-cn.com/problems/single-number-iii/
leetcode260题,只出现一次的数字,也就是说,有两个单着的数,思路很简单:
(1):先用异或操作把成对的数踢出,
(2):之后就是区别两个数了,因为我们最后会得到一个两个数的异或值,那我们用X & -X 可以得到这个数最低位的1。
//leetcode260
namespace lt260 {
vector<int> singleNumber(vector<int>& nums)
{
vector <int> res(2);
res[0] = res[1] = 0;
unsigned int result = 0;
for (auto elem : nums){
result ^= elem;
}
result &= -result; //从右到左的第一个1,因为异或为1,那两个数肯定不一样;
for (auto elem : nums)
{
if ((result & elem) == 0)
{
res[0] ^= elem;
}
else
{
res[1] ^= elem;
}
}
return res;
}
}
//leetcode201
namespace lt201 {
int rangeBitwiseAnd(int left, int right) {
while (right > left)
{
right &= (right - 1);
}
return right;
}
}
//leetcode318
namespace lt318 {
int getNums(string w)
{
int sum = 0;
for (auto s : w)
{
sum |= (1 << (s - 'a'));
}
return sum;
}
int maxProduct(vector<string>& words)
{
vector <int> nums;
vector <int> len;
int maxNum = 0;
for (auto elem : words)
{
nums.push_back(getNums(elem));
len.push_back(elem.size());
}
for (int i = 0; i < nums.size() - 1; i ++)
{
for (int j = i + 1; j < nums.size(); j ++)
{
if ((nums[i] & nums[j]) == 0 && (maxNum < len[i] * len[j])){
maxNum = len[i] * len[j];
}
}
}
return maxNum;
}
}
//leetcode371
namespace lt371 {
int getSum(int a, int b){
if (a == 0 || b == 0)return a | b;
return getSum(a ^ b, (a&b) << 1);
}
}
//leetcode397
namespace lt397 {
int integerReplacement(int n) {
int len = 0;
while (n > 1)
{
if ((n & 1) == 0){
n >>= 1;
}else if ((n + 1) % 4 == 0 && n != 3){
n ++;
}else{
n --;
}
len ++;
}
return len;
}
}
//leetcode461
namespace lt461 {
int hammingDistance(int x, int y) {
x ^= y;
int len = 0;
while (x)
{
if (x&1)
len ++;
x >>= 1;
}
return len;
}
}
//leetcode693
namespace lt693 {
bool hasAlternatingBits(int n) {
int m = (n >> 1);
m ^= n;
while(m)
{
if (!(m&1))return false;
m >>= 1;
}
return true;
}
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。