每日一题（字符串篇）

发布于: 2024-11-5 更新于: 2024-11-15 收录于: 编程 , 算法

文章字数: 11680 阅读时间: 24 分钟

简单题

13. 罗马数字转整数

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符	数值
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

例如，罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。

示例 1:

输入: s = “III”
输出: 3

示例 2:

输入: s = “IV”
输出: 4

示例 3:

输入: s = “IX”
输出: 9

示例 4:

输入: s = “LVIII”
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:

输入: s = “MCMXCIV”
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
    int romanToInt(string s)
    {
        // 创建一个哈希表，将罗马数字对应的整数值进行映射
        unordered_map<char, int> map = {
            {'I', 1},
            {'V', 5},
            {'X', 10},
            {'L', 50},
            {'C', 100},
            {'D', 500},
            {'M', 1000}};
        char preChar = 'I'; // 初始化前一个字符为 'I'
        int sum = 0;        // 用于存储转换后的整数总和
        // 从字符串的最后一个字符开始向前遍历
        for (int i = s.length() - 1; i >= 0; --i)
        {
            // 如果当前字符对应的值小于前一个字符对应的值，则减去当前值
            if (map[s[i]] < map[preChar])
                sum -= map[s[i]];
            else // 否则，加上当前值
                sum += map[s[i]];
            preChar = s[i]; // 更新前一个字符
        }
        return sum; // 返回最终计算出的整数值
    }

代码分析

哈希表的使用：
- 利用 unordered_map<char, int> 创建了一个哈希表，将罗马数字字符（如 ‘I’, ‘V’, ‘X’ 等）对应的整数值进行了映射。这使得查找每个罗马字符的整数值变得高效。
初始化变量：
- preChar 用于记录前一个字符，初始设为 ‘I’。
- sum 用于累计转换后的总和，初始为 0。
从后向前遍历：
- 该算法自字符串的最后一个字符开始向前遍历，这是处理罗马数字的一种常见方法。
- 遍历过程中比较当前字符与前一个字符对应的值：
  - 若当前字符的值小于前一个字符的值，则表示需减去当前值。 - 否则，直接加上当前值。
更新前一个字符：
- 在每次循环结束后，更新 preChar 为当前字符，以便下次判断。
返回结果：
- 最终返回 sum，即转换得到的整数值。

注意点

字符顺序的重要性：罗马数字的构成规则决定了从后向前遍历是必要的，这是因为可能会出现小的罗马数字在大的罗马数字前面的情况（如 IV = 4）。
边界条件：应注意输入字符串的合法性，例如只允许包含有效的罗马数字字符。
性能考虑：该实现的时间复杂度为 O(n)，其中 n 是输入字符串的长度；空间复杂度为 O(1)，因映射表不会随输入大小而变化。
哈希表的适用性：使用哈希表可以快速查找罗马字符的值，这是提高效率的重要设计。

67. 二进制求和

力扣原题链接 (简单题)

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

示例 1：

输入: a = “11”, b = “1”
输出： “100”

示例 2：

输入： a = “1010”, b = “1011”
输出： “10101”

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
    string addBinary(string a, string b)
    {
        vector<int> numA, numB, res; // 用于存储二进制数字和结果的向量
        // 将二进制字符串 a 转换为数字向量 numA
        for (const auto &nA : a)
        {
            if (nA == '1')
                numA.push_back(1); // 如果是 '1'，则添加 1
            else
                numA.push_back(0); // 否则添加 0
        }
        // 将二进制字符串 b 转换为数字向量 numB
        for (const auto &nB : b)
        {
            if (nB == '1')
                numB.push_back(1); // 如果是 '1'，则添加 1
            else
                numB.push_back(0); // 否则添加 0
        }
        int k = 0, sum = 0; // k 用于记录进位，sum 用于计算和
        // 当 numA 和 numB 都不为空时进行加法运算
        while (!numA.empty() && !numB.empty())
        {
            sum = k + numA.back() + numB.back(); // 计算当前位的和
            k = 0;                               // 初始化进位
            if (sum / 2 > 0)                     // 判断是否需要进位
            {
                k = 1;                  // 进位为 1
                res.push_back(sum % 2); // 当前位结果
            }
            else
                res.push_back(sum); // 当前位结果为 sum
            numA.pop_back();        // 移除处理过的数字
            numB.pop_back();        // 移除处理过的数字
        }
        // 处理 numA 还剩余的部分
        while (!numA.empty())
        {
            sum = k + numA.back(); // 计算当前位的和
            k = 0;                 // 初始化进位
            if (sum / 2 > 0)       // 判断是否需要进位
            {
                k = 1;                  // 进位为 1
                res.push_back(sum % 2); // 当前位结果
            }
            else
                res.push_back(sum); // 当前位结果为 sum
            numA.pop_back();        // 移除处理过的数字
        }
        // 如果 numB 为空且还有进位，则添加 1
        if (numB.empty() && k > 0)
        {
            res.push_back(1);
            k = 0; // 清除进位
        }
        // 处理 numB 还剩余的部分
        while (!numB.empty())
        {
            sum = k + numB.back(); // 计算当前位的和
            k = 0;                 // 初始化进位
            if (sum / 2 > 0)       // 判断是否需要进位
            {
                k = 1;                  // 进位为 1
                res.push_back(sum % 2); // 当前位结果
            }
            else
                res.push_back(sum); // 当前位结果为 sum
            numB.pop_back();        // 移除处理过的数字
        }
        // 如果还有进位，添加 1
        if (k > 0)
            res.push_back(1);
        // 将结果向量转换为字符串
        string s(res.size(), '0');
        for (size_t i = 0; i < res.size(); ++i)
        {
            s[i] = static_cast<char>(res[i] + '0'); // 将数字转换为字符
        }
        // 反转字符串以得到正确的结果
        return string(s.rbegin(), s.rend());
    }

