剑指offer 字符串持续更新中...

devtools/2025/2/6 20:16:35/

文章目录

1. 替换空格
- 1.1 题目描述
- 1.2 从前向后替换空格
- 1.3 从后向前替换空格

持续更新中…

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;}
};