题目：将二进制表示减到 1 的步骤数
给你一个以二进制形式表示的数字s。请你返回按下述规则将其减少到 1 所需要的步骤数：
•如果当前数字为偶数，则将其除以 2 。
•如果当前数字为奇数，则将其加上 1 。
题目保证你总是可以按上述规则将测试用例变为 1 。
示例 1：
输入：s = "1101"
输出：6
解释："1101" 表示十进制数 13 。
Step 1) 13 是奇数，加 1 得到 14
Step 2) 14 是偶数，除 2 得到 7
Step 3) 7  是奇数，加 1 得到 8
Step 4) 8  是偶数，除 2 得到 4
Step 5) 4  是偶数，除 2 得到 2
Step 6) 2  是偶数，除 2 得到 1
示例 2：
输入：s = "10"
输出：1
解释："10" 表示十进制数 2 。
Step 1) 2 是偶数，除 2 得到 1
示例 3：
输入：s = "1"
输出：0
提示：
•  1 <= s.length <= 500
•s由字符'0'或'1'组成。
•s[0] == '1'数学二进制的算法
语言:C++
class Solution {
public:
int numSteps(string s) {
int steps = 0;
while (s != "1") {
++steps;
if (s.back() == '0') {
// 偶数的情况
s.pop_back();
}
else {
// 第一步：出最低位的 0
// 第二步：把这个 0 变成 1，并将后面所有的 1 变成 0，这样就实现了 +1
// 特别地，如果 s 中全是 1，那么会有额外的进位
for (int i = s.size() - 1; i >= 0; --i) {
if (s[i] == '1') {
s[i] = '0';
if (i == 0) {
s = "1" + s;
break;
}
}
else {
s[i] = '1';
break;
}
}
}
}
return steps;
}
};
语言:C++
class Solution {
public:
int numSteps(string s) {
int n = s.size();
int ans = 0;
/
/ meet1 记录我们有没有遇见过字符 1
bool meet1 = false;
// 从后向前遍历字符
for (int i = n - 1; i >= 0; --i) {
if (s[i] == '0') {
// 如果当前字符为 0，分为两种情况
// (1) 还没有遇见过字符 1，那么这个 0 是字符串低位的 0，需要一次除二操作
// (2) 遇见过字符 1，那么这个 0 会因为它右侧的某次加一操作变为 1，因此它需要一次加一和一次除二操作
ans += (meet1 ? 2 : 1);
}
else {
// 如果当前字符为 1，分为两种情况
// (1) 还没有遇见过字符 1，那么这个 1 需要一次加一和一次除二操作
//    这里需要考虑一种特殊情况，就是这个 1 是字符串最左侧的 1，它并不需要任何操作// (2) 遇见过字符 1，那么这个 1 会因为它右侧的某次加一操作变为 0，因此它只需要一次除二操作
if (!meet1) {
if (i != 0) {
ans += 2;
}
meet1 = true;
}
else {
++ans;
}
}
}
return ans;
}
};
语言:Java
class Solution {
public int numSteps(String s) {
int n = s.length();
int ans = 0;
/
/ meet1 记录我们有没有遇见过字符 1
boolean meet1 = false;
// 从后向前遍历字符
for (int i = n - 1; i >= 0; --i) {
if (s.charAt(i) == '0') {
// 如果当前字符为 0，分为两种情况
// (1) 还没有遇见过字符 1，那么这个 0 是字符串低位的 0，需要一次除二操作
// (2) 遇见过字符 1，那么这个 0 会因为它右侧的某次加一操作变为 1，因此它需要一次加一和一次除二操作
ans += (meet1 ? 2 : 1);
} else {
// 如果当前字符为 1，分为两种情况
// (1) 还没有遇见过字符 1，那么这个 1 需要一次加一和一次除二操作
//    这里需要考虑一种特殊情况，就是这个 1 是字符串最左侧的 1，它并不需要任何操作// (2) 遇见过字符 1，那么这个 1 会因为它右侧的某次加一操作变为 0，因此它只需要一次除二操作
if (!meet1) {
if (i != 0) {
ans += 2;
}
meet1 = true;
} else {
++ans;
}
}
}
return ans;
}
}
语言:Python
class Solution:
def numSteps(self, s: str) -> int:
n, ans = len(s), 0
# meet1 记录我们有没有遇见过字符 1
meet1 =False
for i in range(n -1, -1, -1):
if s[i] =='0':
# 如果当前字符为 0，分为两种情况
# (1) 还没有遇见过字符 1，那么这个 0 是字符串低位的 0，需要一次除二操作
# (2) 遇见过字符 1，那么这个 0 会因为它右侧的某次加一操作变为 1，因此它需要一次加一和一次除二操作
ans += (2if meet1 else1)
else:
# 如果当前字符为 1，分为两种情况
# (1) 还没有遇见过字符 1，那么这个 1 需要一次加一和一次除二操作
#    这里需要考虑一种特殊情况，就是这个 1 是字符串最左侧的 1，它并不需要任何操作# (2) 遇见过字符 1，那么这个 1 会因为它右侧的某次加一操作变为 0，因此它只需要一次除二操作
if not meet1:
if i !=0:
ans +=2
meet1 =True
else:
ans +=1
return ans
语言:php
class S olution {
/**
* @param String $s
* @return Integer
*/
function numSteps($s) {
$len = strlen($s)-1;
if($len==0)
return0;
$k = $len;
$count = 0;
while($len!=0)
{
//如果末尾为0 则数字必为偶数
//偶数的话直接去掉末尾的0即可
if($s[$len]=="0"){
$len--;
}else{
//否则末尾为1则为奇数，实现+1进位
$s[$k] = "0";
if($s[$k-1]=="0")
$s[$k-1]="1";
else{
while($s[$k-1]!="0"){
if($k>1){
$s[$k-1]="0";
$k--;
}
else{
break;
}
}
if($k<=1){
if($len==strlen($s)-1)
$s[$len+1]="0";
$len++;
$k = $len;
}else{
$s[$k-1]="1";
}
}
}
$k = $len;
$count++;
}
return$count;
}
}
语言:golang
func numSteps(s string) int {
l := list.New()
for i, size := 0, len(s); i < size; i++ {        if s[i] == '1' {
l.PushBack(1)
} else {
l.PushBack(0)
}
}
res := 0
for l.Len() > 1 {
res++
if l.Back().Value == 0 {
l.Remove(l.Back())
} else {
for e := l.Back();; {
if e.Value == 1 {
e.Value = 0
if e == l.Front() {
l.PushFront(1)
break
}
e = e.Prev()
} else {

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。