LeetCode 1694 Reformat Phone Number 电话号码重新格式化：Go 贪心分块解法与源码解析

LeetCode 1694 Reformat Phone Number 电话号码重新格式化Go 贪心分块解法与源码解析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 1694「Reformat Phone Number重新格式化电话号码」展开以 LeetCode-Go 仓库中该题目的 README 题解 为骨架结合同目录下的 Go 源码实现 与 单元测试完整讲解题目规则、五种示例、分块贪心思路、逐行代码解析与复杂度分析。读完本文你将掌握一类「清洗字符串 → 按规则分组 → 拼接输出」的字符串处理题的通用解法套路并能在本地仓库中直接运行测试验证结果。一、题目概述给定一个字符串形式的电话号码number它由数字、空格 和破折号-组成。请你按下述方式重新格式化电话号码首先删除所有的空格和破折号其次将数字从左到右每 3 个一组分块直到剩下4 个或更少数字剩下的数字按以下规则再分块2 个数字单个含 2 个数字的块3 个数字单个含 3 个数字的块4 个数字两个分别含 2 个数字的块最后用破折号-将这些块连接起来。注意重新格式化过程中不应生成仅含 1 个数字的块并且最多生成两个含 2 个数字的块。最后返回格式化后的电话号码字符串。二、示例全解析题目原文档给出了 5 个示例覆盖了分块规则的几乎所有分支逐个推演如下。示例 1余数为 0 的场景输入number 1-23-45 6 输出123-456去除空格与破折号后得到数字串123456共 6 位。6 位数字按每 3 个一组正好分为123和456两个块用破折号连接得到123-456。示例 2剩下 4 位的场景输入number 123 4-567 输出123-45-67清洗后数字串为1234567共 7 位。分组过程Step 1当前多于 4 位先取前 3 位作为第 1 个块123Step 2剩余 4 位按规则拆成两个 2 位块45与67。最终输出123-45-67。示例 3剩下 2 位的场景输入number 123 4-5678 输出123-456-78清洗后数字串为12345678共 8 位。分组过程Step 1第 1 个块123Step 2仍多于 4 位第 2 个块456Step 3剩余 2 位单独作为一个 2 位块78。最终输出123-456-78。示例 4最短输入2 位输入number 12 输出12清洗后只剩 2 位直接作为一个块无需任何破折号。示例 5混合大量分隔符输入number --17-5 229 35-39475 输出175-229-353-94-75清洗后数字串为1752293539475共 13 位注意末尾还有一个空格被一并删除。分组过程前三个 3 位块175、229、353剩余 4 位拆成94与75。最终输出175-229-353-94-75末尾恰好是两个 2 位块验证了「最多生成两个含 2 个数字的块」的约束。三、约束条件2 number.length 100number由数字以及字符-和 组成number中至少包含两个数字其中「至少包含两个数字」保证了清洗后数字串长度恒 ≥ 2永远不会出现 0 位或 1 位数字需要处理的情况这也让「不生成仅含 1 个数字的块」这一要求天然可满足。四、解题思路基于长度取模的分块策略原文档的解题思路指出这是一道简单题核心在于利用长度与 3 的余数关系一次性确定分块方案。清洗后的数字串长度为n设threeDigits n / 3按 3 位一组可分的块数twoDigits需要拆成 2 位块的个数。根据n % 3的取值分三种情况n % 3含义分块方案举例0恰好整除 3全部按 3 位分组twoDigits 06 位 →xxx-xxx1直接按 3 位分组会剩 1 位非法少取一个 3 位块让末尾剩 4 位再拆成两个 2 位块twoDigits 27 位 →xxx-xx-xx2按 3 位分组后剩 2 位末尾一个 2 位块twoDigits 18 位 →xxx-xxx-xx关键洞察在于除 3 余 1 即等价于末尾剩 4 位。因为n % 3 1时n 3k 1若取k - 1个 3 位块则剩余3(k-1) 之后还剩 3 1 4位——正好满足「4 个数字拆成两个 2 位块」的规则且保证全程不会出现 1 位块。原文档中提到「先判断号码是不是 2 位和 4 位如果是单独输出这 2 种情况」这是对思路的通俗化描述而实际代码见下节并未对 2 位、4 位做显式特判而是通过上述取模逻辑统一处理2 位数字n % 3 2→threeDigits 0、twoDigits 1自然得到单个 2 位块4 位数字n % 3 1→threeDigits 1 - 1 0、twoDigits 2自然得到xx-xx。这种「用数学归纳代替特判」的做法正是本题代码的精妙之处。五、Go 源码实现与逐行解析仓库中的实现位于 1694. Reformat Phone Number.go完整代码如下package leetcode import ( strings ) func reformatNumber(number string) string { parts, nums : []string{}, []rune{} for _, r : range number { if r ! - r ! { nums append(nums, r) } } threeDigits, twoDigits : len(nums)/3, 0 switch len(nums) % 3 { case 1: threeDigits-- twoDigits 2 case 2: twoDigits 1 default: twoDigits 0 } for i : 0; i threeDigits; i { s : s string(nums[0:3]) nums nums[3:] parts append(parts, s) } for i : 0; i twoDigits; i { s : s string(nums[0:2]) nums nums[2:] parts append(parts, s) } return strings.Join(parts, -) }1. 清洗阶段剔除空格与破折号parts, nums : []string{}, []rune{} for _, r : range number { if r ! - r ! { nums append(nums, r) } }使用[]rune{}按字符收集数字range遍历字符串时以 Unicode 码点为单位对本题纯 ASCII 输入而言等价于逐字符处理过滤条件是r ! - r ! 即保留除破折号与空格外的所有字符——由于输入约束保证了其余字符均为数字这里无需再做数字合法性校验注意过滤发生在分组之前因此输入中的任何分隔符位置都不会影响后续分组结果。2. 规划阶段用取模确定块数量threeDigits, twoDigits : len(nums)/3, 0 switch len(nums) % 3 { case 1: threeDigits-- twoDigits 2 case 2: twoDigits 1 default: twoDigits 0 }threeDigits先按「整除 3」乐观取值再根据余数修正len(nums) % 3 1时将threeDigits减 1同时twoDigits 2——这正是「末尾 4 位拆成两个 2 位块」的数学表达len(nums) % 3 2时twoDigits 1末尾单独留一个 2 位块由于约束保证len(nums) 2余数只可能是0、1、2且len(nums) 2时threeDigits 0、twoDigits 1len(nums) 4时threeDigits 0、twoDigits 2均不会出现负的块数。3. 拼接阶段切块并连接for i : 0; i threeDigits; i { s : s string(nums[0:3]) nums nums[3:] parts append(parts, s) } for i : 0; i twoDigits; i { s : s string(nums[0:2]) nums nums[2:] parts append(parts, s) } return strings.Join(parts, -)第一阶段按 3 位切块每次从nums头部切走 3 个字符并收缩切片nums nums[3:]第二阶段按 2 位切块处理末尾剩余数字两个循环按顺序执行保证输出块的先后顺序与原始数字顺序一致最后通过strings.Join(parts, -)用破折号连接所有块这也是仓库代码的风格选择——strings.Join比手工拼接更简洁且性能更优。六、边界情况与正确性论证为什么不会出现 1 位块分块总数由threeDigits twoDigits决定而n 3 × threeDigits 2 × twoDigits。当n % 3 1时若不舍弃一个 3 位块末尾将只剩 1 位——这正是代码中threeDigits--的意义。调整之后余 13(k-1) 2×2 3k 1 n✅余 23k 2×1 3k 2 n✅余 03k 0 n✅三种情况等式恒成立且每个块的长度只可能是 3 或 2从数学上排除了 1 位块的存在。为什么 2 位块最多两个由分块方案可知twoDigits的取值只可能是0、1、2恰好对应原题「最多生成两个含 2 个数字的块」的约束。七、测试用例验证仓库在 1694. Reformat Phone Number_test.go 中提供了Test_Problem1694测试覆盖了题目的 5 个官方示例并额外补充了一个边界用例输入期望输出覆盖点1-23-45 6123-4566 位整除 3123 4-567123-45-677 位余 1末尾 4 位拆两块123 4-5678123-456-788 位余 21212最短输入2 位--17-5 229 35-39475 175-229-353-94-7513 位混合分隔符 末尾空格9964-99-644 位余 1 且末尾带破折号其中9964-这一补充用例直接验证了「4 位数字拆成两个 2 位块」的分支len(nums) 4len/3 1余 1 使threeDigits归零、twoDigits 2最终输出99-64。测试结构上仓库沿用了统一的questionXXXX / paraXXXX / ansXXXX表驱动模式para1694保存输入参数ans1694保存期望答案测试循环逐条打印输入与reformatNumber的实际输出。八、复杂度分析时间复杂度O(n)其中n为number字符串长度≤ 100。清洗阶段遍历一次字符串分块阶段遍历的数字总数不超过清洗后的位数两个循环均为线性。空间复杂度O(n)。nums切片保存全部数字字符parts切片保存分块结果二者规模都与输入长度成正比。由于每轮都是「读取 → 切块 → 移动切片头指针」的线性扫描且未引入哈希表或排序等额外操作该实现的空间与时间开销都是本题的最优级别。九、在仓库中运行与验证本仓库以github.com/halfrost/LeetCode-Go为 Go module见 go.modGo 版本 1.19题目代码位于leetcode包下。若想在本地验证本题实现可在仓库根目录执行go test -v ./leetcode/ -run Test_Problem1694-run Test_Problem1694只运行本题的测试函数如需生成覆盖率报告仓库提供了 gotest.sh 脚本./gotest.sh该脚本以-covermodeatomic对./leetcode/...全部包一次性生成coverage.txt这也从侧面印证了仓库「100% test coverage」的测试组织方式——每道题均配有对应的表驱动测试函数。十、总结LeetCode 1694 是一道典型的字符串清洗 规则分块问题。其核心套路可以抽象为三步清洗用一次线性扫描剔除无关字符得到纯数字序列规划利用长度对 3 取模的结果一次性算出 3 位块与 2 位块的数量避免逐块做状态判断拼接按规划顺序切块并用分隔符连接。仓库实现通过「取模修正块数」的方式优雅地统一了 2 位、3 位、4 位数字的三种结尾情况避免了显式特判值得在类似的格式化类题目如版本号归一化、日期格式化中复用同样的思维模型。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考