C++ 中将二进制数约简为 1 的步骤
假设我们有一个二进制数 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
进位 := 0，和 := 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 的大小，然后减去 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)
如果进位非零，则 −
在 ret 末尾插入进位
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] - ASCII 值为 '0'
return ret
在主方法中执行以下操作:
ret := 0
定义一个数组 x = makeVector from s
当 x 的大小 > 1 时，执行 −
(将 ret 增加 1)
如果 x 的最后一个元素等于 0，则执行 −
从 x 中删除最后一个元素
否则
定义一个大小为 1 的数组 temp
temp[0] := 1
x := makeVector(addBinary(x, temp))
return 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
