C++ LeetCode1805字符串不同整数数目

LeetCode 1805.字符串中不同整数的数目

力扣题目链接：leetcode.cn/problems/nu…

给你一个字符串 word ，该字符串由数字和小写英文字母组成。

请你用空格替换每个不是数字的字符。例如，"a123bc34d8ef34" 将会变成 " 123  34 8  34" 。注意，剩下的这些整数为（相邻彼此至少有一个空格隔开）："123"、"34"、"8" 和 "34" 。

返回对 word 完成替换后形成的 不同 整数的数目。

只有当两个整数的 不含前导零 的十进制表示不同， 才认为这两个整数也不同。

示例 1：

输入：word = "a123bc34d8ef34"
输出：3
解释：不同的整数有 "123"、"34" 和 "8" 。注意，"34" 只计数一次。

示例 2：

输入：word = "leet1234code234"
输出：2

示例 3：

输入：word = "a1b01c001"
输出：1
解释："1"、"01" 和 "001" 视为同一个整数的十进制表示，因为在比较十进制值时会忽略前导零的存在。

提示：

• 1 <= word.length <= 1000
• word 由数字和小写英文字母组成

方法一：遍历拆分

这个问题主要包括三部分：

• 将数字从字符串中抽取出来
• 将数字的前导零去除
• 数字的去重与计数

接下来逐个解决这三个问题

1. 将数字从字符串中提取出来：

我们需要一个布尔类型的变量“lastIsNum”来记录上一个字符是否为数字。初始值为false

同时，我们还需要一个字符串，用来存储整个字符串中的某个数字。string thisString

接下来遍历字符串。若字符串遍历结束或者遍历到字母字符时，将lastIsNum标记为true，否则将lastIsNum标记为false

如果这个字符是字母，但上一个字符是数字，那么就说明我们找到了“一个数字的末尾”，此时我们就提取出了这个数字。

处理完这个数字记得将字符串清空。

如果这个字符是数字，那么直接无脑添加数字字符串thisString的末尾即可。

2. 将数字的前导零去除：

使用一个整数类型的变量firstLoc来记录一个数字第一个非零的位置，初始值为-1

接着遍历数字字符串，遇到第一个非零数字就结束遍历，并将firstLoc修改为遍历到的位置。

如果最后firstLoc的值仍未-1，那么就说明整个数字字符串全是0

否则，从firstLoc开始到字符串末尾所组成的子串即为去除前导零后的数字字符串

3. 数字的去重与统计：

题目问的是“有多少不同的数字”，这就需要我们对所有的数字做去重处理。

这个过程很简单，直接使用一个哈希表即可

将所有的处理过的数字字符串放入哈希表，最后返回哈希表的大小即为去重后的结果。

• 时间复杂度O(len(word))
• 空间复杂度O(len(word))

AC代码

C++

class Solution {
private:
    unordered_set<string> se;

    void insert(string toInsert) {
        int firstLoc = -1;
        for (int i = 0; i < toInsert.size(); i++) {
            if (toInsert[i] != '0') {
                firstLoc = i;
                break;
            }
        }
        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();
        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();
    }
};