假设你有一个二进制字符串S并且你只被允许做一个操作，即Right-Rotate by K-bitsK = [0, Length of the string]的地方.编写一个算法，该算法将打印定义进程可以创建的最大二进制数。
例如：
S = [00101]那么我可以从过程中获得的最大值是10100即20.S = [011010]那么我可以从过程中获得的最大值是110100即52.S = [1100]那么我可以从过程中获得的最大值是1100即12.
字符串S的长度有一个上限，即5*(10^5).
我想到的想法有点天真，那就是：我们知道，当你右旋任何二进制数1-bit时，你会得到相同的二进制数，m旋转后m = number of bits required to represent that number。
因此，我按1向右旋转，直到我到达我开始使用的数字，在此过程中，我跟踪我遇到的最大值，最后我打印最大值。
有没有解决问题的有效方法？
UPD1：这是问题的根源 One-Zero，这一切都归结为我上面描述的陈述。
UPD2：由于答案可能很大，程序将打印答案模10^9 + 7.
您希望查找在带有环绕的二进制编码字符串中表示的最大数字。
以下是解决方案的步骤：
- 设
len字符串的长度 - 分配大小为
2 * len的数组，并将字符串复制到其中。 - 使用线性搜索，查找此数组中长度
len的最大子字符串的位置pos(字典顺序可用于此)。 - 计算
res，转换后的数模109+7，从pos开始读取len位。 - 释放阵列并返回
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] -> %ldn", argv[i], max_bin(argv[i]));
}
return 0;
}
如果需要，避免内存分配是可行的。
又是我。
今天早上我在淋浴时对你的问题进行了更多的思考，我突然想到你可以对输入字符串的开始索引数组进行快速选择(如果你熟悉的话)，并据此确定最"有价值的"旋转的索引。
我在这里展示的内容并不关心以您需要的方式呈现结果，只关心确定旋转的最佳偏移量是多少。
这不是教科书式的快速选择实现，而是一种简化的方法，它做同样的事情，同时考虑到我们正在处理的是一串零和一。
主要驱动逻辑：
static void Main(string[] args)
{
Console.WriteLine(FindBestIndex("")); // exp -1
Console.WriteLine(FindBestIndex("1")); // exp 0
Console.WriteLine(FindBestIndex("0")); // exp 0
Console.WriteLine(FindBestIndex("110100")); // exp 0
Console.WriteLine(FindBestIndex("100110")); // exp 3
Console.WriteLine(FindBestIndex("01101110")); // exp 4
Console.WriteLine(FindBestIndex("11001110011")); // exp 9
Console.WriteLine(FindBestIndex("1110100111110000011")); // exp 17
}
设置我们将要排序的索引数组，然后调用FindHighest来完成实际工作：
static int FindBestIndex(string input)
{
if (string.IsNullOrEmpty(input))
return -1;
int[] indexes = new int[input.Length];
for (int i = 0; i < indexes.Length; i++)
{
indexes[i] = i;
}
return FindHighest(input, indexes, 0, input.Length);
}
根据每个索引是指向字符串中此偏移量处以 0 开头还是以 1 开头的字符串，将索引数组分为两半。
一旦完成，如果我们只有一个元素以 1 开头，我们就拥有最好的字符串，否则如果我们有更多，则根据下一个索引对它们进行分区。如果没有一个以 1 开头，则以相同的方式继续从 0 开始。
static int FindHighest(string s, int[] p, int index, int len)
{
// allocate two new arrays,
// one for the elements of p that have zero at this index, and
// one for the elements of p that have one at this index
int[] zero = new int[len];
int[] one = new int[len];
int count_zero = 0;
int count_one = 0;
// run through p and distribute its elements to 'zero' and 'one'
for (int i = 0; i < len; i++)
{
int ix = p[i]; // index into string
int pos = (ix + index) % s.Length; // wrap for string length
if (s[pos] == '0')
{
zero[count_zero++] = ix;
}
else
{
one[count_one++] = ix;
}
}
// if we have a one in this position, use that, else proceed with zero (below)
if (count_one > 1)
{
// if we have more than one, sort on the next position (index)
return FindHighest(s, one, index + 1, count_one);
} else if (count_one == 1)
{
// we have exactly one entry left in ones, so that's the best one we have overall
return one[0];
}
if (count_zero > 1)
{
// if we have more than one, sort on the next position (index)
return FindHighest(s, zero, index + 1, count_zero);
}
else if (count_zero == 1)
{
// we have exactly one entry left in zeroes, and we didn't have any in ones,
// so this is the best one we have overall
return zero[0];
}
return -1;
}
请注意，这可以通过扩展逻辑来进一步优化：如果输入字符串有任何one，那么将字符串以zero开头的索引添加到索引数组中是没有意义的FindBestIndex，因为这些索引会较差。此外，如果索引确实以one开头，但前一个索引也以 开头，您也可以省略当前索引，因为前一个索引总是更好，因为该字符串流入此字符。
如果您愿意，还可以重构以删除递归以支持循环。
如果我正在解决这个问题，我会这样做，如下所示。
我认为这一切都与计算"1"和"0"的交替运行有关，将"1"的运行和"0"的运行视为一对，然后抨击这些对的列表。
让我们首先扫描到第一个"1"，并设置起始位置s。 然后计算 '1's c1 的每次运行和 '0's c0 的后续运行，创建对(c1，c0)。
然后，扫描向前进行到末端，根据需要进行圆形包装。 如果我们将一个或多个"1"和"0"的运行表示为个位数，将"|"表示为字符串的开头和结尾，那么我们会遇到以下情况：
|10101010|
^ initial start position s -- the string ends neatly with a run of '0's
|1010101|
^ new start position s -- the string starts and ends in a '1', so the first
run of '1's and run of '0's are rotated (left),
to be appended to the last run of '1's
Note that this changes our start position.
|01010101|
^ initial start position s -- the first run of '0's is rotated (left),
to follow the last run of '1's.
|010101010|
^ initial start position s -- the first run of '0's is rotated (left),
to be appended to the last run of '0's.
注意：如果字符串都以"1"开头和结尾，则最初有n次运行 '0 和n+1次运行 '1'，但旋转将其减少到n次运行 '1'。 类似地，但相反，如果字符串都以"0"开头和结尾。
让我们使用A作为货币对(a1，a0)的简写。 假设我们有另一对X--(x1，x0)-- 然后可以比较两对，因此：
- 如果a1> x1或 (a1 = x1 和 (a0
) => A> X--A是更好的开始 - 如果a1 = x1且a0 = x0=>A = X
- 如果a1
或 (a1 = x1和 (a0> x0) =>A <</em> X--X是更好的开始
诀窍可能是将每对打包成一个整数 - 比如(x1 * N) - x0，其中N至少是字符串的最大允许长度 - 以便于比较。
在扫描字符串(如上所述)期间，让我们构造一个对向量。 在此过程中，收集最大的对值A，以及A每次出现的位置列表s。 列表中的每个s都是潜在的最佳起始位置。 (记录的 s必须是对向量中的索引和原始字符串中的偏移量。
[如果输入字符串真的很大，那么构造所有对的整个向量会消耗内存。 在这种情况下，需要将向量作为"虚拟"向量处理，并且当需要该向量中的项时，必须通过读取实际字符串的相应部分来创建它。
现在：
让我们简化两个或多个连续A的组。 显然，在这样一个组中，第二个和随后的A不可能是最好的开始，因为左边有一个更好的A。 因此，在扫描中，我们只需要记录此类组的第一个A的s。
如果字符串以一个或多个 A 开头并以一个或多个A结尾，则需要"旋转"将它们收集为单个组，并仅记录该组中最左侧A的s(以通常的方式)。
如果清单上只有一个，我们的工作就完成了。 如果字符串是端到端A，则会在此处找到。
否则，我们需要考虑(初始)A的每个s后面的对 - 当我们说"跟随"时，我们包括从字符串的末尾到开头的环绕(以及，等效地，对列表)。
注意：在这一点上，我们知道我们列表中的所有(初始)A后面跟着零个或多个A，然后至少有一个x，其中x。
因此，设置i = 1，并考虑s+i处的所有对作为我们的s列表。 仅保留找到的最大对的实例的s。 因此，对于i = 1，在本例中，我们考虑对x、y和z：
- 。斧头。。。。嗡......亚利桑那州..斧头。。。哎。。。
如果x是最大的，则此通道将丢弃Ay和两个Az。 如果只剩下一个s——在这个例子中，y是最大的——我们的工作就完成了。 否则，对i = i+1重复此操作。
还有最后一个(我认为)皱纹。 假设在发现z是第 i 对中最大的一个后，我们有：
- 。A===zA===z...
其中两个运行===彼此相同。 通过告诉我们在相同的运行中忽略第二个和后续A的相同逻辑，我们现在可以丢弃第二个 A===z。 事实上，我们可以丢弃第三个、第四个等连续的 A===z。 令人高兴的是，这处理了(说)的极端情况：
=zA===zA===- zA==
其中字符串是A===z的序列！
我不知道，当我带着铅笔和纸出发时，这一切似乎比我预期的要复杂：-(
我想有人比我聪明得多，可以将其简化为一些标准的最大前缀字符串问题。
我今天很无聊，所以我敲掉了一些代码(并在 2020 年 4 月 10 日对其进行了修订)。
typedef unsigned int uint ; // assume that's uint32_t or similar
enum { max_string_len = 5 * 100000 } ; // 5 * 10^5
typedef uint64_t pair_t ;
static uint
one_zero(const char* str, uint N)
{
enum { debug = false } ;
void* mem ;
size_t nmx ;
uint s1, s0 ; // initial run of '1'/'0's to be rotated
uint s ;
pair_t* pv ; // pair vector
uint* psi ; // pair string index
uint* spv ; // starts vector -- pair indexes
uint pn ; // count of pairs
uint sn ; // count of starts
pair_t bp ; // current best start pair value
uint bpi ; // current best start pair index
uint bsc ; // count of further best starts
char ch ;
if (N > max_string_len)
{
printf("*** N = %u > max_string_len (%u)n", N, max_string_len) ;
return UINT_MAX ;
} ;
if (N < 1)
{
printf("*** N = 0 !!n") ;
return UINT_MAX ;
} ;
// Decide on initial start position.
s = s1 = s0 = 0 ;
if (str[0] == '0')
{
// Start at first '1' after initial run of '0's
do
{
s += 1 ;
if (s == N)
return 0 ; // String is all '0's !!
}
while (str[s] == '0') ;
s0 = s ; // rotate initial run of '0's
}
else
{
// First digit is '1', but if last digit is also '1', need to rotate.
if (str[N-1] == '1')
{
// Step past the leading run of '1's and set length s1.
// This run will be appended to the last run of '1's in the string
do
{
s += 1 ;
if (s == N)
return 0 ; // String is all '1's !!
}
while (str[s] == '1') ;
s1 = s ; // rotate initial run of '1's
// Step past the (now) leading run of '0's and set length s0.
// This run will be appended to the last run of '1's in the string
//
// NB: we know there is at least one '0' and at least one '1' before
// the end of the string
do { s += 1 ; } while (str[s] == '0') ;
s0 = s - s1 ;
} ;
} ;
// Scan the string to construct the vector of pairs and the list of potential
// starts.
nmx = (((N / 2) + 64) / 64) * 64 ;
mem = malloc(nmx * (sizeof(pair_t) + sizeof(uint) + sizeof(uint))) ;
pv = (pair_t*)mem ;
spv = (uint*)(pv + nmx) ;
psi = (uint*)(spv + nmx) ;
pn = 0 ;
bp = 0 ; // no pair is 0 !
bpi = 0 ;
bsc = 0 ; // no best yet
do
{
uint x1, x0 ;
pair_t xp ;
psi[pn] = s ;
x1 = x0 = 0 ;
do
{
x1 += 1 ;
s += 1 ;
ch = (s < N) ? str[s] : ' ' ;
}
while (ch == '1') ;
if (ch == ' ')
{
x1 += s1 ;
x0 = s0 ;
}
else
{
do
{
x0 += 1 ;
s += 1 ;
ch = (s < N) ? str[s] : ' ' ;
}
while (str[s] == '0') ;
if (ch == ' ')
x0 += s0 ;
} ;
// Register pair (x1,x0)
reg:
pv[pn] = xp = ((uint64_t)x1 << 32) - x0 ;
if (debug && (N == 264))
printf("si=%u, sn=%u, pn=%u, xp=%lx bp=%lxn", psi[sn], sn, pn, xp, bp) ;
if (xp > bp)
{
// New best start.
bpi = pn ;
bsc = 0 ;
bp = xp ;
}
else
bsc += (xp == bp) ;
pn += 1 ;
}
while (ch != ' ') ;
// If there are 2 or more best starts, need to find them all, but discard
// second and subsequent contiguous ones.
spv[0] = bpi ;
sn = 1 ;
if (bsc != 0)
{
uint pi ;
bool rp ;
pi = bpi ;
rp = true ;
do
{
pi += 1 ;
if (pv[pi] != bp)
rp = false ;
else
{
bsc -= 1 ;
if (!rp)
{
spv[sn++] = pi ;
rp = true ;
} ;
} ;
}
while (bsc != 0) ;
} ;
// We have: pn pairs in pv[]
// sn start positions in sv[]
for (uint i = 1 ; sn > 1 ; ++i)
{
uint sc ;
uint pi ;
pair_t bp ;
if (debug && (N == 264))
{
printf("i=%u, sn=%u, pv:", i, sn) ;
for (uint s = 0 ; s < sn ; ++s)
printf(" %u", psi[spv[s]]) ;
printf("n") ;
} ;
pi = spv[0] + i ; // index of first s+i pair
if (pi >= pn) { pi -= pn ; } ;
bp = pv[pi] ; // best value, so far.
sc = 1 ; // new count of best starts
for (uint sj = 1 ; sj < sn ; ++sj)
{
// Consider the ith pair ahead of sj -- compare with best so far.
uint pb, pj ;
pair_t xp ;
pb = spv[sj] ;
pj = pb + i ; // index of next s+i pair
if (pj >= pn) { pj -= pn ; } ;
xp = pv[pj] ;
if (xp == bp)
{
// sj is equal to the best so far
//
// So we keep both, unless we have the 'A==zA==z' case,
// where 'z == xp == sp', the current 'ith' position.
uint pa ;
pa = pi + 1 ;
if (pa == pn) { pa = 0 ; } ; // position after first 'z'
// If this is not an A==zA==z case, keep sj
// Otherwise, drop sj (by not putting it back into the list),
// but update pi so can spot A==zA==zA===z etc. cases.
if (pa != pb)
spv[sc++] = spv[sj] ; // keep sj
else
pi = pj ; // for further repeats
}
else if (xp < bp)
{
// sj is less than best -- do not put it back into the list
}
else
{
// sj is better than best -- discard everything so far, and
// set new best.
sc = 1 ; // back to one start
spv[0] = spv[sj] ; // new best
pi = pj ; // new index of ith pair
bp = xp ; // new best pair
} ;
} ;
sn = sc ;
} ;
s = psi[spv[0]] ;
free(mem) ;
return s ;
}
我已经针对其他地方给出的蛮力方法对此进行了测试，据我所知，这是(现在，2020 年 4 月 10 日)工作代码。
当我在我的机器上计时时，对于 100,000 个 400,000..500,000 个字符(随机)的随机字符串，我得到：
Brute Force: 281.8 secs CPU
My method: 130.3 secs CPU
这不包括构造随机字符串并运行空测试的 8.3 秒。 (这听起来可能很多，但对于 100,000 个 450,000 个字符的字符串，平均而言，每个字符的 CPU 周期不到 1 个。
因此，对于随机字符串，我的复杂方法比蛮力快两倍多一点。 但它使用 ~N*16 字节的内存，其中暴力破解方法使用 N*2 字节。 鉴于所涉及的努力，结果并不十分令人满意。
但是，我也尝试了两个病理案例，(1)重复"10"和(2)重复"10100010"，对于仅1000(不是100000)400,000个字符的字符串(随机)，我得到了：
Brute Force: (1) 1730.9 (2) 319.0 secs CPU
My method: 0.7 0.7 secs CPU
那个O(n^2)每次都会杀了你！
#include <iostream>
#include <string>
#include <math.h>
using namespace std;
int convt(int N,string S)
{
int sum=0;
for(int i=0; i<N; i++)
{
int num=S[i];
sum += pow(2,N-1-i)*(num-48);
}
return sum;
}
string rot(int N, string S)
{
int temp;
temp = S[0];
for( int i=0; i<N;i++)
S[i]=S[i+1];
S[N-1]=temp;
return S;
}
int main() {
int t;
cin>>t;
while(t--)
{
int N,K;
cin>>N;
cin>>K;
char S[N];
for(int i=0; i<N; i++)
cin>>S[i];
string SS= S;
int mx_val=INT_MIN;
for(int i=0;i<N;i++)
{
string S1=rot(N,SS);
SS= S1;
int k_val=convt(N,SS);
if (k_val>mx_val)
mx_val=k_val;
}
int ki=0;
int j=0;
string S2=S;
while(ki!=K)
{
S2=rot(N,S2);
if (convt(N,S2)==mx_val)
ki++;
j++;
}
cout<<j<<endl;
}
}