資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++中將二進位制表示的數字減少到一的步驟數
假設我們有一個用二進位制形式表示的數字 s。我們必須找到根據以下規則將其減少到 1 的步驟數：
如果當前數字為偶數，則必須將其除以 2。
如果當前數字為奇數，則必須加 1。
因此，如果輸入類似於“1101”，則輸出將為 6，因為“1101”為 13。所以，13 為奇數，加 1 得到 14。然後 14 為偶數，除以 2 得到 7。之後 7 為奇數，加 1 得到 8。
然後 8 再次為偶數，所以除以 2 得到 4。再次 4 為偶數，除以 2 得到 2，最後 2 為偶數，除以 2 得到 1。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式 addStrings()，它將接收一個數組 num1、一個數組 num2、
定義一個數組 ret
carry := 0，sum := 0
反轉 num1 和 num2
i := 0，j := 0
當 (i < num1 的大小 或 j < num2 的大小) 時，執行：
如果 i < num1 的大小 且 j < num2 的大小，則：
sum := carry + (num1[i] + num2[j])
在 ret 的末尾插入 sum mod 2
carry := sum / 2
(將 i 增加 1)
(將 j 增加 1)
否則，當 i < num1 的大小 時，則：
sum := carry + (num1[i])
在 ret 的末尾插入 sum mod 2
carry := sum / 2
(將 i 增加 1)
否則
sum := carry + (num2[j])
在 ret 的末尾插入 sum mod 2
carry := sum / 2
(將 j 增加 1)
如果 carry 不為零，則：
在 ret 的末尾插入 carry
i := ret 的大小
ans := 空字串
對於 i >= 0，更新 (將 i 減小 1)，執行：
ans := ans + (ret[i] + '0' 的 ASCII 碼)
返回 (如果 ans 的大小等於 0，則返回“0”，否則返回 ans)
定義一個函式 addBinary()，它將接收一個數組 a、一個數組 b、
返回 addStrings(a, b)
定義一個數組 makeVector 並從 v 中複製
定義一個數組 ret
對於初始化 i := 0，當 i < v 的大小 時，更新 (將 i 增加 1)，執行：
在 ret 的末尾插入 v[i] - '0' 的 ASCII 碼
返回 ret
從主方法執行以下操作：
ret := 0
定義一個數組 x = 從 s 中建立 makeVector
當 x 的大小 > 1 時，執行：
(將 ret 增加 1)
如果 x 的最後一個元素等於 0，則：
從 x 中刪除最後一個元素
否則
定義一個大小為 1 的陣列 temp
temp[0] := 1
x := makeVector(addBinary(x, temp))
返回 ret
示例
讓我們檢視以下實現以更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string addStrings(vector<int> num1, vector<int> num2){
vector<int> ret;
int carry = 0;
int sum = 0;
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
int i = 0;
int j = 0;
while (i < num1.size() || j < num2.size()) {
if (i < num1.size() && j < num2.size()) {
sum = carry + (num1[i]) + (num2[j]);
ret.push_back(sum % 2);
carry = sum / 2;
i++;
j++;
}
else if (i < num1.size()) {
sum = carry + (num1[i]);
ret.push_back(sum % 2);
carry = sum / 2;
i++;
}
else {
sum = carry + (num2[j]);
ret.push_back(sum % 2);
carry = sum / 2;
j++;
}
}
if (carry)
ret.push_back(carry);
i = ret.size() - 1;
string ans = "";
for (; i >= 0; i--)
ans += (ret[i] + '0');
return ans.size() == 0 ? "0" : ans;
}
string addBinary(vector<int>& a, vector<int>& b){
return addStrings(a, b);
}
vector<int> makeVector(string v){
vector<int> ret;
for (int i = 0; i < v.size(); i++)
ret.push_back(v[i] - '0');
return ret;
}
int numSteps(string s){
int ret = 0;
vector<int> x = makeVector(s);
while (x.size() > 1) {
ret++;
if (x.back() == 0) {
x.pop_back();
}
else {
vector<int> temp(1);
temp[0] = 1;
x = makeVector(addBinary(x, temp));
}
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.numSteps("1101"));
}輸入
"1101"
輸出
6
164 次檢視
