31天刷完剑指offer——(第3天) 字符串

#pragma once
#include<string>

using std::string;

/* 利用辅助字符串存储结果

class Solution {
public:
    string replaceSpace(string s) {
        string str;
        for (auto ch : s) {
            if (ch == ' ') {
                str += "%20";
            }
            else {
                str += ch;
            }
        }

        return str;
    }
};

*/


// 原地修改 （空间复杂度和时间复杂度都更好）
class Solution {
public:
    string replaceSpace(string s) {
        int counts = 0;
        for (auto ch : s) {          // 获取字符串s中的空格数
            if (ch == ' ') {
                ++counts;
            }
        }

        int n = s.size();                        // 保存原s的size （因为扩容后会改变s的size）
        s.resize(s.size() + 2 * counts);         // 扩容 （使得s的空间正好容得下 替换后的字符串。之所以是2*counts而不是3*counts，是因为s中本来就有一个空格）
        int i = n - 1, j = s.size() - 1;         // i指向原s中最后一个元素，j指向扩容后s的最后一个位置

        while (i != j) {              // 从后完全复制内容，当所有空格都被替换后 i==j，即替换完成
            if (s[i] != ' ') {        
                s[j--] = s[i--];
            }
            else {
                s[j--] = '0';
                s[j--] = '2';
                s[j--] = '%';
                --i;
            }
        }

        return s;
    }
};

#pragma once
#include<string>

using std::string;

// 翻转
class Solution {
public:

    void reverse(int left, int right, string& s);
    string reverseLeftWords(string s, int n) {
        int len = s.size();
        reverse(0, len - 1, s);             // 整体翻转
        reverse(0, len - n - 1, s);         // 局部翻转
        reverse(len - n, len - 1, s);       // 局部翻转

        return s;
    }
};

void Solution::reverse(int left, int right, string& s) {
    while (left < right) {
        std::swap(s[left++], s[right--]);
    }
}