字符移位(腾讯2017实习生）

字符移位

1、题目：
小Q最近遇到了一个难题：把一个字符串的大写字母放到字符串的后面，各个字符的相对位置不变，且不能申请额外的空间。
你能帮帮小Q吗？

输入描述:
输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.

输出描述:
对于每组数据，输出移位后的字符串。

输入例子:
AkleBiCeilD

输出例子:
kleieilABCD

2、代码：

#include <iostream>
#include <string>
#include <vector>
using namespace std;
void move(string *sp,const int &big,const int &small)
{
    string s=*(sp+big);
    for (int i = big;i <small;++i)
    {
        *(sp+i) = *(sp+i + 1);
    }
    *(sp+small) = *(sp+big);
}


string getMoveBig(string str)
{
    int len = str.length(),big=-1,small=-1;
    bool flagB = true,flagS=false;
    for (int i = len - 1;i >= 0;--i)
    {
        if (str[i] >= 97 && str[i] <= 122)
        {
            if (!flagS)
            {
                small = i;
                flagS = true;
            }
            flagB = false;
        }
        else
        {
            if (!flagB)
            {
                big = i;
                char c = str[big];
                for (int j = big;j <small;++j)
                {
                    str[j] = str[j+1];
                }
                str[small] = c;
                --small;
            }
        }
    }
    return str;
}

int main()
{
    string str;
    vector<string> vs;
    while (cin >> str)
    {
        vs.push_back(str);
    }
    for (auto iter = vs.begin();iter != vs.end();++iter)
    {
        cout << getMoveBig(*iter) << endl;
    }
    system("pause");
    return 0;
}

3、总结：
我以为不会AC（牛客网）的，结果竟然过了。表示自己感觉自己写的耗时应该比较大。主要思路：
A. 从后往前，两个位置标志，一个是碰到的第一个大写字母（位置big），另一个是第一个小写（位置small），执行过程中一定要将位置确定好。
B.一旦碰到了大写字母，就开始移动，small前部分往前移一个，big后填small。