LeetCode 165 版本号比较Compare Version Numbers题解递归与数组两种实现思路的完整剖析【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本文基于 leetcode 仓库「每日一题」活动在 2019-09-16 记录的题解文档daily/2019-09-16.md围绕经典字符串模拟题165. Compare Version Numbers版本号比较展开。版本号比较是软件工程中真实高频的场景依赖版本检查、语义化版本解析、OTA 升级判断也是面试中考察字符串解析基本功的典型题目。读完本文你将掌握本问题的两类完整可运行实现递归解法与数组解法理解前导零处理、缺省修订号补零、多级版本对齐三个核心难点并能将这套分隔字符串 → 逐段转数字 → 逐级比较的通用模式迁移到其他字符串解析题目中。题目信息卡片项目内容题目165. Compare Version Numbers版本号比较活动日期2019-09-16每日一题标签String本题目录位于仓库的每日一题系列中该系列是仓库交流群内大家一起解一道题的沉淀成果题目会被记录并筛选进入仓库题解模块机制说明见 daily/README.md。题目描述与示例比较两个版本号version1和version2如果version1 version2返回1如果version1 version2返回-1除此之外返回0。题目给出如下约束与约定版本字符串非空并且只包含数字和.字符.字符不代表小数点而是用于分隔数字序列。例如2.5不是两个半也不是差一半到三而是第二版中的第五个小版本可以假设版本号每一级的默认修订版号为 0。例如版本号3.4的第一级大版本和第二级小版本修订号分别为3和4其第三级和第四级修订号均为0版本字符串由以点.分隔的数字字符串组成数字字符串可能有前导零版本字符串不以点开始或结束并且其中不会有两个连续的点即输入格式保证合法无需做格式校验。官方示例示例 1输入version1 0.1,version2 1.1输出-1示例 2输入version1 1.0.1,version2 1输出1示例 3输入version1 7.5.2.4,version2 7.5.3输出-1示例 4输入version1 1.01,version2 1.001输出0解释忽略前导零01和001表示相同的数字1。示例 5输入version1 1.0,version2 1.0.0输出0解释version1没有第三级修订号这意味着它的第三级修订号默认为0。问题拆解三个关键难点原文档明确指出这个问题简化后就是依次比较每一个修订版本的大小因此可以拆解为三个子问题获取每个修订版本号大小从字符串中按.分隔并提取出每一段数字处理每个修订版本号的前导零问题01与001表示同一个数字1需要在解析阶段消化处理两个版本修订层级数量不同的情况如1.0与1.0.0比较缺少的层级需要按0补齐。围绕这三个问题原文档给出了两套解法下面逐一展开。解法一递归逐级比较C解题思路递归解法的核心思想是每一轮递归只负责解析当前层级第一个点之前的数字段比较后如果相等就把剩余部分继续交给下一轮递归处理。针对三个子问题的处理方式如下问题 1提取修订号对字符串处理比较熟悉的话会比较简单——直接遍历字符串找到第一个点first_dot找不到的情况设为-1用substr取出点前的数字段即可。第二、第三个点之后的段落通过递归天然回避了定位复杂度每一轮都相当于重新找第一个点前的数字问题 2前导零解析时定义初值v 0每次计算v v * 10 (str[i] - 0)乘 10 累加的方式天然吞掉了前导零例如001会解析为0*100 → 0*100 → 0*101 1问题 3层级数不同当某一轮中一个版本的first_dot -1已无剩余层级而另一个还有剩余层级时给已耗尽的一方补一个0作为当前层的修订号再继续递归从而在逻辑上实现缺省修订号默认 0。完整实现class Solution { public: int first_num(string str, int first_dot){ int v1 0; first_dot -1; for(int i 0; i str.size(); i){ if(str[i] .){ first_dot i; break; } else v1 v1 * 10 (str[i] - 0); } return v1; } int compareVersion(string version1, string version2) { int v1 0, v2 0; int v1_first_dot, v2_first_dot; v1 first_num(version1, v1_first_dot); v2 first_num(version2, v2_first_dot); if(v1 v2) return 1; else if(v1 v2) return -1; else{ if(v1_first_dot -1 v2_first_dot -1) return 0; if(v1_first_dot -1) version1 0; else version1 version1.substr(v1_first_dot1); if(v2_first_dot -1) version2 0; else version2 version2.substr(v2_first_dot1); return compareVersion(version1, version2); } } };说明原文档在讲解前导零处理时提到的表达式为str[i] - a结合实现代码可确认这是文档笔误正确写法应为str[i] - 0将字符数字转为数值原文档找到第一个逗号中的逗号实际指分隔用的点字符.。关键细节解读辅助函数first_num通过引用参数first_dot向外输出第一个点的下标函数本身返回点前数字段的整数值。扫描过程中一旦遇到.立即break因此每次只解析一级修订号递归终止条件当两个版本的first_dot同时为-1说明双方所有层级都已比较完毕且全部相等返回0单方耗尽时的处理若version1已无剩余层级而version2还有则将version1置为0再递归例如比较1.0与1.0.0第二轮version1 0、version2 0相等第三轮双方first_dot均为-1返回0与示例 5 一致复杂度每一轮递归消耗掉当前版本剩余字符串中的一部分整体扫描两串各一次时间复杂度为 O(n m)n、m 为两个版本串长度递归栈深度取决于修订层级数最坏 O(max(n, m))。由于每轮递归会通过substr生成新的字符串实际运行存在字符串拷贝开销这也是后续数组解法的优化动机之一。解法二数组化比较C解题思路数组解法的思路更直观先把每个版本号完整解析成一列整型修订号存入数组再按下标逐位比较。相比递归解法它一次性完成全部解析比较阶段不再涉及字符串操作只做纯整数比较性能更可控。原文档中该解法由作者 ljj666 提供。完整实现int compareVersion(char * version1, char * version2){ if (version1 NULL || version2 NULL) return -1; int *val1 (int *)calloc(1024, sizeof(int)); int *val2 (int *)calloc(1024, sizeof(int)); int len1 strlen(version1), top1 0; int len2 strlen(version2), top2 0; int i, n; for (i 0, n 0; i len1; i) { //解析版本1 if (version1[i] .) { val1[top1] n; n 0; }else n n*10 (version1[i] 0x0f); } val1[top1] n; for (i 0, n 0; i len2; i) { //解析版本2 if (version2[i] .) { val2[top2] n; n 0; }else n n*10 (version2[i] 0x0f); } val2[top2] n; for (i 0; i top1 i top2; i) { //比较版本大小 if (val1[i] val2[i]) return 1; else if (val1[i] val2[i]) return -1; } if (i top1) { //由于可能有的版本还没遍历完 while (i top1) if (val1[i]) return 1; //只要版本后面的数字出现的不是0就意味着两个版本不一样 }else{ while (i top2) if (val2[i]) return -1; } return 0; }关键细节解读空指针防御入口处对version1、version2判空空指针直接返回-1固定容量数组使用calloc(1024, sizeof(int))分配两段整数数组存放各级修订号calloc会将内存初始化为 0配合缺省修订号为 0的语义天然合适top1、top2作为栈顶指针记录已解析的修订号个数位运算取数技巧version1[i] 0x0f利用字符0~9的 ASCII 码低 4 位恰好等于其数值本身的特性等价于str[i] - 0是与解法一在取数环节的差异点两阶段比较第一阶段按位比较公共部分i top1 i top2一旦发现不等立即返回第二阶段处理某个版本还有剩余层级的情况——只要剩余层级中存在非 0 数字就说明两个版本不等否则视为补 0 后相等。例如1.0与1.0.0前两轮相等top1 2、top2 3第二阶段扫描val2剩余的val2[2] 0不触发返回最终返回0复杂度单次线性扫描完成解析比较阶段也是线性时间复杂度 O(n m)空间复杂度 O(1024) 级别的常数空间受固定容量数组限制。两种解法对比与通用模式提炼维度解法一递归C解法二数组C核心思想逐级解析、递归处理剩余部分一次性全量解析为数组、逐位比较前导零处理累加式v v*10 (str[i]-0)累加式n n*10 (str[i]0x0f)层级不对齐处理缺省方补0字符串继续递归比较公共部分后扫描剩余层级的非零项额外开销substr反复拷贝字符串、递归栈固定 1024 容量数组无双份字符串拷贝时间复杂度O(n m)O(n m)空间复杂度递归栈深度 O(层级数)最坏 O(max(n, m))常数级固定 1024 容量两者的共同本质以.为分隔符将版本字符串切分为数字序列比较时遵循前导零等价、缺省层按 0 补足的规则逐级比较。这套模式完全可以迁移到其他以定界符分隔的字符串解析问题中例如将字符串按分隔符拆段、逐段转数值、再按位比较/处理。从仓库的分类看本题属于字符串问题家族仓库的字符串专题 thinkings/string-problems.md 指出字符串本质上是字符数组很多数组的思维和方法如指针、逐位累加都可以用在字符串问题上并发挥很好的作用——本问题的乘 10 累加吞前导零按点分段逐级比较正是这一论断的典型例证。仓库每日一题中与本题同属String标签的还有 14. Longest Common Prefix每日一题 2019-06-03 等可作为字符串类题目的横向对照。仓库中的延伸阅读材料每日一题活动机制与历史题目汇总daily/README.md本题收录于 daily/2019-09-16.md字符串问题方法论thinkings/string-problems.md字符串与字符数组的关系、substr 类实现、回文/前缀/公共子串等子专题每日一题的 JavaScript 解答归档daily/answers/14.longest-common-prefix.js展示了仓库内字符串类题目的 JS 实现风格带lc注释头、复杂度注释、tag 标注本题也可按相同规范自行实现一份 JavaScript 版如split(.)后逐段parseInt或乘 10 累加用于日常演练双指针与字符串解析的关联思路可参考 91 天学算法基础篇 91/two-pointers.md 中对指针逐位推进思想的阐述。小结版本号比较这道题表面简单实则集中考查了字符串解析的三项基本功按分隔符分段、数字转换中的前导零处理、长度不齐时的缺省补零。递归解法以最少的辅助数据结构完成了逐级比较逻辑紧凑但存在字符串拷贝开销数组解法以固定容量数组换取了解析与比较的解耦适合追求稳定性能和 C 语言风格的场景。理解这两套实现的差异与共性不仅有助于应对面试中的同类模拟题也为日常处理以点/斜杠/连字符分隔的编号字符串提供了可直接套用的代码模板。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考