文字列循環シフトアルゴリズム
1044 ワード
アルゴリズムをちゃんと勉強するつもりです.真似から始まります.今書いているアルゴリズムは他の人の原理を見て自分で実現します.蓄積が少なすぎて、多くの問題が一番いい解決策を思いつかないですが、後でよくなります.
文字列の循環シフト(左シフトと右シフトの原理は同じ)原理:
文字列1234 abcdのように、右に4ビットシフトして、下記のように実現します.
1234 bcd→4321 bcd→4321 dcba→abcd 234
前の4文字を反転させ、後の4文字を反転させて、全部反転させます.
文字列の循環シフト(左シフトと右シフトの原理は同じ)原理:
文字列1234 abcdのように、右に4ビットシフトして、下記のように実現します.
1234 bcd→4321 bcd→4321 dcba→abcd 234
前の4文字を反転させ、後の4文字を反転させて、全部反転させます.
/*
*
2013.7.23
DVD0423
function:
:
: N
K , O(N), O(1),
:
N=8 abcdefgh;
:
K=4, 4 , efghabcd。
*
*/
#include
#include
using namespace std;
void invertString(string &strN, int start, int end)
{
int length = end - start;
for(int i = 0; i < length/2; ++i)
{
char temp;
temp = strN[end-1-i];
strN[end-1-i] = strN[start+i];
strN[start+i] = temp;
}
}
void rightShift(string &strN, int K)
{
int N= strN.length();
invertString(strN, 0, N-K);
invertString(strN, N-K, N);
invertString(strN, 0, N);
}
int main(int argc, char *argv[])
{
string strN;
int K= 0;
cout<>strN>>K;
rightShift( strN, K);
cout<