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();
}
};以上就是C++ LeetCode1805字符串不同整数数目的详细内容，更多关于C++ 字符串不同整数数目的资料请关注其它相关文章！
查看更多关于【C/C++教程】的文章
