C++ 实现 LeetCode 1805. 字符串中不同整数的数目

Ivy

发布时间：2026-10-15| 5人浏览过

原创

本文讲解 LeetCode 1805 题「字符串中不同整数的数目」的 C++ 解决方案。通过将字母替换为空格分隔数字，去除前导零后进行去重统计，最终利用哈希表高效得出结果。

题目解析与解题思路

力扣题目链接：leetcode.cn/problems/number-of-different-integers-in-a-string（注：原链接截断，此处以题目描述为准）

本题要求从由数字和小写英文字母组成的字符串 word 中提取所有整数，并统计其中不同整数的数量。关键判断标准是：仅当两个整数的十进制表示（不含前导零）不同时，才视为不同的整数。

示例说明：

示例 1：输入 "a123bc34d8ef34"，提取出 "123", "34", "8", "34"。去重后为 "123", "34", "8"，结果为 3。
示例 3：输入 "a1b01c001"，提取出的 "1", "01", "001" 在去除前导零后均变为 "1"，因此视为同一个整数，结果为 1。

解决步骤：

提取数字：将非数字字符视为分隔符，分离出连续的纯数字子串。
规范化处理：去除每个数字串的前导零。若全为零，则保留一个 "0"。
去重计数：将规范化后的数字存入无序集合（Hash Set），利用其特性自动去重，最后返回集合大小。

具体实现方法

第1步：遍历字符串并识别数字边界

目的：准确捕获连续的整数片段。

操作：定义布尔变量 lastIsNum 标记上一个字符是否为数字。遍历字符串时，若当前字符是字母或到达字符串末尾，且 lastIsNum 为真，说明此前是一个完整数字串的结尾，触发提取逻辑。反之，若当前字符是数字，则将其追加到临时缓冲区。

第2步：去除前导零

目的：统一数值表示，消除格式差异带来的干扰。

操作：对于提取出的数字字符串，查找第一个非 '0' 字符的位置 firstLoc。如果 firstLoc 仍为初始值 -1，说明整个串全是 0，插入 "0"；否则，截取从 firstLoc 到末尾的子串作为规范形式。

第3步：存储至哈希表去重

目的：快速完成统计。

操作：使用 C++ std::unordered_set<string> 容器。每得到一个规范化后的数字串，调用 insert 方法。由于 set 的唯一性，重复的数字会被忽略。最终返回 set.size()。

C++ 参考代码

class Solution {
private:
    unordered_set se;

    void insert(string toInsert) {
        int firstLoc = -1;
        for (int i = 0; i < toInsert.size(); i++) {
            if (toInsert[i] != '0') {
                firstLoc = i;
                break;
            }
        }
        // 如果全是0，则记录为 "0"
        if (firstLoc == -1)
            se.insert("0");
        else
            // 否则跳过前导零
            se.insert(toInsert.substr(firstLoc));
    }
public:
    int numDifferentIntegers(string word) {
        bool lastIsNum = false;
        string thisString;
        int n = word.size();
        // 遍历至 n，方便处理末尾为数字的情况
        for (int i = 0; i <= n; i++) {
            // 如果是字母或者到达了字符串末尾
            if (i == n || isalpha(word[i])) {
                // 如果之前是在记录数字，说明一个数字结束
                if (lastIsNum) {
                    lastIsNum = false;
                    insert(thisString); // 存入并处理前导零
                    thisString.clear(); // 清空临时串
                }
            } else {
                // 是数字，继续拼接
                thisString += word[i];
                lastIsNum = true;
            }
        }
        return se.size();
    }
};