主要步骤

字符串转换：
- 将二进制字符串 a 和 b 转换为整数向量 numA 和 numB。如果字符为 '1'，则在向量中添加 1，否则添加 0。
加法运算：
- 使用两个 while 循环遍历两个向量，直到至少一个向量为空，逐位对两个二进制位进行加法计算，同时处理进位 k。
- 如果当前位的和大于等于2，则进位 k 设为1，否则进位为0。
处理剩余位：
- 如果一个向量处理完了，继续处理另一个向量中剩余的位及进位。
构建结果字符串：
- 最后，将结果向量 res 转换为字符串，注意需要反转字符串以得到正确的二进制表示。

注意点

进位处理：在每次计算时，要注意处理进位，其值可能会影响当前位的和。
字符串反转：结果向量存储的是从最低位开始的计算结果，因此在返回前需要反转字符串顺序。
字符转换：在向结果字符串中插入数字时，通过加 '0' 转换整数为字符。
边界条件：需要考虑到一个或者两个输入字符串为空的情况，以防止出现错误。

434. 字符串中的单词数

力扣原题链接 (简单题)

统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。

请注意，你可以假定字符串里不包括任何不可打印的字符。

示例:

输入: “Hello, my name is John”
输出: 5
解释: 这里的单词是指连续的不是空格的字符，所以 “Hello,” 算作 1 个单词。

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
    int countSegments(string s)
    {
        // 如果字符串为空，则返回0
        // if (s.empty())
        //     return 0;
        int count = 0; // 单词计数器
        s.push_back(' '); // 在字符串末尾添加空格，以便处理最后一个单词
        // 遍历字符串
        for (size_t i = 0; i < s.length() - 1; ++i)
        {
            // 如果当前字符不是空格且下一个字符是空格，则说明找到了一个单词
            if (!isspace(s[i]) && isspace(s[i + 1]))
                ++count; // 增加单词计数
        }
        return count; // 返回单词总数
    }

代码逻辑

特殊情况处理:
- 在字符串末尾添加一个空格，以确保最后一个单词能够被正确识别。这是为了避免处理最后一个单词时遗漏。
初始化计数器:
- 定义一个变量 count 用于记录单词的数量，并初始化为 0。
遍历字符串:
- 使用 for 循环遍历字符串的每个字符，检查当前字符和下一个字符： - 如果当前字符不是空格且下一个字符是空格，说明找到了一个完整的单词，计数器 count 加一。
返回结果:
- 循环结束后，返回单词总数。

注意点

字符判断：使用 isspace 函数来判断字符是否为空格，确保在统计时只考虑空格。
边界情况：如果字符串为空，虽然在代码中可以处理，但可以提前返回 0 以优化性能（这部分已注释）。

680. 验证回文串 II

力扣原题链接 (简单题)

给你一个字符串 s，最多可以从中删除一个字符。

请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

示例 1：

输入： s = “aba”
输出： true

示例 2：

输入： s = “abca”
输出： true
解释： 你可以删除字符 ‘c’ 。

示例 3：

