c++ - 查找字符串可以减少为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