笔者最近在找工作时，无意间读到了一本名为《剑指offer》的书，粗略翻阅了一下，感觉这将会是一本能让我不再苦恼于笔试和面试“手搓代码”的书。故笔者写下该系列博客记录自己的学习历程，希望能和这本书的读者朋友们一起交流学习心得。
介绍：《剑指Offer：名企面试官精讲典型编程题（第2版）》剖析了80个典型的编程面试题，系统整理基础知识、代码质量、解题思路、优化效率和综合能力这5个面试要点。
编程题链接：牛客网在线编程_算法面试_面试必刷TOP101 (nowcoder.com)
本博客关键词：字符串，替换空格
字符串
字符串是由若干字符组成的序列。由于字符串在编程时使用频率很高，为了优化，很多语言对字符串都做了特殊的规定。
C语言
先从C语言的字符串讲起，C语言有两种常用的初始化字符串的方式：char str[]="hello"和char *str="hello"。大家先看看下面这个代码，看看会输出什么：
int main(int argc, char const *argv[])
{char str1[] = "hello";char str2[] = "hello";const char *str3 = "hello";const char *str4 = "hello";if (str1 == str2){printf("str1 = str2\n");}else{printf("str1 != str2\n");}if (str3 == str4){printf("str3 = str4\n");}else{printf("str3 != str4\n");}return 0;
}
结果是输出：str1 != str2和str3 = str4。为了节省内存，C/C++把常量字符串放在单独的一个内存区域（只读区）。当几个指针赋值给相同的常量字符串时，他们实际上会指向相同的内存地址。如果通过数组来初始化的话，就算字符串内容相同，但是对应的内存地址也是不同的。
C++
C++除了可以通过char str[]="hello"和char *str="hello"这两种方式来定义字符串外，还提供了一种string方法
string是C++标准库中的一个类，是一种更强大、更方便的处理字符串的方法。string会自动管理内存，自动调整内存大小，并为字符串操作提供了很多方法。
下面介绍C++中string类的几大特点：
- 支持字符串拼接（
+）、比较（==、!=）、访问单个字符（[]或at()）等操作。 - 提供了许多方法来操作字符串，如
length()（获取长度）、substr()（获取子字符串）、find()（查找子串）、insert()（插入）、erase()（删除）和replace()（替换）。 - 自动管理内存。
#include <iostream>
#include <string>using namespace std;int main(int argc, char const *argv[])
{string str1 = "hello";string str2 = " world";string str3 = str1 + str2;cout << str3 << endl; // 输出：hello worldcout << str1.size() << str2.size() << str3.size() << endl; // 输出：5 6 11；计算字符串大小不包括'\0'cout << str3.substr(6, 5) << endl; // 输出：world；substr为从str3索引为6的字符开始算起的5个字符cout << str3.replace(6, 5, "string") << endl; // 输出：hello stringreturn 0;
}
替换空格
剑指offer编程题链接：
替换空格_牛客题霸_牛客网 (nowcoder.com)
请实现一个函数，将一个字符串s中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
测试用例：
- 字符串内没有空格：
"HelloWorld" - 字符串内有空格，但分布在前中后的位置：
" HelloWorld","Hello World","HelloWorld " - 字符串全是空格：
" " - 空字符串：
""
解法一：充分利用string的性质
class Solution {public:string replaceSpace(string s) {if (s.empty()) {return "";}for (int i = 0; i < s.size(); i++) {if (s[i] == ' ') {s.replace(i, 1, "%20");}}return s;}
};
由于string具有自动管理内存的功能，我们在处理string字符串时无需注意字符在内存中位置移动的问题，通过replace方法将空格替换为"%20就是最直接最简单的。
解法二：双指针法
- 时间复杂度：
O(n) - 空间复杂度：最差为
O(n)
class Solution {public:string replaceSpace(string s) {if (s.empty()) {return "";}int originalIndex = s.size();int blankCount = 0;for (char i : s) {if (i == ' ') {blankCount++;}}int newIndex = originalIndex + 2 * blankCount;// 扩展字符串大小，确保有足够的空间进行操作s.resize(s.size() + 1 + 2 * blankCount);while (originalIndex < newIndex) {if (s[originalIndex] != ' ') {s[newIndex] = s[originalIndex];--newIndex;--originalIndex;} else {s[newIndex--] = '0';s[newIndex--] = '2';s[newIndex--] = '%';--originalIndex;}}return s;}
};
这里对string进行了一个扩容操作：s.resize(s.size() + 1 + 2 * blankCount);，一开是我没有加这句，测试用例显示不通过，查看输出就是结果只返回了s原始大小的字符串，没有动态扩容，查了下资料，得出以下结论：
std::string确实会自动管理内存，但这种“自动管理”是在对字符串进行追加或插入操作时（例如用append）才会发生。如果直接通过下标访问或修改字符串的位置（比如str[index]），就需要确保这些位置是有效的，即字符串已经有足够的容量，否则会出现越界访问问题。
