1. 替換空格

替換空格

1.1 題目描述

題目描述：將一個(gè)字符串s中的每個(gè)空格替換成“%20”。

示例：

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

1.2 從前向后替換空格

時(shí)間復(fù)雜度是O(n^2)

#include <string>
class Solution {
    std::string res;        // 要返回的字符串
    int n, blank_cnt;       // res的長度, 空格的個(gè)數(shù)
  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開始，將每個(gè)字符向后移動(dòng)兩次
    void moveStr(int pos) {
        for (int i = n; i >= pos + 1; --i) {
            res[i + 2] = res[i];
        }
    }

    // 得到空格的個(gè)數(shù)
    int countBlank(string s) {
        int cnt = 0;
        for (int i = 0; i < s.size(); ++i)
            if (res[i] == ' ')
                cnt++;
        return cnt;
    }
};

1.3 從后向前替換空格

時(shí)間復(fù)雜度是O(n)

#include <cstddef>
#include <string>
#include <type_traits>
class Solution {
    std::string res;        // 要返回的字符串
    size_t n, blank_cnt;    // res的長度, 空格的個(gè)數(shù)
    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;
    }

    // 得到空格的個(gè)數(shù)
    int countBlank(string s) {
        int cnt = 0;
        for (int i = 0; i < s.size(); ++i)
            if (res[i] == ' ')
                cnt++;
        return cnt;
    }
};

這題88. 合并兩個(gè)有序數(shù)組 - 力扣（LeetCode）與之類似，我們可以得到一個(gè)結(jié)論：合并兩個(gè)字符串（包括數(shù)組），如果從前往后復(fù)制，可能重復(fù)移動(dòng)，那么就可以考慮從后往前復(fù)制