输入： s = “abc”
输出： false

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
    bool validPalindrome(string s)
    {
        int left = 0, right = s.length() - 1; // 初始化左右指针
        // 检查当前字符串是否是回文
        while (left <= right && s[left] == s[right])
        {
            ++left;  // 向右移动左指针
            --right; // 向左移动右指针
        }
        // 如果左指针大于右指针，说明字符串是回文
        if (left > right)
            return true;
        // 保存当前的左右指针位置
        int tempLeft = left, tempRight = right;
        // 尝试删除左边的字符
        ++left; // 删除左边的字符
        while (left <= right && s[left] == s[right])
        {
            ++left;  // 向右移动左指针
            --right; // 向左移动右指针
        }
        // 如果删除左边字符后成为回文，返回 true
        if (left > right)
            return true;
        // 恢复原来的左右指针位置
        left = tempLeft;
        right = tempRight;
        // 尝试删除右边的字符
        --right; // 删除右边的字符
        while (left <= right && s[left] == s[right])
        {
            ++left;  // 向右移动左指针
            --right; // 向左移动右指针
        }
        // 如果删除右边字符后成为回文，返回 true；否则返回 false
        if (left > right)
            return true;
        else
            return false;
    }

主要步骤

初始化指针：分别设置左右指针 left 和 right，指向字符串的两端。
检查是否是回文：通过循环比较左右指针指向的字符，如果相等则左右指针同时向内移动；如果不相等，则记录当前的指针位置以备后续操作。
尝试删除字符：
- 删除左边的字符：移动左指针向右，再次检查是否形成回文。
- 恢复指针位置：在尝试删除右边字符之前，需将指针恢复到未删除状态。
- 删除右边的字符：移动右指针向左，再次检查是否形成回文。
结果返回：如果经过删除一个字符后，满足回文条件则返回 true，否则返回 false。

注意点

两次循环的条件：在检查字符串是否为回文时，注意需要在左右指针未交汇前进行比较。
指针恢复：在删除一个字符后，要将左右指针恢复，确保下一次操作从正确的位置开始。
边界条件处理：需要考虑空字符串和单字符字符串的情况，这些特殊情况在逻辑上应当直接返回 true。

819. 最常见的单词

力扣原题链接 (简单题)

给你一个字符串 paragraph 和一个表示禁用词的字符串数组 banned ，返回出现频率最高的非禁用词。题目数据保证至少存在一个非禁用词，且答案唯一。

paragraph 中的单词 不区分大小写 ，答案应以小写形式返回。

示例 1：

输入： paragraph = “Bob hit a ball, the hit BALL flew far after it was hit.”, banned = [“hit”]
输出： “ball”
解释： “hit” 出现了 3 次，但它是禁用词。“ball” 出现了两次（没有其他单词出现这么多次），因此它是段落中出现频率最高的非禁用词。请注意，段落中的单词不区分大小写，标点符号会被忽略（即使它们紧挨着单词，如 “ball,"），并且尽管 “hit” 出现的次数更多，但它不能作为答案，因为它是禁用词。

示例 2：

输入： paragraph = “a.”, banned = []
输出： “a”

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
    string mostCommonWord(string paragraph, vector<string> &banned)
    {
        // 遍历段落中的每一个字符
        for (auto &c : paragraph)
        {
            // 将大写字母转换为小写字母
            if (isupper(c))
                c = tolower(c);
            // 将标点符号替换为空格
            if (ispunct(c))
                c = ' ';
        }
        // 使用字符串流处理段落
        istringstream is(paragraph);
        // 创建一个集合来存储禁用词
        unordered_set<string> set;
        for (const auto &s : banned)
        {
            set.emplace(s); // 将禁用词添加到集合中
        }
        // 创建一个映射来记录每个单词的出现次数
        unordered_map<string, int> map;
        string word;
        // 逐个读取单词并统计出现次数
        while (is >> word)
        {
            ++map[word]; // 单词出现次数加一
        }
        int count = 0;    // 用于记录最高频率
        string maxString; // 用于记录出现频率最高的单词
        // 遍历统计的单词及其出现次数
        for (const auto &p : map)
        {
            // 如果单词在禁用词集合中，则跳过
            if (set.find(p.first) != set.end())
            {
                continue;
            }
            // 更新最高频率及对应的单词
            if (p.second > count)
            {
                maxString = p.first; // 更新最高频率单词
                count = p.second;    // 更新最高频率
            }
        }
        return maxString; // 返回频率最高的非禁用词
    }

主要步骤

字符处理：
- 将段落中的字符转换为小写。
- 将标点符号替换为空格，以便以后能准确地分割出单词。
使用字符串流（istringstream）
- 通过字符串流将处理后的段落分割成单词，方便后续的统计操作。
禁用词集合：
- 使用 unordered_set 来存储禁用词，方便查找。
单词统计：
- 使用 unordered_map 来统计每个单词的出现次数。
找出最高频单词：
- 遍历已统计的单词，排除掉禁用词，更新出现频率最高的非禁用词。

注意点

