【2022-12-06每日一题】1805. 字符串中不同整数的数目[Easy]
2022-12-06
2分钟阅读时长
2022-12-06每日一题：1805. 字符串中不同整数的数目
难度：Easy
标签：哈希表 、 字符串
给你一个字符串 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 <= 1000word由数字和小写英文字母组成
方法一：哈希表（自己）
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
func numDifferentIntegers(word string) int {
nums := make(map[int]bool)
num, valid := 0, false
for _, c := range word {
if c >= '0' && c <= '9' {
num += num*10+int(c-'0')
valid = true
} else if valid {
nums[num] = true
num, valid = 0, false
}
}
if valid {
nums[num] = true
}
return len(nums)
}
复杂度分析
- 时间复杂度: O(n)。
- 空间复杂度: O(n)。
方法二：双指针+模拟
写法一
func numDifferentIntegers(word string) int {
s, n := map[string]struct{}{}, len(word)
for i := 0; i < n; i++ {
if word[i] >= '0' && word[i] <= '9' {
// 跳过前缀0
for i < n && word[i] == '0' {
i++
}
// 查找数字结束位置
j := i
for j < n && word[j] >= '0' && word[j] <= '9' {
j++
}
s[word[i:j]] = struct{}{} // a000，此时word[i:j]为空字符串
i = j
}
}
return len(s)
}
写法二
func numDifferentIntegers(word string) int {
s, n := map[string]bool{}, 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++
}
// 去重前导0
for p2-p1 > 1 && word[p1] == '0' {
p1++
}
s[word[p1:p2]] = true
p1 = p2
}
return len(s)
}
复杂度分析
- 时间复杂度: O(n)。
- 空间复杂度: O(n)。