查找字符串可减少为0的步数

Question

我的任务：

您将获得一个非负整数变量$ Z $。有两个可以更改其值的操作：

• 如果$ Z $是奇数，则从中减去1；

• 如果$ Z $是偶数，将其除以2。

执行这些操作，直到$ Z $的值变为0。

您必须编写一个函数：int solution(string &S);这样，当给定由包含变量$ Z $初始值的二进制表示形式的$ N $个字符组成的字符串S时，返回步数之后，如上所述，$ Z $的值将变为0。

#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

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

您不应该将字符串转换为数字，因为它可能太长而无法容纳32-bit甚至64-bit整数。相反，您应该意识到，我们只需要知道1 s 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，它是最后一个数字，则仅一步之遥。

但是，步骤数可以表示为：

1. 如果数字为0，则步数也为0。
2. 如果仅出现1，则步数为字符串的size。
3. 如果出现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);
}