大小写处理： 函数中使用了tolower来处理大写字母，确保比较时统一为小写。
标点符号处理： 使用 ispunct 判断字符是否为标点符号，如果是则替换为空格，这样可以避免标点符号对单词统计的干扰。

859. 亲密字符串

力扣原题链接 (简单题)

给你两个字符串 s 和 goal ，只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果，就返回 true ；否则返回 false 。

交换字母的定义是：取两个下标 i 和 j （下标从 0 开始）且满足 i != j ，接着交换 s[i] 和 s[j] 处的字符。

例如，在 "abcd" 中交换下标 0 和下标 2 的元素可以生成 "cbad" 。

示例 1：

输入： s = “ab”, goal = “ba”
输出： true
解释： 你可以交换 s[0] = ‘a’ 和 s[1] = ‘b’ 生成 “ba”，此时 s 和 goal 相等。

示例 2：

输入： s = “ab”, goal = “ab”
输出： false
解释： 你只能交换 s[0] = ‘a’ 和 s[1] = ‘b’ 生成 “ba”，此时 s 和 goal 不相等。

示例 3：

输入： s = “aa”, goal = “aa”
输出： true
解释： 你可以交换 s[0] = ‘a’ 和 s[1] = ‘a’ 生成 “aa”，此时 s 和 goal 相等。

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
    bool buddyStrings(string s, string goal)
    {
        // 如果两个字符串长度不相等或者长度为1，直接返回 false
        if (s.length() != goal.length() || s.length() == 1)
            return false;
        // 当字符串长度为2时
        if (s.length() == 2)
        {
            // 交换 s 的两个字符
            swap(s[0], s[1]);
            // 判断交换后是否等于 goal
            if (s == goal)
                return true; // 相等，返回 true
            else
                return false; // 不相等，返回 false
        }
        int temp = -1;     // 记录不相等字符的下标
        int count = 0;     // 记录不相等字符的数量
        bool flag = false; // 标志是否有不相等字符
        // 遍历字符串
        for (int i = 0; i < s.length(); ++i)
        {
            // 如果字符不相等
            if (s[i] != goal[i])
            {
                ++count;     // 不相等计数加一
                flag = true; // 设置标志为 true
                // 如果不相等次数超过2，直接返回 false
                if (count > 2)
                    return false;
                // 记录第一个不相等字符的下标
                if (temp == -1)
                    temp = i;
                else
                {
                    // 交换 s 的字符
                    swap(s[i], s[temp]);
                    // 判断交换后是否等于 goal
                    if (s == goal)
                        return true; // 相等，返回 true
                    else
                        return false; // 不相等，返回 false
                }
            }
        }
        // 如果没有不相等的字符，检查是否存在重复字符
        if (flag == true)
            return false; // 有不相等字符但未成功交换，返回 false
        else
        {
            unordered_set<char> set; // 创建一个集合用于存储字符
            // 将字符串 s 中的字符插入集合
            for (const auto &c : s)
            {
                set.emplace(c); // 插入字符
            }
            // 如果集合中的字符数量等于字符串长度，说明没有重复字符
            if (set.size() == s.length())
                return false; // 返回 false，因为不能通过交换得到相等字符串
        }
        return true; // 其它情况下返回 true
    }

主要逻辑和步骤

长度检查：
- 如果 s 和 goal 的长度不相等，或者长度为1，直接返回 false。因为短字符串无法通过交换产生目标字符串。
处理长度为2的特殊情况：
- 对于长度为2的字符串，其实只需直接交换两个字符并作比较。如果交换后相等则返回 true，否则返回 false。
遍历检查不相等字符：
- 使用循环判断 s 和 goal 中的字符是否不相等。
- 维护一个计数器 count 来记录不相等字符的数量，以及一个标志 flag 来标记是否存在不相等的字符。
- 如果不相等的字符数量超过2，直接返回 false。
- 对于找到的第一个和第二个不相等字符的下标进行记录，尝试进行交换并判断交换后的字符串是否与 goal 相等。
处理没有不相等字符的情况：
- 如果没有不相等的字符（即 flag 为 false），此时需要检查字符串 s 是否存在重复字符。
- 使用一个集合 set 来存放 s 中的字符。若集合的大小等于 s 的长度，说明没有重复字符，此时无法通过交换得到相等的字符串，因此返回 false。
结束判断：
- 在其余情况下（如存在重复字符且没有不相等字符），返回 true。

注意点

边界条件：始终检查字符串的长度，避免不必要的错误。
字符交换：确保仅在找到两个不相等的字符后才进行交换并比较。
集合去重：使用集合来判断字符串中是否有重复字符，相比遍历会更加高效直观。

中等题

