时间戳

首页 > 解决方案 > 如果只允许一个操作，即按 K 位右移，则二进制字符串将产生的最大二进制数，其中 K = [0，字符串长度]

c - 如果只允许一个操作，即按 K 位右移，则二进制字符串将产生的最大二进制数，其中 K = [0，字符串长度]

问题描述

假设您有一个二进制字符串S，并且您只能执行一项操作，即Right-Rotate by K-bitswhere K = [0, Length of the string]。编写一个算法，该算法将打印您可以通过定义的过程创建的最大二进制数。

例如：

  1. S = [00101]那么我可以从这个过程中得到的最大值是10100ie 20。
  2. S = [011010]那么我可以从这个过程中得到的最大值是110100ie 52。
  3. S = [1100]那么我可以从这个过程中得到的最大值是1100ie 12。

字符串的长度S有一个上限，即5*(10^5)。

我想到的想法有点天真，那就是：正如我们所知，当您将任何二进制数右旋转 时1-bit，您在旋转后得到相同的二进制数mwhere m = number of bits required to represent that number。
所以，我向右旋转1直到我得到我开始的数字，在这个过程中，我跟踪我遇到的最大值，最后我打印最大值。

有没有解决问题的有效方法？

UPD1：这是问题的根源One-Zero，这一切都归结为我上面描述的陈述。

UPD2：由于答案可能很大，程序将打印答案模10^9 + 7.

标签： calgorithmbit-manipulation

解决方案

您想找到用环绕的二进制编码字符串表示的最大数字。

以下是解决方案的步骤：

  1. 设为len字符串的长度
  2. 分配一个大小数组2 * len并将字符串复制到它。
  3. 使用线性搜索，找到该数组pos中长度最大的子串的位置len（可以使用字典顺序）。
  4. 计算res，转换后的数模 10 9 +7，读取len从 开始的位pos。
  5. 释放数组并返回res。

这是一个简单的函数实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long max_bin(const char *S) {
    size_t i, pos, len;
    char *a;
    // long has at least 31 value bits, enough for numbers upto 2 * 1000000007
    long res;

    if ((len = strlen(S)) == 0)
        return 0;

    if ((a = malloc(len + len)) == NULL)
        return -1;

    memcpy(a, S, len);
    memcpy(a + len, S, len);
    // find the smallest right rotation for the greatest substring
    for (pos = i = len; --i > 0;) {
        if (memcmp(a + i, a + pos, len) > 0)
            pos = i;
    }
    res = 0;
    for (i = 0; i < len; i++) {
        res = res + res + a[pos + i] - '0';
        if (res >= 1000000007)
            res -= 1000000007;
    }
    free(a);
    return res;
}

int main(int argc, char *argv[]) {
    for (int i = 1; i < argc; i++) {
        printf("[%s] -> %ld\n", argv[i], max_bin(argv[i]));
    }
    return 0;
}

如果需要，避免内存分配是可行的。

推荐阅读