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

栏目: IT技术 · 发布时间: 4年前

内容简介:下班坐地铁的时候,好友突然给我发过来一条微信:这道题是这样:

事情经过

下班坐地铁的时候,好友突然给我发过来一条微信:

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

这道题是这样:

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

咱们软件开发不是经常不是有版本号吗?

比如经典的兼容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小数计算不准确的问题,他肯定是从那获得的灵感。

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

不过他居然说我是暴力解法,我怎么觉得他那种才是暴力解法……

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

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

我的split方法

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)的这种形式来解题。

接下来咱们再来看一下我朋友的方法:

朋友的replace方法

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

经测试有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倍……嗯。

而且我感觉我多比他写的判断参数也耗费了不少时间,懒得改了,拿一个极端的例子再试一下:

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

还是数倍的差距,大家怎么看呢?有没有更好的办法实现这道题呢?


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

HTTP权威指南

HTTP权威指南

David Gourley、Brian Totty / 陈涓、赵振平 / 人民邮电出版社 / 2012-9 / 109.00元

超文本转移协议(Hypertext Transfer Protocol,HTTP)是在万维网上进行通信时所使用的协议方案。HTTP有很多应用,但最著名的是用于web浏览器和web服务器之间的双工通信。 HTTP起初是一个简单的协议,因此你可能会认为关于这个协议没有太多好 说的。但现在,你手上拿着的是却一本两磅重 的书。如果你对我们怎么会写出一本650页 的关于HTTP的书感到奇怪的话,可以去......一起来看看 《HTTP权威指南》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

SHA 加密
SHA 加密

SHA 加密工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换