亲宝软件园·资讯

展开

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

LetMeFly 人气:0

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. 将数字从字符串中提取出来:

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

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

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

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

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

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

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

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

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

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

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

3. 数字的去重与统计:

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

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

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

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();
    }
};

加载全部内容

相关教程
猜你喜欢
用户评论