当前位置：首页 > article >正文

C++之《剑指offer》学习记录（9）：字符串替换空格

article 2025/1/10 12:01:04

笔者最近在找工作时，无意间读到了一本名为《剑指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 world
    cout << 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 string

    return 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]），就需要确保这些位置是有效的，即字符串已经有足够的容量，否则会出现越界访问问题。

查看全文

http://www.kler.cn/a/354661.html