题目

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

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

解题思路

1. 双指针

p1指向整数起始位置

p2指向整数结束位置

dic用来判断是否重复

2. 整数加法

这个只有Python能使用，golang和c++都会超int只能使用字符串

找到整数就num就*10 + 整数

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def numDifferentIntegers(self, word: str) -> int:
        dic = set()
        num = 0
        flag = False
        for i, x in enumerate(word):
            if x.isdigit():
                num = num * 10 + (ord(x) - ord('0'))
                flag = True
            elif flag and num not in dic:
                dic.add(num)
                flag = False
                num = 0
            else:
                flag = False
                num = 0
        dic.add(num) if flag and num not in dic else ...
        return len(dic)

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
class Solution {
public:
    int numDifferentIntegers(string word) {
        unordered_map<string, bool> dic;
        int p1 = 0, n = word.size();
        while (true) {
            while (p1 < n && 'a' <= word[p1] && word[p1] <= 'z') {
                p1++;
            }
            if (p1 == n) break;
            
            int p2 = p1;
            while (p2 < n && '0' <= word[p2] && word[p2] <= '9') {
                p2++;
            }
            while (p2 - p1 > 1 && word[p1] == '0') {
                p1++;
            }
            dic[word.substr(p1, p2 - p1)];
            p1 = p2;
        }
        return dic.size();
    }
};

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func numDifferentIntegers(word string) int {
    dic := make(map[string] bool)
    n := len(word)
    p1 := 0
    for {
        for p1 < n && !unicode.IsDigit(rune(word[p1])) {
            p1++
        }
        if p1 == n {
            break
        }
        p2 := p1
        for p2 < n && unicode.IsDigit(rune(word[p2])) {
            p2++
        }
        for p2 - p1 > 1 && word[p1] == '0' {
            p1++
        }
        dic[word[p1: p2]] = true
        p1 = p2
    }
    return len(dic)
}