6. Z 字形变换

力扣原题链接 (中等题)

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P A H N A P L S I I G Y I R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

示例 1：

输入： s = “PAYPALISHIRING”, numRows = 3
输出： “PAHNAPLSIIGYIR”

示例 2：

输入： s = “PAYPALISHIRING”, numRows = 4
输出： “PINALSIGYAHRPI”
解释： P I N A L S I G Y A H R P I

示例 3：

输入： s = “A”, numRows = 1
输出： “A”

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
    string convert(string s, int numRows)
    {
        // 如果字符串长度小于等于行数或行数为1，则返回原字符串
        if (s.length() <= numRows || numRows == 1)
            return s;
        int row = numRows, column = 1000;                         // 定义行数和列数
        vector<vector<char>> vec(row, vector<char>(column, ' ')); // 创建二维字符数组，并用空格初始化
        deque<char> deq;                                          // 使用双端队列存储字符
        // 将输入字符串的字符逐个放入双端队列中
        for (const auto &c : s)
        {
            deq.push_back(c);
        }
        // 开始进行 Z 字形的填充
        for (int i = 0, j = 0; i < row && !deq.empty() && 0 <= j < column; ++i)
        {
            // 当到达最后一行时，从下往上填充
            if (i == row - 1)
            {
                for (int temp = i; temp >= 0 && !deq.empty() && j < column; --temp, ++j)
                {
                    vec[temp][j] = deq.front(); // 将字符填入当前行
                    deq.pop_front();            // 移除已填充的字符
                    i = temp;                   // 回到当前填充的行
                }
            }
            else
            {
                // 否则正常从上往下填充
                vec[i][j] = deq.front(); // 将字符填入当前行
                deq.pop_front();         // 移除已填充的字符
            }
        }
        // 将填充好的二维数组转换为结果字符串
        string res;
        for (const auto &str : vec)
        {
            for (const auto &c : str)
                if (c != ' ')         // 排除空格
                    res.push_back(c); // 将非空字符加入结果字符串
        }
        return res; // 返回结果字符串
    }

主要步骤

输入检查：
- 如果字符串长度小于等于行数 numRows 或行数为1，则直接返回原字符串。
数据结构：
- 使用二维字符数组 vec 来存储 Z 字形排列的结果，使用 deque 来存储输入字符串的字符。
Z 字形排列填充：
- 遍历行数，将字符填入 vec 中。
- 当到达最后一行时，需从下往上继续填充；其他行则是从上往下填充。
结果字符串提取：
- 将填充好的二维数组中的非空字符提取到结果字符串 res 中，最后返回该结果。

注意点

行数和字符数的判断：在进行字符排列前，应处理特殊情况下如行数大于字符串长度时的逻辑。
Z 字形填充逻辑：在填充的过程中需要特别注意行索引的变化，确保在最后一行填充完成后能够正确回升至上一行。

8. 字符串转换整数 (atoi)

力扣原题链接 (中等题)

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数。

函数 myAtoi(string s) 的算法如下：

空格： 读入字符串并丢弃无用的前导空格（" "）
符号： 检查下一个字符（假设还未到字符末尾）为 '-' 还是 '+'。如果两者都不存在，则假定结果为正。
转换： 通过跳过前置零来读取该整数，直到遇到非数字字符或到达字符串的结尾。如果没有读取数字，则结果为0。
舍入： 如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被舍入为 −231 ，大于 231 − 1 的整数应该被舍入为 231 − 1 。

返回整数作为最终结果。

示例 1：

输入： s = “42”
输出： 42
解释： 第 1 步：“42”（当前没有读入字符，因为没有前导空格）第 2 步：“42”（当前没有读入字符，因为这里不存在 ‘-’ 或者 ‘+’）第 3 步：”42"（读入 “42”）

示例 2：

输入： s = " -042"
输出： -42
解释： 第 1 步："___-042"（读入前导空格，但忽视掉）第 2 步：" - 042"（读入 ‘-’ 字符，所以结果应该是负数）第 3 步：" -042"（读入 “042”，在结果中忽略前导零）

示例 3：

输入： s = “1337c0d3”
输出： 1337
解释： 第 1 步：“1337c0d3”（当前没有读入字符，因为没有前导空格）第 2 步：“1337c0d3”（当前没有读入字符，因为这里不存在 ‘-’ 或者 ‘+’）第 3 步：“1337c0d3”（读入 “1337”；由于下一个字符不是一个数字，所以读入停止）

示例 4：

输入： s = “0-1”
输出： 0
解释： 第 1 步：“0-1” (当前没有读入字符，因为没有前导空格) 第 2 步：“0-1” (当前没有读入字符，因为这里不存在 ‘-’ 或者 ‘+’) 第 3 步：“0-1” (读入 “0”；由于下一个字符不是一个数字，所以读入停止)

