Блог

Мы дали двоичную строку длиной n, мы можем циклически сдвигать эту строку любое количество раз.Пусть X — десятичное представление строки s. Найдите наибольшую степень 2, с которой X может быть делимым, если оно может быть делимым с произвольно большой степенью печати «-1».Для получения результата вам необходимо напечатать одно целое число, обозначающее максимальную степень 2, на которую X может быть делимым. пример: Ввод: 0011 Вывод: 2

Объяснение: мы можем циклически сдвигать строку 2 раза, чтобы получить «1100», которое делится на 2 ^ 2, следовательно, ответ равен 2.

Вот мое решение.. однако это дает мне tle в большинстве тестовых примеров и неправильный ответ в некоторых тестовых примерах..

 int highestpower(int n)
{
    return (n amp; (~(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;
}
  

как я могу решить этот ответ?Спасибо..

Мне трудно понять логику вашего кода. На практике это не удалось практически во всех случаях, которые я тестировал.

Более того, это кажется довольно сложным. Достаточно посчитать количество последовательных нулей. Мы просто должны обратить внимание, что это вычисление должно выполняться циклическим способом. Например, если 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 amp; (~(n - 1)));
}

int findnum(const std::stringamp; 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::stringamp; 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::stringamp; 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";
    }
}