# 春节刷题计划（二）| 一题三解，搞定版本号判断

    你好，我是朱涛。今天是除夕夜，先祝你虎年春节快乐！

在上节刷题课中，我给你留了一个作业，那就是：用Kotlin来完成 [LeetCode的165号题《版本号判断》](https://leetcode-cn.com/problems/compare-version-numbers/)。那么今天这节课，我就来讲讲我的解题思路，希望能给你带来一些启发。

这道题目其实跟我们平时的工作息息相关。给你两个字符串代表的版本号，需要你判断哪个版本号是新的，哪个版本号是旧的。比如，2.0与1.0对比的话，2.0肯定是新版本，1.0肯定是旧版本。对吧？

不过，这里面还有一些问题需要留意，这些都是我们在正式写代码之前要弄清楚的。

*   首先，版本号是可能以0开头的。比如0.1、1.01，这些都是合理的版本号。
*   另外，如果是以0开头的话，1个0和多个0，它们是等价的，比如1.01、1.001、1.00001之间就是等价的，也就是说这几个版本号其实是相等的。
*   还有，1.0、1.0.0、1.0.0.0它们之间也是等价的，也就是说这几个版本号也是相等的。

## 思路一

好了，理解了题意以后，我们就可以开始写代码了，LeetCode上面给了我们一个待实现的方法，大致如下：

```plain
fun compareVersion(version1: String, version2: String): Int {
    // 待完善
}

```

分析完题目以后，也许你已经发现了，这道题目其实并不需要什么特殊的数据结构和算法基础，这是一道单纯的“模拟题”。我们脑子里是如何对比两个版本号的，我们的代码就可以怎么写。  
下面我做了一个动图，展示了版本号对比的整体流程。

![图片](https://static001.geekbang.org/resource/image/25/ab/25a423b14908721aef1dd36082d345ab.gif?wh=1080x608)

我们可以看到，这个对比的流程，大致可以分为以下几个步骤。

*   第一步，将版本号的字符串用“点号”进行分割，得到两个字符串的列表。
*   第二步，同时遍历这两个列表，将列表中的每一个元素转换成整数，比如，当遍历到第二位的时候，5、05这两个字符串，都会转换成数字5。这里**有个细节**，那就是当版本号的长度不一样的时候，比如，遍历到7.05.002.2的最后一位时，7.5.2其实已经越界了，这时候我们需要进行补零，然后再转换成数字。
*   第三步，根据转换后的数字进行对比，如果两者相等的话，我们就继续遍历下一位。如果不相等的话，我们就能直接返回对比的结果了。
*   第四步，如果两个版本号都遍历到了末尾，仍然没有对比出大小的差异，那么我们就认为这两个版本号相等，返回0即可。

所以，按照上面的思路，我们可以把compareVersion()这个函数分为以下几个部分：

```plain
fun compareVersion(version1: String, version2: String): Int {
    // ① 使用“.”，分割 version1 和 version2，得到list1、list2
    // ② 同时遍历list1、list2，取出的元素v1、v2，并将其转换成整数，这里注意补零操作
    // ③ 对比v1、v2的大小，如果它们两者不一样，我们就可以终止流程，直接返回结果。
    // ④ 当遍历完list1、list2后仍然没有判断出大小话，说明两个版本号其实是相等的，这时候应该返回0
}

```

那么接下来，其实就很简单了。我们只需要将注释里面的自然语言，用代码写出来就行了。具体代码如下：

```plain
fun compareVersion(version1: String, version2: String): Int {
    // ① 分割
    val list1 = version1.split(".")
    val list2 = version2.split(".")

    var i = 0
    while (i < list1.size || i < list2.size) {
        // ② 遍历元素
        val v1 = list1.getOrNull(i)?.toInt()?:0
        val v2 = list2.getOrNull(i)?.toInt()?:0

        // ③ 对比
        if (v1 != v2) {
            return v1.compareTo(v2)
        }
        i++
    }

    // ④ 相等
    return 0
}

```

在上面的代码中，有两个地方需要格外注意。

**一个是while循环的条件**。由于list1、list2的长度可能是不一样的，所以，我们的循环条件是：list1、list2当中只要有一个没有遍历完的话，我们就要继续遍历。

还有一个需要注意的地方，**getOrNull(i)，这是Kotlin独有的库函数**。使用这个方法，我们不必担心越界问题，当index越界以后，这个方法会返回null，在这里我们把它跟 [Elvis表达式](https://time.geekbang.org/column/article/472154)结合起来，就实现了自动补零操作。这也体现出了Kotlin表达式语法的优势。

好，到这里，我们就用第一种思路实现了版本号对比的算法。下面我们再来看看第二种思路。

## 思路二

前面的思路，我们是使用的Kotlin的库函数split()进行分割，然后对列表进行遍历来判断的版本号。其实，这种思路还可以**进一步优化**，那就是我们自己遍历字符串，来模拟split的过程，然后在遍历过程中，我们顺便就把比对的工作一起做完了。

思路二的整体过程比较绕，我同样是制作了一个动图来描述这个算法的整体流程：

![图片](https://static001.geekbang.org/resource/image/dd/67/dd6a09c1428892c7dc5a52623842d067.gif?wh=1080x608)

以上的整体算法过程，是典型的“**双指针**”思想。运用这样的思想，我们大致可以写出下面这样的代码：

```plain
fun compareVersion(version1: String, version2: String): Int {
    val length1 = version1.length
    val length2 = version2.length

    // ①
    var i = 0
    var j = 0
    // ②
    while (i < length1 || j < length2) {
        // ③
        var x = 0
        while (i < length1 && version1[i] != '.') {
            x = x * 10 + version1[i].toInt() - '0'.toInt()
            i++
        }
        i++

        // ④
        var y = 0
        while (j < length2 && version2[j] != '.') {
            y = y * 10 + version2[j].toInt() - '0'.toInt()
            j++
        }
        j++

        // ⑤
        if (x != y) {
            return x.compareTo(y)
        }
    }
    // ⑥
    return 0
}

```

这段代码一共有6个注释，我们来一个个解释。

*   注释①，代表的就是我们遍历两个版本号的index，双指针，指的就是它们两个。
*   注释②，最外层的while循环，其实就是为了确保双指针可以遍历到两个字符串的末尾。你注意下这里的循环条件，只要version1、version2当中有一个没到末尾，就会继续遍历。
*   注释③，这里就是在遍历version1，一直到字符串末尾，或者遇到“点号”。在同一个循环当中，我们会对x的值进行累加，这个做法其实就是把字符串的数字转换成十进制的数字。
*   注释④，这里和注释③的逻辑一样，只是遍历的对象是version2。
*   注释⑤，这里会对累加出来的x、y进行对比，不相同的话，我们就可以返回结果了。
*   注释⑥，如果遍历到末尾还没有结果，这就说明version1、version2相等。

现在，我们就已经用Kotlin写出了两个题解，使用的思路都是命令式的编程方式。也许你会好奇，**这个问题能用函数式的思路来实现吗？**

答案当然是可以的！

## 思路三

我们在前面就提到过，Kotlin是支持多范式的，我们可以根据实际场景来灵活选择编程范式。那么在这里，我们可以借鉴一下前面第一种解法的思路。

其实，想要解决这个问题，我们只要能把version1、version2转换成两个整数的列表，就可以很好地进行对比了。我制作了一个动图，方便你理解：

![图片](https://static001.geekbang.org/resource/image/ee/32/eea4765d618437d7145ae77c8e404a32.gif?wh=1080x608)

根据这个流程，我们可以大致写出下面这样的代码：

```plain
fun compareVersion(version1: String, version2: String): Int =
    version1.split(".")
        .zipLongest(version2.split("."), "0") // ①
        .onEach { // ②
            with(it) {
                if (first != second) {
                    return first.compareTo(second)
                }
            }
        }.run { return 0 }

```

这段代码看起来很简洁，核心的逻辑在两个方法当中，我分别用注释标注了。

*   注释①，zipLongest()这个方法，它的作用是将version1、version2对应的列表合并到一起，它返回值的类型是List<Pair<Int, Int>>。
*   注释②，onEach()，其实它是一个高阶函数，它的作用就是遍历List当中的每一个Pair，将其中的整型版本号拿出来对比，如果不一样，就可以直接返回结果。

现在，你可能会感慨，这代码看起来真香啊！这个嘛……别高兴得太早。虽然Kotlin支持基础的zip语法，但它目前还不支持zipLongest()这么高级的操作符。

那么这该怎么办呢？我们只能自己来实现zipLongest()了！为了让前面的代码通过编译，我们必须要自己动手实现下面三个扩展函数。

```plain
private fun Iterable<String>.zipLongest(
    other: Iterable<String>,
    default: String
): List<Pair<Int, Int>> {
    val first = iterator()
    val second = other.iterator()
    val list = ArrayList<Pair<Int, Int>>(minOf(collectionSizeOrDefault(10), other.collectionSizeOrDefault(10)))
    while (first.hasNext() || second.hasNext()) {
        val v1 = (first.nextOrNull() ?: default).toInt()
        val v2 = (second.nextOrNull() ?: default).toInt()
        list.add(Pair(v1, v2))
    }
    return list
}

private fun <T> Iterable<T>.collectionSizeOrDefault(default: Int): Int =
        if (this is Collection<*>) this.size else default

private fun <T> Iterator<T>.nextOrNull(): T? = if (hasNext()) next() else null

// Pair 是Kotlin标准库提供的一个数据类
// 专门用于存储两个成员的数据
// 提交代码的时候，Pair不需要拷贝进去
public data class Pair<out A, out B>(
    public val first: A,
    public val second: B
) : Serializable {
    public override fun toString(): String = "($first, $second)"
}

```

这三个扩展函数实现起来还是比较简单的，zipLongest()其实就是合并了两个字符串列表，然后将它们按照index合并成Pair，另外那两个扩展函数都只是起了辅助作用。

这样，我们把前面的代码一起粘贴到LeetCode当中，其实代码是可以通过的。不过呢，我们的代码当中其实还有一个**比较深的嵌套**，看起来不是很顺眼：

```plain
fun compareVersion(version1: String, version2: String): Int =
    version1.split(".")
        .zipLongest(version2.split("."), "0")
        .onEach {
            // 这里的嵌套比较深
            with(it) {
                if (first != second) {
                    return first.compareTo(second)
                }
            }
        }.run { return 0 }

```

你可以注意到，在onEach当中，有一个代码块，它有两层嵌套，这看起来有点丑陋。那么，我们能不能对它进一步优化呢？

当然是可以的。

这里，我们只需要想办法让onEach当中的Lambda，变成[带接收者的函数类型](https://time.geekbang.org/column/article/476637)即可。具体做法就是，我们自己实现一个新的onEachWithReceiver()的高阶函数。

```plain
//                                                        注意这里
//                                                           ↓
inline fun <T, C : Iterable<T>> C.onEachWithReceiver(action: T.() -> Unit): C {
    return apply { for (element in this) action(element) }
}

//                                                   注意这里
// Kotlin库函数当中的onEach                                ↓
public inline fun <T, C : Iterable<T>> C.onEach(action: (T) -> Unit): C {
    return apply { for (element in this) action(element) }
}

```

上面的代码展示了onEach()和onEachWithReceiver()之间的差别，可以看到，它们两个的函数体其实没有任何变化，区别只是action的函数类型而已。

所以在这里，借助onEachWithReceiver()，就可以进一步简化我们的代码：

```plain
fun compareVersion(version1: String, version2: String): Int =
    version1.split(".")
        .zipLongest(version2.split("."), "0")
        .onEachWithReceiver {
            // 减少了一层嵌套
            if (first != second) {
                return first.compareTo(second)
            }
        }.run { return 0 }

```

在这段代码中，我们把onEach()改成了onEachWithReceiver()，因为它里面的Lambda是带有接收者，原本的Pair对象变成了this对象，这样，我们就可以直接使用first、second来访问Pair当中的成员了。

现在，就让我们来看看整体的代码吧：

```plain
fun compareVersion(version1: String, version2: String): Int =
    version1.split(".")
        .zipLongest(version2.split("."), "0")
        .onEachWithReceiver {
            if (first != second) {
                return first.compareTo(second)
            }
        }.run { return 0 }

private inline fun <T, C : Iterable<T>> C.onEachWithReceiver(action: T.() -> Unit): C {
    return apply { for (element in this) action(element) }
}

private fun <T> Iterable<T>.collectionSizeOrDefault(default: Int): Int =
    if (this is Collection<*>) this.size else default

private fun <T> Iterator<T>.nextOrNull(): T? = if (hasNext()) next() else null

private fun Iterable<String>.zipLongest(
    other: Iterable<String>,
    default: String
): List<Pair<Int, Int>> {
    val first = iterator()
    val second = other.iterator()
    val list = ArrayList<Pair<Int, Int>>(minOf(collectionSizeOrDefault(10), other.collectionSizeOrDefault(10)))
    while (first.hasNext() || second.hasNext()) {
        val v1 = (first.nextOrNull() ?: default).toInt()
        val v2 = (second.nextOrNull() ?: default).toInt()
        list.add(Pair(v1, v2))
    }
    return list
}

```

好了，这就是我们的第三种思路。看完这三种思路以后，你会更倾向于哪种思路呢？

## 小结

这节课，我们使用了三种思路，实现了[LeetCode的165号题《版本号判断》](https://leetcode-cn.com/problems/compare-version-numbers/)。其中，前两种思路，是命令式的编程方式，第三种是偏函数式的方式。在我看来呢，这三种方式各有优劣。

*   思路一，代码逻辑比较清晰，代码量小，时间复杂度、空间复杂度较差。
*   思路二，代码逻辑比较复杂，代码量稍大，时间复杂度、空间复杂度非常好。
*   思路三，代码主逻辑非常清晰，代码量大，时间复杂度、空间复杂度较差。

第三个思路其实还有一个额外的优势，那就是，我们自己实现的扩展函数，可以用于以后解决其他问题。这就相当于沉淀出了有用的工具。

## 小作业

好，最后，我还是给你留一个小作业，请你用Kotlin来完成[LeetCode的640号题《求解方程》](https://leetcode-cn.com/problems/solve-the-equation/)。这道题目我同样会在下节课给出答案解析。

欢迎继续给我留言，我们下节课再见。