问题
- 求 1-10000 之间的所有对称数（回文）
- 如：1，2，11，22，101，232，1221...
思路1-使用数组反转、比较
- 数字转换为字符串，再转换为数组
- 数组 reverse, 再 join 为字符串
- 前后字符串进行对比
代码实现
/**
* 查询1-max所有对称数（数组反转）
*/
export const findPalindromeNumbers1 = (max: number): number[] => {
if (max <= 0) return [];
const res = [];
for (let i = 1; i <= max; i++) {
const s = i.toString();
// 反转后比较
if (s === s.split('').reverse().join('')) {
res.push(i);
}
}
return res;
}
思路2-字符串头尾比较
- 数字转换为字符串
- 字符串头尾字符比较
- （也可以使用栈，像括号匹配，但要注意奇偶数）
代码实现
/**
* 查询1-max所有对称数（字符串头尾比较）
*/
export const findPalindromeNumbers2 = (max: number): number[] => {
if (max <= 0) return [];
const res = [];
for (let i = 1; i <= max; i++) {
const s = i.toString();
// 字符串头尾比较
let startIndex = 0; // 字符串开始位置
let endIndex = s.length - 1; // 字符串结束位置
let allEqual = true;
while (startIndex < endIndex) {
if (s[startIndex] !== s[endIndex]) {
allEqual = false;
break;
}
// 继续比较
startIndex ++;
endIndex --;
}
if (allEqual) {
res.push(i);
}
}
return res;
}
思路3 - 生成翻转数
- 使用 % 和 Math.floor 生成反转数
- 前后数字进行对比
- （全程操作数字，没有字符串类型）
代码实现
/**
* 查询1-max所有对称数（翻转数字）
*/
export const findPalindromeNumbers3 = (max: number): number[] => {
if (max <= 0) return [];
const res = [];
for (let i = 1; i <= max; i++) {
let n = i;
// 存储翻转数
let val = 0;
// 生成翻转数 通过 %取余 获取到末端数,通过 /除法 进行降位
while (n) {
val = val * 10 + n % 10;
n = Math.floor(n / 10);
}
if (val === i) {
res.push(i);
}
}
return res;
}
功能测试
export const findPalindromeFunctionalTest = () => {
const res = findPalindromeNumbers3(200);
console.log(res);
};
单元测试
/**
* @description 查询对称数单元测试
*/
describe('查询对称数', () => {
test('正常情况', () => {
const res = findPalindromeNumbers3(200);
expect(res.length).toBe(28);
});
test('max 小于等于 0', () => {
const res = findPalindromeNumbers3(-1);
expect(res).toEqual([]);
});
});
执行 yarn jest:
PASS tests/find-palindrome-numbers.test.ts
查询对称数
✓ 正常情况 (4 ms)
✓ max 小于等于 0 (29 ms)
性能测试
分别使用三种方式查询100W以内所的对称数
export const findPalindromePerformanceTest = () => {
console.time('findPalindromeNumbers1');
findPalindromeNumbers1(100 * 10000);
console.timeEnd('findPalindromeNumbers1');
console.time('findPalindromeNumbers2');
findPalindromeNumbers2(100 * 10000);
console.timeEnd('findPalindromeNumbers2');
console.time('findPalindromeNumbers3');
findPalindromeNumbers3(100 * 10000);
console.timeEnd('findPalindromeNumbers3');
}
结果：
* findPalindromeNumbers1: 631.39599609375 ms
* findPalindromeNumbers2: 49.354248046875 ms
* findPalindromeNumbers3: 37.335693359375 ms
性能分析
- 思路1 - 看似是 O(n)，但数组转换、操作都需要时间，所以慢
- 思路2 VS 思路3，操作数字更快（电脑原型就是计算器）
- 思路2要用栈，不合适。因为栈也一般用数组实现，会慢
尽量不要转换数据结构，尤其数组这种有序结构，尽量不要用内置API，如reverse，不好识别复杂度。数字操作最快，其次是字符串。
