字节/蚂蚁/美团/拼多多 LeetCode 165.比较版本号

思路1.把字符串按照 . 分割并存储到字符串数组每次按顺序从两个字符串数组中取出1个元素并转成整数依次比较。2.查看下面的示例发现示例1的列表为[1,2]和[1,10]示例2的列表均为[1,1]示例3的列表均为[1,0,0,0]。示例 1输入version1 1.2, version2 1.10输出-1解释version1 的第二个修订号为 2version2 的第二个修订号为 102 10所以 version1 version2。示例 2输入version1 1.01, version2 1.001输出0解释忽略前导零01 和 001 都代表相同的整数 1。示例 3输入version1 1.0, version2 1.0.0.0输出0解释version1 有更少的修订号每个缺失的修订号按 0 处理。3.问题可以转化为比较这两个列表的字典序1从左到右遍历两个列表分别记作a和b2如果a[i] b[i]返回-13如果a[i] b[i]返回14否则继续向后遍历5如果遍历过程中没有返回说明两个列表相同返回0。4.复杂度分析1时间复杂度O(n m)其中n是version1的长度m是version2的长度。2空间复杂度O(n m)。附代码class Solution { public int compareVersion(String version1, String version2) { // string.split(\\.)是Java中用正则表达式分割字符串的方法 // 在正则表达式中\.表示普通的点字符 // 但由于在Java字符串中\本身需要转义所以要写成\\. // 所以本质的含义就是按照点号字符分割字符串只是因为点号在正则表达式中有特殊的含义所以需要转义 String[] a version1.split(\\.); // 字符串数组a存储按点分割的version1 String[] b version2.split(\\.); // 字符串数组b存储按点分割的version2 int n a.length; // version1有多少段 int m b.length; // version2有多少段 for (int i 0; i n || i m; i) { int ver1 i n ? Integer.parseInt(a[i]) : 0; int ver2 i m ? Integer.parseInt(b[i]) : 0; if (ver1 ! ver2) { return ver1 ver2 ? -1 : 1; } } return 0; } }ACM模式import java.util.Scanner; class Solution { public int compareVersion(String version1, String version2) { // string.split(\\.)是Java中用正则表达式分割字符串的方法 // 在正则表达式中\.表示普通的点字符 // 但由于在Java字符串中\本身需要转义所以要写成\\. // 所以本质的含义就是按照点号字符分割字符串只是因为点号在正则表达式中有特殊的含义所以需要转义 String[] a version1.split(\\.); String[] b version2.split(\\.); int n a.length; int m b.length; for (int i 0; i n || i m; i) { int ver1 i n ? Integer.parseInt(a[i]) : 0; int ver2 i m ? Integer.parseInt(b[i]) : 0; if (ver1 ! ver2) { return ver1 ver2 ? -1 : 1; } } return 0; } } public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); // 读取两个版本号字符串 String version1 scanner.next(); String version2 scanner.next(); // 比较版本号 Solution solution new Solution(); int result solution.compareVersion(version1, version2); System.out.println(result); scanner.close(); } }