文字列の循環シフト
文字列をnビット移動します.1つずつ移動できます.そうすると、n回移動し、len個ずつ移動します.アルゴリズム時間の複雑さはO(n*len)である.新しいメモリを開発して、移動の最終位置を計算して、直接そこに置くこともできます.このように時間責任度はO(1)、空間複雑度はO(len)です.このほか,時間責任度がO(1),空間責任度もO(1)のアルゴリズムがある.
1つ目の方法は,右の左をnビットずつ移動することである.最後まで行って、最後の反転をよくします.
2つ目の方法は,まず前のn文字列を反転させ,その後の反転を行う.最後に文字列全体を反転
第3の方法は、一度に所定の位置に移動することです.
上のシフトはすべて複数回シフトする必要がありますが、移動する文字列を一度に位置させる方法はありませんか.
abcdefghを見て、左に3を移動します.すべての文字列の最終的な位置を一度に計算することができ、シフトすればよい.
aを保存し、dをaに移動し、gをdに移動し、bをgに移動し、eをbに移動し、hをeに移動し、cをhに移動し、fをcに移動し、aをfに移動し、終了する.
4を左に移動すると、デッドサイクルが発生します.これは文字列長とシフトビット数に関係し,両者を移動する最大公約数回数である.
テスト:
1つ目の方法は,右の左をnビットずつ移動することである.最後まで行って、最後の反転をよくします.
// n
void shift(std::string &str, int n)
{
int len = str.length();
if (len <= 0) return;
n = n%len;
int start = 0;//
int end = n;//
int mark = end;//
while (true)
{
while (start != mark&&end < len)
{
char temp = str[start];
str[start] = str[end];
str[end] = temp;
++start;
++end;
//std::cout << str << std::endl;
}
if (start == mark)
{
if (end >= len)
return;
else
mark = end;// mark
}
else if (end >= len)
end = mark;
}
}
2つ目の方法は,まず前のn文字列を反転させ,その後の反転を行う.最後に文字列全体を反転
// [start end]
void inversion(std::string& str, int start, int end)
{
char temp;
while (start<end)
{
temp = str[start];
str[start] = str[end];
str[end] = temp;
++start;
--end;
}
}
void shift1(std::string& str, int n)
{
int len = str.length();
if (len <= 0) return;
n = n%len;
inversion(str, 0, n - 1);// n
inversion(str, n, len - 1);//
inversion(str, 0, len - 1);//
}
第3の方法は、一度に所定の位置に移動することです.
上のシフトはすべて複数回シフトする必要がありますが、移動する文字列を一度に位置させる方法はありませんか.
abcdefghを見て、左に3を移動します.すべての文字列の最終的な位置を一度に計算することができ、シフトすればよい.
aを保存し、dをaに移動し、gをdに移動し、bをgに移動し、eをbに移動し、hをeに移動し、cをhに移動し、fをcに移動し、aをfに移動し、終了する.
4を左に移動すると、デッドサイクルが発生します.これは文字列長とシフトビット数に関係し,両者を移動する最大公約数回数である.
//
int gcd(int max, int min)
{
if (min == 0)
return max;
return gcd(min, max%min);
}
void shift2(std::string& str, int n)
{
int len = str.length();
if (len <= 0) return;
n = n%len;
int GCD = gcd(len, n);
int loop = len / GCD;
for (int i = 0; i < GCD; ++i)//
{
char temp = str[i];
int j;
for (j = 0; j < loop - 1; ++j)// loop 。
{
str[(i + j*n) % len] = str[(i + j*n + n) %len ];
}
str[(i + j*n) % len] = temp;
}
}
テスト:
int main()
{
std::string str = "abcde";
shift(str, 3);
std::cout << str << std::endl;
shift1(str, 3);
std::cout << str << std::endl;
shift2(str, 3);
std::cout << str << std::endl;
return 0;
}