学校里做到了回文数的判定算法(当时用的是VB,能过就行了,但是我怎么会就这么满足呢 :twisted: )。决定使用现在最凉的JavaScript重写该算法,把自己的一些想法在这里做一个总结。

注:运行环境使用NodeJS v11.9.0

一、不成熟的想法

判断回文数嘛...戴兜的第一想法是将提供的数转换为字符串,把字符串倒置,然后和原来的比较一下不就好了,多简单的事。

JS中数组提供了reverse方法以返回一个倒序的数组,那么不难想到,字符串的倒置应该依靠数组实现。首先使用split方法将字符串分割为数组,倒置,再使用join将其拼合为字符串。那么,反转"abcd"的代码大概是这样的:

let raw = "abcd";
let rawArray = raw.split("");
let processedArray = rawArray.reverse();
processedArray.join(""); // => "dcba"

用链式写法让代码看起来优美一些:

"abcd".split("").reverse().join(""); // => "dcba"

那么,现在有一个参数x储存了需要判断的回文数,如何将这个x转换为字符串呢?

首先最简单的一种,x.toString(),效率怎么样呢?在我的设备上执行1000万次耗时618±5ms。有没有效率更高的方法呢?答案是有,通过让数值与字符串做加法运算来使其转换为字符,大概这样:""+x,执行1000万次耗时97±4ms。(这里不是本文重点,本没有必要吹毛求疵,但请允许我凑一点字数 :cry:

这已经很快了,还有没有更快的呢?这里要介绍的是JS在ES6标准中引入的一个新的字面量——模板字面量(Template literals),倘若使用使用模板字符串,我们可以让耗时缩短至80±3ms,可以这么写: `${x}`

最后, 再结合与原字符串的比较(完整代码判定100万次耗时1250±100ms,效率超低有没有),你所得到的完整代码应该是:

function isPalindrome(x) {
return `${x}` === `${x}`.split("").reverse().join("");
}

二[1]、继续深入

使用第一种方法效率不是很高,一是因为数据类型的转换消耗性能,二是因为JS的数组效率本身就不是很高。我们尝试直接对数进行判断。下面是我的第一次尝试:

function isPalindrome(x) {
    let mod = 0, result = 0, tmp=x;
    while (Math.floor(tmp / 10) != 0) {
        mod = tmp % 10;
        tmp = Math.floor(tmp / 10);
        result = result * 10 + mod;
    }
    result = result * 10 + tmp;
    return result == x;
}

每次循环将 result 的值乘以10后加上 tmp 的余数(最后1位),并将 tmp 整除10(去掉最后1位),即可完成数值的倒置,对数值 123454321 进行100万次判定耗时169±5ms,其实作为第一次的尝试结果我还是很满意的,若吹毛求疵一点,可以使用按位非操作符(~)替换取整操作,原理可以参考MDN,将 Math.floor(tmp / 10) 修改为 ~~(tmp / 10) 替换后同样运行100万次只需耗时60±3ms。

二[2]、特殊情况

第一种情况,负数。负数倒置后一定与原数不等,所以我们可以直接对负数返回false。

第二种情况,0。0作为一个一直很特殊的存在,怎么能忘了它?当一个数末位数为0时,倒置后仍与原数相等的,只有0。那么,我们能对这些情况进行特殊的判断。补充后的代码如下:

function isPalindrome(x) {
    if (x < 0 || (x != 0 && x % 10 == 0)) {
        return false; //若x为负数或x能被10整除且不为0,直接返回false
    }
    let mod = 0, result = 0, tmp=x;
    while (Math.floor(tmp / 10) != 0) {
        mod = tmp % 10;
        tmp = Math.floor(tmp / 10);
        result = result * 10 + mod;
    }
    result = result * 10 + tmp;
    return result == x;
}

这样修改后,对于一些特殊情况,可以迅速完成判断。

三[1]、还能优化?

倒置全部效率真的好低唉 :cry: 。仔细想想,有必要倒置所有数字么?只需要让首位与末尾比较,第二位与倒数第二位比较……我们要做的,就是从首位开始取一半的数字,从末尾开始取一半的数字。(也就是只倒置一半的数字)

可能会有人问,万一数字有奇数个呢?影响其实不是很大,因为若为偶数个,能直接取完;奇数个的话,中间的数字永远和自己相等,可以直接忽略。

三[2]、如何实现?

说出来你可能不信,我们只需将循环条件修改为 tmp > result 。这是因为当 tmp 小于 result 的时候,我们已经完成了一半数字的转换。为了提高效率,我们甚至可以去掉 tmpmod 辅助变量,直接操作 x ,修改完成的代码大概是下面这个样子:

function isPalindrome(x) {
    if (x < 0 || (x != 0 && x % 10 == 0)) {
        return false; //若x为负数或x能被10整除且不为0,直接返回false
    }
    let result = 0;
    while(x > result) {
        result = result * 10 + x % 10;
        x = ~~(x/10);
    }
    return x == result || x == ~~(result/10);
}

最后一句添加判断条件 x == ~~(result/10) 能让 xresult 不相等时考虑「三[1]、还能优化?」中提到的最后一种情况,忽略中间一位再次比较。最后我们100万次判定只需耗时42ms左右。


在迷失中寻找自我