一、上题目
返回两个正整数范围内的回文数（对称数），如1-10000之间的所有回文数（对称数）。
何为回文数，即是对称的数字，如个位数1、2、3，或者是11、22、33、121这样的。
二、分析
从题目中分析是相当于将指定范围内的数遍历一遍，然后依次判断是否是回文数，重点就在如何判断一个数是回文数。
回文数具备对称的特点，如果将回文数翻转之后还相等，那这个数就是回文数。
三、方案一：利用split、reverse、join方法
/** * @method findPalindrome1 * @description 寻找回文数 - split、reverse、join * @param left number * @param right number * @returns number[] */ function findPalindrome1(left: number, right: number): number[] { // 存放回文数 const res: number[] = []; for (let i = left; i <= right; i++) { // 1. 将数字转为字符串 const s = i.toString(); // 2. 分割成数组，然后反转、再拼接 const revS = s.split('').reverse().join(''); // 3. 比较两个字符 if (s === revS) { res.push(i); } } // 返回结果 return res; }
功能测试：
// 调用 const res = findPalindrome1(1, 200); console.log(res); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, 131, 141, 151, 161, 171, 181, 191]
OK，没啥问题~
算法时间复杂度：
外层for循环，复杂度为O(n)O(n)O(n)，内部执行s.split('').reverse().join('')，这几个函数的时间复杂度是不确定的，但是考虑字符串分割、翻转所有元素、拼接元素，总是要大于O(n)O(n)O(n)时间复杂度的。
所以整体上的时间复杂度要 > O(n2)O(n^2)O(n2)。
方案二：字符串自身前后比较
换一种比较字符串是否是回文串的方法 - 字符串自身前后比较(双指针)
/** * @method findPalindrome2 * @description 寻找回文数 - 字符串自身前后比较 * @param left number * @param right number * @returns number[] */ function findPalindrome2(left: number, right: number): number[] { // 接收回文数 const res: number[] = []; for (let i = left; i <= right; i++) { // 1. 将数字转为字符串 const s = i.toString(); // 2. 定义是回文的标志 let isPalindrome = true; // 2. 定义指针startIndex/endIndex指向首位 let startIndex = 0; let endIndex = s.length - 1; // 只要startIndex与endIndex不想遇，则表明中间还有字符，继续向中间逼近 while (startIndex < endIndex) { // 判断首位字符是否对应 if (s[startIndex] !== s[endIndex]) { // 不对应，将标志设置为false isPalindrome = false; // 终止循环，再执行也咩有意义了 break; } // 若相等，将startIndex增加，endIndex减少，向中间逼近 startIndex++; endIndex--; } // 最终判断，是回文，放入结果 if (isPalindrome) { res.push(i); } } // 返回结果 return res; }
功能测试：
// 调用 const res2 = findPalindrome2(1, 200); console.log(res2); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, 131, 141, 151, 161, 171, 181, 191]
OK，没啥问题~
算法时间复杂度：
两层for循环，没啥说的，整体上的时间复杂度是O(n2)O(n^2)O(n2)。
方案三、反转整数
反转整数，也就是将数字还是反转成数字，不再进行字符串的转换。
我们来看下代码
/** * @method findPalindrome3 * @description 寻找回文数 - 字符串自身前后比较 * @param left number * @param right number * @returns number[] */ function findPalindrome3(left: number, right: number): number[] { // 存放回文数 const res: number[] = []; // 遍历数组 for (let i = left; i <= right; i++) { // 设置n的初始值为i let n = i; // 接收反转的结果 let rev = 0; // 循环执行 while (n > 0) { // 每次rev的值都是当前rev的值*10，在加上n对10求余数时的最后一位 rev = rev * 10 + (n % 10); // n除以10，同时向下取整 n = Math.floor(n / 10); } // 反转后相等，是回文数 if (rev === i) { res.push(i); } } // 返回结果 return res; }
功能测试：
// 调用 const res3 = findPalindrome3(1, 200); console.log(res3); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, 131, 141, 151, 161, 171, 181, 191]
也没啥问题~
算法时间复杂度：
两层循环，没啥说的，整体上的时间复杂度是O(n2)O(n^2)O(n2)。
三种方案性能对比
三种方案的时间复杂度大概都集中在O(n2)O(n^2)O(n2)上，那三种方案到底哪个更优呢？直接用事实说话！
以查询1-200W之间的所有回文数为例，进行性能测试
console.time('findPalindrome1'); findPalindrome1(1, 200 * 10000); console.timeEnd('findPalindrome1'); console.time('findPalindrome2'); findPalindrome2(1, 200 * 10000); console.timeEnd('findPalindrome2'); console.time('findPalindrome3'); findPalindrome3(1, 200 * 10000); console.timeEnd('findPalindrome3');
结果上图：
网络异常，图片无法展示
|
从结果上可以看出，
- 在方案一中使用
split、reverse、join是比较消耗性能的，远不如方案二和方案三理想；
- 方案二与方案三对比，后者略胜一筹，数字的处理在计算机中还是占优势的
综上所述，优先考虑使用方案三~
