字符串翻转

如将字符串"abcdef"的前两个字符翻转到后面变成"cdefab"。

整个字符串可以分为左边和右边两部分,翻转思路是:

  • 将左边字符串反序("ab"变成"ba")
  • 将右边字符串反序("cdef"变成"fedc")
  • 左右部分反序后的组合是"bafedc"
  • 最后将整个字符串反序("bafedc"变成"cdefab")得到我们要的结果

完整代码如下:

void invertStr(char str[], int start, int end)
{
    while (end > start) {
        char temp = str[start];
        str[start] = str[end];
        str[end] = temp;
        ++start;
        --end;
    }
}

void rotateStr(char str[], int len, int leftLen)
{
    leftLen %= len;
    invertStr(str, 0, leftLen - 1);
    invertStr(str, leftLen, len - 1);
    invertStr(str, 0, len - 1);
}

int _tmain(int argc, _TCHAR* argv[])
{
    char str[] = "abcdef"; // defabc
    std::cout << "before:" << str << std::endl;
    rotateStr(str, strlen(str), 2);
    std::cout << "after:" << str << std::endl;

    system("pause");
    return 0;
}

std::string版

class Solution {
public:
    string LeftRotateString(string str, int n) {
        if (str.empty()) {
            return "";
        }

        n %= str.size();
        Invert(str, 0, n - 1);
        Invert(str, n, str.size() - 1);
        Invert(str, 0, str.size() - 1);
        return str;
    }

    void Invert(string &str, int from, int to) {
        while (from < to) {
            std::swap(str[from++], str[to--]);
        }
    }
};

单词翻转

class Solution {
public:
    string ReverseSentence(string str) {
        int index = 0;
        for (int i = 0, count = str.size(); i < count; i++) {
            if (str[i] == ' ') {
                Invert(str, index, i - 1);
                index = i + 1;
            }
        }
        Invert(str, index, str.size() - 1);
        Invert(str, 0, str.size() - 1);
        return str;
    }

    void Invert(string &str, int from, int to) {
        while (from < to) {
            std::swap(str[from++], str[to--]);
        }
    }
};

如:I am a student翻转为student a am I

聊天