求 2 的最大幂的二进制字符串问题

Question

我们给定了一个长度为 n 的二进制字符串，我们可以循环移位这个字符串任意数量的 times.Let X 作为字符串 s 的十进制表示。找到可以整除 X 的 2 的最大幂，如果它可以被任意大的幂整除打印“-1”。对于结果，您需要打印一个整数表示 2 的最大幂 X可以整除。前任：输入： 0011 输出： 2

解释：我们可以将字符串循环移位 2 次得到“1100”，它可以被 2^2 整除，因此答案是 2。

这是我的解决方案..但是它在大多数测试用例上给出了答案，在一些测试用例上给出了错误的答案..

int highestpower(int n)
{
    return (n & (~(n - 1)));
}

int findnum(string s)
{
    int value = 0;
    int p=0;
    for(int i = s.length()-1;i>=0;i--)
    {
        value = value+pow(2,p)*(s[i]-'0');
        p++;
    }
    return value;
}

int maximumPower(string s) {
    int ans = 0;
    for(int i=0;i<s.length();i++)
    {
        
        int num = findnum(s.substr(i)+s.substr(0,i));
        ans = max(ans,highestpower(num));
    }
    return ans/2;
}

我该如何解决这个问题？谢谢..

Answer 1

我有点难以理解你的代码逻辑。实际上，它在我测试过的所有情况下都失败了。

而且，好像还挺over-complicated。计算连续零的数量就足够了。我们只需要注意该计算必须以循环方式执行。例如s == 00100，则计数为4，移位后得到10000。处理这种循环的一种简单方法是连接字符串 s2 = s+s = 0010000100，然后计算得到的字符串 s2 中连续零的最大数量。另外，我们必须注意输入的字符串不是只有零组成的。

在下面的代码中，我将你的代码 (maximumPower) 与我的代码 (maximumPower_new) 在几个不同的输入上进行了比较。

结果：

0011    : 2  new: 2
0100010 : 4  new: 3
00100   : 8  new: 4

代码：

#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>

int highestpower(int n)
{
    return (n & (~(n - 1)));
}

int findnum(const std::string& s)
{
    int value = 0;
    int p=0;
    for(int i = s.length()-1;i>=0;i--)
    {
        value = value+pow(2,p)*(s[i]-'0');
        p++;
    }
    return value;
}

int maximumPower(const std::string& s) {
    int ans = 0;
    for(int i = 0; i < s.length(); i++)
    {
        int num = findnum(s.substr(i)+s.substr(0,i));
        ans = std::max(ans,highestpower(num));
    }
    return ans/2;
}

int maximumPower_new (const std::string& s) {
    int n = s.length();
    if (n == 0) return -1;
    std::string s2 = s + s;
    int count = 0;
    int count_max = 0;
    for (auto c: s2) {
        if (c == '0') {
            count ++;
        } else {
            count_max = std::max(count, count_max);
            count = 0;
        }
    }
    count_max = std::max(count, count_max);
    if (count_max >= n) return -1;
    else return count_max;
}

int main() {
    for (std::string s: {"0011", "0100010", "00100"}) {
        std::cout << s << " : " << maximumPower(s) << " new: " << maximumPower_new(s) << "\n";
    }
}

求 2 的最大幂的二进制字符串问题

Binary String Question to find maximum power of 2

c++

string

math

bit