示例 5：

输入： s = “words and 987”
输出： 0
解释： 读取在第一个非数字字符“w”处停止。

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
    int myAtoi(string s)
    {
        bool positive = true; // 标记当前数字是否为正数
        int index = -1;       // 指示有效数字的起始位置
        // 遍历字符串，查找有效的数字起始位置
        for (int i = 0; i < s.length(); ++i)
        {
            if (isspace(s[i])) // 如果是空格，继续下一个字符
                continue;
            if (s[i] == '.' || isalpha(s[i])) // 如果遇到小数点或字母，直接返回0
                return 0;
            if (s[i] == '-') // 如果遇到负号
            {
                index = i + 1;    // 设置有效数字起始位置
                positive = false; // 记录为负数
                break;
            }
            if (s[i] == '+') // 如果遇到正号
            {
                index = i + 1; // 设置有效数字起始位置
                break;
            }
            if (isdigit(s[i])) // 如果当前字符是数字
            {
                index = i; // 设置有效数字起始位置
                break;
            }
        }
        if (index == -1) // 如果没有找到有效数字，返回0
            return 0;
        long long sum = 0; // 用于存储转换后的数字
        // 从有效数字起始位置开始读取数字
        for (int i = index; i < s.length(); ++i)
        {
            if (!isdigit(s[i])) // 如果不是数字，退出循环
                break;
            sum = (s[i] - '0') + sum * 10; // 逐位构造数字
            // 检查是否超出32位有符号整数范围
            if (sum > 2147483648)
            {
                return positive ? INT_MAX : INT_MIN; // 根据符号返回最大或最小值
            }
        }
        if (!positive) // 如果是负数
        {
            sum = -sum; // 转换为负值
        }
        else
        {
            if (sum == 2147483648) // 特殊情况：如果恰好为2147483648
                sum = INT_MAX;     // 归为整型的最大值
        }
        return sum; // 返回最终结果
    }

算法步骤

空格处理：
- 遍历字符串并丢弃前导空格。
符号处理：
- 检查当前字符是否为 ‘-’ 或 ‘+’，以确定数字的符号。
- 如果没有符号，则默认数字为正。
读入数字：
- 跳过前置零，并读取连续的数字字符。
- 遇到非数字字符时结束读取。
范围处理：
- 转换后检查是否超出32位有符号整数范围。
- 若超出范围，则返回对应的最大或最小值。
返回结果：
- 返回转换后的整数作为最终结果。

注意点

空格与非数字字符：
- 使用isspace()来检测空格，并直接跳过。
- 若遇到小数点或字母则直接返回0，避免错误转换。
符号与索引：
- 使用一个index变量标记有效数字的起始位置。
- 负号和正号的处理需要在读取实际数字前完成。
长整型使用：
- 使用long long类型来存储最终的结果，以防在数值计算过程中溢出。
溢出处理：
- sum需要与2147483648进行比较，确保不会超出32位整数的范围。
- 根据符号返回INT_MAX或INT_MIN来处理边界值情况。
特殊情况：
- 处理当结果恰好为2147483648时，应明确归为整型的最大值。

17. 电话号码的字母组合

