求一个字符串可以减少到0的步骤数

Question

我的作业：

You are given a non-negative integer variable $Z$. There are two actions available that can change its value:

if $Z$ is odd, subtract 1 from it;

if $Z$ is even, divide it by 2.

These actions are performed until the value of $Z$ becomes 0.

You have to write a function: int solution(string &S); such that when given a string S consisting of $N$ characters containing a binary representation of the initial value of variable $Z$, returns the number of steps after which the value of $Z$ will become 0, as described above.

#include<iostream>

int solution(string &S) {
    int x = stoi(S, 0, 2);
    int count = 0;
    while (x != 0) {
        if (x % 2 == 0) {
            x /= 2;
            count++;
        } else {
            x -= 1;
            count++;
        }
    }
    return count;
}

现在这段代码的时间复杂度爆炸了。我在编写有效解决方案时哪里出错了？

Answer 1

Now the time complexity of this code blows up. Where am I going wrong in writing an efficient solution?

您不应将字符串转换为数字，因为它可能太长而无法放入 32-bit 甚至 64-bit 整数中。相反，您应该意识到的是，我们所需要知道的只是 1 的数量 onesCount 和整数字符串的长度 size （我们假设没有前导零，因为每个问题陈述）。让我们考虑一个例子。假设我们有一个数字 11001。然后，步骤可以说明如下：

1 1 0 0 1   subtract rightmost bit because it's 1  
    |
    v         
1 1 0 0 0   right shift because rightmost 0  
    |
    V
0 1 1 0 0   right shift because rightmost 0 
    |
    v
0 0 1 1 0   right shift because rightmost 0 
    |
    v
0 0 0 1 1   subtract rightmost bit 1
    |
    v
0 0 0 1 0   right shift because rightmost 0 
    |
    V  
0 0 0 0 1   subtract rightmost bit 1
    |
    V
0 0 0 0 0   Complete.

所以，如您所见，如果最右边的数字是 0（并且左边还有 1），那么它需要一步移动到下一个右边的数字。但是，如果最右边的数字是 1（而且它不是最后一个），那么我们需要 2 步 - 将其无效并移动到下一个右边的数字。显然，如果最左边的数字是 1 并且它是最后一个那么它只是一步。

但是那么，步数可以表示为：

如果数字是0那么步数也是0。
如果 1 只出现一次，则步数为字符串的 size。
如果出现更多 1，则总步数为 onesCount * 2 + (size - onesCount - 1)。但是，这比第 2 节更通用，我们可以在这两种情况下使用它。

代码

uint32_t solveMe(std::string &number) {
    uint32_t onesCount = std::count(number.begin(), number.end(), '1');
    if (onesCount == 0) {
        return 0;
    }

    uint32_t numberSize = number.size();

    return onesCount * 2 + (numberSize - onesCount - 1);
}

更新

正如@lucieon 所指出的，另一种看待这个问题的方式可以用下面的公式来描述：

zerosCount + (onesCount-1)*2 + 1

Answer 2

这是我在 C# 中的解决方案，它涵盖了具有前导零的可能性。包括“00011101”等情况。

public class Solution
{
    public static int EfficientCountStepsToZero(string S)
    {
        var newString = RemoveLeadingZeros(S);
        int zerosCount = 0;
        int onesCount = 0;
        for (int i = 0; i < newString.Length; i++)
        {
            if (newString[i] == '0')
            {
                zerosCount++;
            }
            else
            {
                onesCount++;
            }
        }
        return zerosCount + (onesCount - 1) * 2 + 1;
    }

    private static string RemoveLeadingZeros(string S)
    {
        char[] letter = S.ToCharArray();
        for (int i = 0; i < letter.Length; i++)
        {
            if (letter[i] == '1')
            {
                break;
            }
            letter[i] = ' ';
        }
        return new string(letter).Trim();
    }
}

求一个字符串可以减少到0的步骤数

Find the number of steps a string can be reduced to 0

c++

complexity-theory

stl

time-complexity

c++14