1. 替换空格

替换空格

1.1 题目描述

题目描述：将一个字符串s中的每个空格替换成“%20”。

示例：

输入："We Are Happy"
返回："We%20Are%20Happy"

1.2 从前向后替换空格

时间复杂度是O(n^2)

#include <string>
class Solution {
    std::string res;        // 要返回的字符串
    int n, blank_cnt;       // res的长度, 空格的个数
  public:
    string replaceSpace(string s) {
        res = s;
        blank_cnt = countBlank(s);
        res.resize(s.size() + blank_cnt * 2);
        n = res.size();
        for (int i = 0; i < n; ++i) {
            if (res[i] == ' ') {
                moveStr(i);
                res[i]     = '%';
                res[i + 1] = '2';
                res[i + 2] = '0';
            }
        }
        return res;
    }

    // 从pos+1开始，将每个字符向后移动两次
    void moveStr(int pos) {
        for (int i = n; i >= pos + 1; --i) {
            res[i + 2] = res[i];
        }
    }

    // 得到空格的个数
    int countBlank(string s) {
        int cnt = 0;
        for (int i = 0; i < s.size(); ++i)
            if (res[i] == ' ')
                cnt++;
        return cnt;
    }
};

1.3 从后向前替换空格

时间复杂度是O(n)

#include <cstddef>
#include <string>
#include <type_traits>
class Solution {
    std::string res;        // 要返回的字符串
    size_t n, blank_cnt;    // res的长度, 空格的个数
    int left, right;        // 左右指针
  public:
    string replaceSpace(string s) {
        res = s;
        blank_cnt = countBlank(s);
        res.resize(s.size() + blank_cnt * 2);
        n = res.size();
        left = s.size(), right = n;
        while (left < right) {
            if (res[left] == ' ') {
                left--;
                res[right--] = '0';
                res[right--] = '2';
                res[right--] = '%';
            } else {
                res[right] = res[left];
                right--, left--;
            }
            if (left == right || left < 0)    break;
        }
        std::cout << res;
        return res;
    }

    // 得到空格的个数
    int countBlank(string s) {
        int cnt = 0;
        for (int i = 0; i < s.size(); ++i)
            if (res[i] == ' ')
                cnt++;
        return cnt;
    }
};

这题88. 合并两个有序数组 - 力扣（LeetCode）与之类似，我们可以得到一个结论：合并两个字符串（包括数组），如果从前往后复制，可能重复移动，那么就可以考虑从后往前复制