一道腾讯面试题竟引发我与好友两人争执不下

1次阅读

共计 5640 个字符，预计需要花费 15 分钟才能阅读完成。

上班坐地铁的时候，好友忽然给我发过去一条微信：

这道题是这样：

咱们软件开发不是常常不是有版本号吗？
比方经典的兼容 IE 浏览器的 jQuery1.x 最初的一个版本 1.12.4，但有时咱们又不会准确到第三位，比方：vue3.0、react16.8…

而后实现一个办法，把两个版本号传进去，能够两位 ( 如：3.0)也能够三位 ( 如：1.12.4)，如果第一个版本比第二个版本大，就返回 1。

如果第二个版本比第一个大，就返回 -1。其余状况返回 0。

我很快就想出了一个思路：(先省略后期的各种判断以及类型转换 ) 用 split 办法将其切割成数组，而后把两个数组的第一位相比拟，如果第一位就比拟出后果就能够间接返回，没有必要在比拟第二位了，依此类推，直到比拟到最初一位。如果比拟到最初一位的时候两个数组的长度不统一，就为短的那一方加个 0，比方 3.0 就会变成 3.0.0。

本认为他也会这么想，但万万没想到他说出了一个脑回路跟我不太一样的解法：

他这么一说，我一下子就想到了 JS 小数计算不精确的问题，他必定是从那取得的灵感。

不过他竟然说我是暴力解法，我怎么感觉他那种才是暴力解法……

既然有争议，那咱们就一不做二不休，实现一下吧！

function comparison (version1, version2) {
  // 参数的类型
  const types = ['string', 'number']

  // 第一个参数的类型
  const type1 = typeof version1

  // 第二个参数的类型
  const type2 = typeof version2
  
  // 参数不是字符串或数字的状况下返回 0
  if (!types.includes(type1) || !types.includes(type2)) return 0

  // 如果 version1 是 number 就将其转成字符串
  const ver1 = type1 === 'number' ? version1.toString() : version1

  // 如果 version2 是 number 就将其转成字符串
  const ver2 = type2 == 'number' ? version2.toString() : version2

  // 将 version1 变成数组
  const versionArr1 = ver1.split('.')

  // 将 version2 变成数组
  const versionArr2 = ver2.split('.')

  // 获取长度最长的数组的 length
  const len = Math.max(versionArr1.length, versionArr2.length)

  // 循环比照版本号，如果前一位比拟不出大小就持续向后比照
  for (let i = 0; i < len; i++) {
    // 如果长度不统一将主动补 0 同时将字符串转为数字
    const version1 = Number(versionArr1[i]) || 0
    const version2 = Number(versionArr2[i]) || 0

    if (version1 > version2) {
      // 如果 version1 大就返回 1
      return 1
    } else if (version1 < version2) {
      // 如果 version2 大就返回 -1
      return -1
    } else {
      // 如果比拟到最初就返回 0，否则持续比拟
      if (i + 1 === len) {return 0} else {continue}
    }
  }
}

为了不便观看这里省略了用正则判断传进来的参数是否合乎 xx.xx.xx 模式或者去除后面的 0 等一些繁琐判断 ( 面试题应该也不必写那么细，写出思路即可 )，所以只判断了参数是否为 string 或 number 类型，来测试一下：

因为没有写死判断，所以甚至能够实现有限版本号的比拟：

如同没啥故障哈，反正面试题说的是其余状况返回 0，版本相等、传错参数应该都属于其余状况。

当然这个版本号过多 (1.2.3.4.5.6) 的状况严格意义上也算是传错参数，但为了验证一下版本号过多的状况我的办法性能与敌人的办法性能哪个好 ( 验证一下是否为暴力解法 )，所以写成了这样( 这种更难写呢 )，而且写成这样更利于可继续化发展嘛，如果较真的敌人能够采纳 if(len === 2) 和 if(len === 3)的这种模式来解题。

接下来咱们再来看一下我敌人的办法:

经测试有 bug，起初又改了几版，上面是最终版：

function compareVersion(version1, version2) {let ver1 = version1.split('.')
      let ver2 = version2.split('.')
      let len1 = ''let len2 =''
      ver1.forEach((item,index)=>{
        let zero = ''
        for (let i = 0; i < index; i++) {zero += '0'}
        len1 += zero + item
      })
      ver2.forEach((item,index)=>{
        let zero = ''
        for (let i = 0; i < index; i++) {zero += '0'}
        len2 += zero + item
      })
      let len = len1.length - len2.length
      if(len > 0){len2 = Number(len2) * Math.pow(10,Math.abs(len))
      }else{len1 = Number(len1) * Math.pow(10,Math.abs(len))
      }
      if(len1>len2){return 1}else if(len1<len2){return -1}else{return 0} 
}

<center>（最终版其实没有用到 replace 办法，他也用了 split）</center>
这是他的原代码，没有写正文，起初他发微信过去说让我把循环加 0 的那步去掉，只加一个 0 即可。

刚好我打算革新一下他的代码顺便整顿下格局而后加点正文，革新后如下：

