C++ 中使 a 或 b 等於 c 的最小翻轉次數

假設我們有 3 個正數 a、b 和 c。我們需要找到 a 和 b 中某些位的最小翻轉次數，以使 (a 或 b == c)。這裡我們考慮按位或運算。

翻轉操作包括將二進位制表示中的任何一位從 1 更改為 0 或將 0 更改為 1。因此，如果 a：0010 且 b := 0110，則 c 為 0101，翻轉後，a 將為 0001，b 將為 0100

為了解決這個問題，我們將遵循以下步驟 -

  • ans := 0
  • 對於 i 從 0 到 31 的範圍
    • bitC := (c / 2^i) AND 1
    • bitA := (a / 2^i) AND 1
    • bitB := (b / 2^i) AND 1
    • 如果 (bitA 或 bitB) 與 bitC 不相同，則
      • 如果 bitC 為 0
        • 如果 bitA = 1 且 bitB = 1，則將 ans 增加 2，否則將 ans 增加 1
      • 否則將 ans 增加 1
  • 返回 ans

示例（C++）

讓我們看看以下實現以更好地理解 -

 即時演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minFlips(int a, int b, int c) {
      int ans = 0;
      for(int i = 0; i < 32; i++){
         int bitC = (c >> i) & 1;
         int bitA = (a >> i) & 1;
         int bitB = (b >> i) & 1;
         if((bitA || bitB) != bitC){
            if(!bitC){
               if(bitA == 1 && bitB == 1){
                  ans += 2;
               }
               else {
                  ans += 1;
               }
            }
            else{
               ans += 1;
            }
         }
      }
      return ans;
   }
};
main(){
   Solution ob;
   cout << (ob.minFlips(2,6,5));
}

輸入

2
6
5

輸出

3

更新於：2020-04-30

593 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告