資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C #
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時裝學
法律研究在 C++ 中進行所需的最少翻轉次數，以用 k 個設定的位數最大化數字。
問題表述
給出兩個數字 n 和 k，我們需要透過翻轉其位數找到最大化給定數字所需的最小翻轉次數，使得結果數字恰好有 k 個設定的位數。請注意，輸入必須滿足條件 k 和 lt； 數字 n 中的位數。
示例
我們假設 n = 9 和 k = 2
9 的二進位制表示為 − 1001。它包含 4 位。
具有 2 個設定位數的最大的 4 位二進位制數字為 − 1100 即 12
要將 1001 轉換成 1100，我們必須翻轉高亮顯示的 2 位
演算法
1. Count the number of bits in n. Let us call this variable as bitCount. we can use log2(n) function from math library as fllows: bitCount = log2(n) + 1; 2. Find largest number with k set bits as follows: maxNum = pow(2, k) - 1; 3. Find the largest number possible with k set bits and having exactly same number of bits as n as follows: maxNum = maxNum << (bitCount - k); 4. Calculate (n ^ maxNum) and count number of set bits.
示例
#include <iostream>
#include <cmath>
using namespace std;
int getSetBits(int n){
int cnt = 0;
while (n) {
++cnt;
n = n & (n - 1);
}
return cnt;
}
int minFlipsRequired(int n, int k){
int bitCount, maxNum, flipCount;
bitCount = log2(n) + 1;
maxNum = pow(2, k) - 1;
maxNum = maxNum << (bitCount - k);
flipCount = n ^ maxNum;
return getSetBits(flipCount);
}
int main(){
cout << "Minimum required flips: " << minFlipsRequired(9, 2) << "\n";
return 0;
}輸出
當你編譯並執行以上程式時，它會產生以下輸出 −
Minimum required flips: 2
更新於：2019 年 9 月 23 日
134 次觀看
廣告