function compareVersion(version1, version2) {
      // 将传进的版本号切割为数组
      const ver1 = version1.split('.')
      const ver2 = version2.split('.')

      // 将数组相加两头补 0 最初变成一个数字(字符串)
      let len1 = ver1.reduce((sum, item) => sum + '0' + item, '')
      let len2 = ver2.reduce((sum, item) => sum + '0' + item, '')

      // 得出两个数字 (字符串) 长度的差值
      const len = len1.length - len2.length

      // 如果差值大于 0
      if (len > 0) {
        // 第二个数字就乘以十的差值次方
        len2 = Number(len2) * Math.pow(10, Math.abs(len))
      } else {
        // 否则第一个数字就乘以十的差值次方
        len1 = Number(len1) * Math.pow(10, Math.abs(len))
      }

      if (len1 > len2) {
        // 如果第一个数比第二个数大，返回 1
        return 1
      } else if (len1 < len2) {
        // 如果第一个数比第二个数小，返回 -1
        return -1
      } else {
        // 否则返回 0
        return 0
      } 
}

因为没做判断，导致传入别的值会报错，不过在传参正确的状况下如同没什么故障。

而后今早咱们又争执了一番：

我是这么想的，他这个办法无论第一位是否雷同，都是要循环整个数组的。

而我的只有第一位不一样霎时就能得出后果，而后还说我的算法复杂度是 O(n)，我就想不明确了一个 for 循环遍历数组怎么就成 O(n)了，咱们程序里循环遍历数组多广泛的一件事啊，都成 O(n)了？

而且如果不算后期判断传入的参数是否为数组中的类型的话，我只循环了一次数组，他这个循环两个数组，我说他必定不服，那咱们用数据谈话：

首先在办法的第一行就退出一个console.time(‘ 运行时长：’)，而后再在返回值之前退出console.timeEnd(‘ 运行时长：’)。

这是一个比拟不便的测试程序运行时长的一种形式，留神 console.time() 和 console.timeEnd() 外面的参数肯定要截然不同才管用，大家能够去试试。

我的代码：

function comparison (version1, version2) {console.time('运行时长：')
  // 参数的类型
  const types = ['string', 'number']

  // 第一个参数的类型
  const type1 = typeof version1

  // 第二个参数的类型
  const type2 = typeof version2
  
  // 参数不是字符串或数字的状况下返回 0
  if (!types.includes(type1) || !types.includes(type2)) return 0

  // 如果 version1 是 number 就将其转成字符串
  const ver1 = type1 === 'number' ? version1.toString() : version1

  // 如果 version2 是 number 就将其转成字符串
  const ver2 = type2 == 'number' ? version2.toString() : version2

  // 将 version1 变成数组
  const versionArr1 = ver1.split('.')

  // 将 version2 变成数组
  const versionArr2 = ver2.split('.')

  // 获取长度最长的数组的 length
  const len = Math.max(versionArr1.length, versionArr2.length)

  // 循环比照版本号，如果前一位比拟不出大小就持续向后比照
  for (let i = 0; i < len; i++) {
    // 如果长度不统一将主动补 0 同时将字符串转为数字
    const version1 = Number(versionArr1[i]) || 0
    const version2 = Number(versionArr2[i]) || 0

    if (version1 > version2) {console.timeEnd('运行时长：')  
      // 如果 version1 大就返回 1
      return 1
    } else if (version1 < version2) {console.timeEnd('运行时长：')
      // 如果 version2 大就返回 -1
      return -1
    } else {
      // 如果比拟到最初就返回 0，否则持续比拟
      if (i + 1 === len) {console.timeEnd('运行时长：')
        return 0
      } else {continue}
    }
  }
}

他的代码：

function compareVersion(version1, version2) {console.time('运行时长：')  
      // 将传进的版本号切割为数组
      const ver1 = version1.split('.')
      const ver2 = version2.split('.')

      // 将数组相加两头补 0 最初变成一个数字(字符串)
      let len1 = ver1.reduce((sum, item) => sum + '0' + item, '')
      let len2 = ver2.reduce((sum, item) => sum + '0' + item, '')

      // 得出两个数字 (字符串) 长度的差值
      const len = len1.length - len2.length

      // 如果差值大于 0
      if (len > 0) {
        // 第二个数字就乘以十的差值次方
        len2 = Number(len2) * Math.pow(10, Math.abs(len))
      } else {
        // 否则第一个数字就乘以十的差值次方
        len1 = Number(len1) * Math.pow(10, Math.abs(len))
      }

      if (len1 > len2) {console.timeEnd('运行时长：')
        // 如果第一个数比第二个数大，返回 1
        return 1
      } else if (len1 < len2) {console.timeEnd('运行时长：')
        // 如果第一个数比第二个数小，返回 -1
        return -1
      } else {console.timeEnd('运行时长：')
        // 否则返回 0
        return 0
      } 
}

测试后果：

按理说，应该是第一位就能比拟出后果，并且位数很长的一个数值，运行的差距就越显著，来试一下：

差了两倍多，不过感觉怎么没有本人设想中的差距那么显著呢？换下地位再试试：

这回差了 6 倍……嗯。

而且我感觉我多比他写的判断参数也消耗了不少工夫，懒得改了，拿一个极其的例子再试一下：

还是数倍的差距，大家怎么看呢？有没有更好的方法实现这道题呢？

正文完