[leetcode每日一题] 3226. 使两个整数相等的位更改次数

yyyyye

位运算，简单水一下

class Solution {
public:
    int minChanges(int n, int k) {
        int cnt = 0;
        if((n & k) != k)
            return -1;
        int t = n ^ k;
        while(t)
        {
            if(t & 1)
            {
                cnt++;
            }
            t >>= 1;
        }
        return cnt;
    }
};

ssssshi

正常转2比较，终于有个能写的题了！！

class Solution {
#include<vector>
public:
    int minChanges(int n, int k) {
        vector<int>arr1,arr2;
        int cnt=0, i=0;
    if(k>n)return -1;
    while(n!=0)
    {
        arr1.push_back(n%2);
        n/=2;
    }
    arr2.assign(arr1.size(),0);
    while(k!=0)
    {
        arr2.at(i++)=k%2;
        k/=2;
    }
    for(int i1=0;i1<arr1.size();i1++)
    {
        if(arr1.at(i1)==0&&arr2.at(i1)==1)return -1;
        if(arr1.at(i1)==1&&arr2.at(i1)==0) cnt++;
    }
    return cnt; 
        

    }
};

Zero_canyon

class Solution {
public:
    int minChanges(int n, int k) {
        if(k > n)return -1;
        int nn, kk;
        int count = 0;

        while(n)
        {
            nn = n%2;
            kk = k%2;
            if(!nn && kk)return -1;
            if(nn && !kk)
            count++;
            n/=2;
            k/=2;
        }
        return count;
    }
};```
简单无脑入门流
比较二进制各位，大1小0就变，小1大0就不行

ygxdsh

和✌神一样用了位运算，不过思路不一样。
我的想法是先判断能否更改成功，再间接计算更改次数。
用到了n&-n用来求n二进制中最后一个1
（例如10二进制为1010，最后一个1在第二位，也就是数字2，倒数第二个1在第四位，也就是数字8）
具体代码如下

int minChanges(int n, int k)
{
    int ans = 0;
    while (k)
    {
        int kk = k & -k;
        if (n / kk % 2 == 0)
            return -1;
        ans--;
        k -= kk;
    }
    while (n)
    {
        int nn = n & -n;
        ans++;
        n -= nn;
    }
    return ans;
}

具体思路是先看看k二进制中的1是否在n的二进制中存在，若不存在直接返回-1即可
若都存在，说明可以通过修改得到。
计算修改次数的方法也非常简单，只需要用n二进制中1的数量减去k二进制中1的数量即可
唯一需要注意的点是，记得每次取最后一个1下次循环前要将它减掉，才能把二进制中所有的1遍历一遍

tjp

不会用位运算，就直接在10进制的时候一位一位的比较，不断除2，再对2取余，如果n的余数为1，k的余数为0则可以进行转换，于是将ans++，如果是0和1则可以直接输出-1，就这样比较至两数除2都等于0。

public:
    int minChanges(int n, int k) {
        int sum = n - k;
        int ans = 0;

        while (n != 0) {
            if (sum < 0) {
                return -1;  

            }
           if(n%2==1)
           {
            if(sum % 2==1){ans++;}
           }else
           {if(sum%2==1){return -1;}
            }
        

            n/=2;sum/=2;
           

        }

        return ans; 
    }
};

`

xxingyu

