一、题目

1、题目描述

给你两个版本号 version1 和 version2 ，请你比较它们。

版本号由一个或多个修订号组成，各修订号由一个 ‘.’ 连接。每个修订号由 多位数字 组成，可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编号，下标从 0 开始，最左边的修订号下标为 0 ，下一个修订号下标为 1 ，以此类推。例如，2.5.33 和 0.1 都是有效的版本号。

比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较 忽略任何前导零后的整数值 。也就是说，修订号 1 和修订号 001 相等 。如果版本号没有指定某个下标处的修订号，则该修订号视为 0 。例如，版本 1.0 小于版本 1.1 ，因为它们下标为 0 的修订号相同，而下标为 1 的修订号分别为 0 和 1 ，0 < 1 。

返回规则如下：

如果 version1 > version2 返回 1，
如果 version1 < version2 返回 -1，
除此之外返回 0。

示例 1：
输入：version1 = “1.01”, version2 = “1.001”
输出：0
解释：忽略前导零，“01” 和 “001” 都表示相同的整数 “1”

示例 2：
输入：version1 = “1.0”, version2 = “1.0.0”
输出：0
解释：version1 没有指定下标为 2 的修订号，即视为 “0”

示例 3：
输入：version1 = “0.1”, version2 = “1.1”
输出：-1
解释：version1 中下标为 0 的修订号是 “0”，version2 中下标为 0 的修订号是 “1” 。0 < 1，所以 version1 < version2

2、基础框架

• C++版本给出的基础框架如下：

3、原题链接

https://leetcode.cn/problems/compare-version-numbers/

二、解题报告

1、思路分析

  $(1)$总体思路：同时遍历两个字符串，记录每个修订号，进行比较。
  $(2)$本题最大的难点在于边界的控制。
  $(3)$前导0不记录，用flag标签来判断是否为前导0。
  $(4)$当一个版本号遍历到末尾时，另外一个未遍历到末尾，则将遍历到末尾的，在之后的遍历中修订号全部记为0.

2、时间复杂度

3、代码详解

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int m = version1.length();
        int n = version2.length();
        string s1 = "";
        string s2 = "";
        int i = 0;
        int j = 0;
        bool flag = false;
        while(i < m && j < n) {
            while(i < m && version1[i] != '.') {
               if (version1[i] != '0') {
                   s1 += version1[i];
                   flag = true;
               }else {
                   if (flag) {
                       s1 += version1[i];
                   }
               } 
               i++;
            }
            if (i < m) i++;
            if (!flag) s1 = "0";
            flag = false;
            while(j < n && version2[j] != '.') {
               if (version2[j] != '0') {
                   s2 += version2[j];
                   flag = true;
               }else {
                   if (flag) {
                       s2 += version2[j];
                   }
               } 
               j++;
            }
            if (j < n) j++;
            if (!flag) s2 = "0";
            flag = false;
            if (stoi(s1) < stoi(s2)) {
                return -1;
            } else if (stoi(s1) > stoi(s2)) {
                return 1;
            } else {
                s1 = "";
                s2 = "";
            }
        } 
        if(i == m){
            s1 = "0";
        }
        if(j == n){
            s2 = "0";
        }
        while (i < m ) {
            while (i < m && version1[i] != '.') {
                if (version1[i] != '0') {
                   s1 += version1[i];
                   flag = true;
               }else {
                   if (flag) {
                       s1 += version1[i];
                   }
               } 
               i++;
            }
            if (i < m) i++;
            if (!flag) s1 = "0";
            flag = false;
            if (stoi(s1) < stoi(s2)) {
                return -1;
            } else if (stoi(s1) > stoi(s2)) {
                return 1;
            } else {
                s1 = "";
            }
        }
        while (j < n ) {
            while (j < n && version2[j] != '.') {
                if (version2[j] != '0') {
                   s2 += version2[j];
                   flag = true;
               }else {
                   if (flag) {
                       s2 += version2[j];
                   }
               } 
               j++;
            }
            if (j < n) j++;
            if (!flag) s2 = "0";
            flag = false;
            if (stoi(s1) < stoi(s2)) {
                return -1;
            } else if (stoi(s1) > stoi(s2)) {
                return 1;
            } else {
                s2 = "";
            }
        }
        return 0;
    }
};

三、本题小知识

1.C++中string转int。使用stoi函数