C++ 算法技巧 — 字符串 (String)

章节概述

字符串是字符序列，在算法竞赛中常见的操作包括遍历、查找、替换、转换等。
C++ string 类提供了丰富的成员函数。

核心原理

1. 字符串的底层表示

C 风格: char 数组，以 ‘\0’ 结尾
C++ string: 动态分配，自动管理内存

2. 核心操作复杂度

操作	复杂度	说明
s[i]	O(1)	下标访问
s.size()	O(1)	返回长度
s.find(c)	O(n)	查找字符/子串
s.substr(pos, len)	O(len)	截取子串
s.erase(0, 1)	O(n)	删除首字符需移动

3. 字符处理技巧

字符转数字: c - '0'
字符下标映射: c - 'a' → [0, 25]
小写转大写: c - 32 或 toupper(c)
数字反转: while(n) { rev = rev*10 + n%10; n /= 10; }

关键数据结构

A_容器_Container — string 是特殊的 vector

P5015 [NOIP2018 普及组] 标题统计

题目: 给定一行字符串标题，统计其中英文字符和数字字符的总数。

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s;
    getline(cin, s);
    int cnt = 0;
    for (char c : s)
        if (c != ' ' && c != '\n')
            cnt++;
    cout << cnt << endl;
    return 0;
}

P1765 手机

题目: 手机键盘上字母分布，每个字母在键上的位置决定按键次数。求总按键次数。

#include <iostream>
#include <string>
using namespace std;
int main() {
    string k[] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    string s;
    getline(cin, s);
    int ans = 0;
    for (char c : s) {
        if (c == ' ') { ans++; continue; }
        for (int i = 0; i < 8; i++) {
            int pos = k[i].find(c);
            if (pos != string::npos) {
                ans += pos + 1;
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

P1553 数字反转（升级版）

题目: 给定一个数（可能为整数、小数、分数或百分数），反转其数字部分。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
string rev(string s) {
    reverse(s.begin(), s.end());
    while (s.size() > 1 && s[0] == '0') s.erase(0, 1);
    return s;
}
 
int main() {
    string s;
    cin >> s;
    if (s.find('.') != string::npos) {
        int pos = s.find('.');
        string a = s.substr(0, pos), b = s.substr(pos + 1);
        while (b.size() > 1 && b.back() == '0') b.pop_back();
        cout << rev(a) << "." << rev(b) << endl;
    } else if (s.find('/') != string::npos) {
        int pos = s.find('/');
        cout << rev(s.substr(0, pos)) << "/" << rev(s.substr(pos + 1)) << endl;
    } else if (s.back() == '%') {
        s.pop_back();
        cout << rev(s) << "%" << endl;
    } else {
        cout << rev(s) << endl;
    }
    return 0;
}

RootStack

探索

C++ 算法技巧 — 字符串 (String)

章节概述

核心原理

关键数据结构

P5015 [NOIP2018 普及组] 标题统计

P1765 手机

P1553 数字反转（升级版）

推荐练习题（洛谷）

相关技巧

多平台练习

关系图谱

目录

反向链接