資料結構
網路
關係型資料庫管理系統
作業系統
Java
微軟 Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究用 C++ 實現整數替換
假設我們有一個正整數 n，並且我們可以執行以下操作−
如果 n 為偶數，將 n 替換為 n/2。
如果 n 為奇數，你可以將 n 替換為 n + 1 或 n - 1。
我們必須找到將 n 變成 1 所需的最小替換次數？
所以如果該數為 7，那麼答案將為 4，因為 7 → 8 → 4 → 2 → 1 或 7 → 6 → 3 → 2 → 1
為了解決這個問題，我們將遵循以下步驟−
ret := 0, n := x
while n > 1
如果 n 為偶數，則 c := n / 2
否則當 n 為偶數時
如果 n 為 3 或 n/2 為偶數，則將 n 減 1，否則將 n 加 1
將 ret 加 1
返回 ret。
示例 (C++)
讓我們看看以下實現以獲得更好的理解 −
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int bitCount(int x){
int ret = 0;
while(x){
ret++;
x >>= 1;
}
return ret;
}
int integerReplacement(int x) {
int ret = 0;
lli n = x;
while(n > 1){
if(n % 2 == 0){
n >>= 1;
}
else if(n & 1){
if(n == 3 || (((n >> 1) & 1 )== 0)){
n--;
} else {
n++;
}
}
ret++;
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.integerReplacement(7));
}輸入
7
輸出
4
更新於： 2020 年 5 月 2 日
581 次瀏覽
廣告