力扣原题链接 (中等题)

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入： digits = “23”
输出： [“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

示例 2：

输入： digits = ""
输出： []

示例 3：

输入： digits = “2”
输出： [“a”,“b”,“c”]

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
    vector<string> letterCombinations(string digits)
    {
        // 如果输入字符串为空，直接返回空的结果
        if (digits.empty())
            return {};
        // 创建一个映射，将数字字符映射到对应的字母组合
        unordered_map<char, vector<string>> nums;
        nums.emplace('2', vector<string>{"a", "b", "c"});
        nums.emplace('3', vector<string>{"d", "e", "f"});
        nums.emplace('4', vector<string>{"g", "h", "i"});
        nums.emplace('5', vector<string>{"j", "k", "l"});
        nums.emplace('6', vector<string>{"m", "n", "o"});
        nums.emplace('7', vector<string>{"p", "q", "r", "s"});
        nums.emplace('8', vector<string>{"t", "u", "v"});
        nums.emplace('9', vector<string>{"w", "x", "y", "z"});
        string tempStr;                             // 临时字符串，用于拼接字母
        int nextIndex = 1, len = digits.length();   // 初始化下一个数字的索引和输入字符串的长度
        vector<string> res = nums[digits[0]], temp; // 初始化结果为第一个数字对应的字母组合
        // 遍历输入的每一个数字
        while (nextIndex < len)
        {
            temp = res;  // 暂存当前的结果
            res.clear(); // 清空结果，以便存放新的组合
            // 遍历当前的组合
            for (const auto &strNow : temp)
            {
                tempStr = strNow; // 取出当前字符串
                // 遍历下一个数字对应的字母
                for (const auto &strNext : nums[digits[nextIndex]])
                {
                    tempStr += strNext;                     // 拼接当前字母
                    res.push_back(tempStr);                 // 将新组合添加到结果中
                    tempStr.erase(tempStr.length() - 1, 1); // 删除最后一个字母，恢复到原始状态
                }
                tempStr.clear(); // 清空临时字符串
            }
            ++nextIndex; // 移动到下一个数字
        }
        return res; // 返回所有组合结果
    }

关键步骤

边界条件检查：
- 如果输入字符串 digits 为空，直接返回一个空的 vector<string>。
映射创建：
- 使用 unordered_map<char, vector<string>> 创建一个数字到字母组合的映射。每个数字字符（‘2’-‘9’）对应一组字母，利用 emplace 方法高效插入。
组合生成：
- 初始化 res 为第一个数字对应的字母组合。
- 使用 while 循环遍历输入字符串中的每个数字（从第二个数字开始）。
- 利用双重循环生成所有可能的组合：
  - 外层循环遍历当前对应的所有组合。
  - 内层循环遍历下一个数字对应的所有字母进行拼接。
  - 每次拼接完成后，将新组合加入到 res 中，并通过 erase 恢复 tempStr 为之前的状态。
返回结果：
- 完成所有组合生成后，返回最终结果 res。

注意点

字符映射的建立：在数字与字母之间建立映射时，确保字符的准确对应，避免遗漏。
临时字符串管理：使用 tempStr 来拼接组合时，需要在每次拼接后进行清理，以防止意外影响后续的组合生成。

686. 重复叠加字符串匹配

力扣原题链接 (中等题)

给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。

注意： 字符串 "abc" 重复叠加 0 次是 ""，重复叠加 1 次是 "abc"，重复叠加 2 次是 "abcabc"。

示例 1：

输入： a = “abcd”, b = “cdabcdab”
输出： 3
解释： a 重复叠加三遍后为 “abcdabcdabcd”, 此时 b 是其子串。

示例 2：

输入： a = “a”, b = “aa”
输出： 2

示例 3：

输入： a = “a”, b = “a”
输出： 1

示例 4：

输入： a = “abc”, b = “wxyz”
输出： -1

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
    int repeatedStringMatch(string a, string b)
    {
        deque<int> deque; // 用于存储字符 a 中与 b 的首字符相同的所有索引
        // 遍历字符串 a，寻找与字符串 b 的首字符相同的字符索引
        for (int i = 0; i < a.length(); ++i)
        {
            if (a[i] == b[0])       // 如果找到了相同的字符
                deque.push_back(i); // 将索引加入队列
        }
        if (deque.empty()) // 如果队列为空，说明 a 中没有与 b 的首字符相同的字符
            return -1;     // 返回 -1
        int h = 0, m = 0, n = 0, count = 0; // 初始化变量 h（队列头部）、m（当前比较 a 的索引）、n（当前比较 b 的索引）、count（重复次数计数）
        // 当队列不为空时，继续处理
        while (!deque.empty())
        {
            h = deque.front(); // 取出队列的头部元素
            m = h;             // 初始化 m 为当前比较的 a 的索引
            n = 0;             // 初始化 b 的索引
            count = 0;         // 重复次数重置为 0
            deque.pop_front(); // 移除队列头部元素
            // 对字符串 b 进行遍历
            while (n < b.length())
            {
                if (m == a.length()) // 如果 m 越界，说明需要重复叠加 a
                {
                    m = 0;   // 重置 m
                    ++count; // 增加叠加次数
                }
                if (a[m] != b[n]) // 如果 a[m] 和 b[n] 不相等，说明匹配失败
                    break;        // 退出当前比较
                ++m; // 移动到 a 的下一个字符
                ++n; // 移动到 b 的下一个字符
            }
            if (n == b.length())  // 如果 n 到达了 b 的末尾，说明成功匹配
                return count + 1; // 返回当前叠加次数加 1
        }
        return -1; // 如果没有找到匹配，返回 -1
    }

代码逻辑

寻找匹配的起始点：首先扫描字符串 a，找到所有和字符串 b 的首字符相同的索引位置，并将这些索引存放在一个双端队列 deque 中。
特例处理：如果 deque 为空，说明 a 中没有与 b 的首字符相同的字符，直接返回 -1。
匹配过程：
- 循环处理队列中的每个索引，初始化指针 m（指向 a）和 n（指向 b），以及计数器 count 记录重复叠加的次数。
- 对于字符串 b，逐字符进行比较：
  - 如果 m 超出了 a 的长度，则说明需要重复叠加 a，此时重置 m 并增加 count。
  - 若 a[m] 和 b[n] 不匹配，则退出当前的匹配尝试。
- 如果 n 遍历完了字符串 b，则说明成功找到了匹配，返回当前的叠加次数加 1。
返回值：在无法匹配的情况下，最后返回 -1。

注意点

双端队列的使用：deque 用于存储所有可能的起始匹配位置，便于在匹配失败后，可以快速尝试下一个可能的起始位置。
边界条件：处理好 m 超出 a 长度的情况，确保在需要的时候可以正确地进行字符串的重复叠加。

1513. 仅含 1 的子串数

力扣原题链接 (中等题)

给你一个二进制字符串 s（仅由 ‘0’ 和 ‘1’ 组成的字符串）。

返回所有字符都为 1 的子字符串的数目。

由于答案可能很大，请你将它对 10⁹ + 7 取模后返回。

示例 1：

输入： s = “0110111”
输出 9
解释： 共有 9 个子字符串仅由 ‘1’ 组成 “1” -> 5 次 “11” -> 3 次 “111” -> 1 次

示例 2：

输入： s = “101”
输出： 2
解释： 子字符串 “1” 在 s 中共出现 2 次

示例 3：

输入： s = “111111”
输出： 21
解释： 每个子字符串都仅由 ‘1’ 组成

示例 4：

输入： s = “000”
输出： 0

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
    int numSub(string s)
    {
        int head = -1;            // 用于标记当前连续 '1' 的起始位置
        long long n = 0, sum = 0; // n用于记录连续 '1' 的长度，sum用于累加结果
        s.push_back('0');         // 在字符串末尾添加一个 '0' 以便于处理最后的 '1'
        for (size_t i = 0; i < s.length(); ++i) // 遍历字符串
        {
            if (s[i] == '1') // 如果当前字符是 '1'
            {
                if (head == -1) // 如果还没有找到连续 '1' 的起始位置
                {
                    head = i; // 记录起始位置
                }
                if (s[i + 1] != '0') // 如果下一个字符不是 '0'
                    continue;        // 继续下一次循环，即继续查找下一个 '1'
                else
                {
                    // 当前 '1' 之后是 '0'，说明结束了连续 '1'
                    n = i - head + 1;            // 计算连续 '1' 的长度
                    sum = sum + (1 + n) * n / 2; // 计算由这段连续 '1' 生成的子字符串数量（等差数列求和）
                    head = -1;                   // 重置起始位置，准备查找下一个连续 '1'
                }
            }
        }
        return sum % 1000000007; // 返回结果，取模以避免溢出
    }

代码解析

初始化变量：
- head 用于标记连续 ‘1’ 的起始位置，初始为 -1。
- n 用于记录当前连续 ‘1’ 的长度。
- sum 用于累加所有由 ‘1’ 组成的子字符串的数量。
添加结束标记：
- s.push_back('0');：在字符串末尾增加一个 ‘0’，这样可以简化处理连续 ‘1’ 的逻辑，使得最后一段的子字符串能够正确计算。
遍历字符串：
- 使用 for 循环遍历字符串的每个字符。
- 当遇到字符为 ‘1’ 时，检测是否已经找到了连续 ‘1’ 的起始位置。如果没有，记录当前索引为 head。
- 如果下一个字符仍为 ‘1’，则继续循环，直到遇到 ‘0’。
计算连续 ‘1’ 的数量：
- 当找到一个 ‘0’，表示当前的系列 ‘1’ 结束，计算这段 ‘1’ 的长度 n，并利用等差数列求和的公式 (1 + n) * n / 2 来得出所有子字符串的数量。
重置标记，准备下一个系列：
- 重置 head 以便查找下一个可能的连续 ‘1’。
返回结果：
- 最后返回结果时，将 sum 取模 10⁹ + 7，确保结果在合理范围内。

注意点

边界条件：输入字符串在末尾添加了一个 ‘0’，确保即使字符串结束时是 ‘1’ 也能正确处理。
整数溢出处理：计算结果时很容易发生溢出，特别是长字符串情况下，因此使用 long long 类型来存储中间结果，并进行取模操作。
效率：该算法的时间复杂度为 O(n)，其中 n 是字符串的长度，适合处理较大的输入。
理解等差数列求和：理解 (1 + n) * n / 2 的来源是非常重要的，这个公式用来计算由长度为 n 的连续 ‘1’ 可以形成的所有子字符串的数量。