/*
 * @lc app=leetcode.cn id=3226 lang=cpp
 *
 * [3226] 使两个整数相等的位更改次数
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution {
 public:
  int minChanges(int n, int k) {
    int ans = 0;
    while (n > 0 || k > 0) {
      if ((n & 1) == 0 && (k & 1) == 1) return -1;
      if ((n & 1) == 1 && (k & 1) == 0) ans++;
      n >>= 1;
      k >>= 1;
    }
    return ans;
  }
};
// @lc code=end

Mr-Hate

蒟蒻只会模拟……

class Solution {
public:
    string D_to_B(int n){
        string ans;
        while(n){
            ans+=n%2+'0';
            n/=2;
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
    int minChanges(int n, int k) {
        int ans=0;
        if(n==k)
        return 0;
        string nb=D_to_B(n);
        string kb=D_to_B(k);
        while(nb.size()!=kb.size()){
            nb=nb.size()<kb.size()?'0'+nb:nb;
            kb=nb.size()>kb.size()?'0'+kb:kb;
        }
        int nn=nb.size();
        for(int i=0;i<nn;i++){
            if(nb[i]=='0'&&kb[i]=='1'){
                return -1;
            }
            else if(nb[i]=='1'&&kb[i]=='0'){
                ++ans;
            }
        }
        return ans;
    }
};

Future

写的时候的雷点是while循环应该是或不能并，
因为要看两个各自二进制数，
如果并的话其中一个可能无法得到正确的二进制数
~~写的时候卡这了。~~

public:
    int minChanges(int n, int k) {
        int sign=0,N,K,cot=1;
        while(n>0||k>0)//依次得出n和k的各位二进制数
        {
            N=n%2;//n的每位二进制数
            n/=2;
            K=k%2;//k的每位二进制数
            k/=2;
            if(N!=K)//判断N与K二进制同位的数是否相等
            {
                if(N==1)//n的此位二进制数等于1，更改一次
                {sign++;}
                else
                {cot=0;  break;}//不等于1，则无法实现，cot=0作为标志并跳出循环
            }
        }
        if(cot==0)//判断能否实现
        {
            sign=-1;
        }
        return sign;
    }
};```

xujingyuan

只要二进制中相同位置上n是0但k是1，直接返回-1；其余时候只要二者某一位不相等，计数器加一。

int minChanges(int n, int k) {
    #define maxn 100009
    int a1[maxn]={0};
    int a2[maxn]={0};
    int cnt=0;
    for(int i=0;n>0;i++)
    {
        a1[i]=n%2;
        n=n/2;
    }
    for(int i=0;k>0;i++)
    {
        a2[i]=k%2;
        k=k/2;
    }
    for(int i=0;i<maxn;i++)
    {
     if(a1[i]!=a2[i])
     {
        if(a1[i]==0&&a2[i]==1)
        return -1;
        else
        cnt++;
     }
    }
    return cnt;
}

If_you_love

图片alt
~~孩子觉得生活有盼头了~~早在我的预料之中！
![思路是先求差，然后判断，如果差为0就直接输出0表示不用变化，然后判断n&a!=a来检查是否有n的二进制下某个位为0而a对应的位却是1的情况，如果有这种情况输出-1表示无法转换，否则转换为bitset(20是因为10e6的二进制位数为20位)然后用工具b.count()得到a的二进制中几个1就得到需要换1为0的个数

class Solution {
public:
    int minChanges(int n, int k) {
        int a=n-k;
        if(a==0)
        {
            return 0;
        }
        else 
        {
            if((n&a)!=a)
            {
                return -1;
            }
            else 
            {
                bitset <20> b(a);
                return b.count();
            }
        }
    }
};

If_you_love

If_you_love 人生第一次爱装别骂

Koarz

class Solution {
public:
    int minChanges(int n, int k) {
        unsigned int v = n ^ k;
        int res = std::popcount(v);
        return n < (v | n) ? -1 : res;
    }
};

根据题意要将两个数使用位反转使其相等, 那么要做的就是统计不相等的位有几位, 很容易就能想到使用异或操作实现

使用cpp20提供的std::popcount函数就能得到结果

但是题目是只能将n的1变为0, 就是说如果出现1101和0110这种情况需要返回-1, 那么怎么快速检查呢?

通过思考, 转换成功的条件就是n的0位对应的k的位是不能出现1的, 所以如果两个数经过或运算那么这个新的数一定是小于等于n的那么只要n < (v | n)就返回-1就行

其实一行都能写完return n < (v | n) ? -1 : std::popcount(n ^ k)