3
无重复字符的最长子串
中等高频
146
LRU缓存机制
中等高频
206
反转链表
简单高频
215
数组中的第K个最大元素
中等高频
25
K个一组翻转链表
困难高频
15
三数之和
中等高频
53
最大子数组和
中等高频
912
排序数组
中等高频
21
合并两个有序链表
简单高频
5
最长回文子串
中等高频
200
岛屿数量
中等高频
33
搜索旋转排序数组
中等高频
46
全排列
中等高频
88
合并两个有序数组
简单高频
20
有效的括号
简单高频
121
买卖股票的最佳时机
简单高频
236
二叉树的最近公共祖先
中等高频
92
反转链表 II
中等高频
103
二叉树的锯齿形层序遍历
中等高频
141
环形链表
简单高频
300
最长上升子序列
中等高频
54
螺旋矩阵
中等高频
143
重排链表
中等高频
23
合并K个排序链表
困难高频
415
字符串相加
简单高频
56
合并区间
中等高频
160
相交链表
简单高频
42
接雨水
困难高频
1143
最长公共子序列
中等高频
124
二叉树中的最大路径和
困难高频
93
复原IP地址
中等高频
82
删除排序链表中的重复元素 II
中等中频
19
删除链表的倒数第N个节点
中等中频
142
环形链表 II
中等中频
4
寻找两个正序数组的中位数
困难中频
199
二叉树的右视图
中等中频
102
二叉树的层序遍历
中等中频
165
比较版本号
中等中频
704
二分查找
简单中频
232
用栈实现队列
简单中频
22
括号生成
中等中频
94
二叉树的中序遍历
简单中频
239
滑动窗口最大值
困难中频
69
x 的平方根
简单中频
148
排序链表
中等中频
32
最长有效括号
困难中频
31
下一个排列
中等中频
8
字符串转换整数 (atoi)
中等中频
70
爬楼梯
简单中频
322
零钱兑换
中等中频
43
字符串相乘
中等中频
76
最小覆盖子串
困难中频
41
缺失的第一个正数
困难中频
105
从前序与中序遍历序列构造二叉树
中等中频
78
子集
中等中频
151
翻转字符串里的单词
中等中频
155
最小栈
简单中频
34
在排序数组中查找元素的第一个和最后一个位置
中等中频
394
字符串解码
中等中频
101
对称二叉树
简单中频
39
组合总和
中等中频
470
用 Rand7() 实现 Rand10()
中等低频
64
最小路径和
中等低频
104
二叉树的最大深度
简单低频
110
平衡二叉树
简单低频
144
二叉树的前序遍历
简单低频
48
旋转图像
中等低频
234
回文链表
简单低频
695
岛屿的最大面积
中等低频
122
买卖股票的最佳时机 II
简单低频
240
搜索二维矩阵 II
中等低频
221
最大正方形
中等低频
98
验证二叉搜索树
中等低频
543
二叉树的直径
简单低频
14
最长公共前缀
简单低频
179
最大数
中等低频
113
路径总和 II
中等低频
662
二叉树最大宽度
中等低频
62
不同路径
中等低频
198
打家劫舍
中等低频
152
乘积最大子数组
中等低频
560
和为K的子数组
中等低频
112
路径总和
简单低频
226
翻转二叉树
简单低频
209
长度最小的子数组
中等低频
227
基本计算器 II
中等低频
169
多数元素
简单低频
24
两两交换链表中的节点
中等低频
139
单词拆分
中等低频
283
移动零
简单低频
718
最长重复子数组
中等低频
1
两数之和
简单低频
2
两数相加
中等低频
#165
中等
中频
split-and-compare

比较版本号

这是一道围绕字符串展开的高频练习。建议先掌握「split-and-compare」这套写法,再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。

字符串

题目分析

这道题表面上是在处理「比较版本号」,但先要想清楚题目到底让你返回什么,以及过程中哪些约束必须一直满足。从题型上看,它主要在考 字符串 这些能力。先别急着写代码,先把题目要求翻译成人话,明确结果是什么、约束是什么、过程里要持续维护什么。只有先把题目要求翻译成人话,后面的推荐代码才是在实现思路,而不是直接给答案。

接下来怎么看推荐代码: 带着这个理解再看推荐代码时,重点观察这条主线:先按点号切分两个版本号,再逐段按整数比较,缺失段默认看作 0。

推荐代码

推荐解法:split-and-compare
时间复杂度: O(m+n)
空间复杂度: O(m+n)
核心思路: 先按点号切分两个版本号,再逐段按整数比较,缺失段默认看作 0。
class Solution {
    public int compareVersion(String version1, String version2) {
        // 将版本号分割成数组
        String[] v1 = version1.split("\.");
        String[] v2 = version2.split("\.");
        
        int i = 0;
        int j = 0;
        
        // 比较两个版本号的每一部分
        while (i < v1.length || j < v2.length) {
            // 将当前部分转换为整数,如果超出数组长度则视为0
            int num1 = i < v1.length ? Integer.parseInt(v1[i]) : 0;
            int num2 = j < v2.length ? Integer.parseInt(v2[j]) : 0;
            
            // 比较当前部分
            if (num1 < num2) {
                return -1;
            } else if (num1 > num2) {
                return 1;
            }
            
            // 移动指针
            i++;
            j++;
        }
        
        // 所有部分都相等,返回0
        return 0;
    }
}

结构化讲解

面试时怎么讲

开场思路

这题我会把版本号按点切开,然后逐段按整数比较。

核心过程

  1. 先把两个版本号切成数组。
  2. 从左到右比较同一位置的段值。
  3. 如果某一侧没有这一段,就按 0 处理。
  4. 一旦某段不相等就返回,否则全部比较完返回相等。

复杂度总结

时间复杂度 O(m+n),空间复杂度 O(m+n)

面试补一句:这题最容易错的是忘了“按整数比”和“缺失段看作 0”。

核心思路

版本号比较的关键是“按段比较而不是按整串比较”。每一段都要当整数处理,所以前导零不会影响大小关系。

步骤讲解

1

先按点号切分版本号

把两个版本号都拆成若干段,便于逐段对应比较。

为什么这样做:版本号语义天然按段组织,不适合直接字典序比较。
对应代码提示:String[] parts1 = version1.split("\.");
2

逐段转整数比较

从左到右比较同位置段值,遇到不相等时立刻返回结果。

为什么这样做:高位版本段优先级更高,先出现差异就已经决定大小。
对应代码提示:int a = i < parts1.length ? Integer.parseInt(parts1[i]) : 0;
3

缺失段按 0 处理

如果某一侧段数更少,就把超出的段视作 0 继续比较。

为什么这样做:1.01.0.0 在语义上应当相等。
对应代码提示:int b = i < parts2.length ? Integer.parseInt(parts2[i]) : 0;

易错点

按字符串字典序比较

102 的字符串顺序与整数顺序不同。

正确理解:每段必须转整数比较。

把前导零当成有效差异

011 代表相同版本段值。

正确理解:按整数解析后再比,前导零自然被忽略。

少段的一边直接判小

尾部缺失段可能全是 0,此时两个版本应相等。

正确理解:缺失段要默认按 0 继续比较。

复杂度与适用判断

时间复杂度:O(m+n)
空间复杂度:O(m+n)
比其他方案更好在哪里:比手写字符扫描更直观,也足够满足题目规模。
适用判断:字符串分段后各段语义独立时,优先考虑 split 后逐段处理。

额外提醒

  • 版本号比较的最小单位是“段”,不是单个字符。
动画演示仅在桌面端提供,移动端请优先阅读推荐代码与结构化讲解。