时间戳

首页 > 解决方案 > 求一个字符串可以减到0的步数

c++ - 求一个字符串可以减到0的步数

问题描述

我的任务：

给定一个非负整数变量 $Z$。有两个可用的操作可以改变它的值：

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

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

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

您必须编写一个函数：int solution(string &S); 当给定一个S由 $N$ 个字符组成的字符串时，该字符串包含变量 $Z$ 初始值的二进制表示，返回 $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;
}

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

标签： c++stltime-complexityc++14complexity-theory

解决方案

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

您不应该将字符串转换为数字，因为它可能太长而无法容纳在一个32-bit甚至64-bit整数中。相反，您应该意识到的是，我们只需要知道1s的数量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（并且左边还有1s），那么需要一步才能移动到下一个右边数字。但是，如果最右边的数字是1（并且不是最后一个），那么我们需要2一些步骤 - 取消它并移动到下一个正确的数字。显然，如果最左边的数字是1并且它是最后一个数字，那么它只是一步。

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

  1. 如果一个数字是，0那么步数也是0。
  2. 如果仅出现一次，1则步骤数为size字符串。
  3. 如果1s 出现的次数更多，则总步数为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

推荐阅读