数据结构
网络
关系数据库管理系统
操作系统
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 次查看
