千恋*万花

  • 首页
  • 个人简历
  • 文章分类
    • 后端开发
    • 运维
    • 基础知识
    • 笔记
    • 工作运维记录
    • 随笔
    • 未分类文章
萌奈の笔记簿
分享我的努力,希望为你助力
  1. 首页
  2. 后端开发
  3. golang
  4. 正文

记 leetcode Q1805 解题思路

2022-12-06 3804点热度 0人点赞 0条评论

题目连接 Q1805

题目详情:

给你一个字符串 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 由数字和小写英文字母组成

通过次数 30,436
提交次数 69,994

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/number-of-different-integers-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

最开始我的思路(错误)

这题应该很简单,我只需要:

  1. 用map[int]struct{}作为集合,进行去重操作
  2. 用strconv.Atoi进行数字转换、去零操作
  • 从前往后遍历一遍字符串
    • if 遇到数字 就存到临时变量里。
    • else 不是数字 看看临时变量里有没有内容,有内容就把内容转换为 int 类型,存入 map[int]struct{} 里,顺便清空临时变量。
  • 输出 map 的大小

更正的思路

提交了一次以后,错误点有很多。
我发现我的思考退化了,有很多东西我没想到
我为我一拍脑袋就决定的思路付出了代价……

直接看有一个问题,int超界,题目中说到 1 <= word.length <= 1000,按这个长度,int64都不够用
那么map中的key肯定是不能用int相关的数据类型了,只能用string作为key来存放这个数字

间接地,用string存放数字,就不能用 strconv.Atoi 处理数字(前导0)了。我需要自己处理前导0,之前的思路“从前往后遍历一遍字符串”,无法满足这个需求

综上,我第一次的思路漏洞满出,我只能调整自己的思路了:
我需要在字符串中找到数字区间,并通过调整数字区间,把前导0去掉。显然,我需要双指针来解题

s = start ; e = end

  1. 定义map[string]struct{}作为集合进行去重操作
  2. 定义ps指针,寻找并作为数字的头部,每一步只做每一步的事,此时只需要找到数字开头位置,不需要处理前导0
  3. 找到ps的位置后,定义pe指针(初始值为ps),向后迭代pe,找到数字的尾部
  4. 调整ps的位置,去除前导0,“0”也算一个数,所以迭代ps的终止条件应该为ps < pe-1,以保证数字字符串中,必定有一位数字
  5. 统计,map[word[ps:pe]] = struct{}{},输出len(map)

使用更正的思路后,调试了两次我就AC了。

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可
标签: golang leetcode map 解题思路
最后更新:2023-02-05

初音萌奈

我是练习时长 三年半 的后端开发程序员 谢谢你参观我的博客! 本网站现已支持IPv6 ☞ 个人简历 ☜

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复
文章目录
  • 题目详情:
  • 思路
    • 最开始我的思路(错误)
    • 更正的思路

COPYRIGHT © 2025 HatsuneMona ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

晋ICP备17007130号-4