假设我们有一个二进制形式的数字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的大小），做-
和：=进位+（num2 [j]）
在sum的末尾插入sum mod 2
进位：= sum / 2
（将j增加1）
总和：=进位+（num1 [i]）
在sum的末尾插入sum mod 2
进位：= sum / 2
（将i增加1）
sum：=进位+（num1 [i] + num2 [j]）
在sum的末尾插入sum mod 2
进位：= sum / 2
（将i增加1）
（将j增加1）
如果i <num1的大小和j <num2的大小，则-
否则，当i <num1的大小时，则-
除此以外
如果进位不为零，则-
在ret结尾处插入进位
i：= ret的大小
ans：=空字符串
对于i> = 0，更新（将i减1），-
ans：= ans +（ret [i] + ASCII'0'）
返回（如果ans的大小等于0，则为“ 0”，否则为ans）
定义一个函数addBinary()，它将使用一个数组a，一个数组b，
返回addStrings(a,b)
定义一个数组makeVector并从v复制
在ret的末尾插入v [i]-ASCII为“ 0”
定义数组ret
对于初始化i：= 0，当i <v的大小时，更新（将i增加1），执行-
返回ret
从主要方法中执行以下操作：
ret：= 0
从s定义一个数组x = makeVector
当x> 1的大小时-
定义大小为1的数组温度
temp [0]：= 1
x：= makeVector（addBinary(x,temp)）
从x删除最后一个元素
（增加ret 1）
如果x的最后一个元素等于0，则-
除此以外
返回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