查找1到10000之间的回文数
**问题：在1至10000之间找出所有回文数（对称数）。**
以下是三种不同的实现方法及其性能分析：
方法一：字符串反转法
将数字转换为字符串，然后通过反转字符串来判断是否为回文数。
- 将数字转换为字符串。
- 反转字符串并与其原始值进行比较。
这种方法虽然简单易懂，但由于涉及字符串的多次操作，性能较差。
方法二：字符头尾对比法
将数字转换为字符串后，逐一比较字符串首尾字符是否相同。
- 将数字转换为字符串。
- 从两端开始逐个字符进行比较，直到中间位置。
此方法避免了完整的字符串反转，因此性能优于方法一。
方法三：数学反转法
利用数学运算生成一个数字的反转形式，并与原数字进行比较。
- 使用取模和整除操作逐步构建反转后的数字。
- 最后比较原数字与反转后的数字是否相等。
这种方法仅涉及数值运算，性能最佳。
性能分析
- 方法一：由于需要多次字符串操作，时间复杂度较高。
- 方法二：虽然也是线性复杂度，但比方法一更高效。
- 方法三：纯数值运算，性能最优。
代码实现
方法一
/**
* 查找 1 到 max 范围内的所有回文数 - 字符串反转法
* @param max
* @returns 回文数数组
*/
function getSymmetricNumbers1(max: number): number[] {
const results: number[] = [];
if (max < 1) return results;
for (let num = 1; num <= max; num++) {
const str = num.toString();
const reversedStr = Array.from(str).reverse().join('');
if (str === reversedStr) {
results.push(num);
}
}
return results;
}
方法二
/**
* 查找 1 到 max 范围内的所有回文数 - 头尾字符对比法
* @param max
* @returns 回文数数组
*/
function getSymmetricNumbers2(max: number): number[] {
const results: number[] = [];
if (max < 1) return results;
for (let num = 1; num <= max; num++) {
const str = num.toString();
let isSymmetric = true;
for (let i = 0, j = str.length - 1; i < j; i++, j--) {
if (str[i] !== str[j]) {
isSymmetric = false;
break;
}
}
if (isSymmetric) {
results.push(num);
}
}
return results;
}
方法三
/**
* 查找 1 到 max 范围内的所有回文数 - 数学反转法
* @param max
* @returns 回文数数组
*/
function getSymmetricNumbers3(max: number): number[] {
const results: number[] = [];
if (max < 1) return results;
for (let num = 1; num <= max; num++) {
let original = num;
let reversed = 0;
while (original > 0) {
reversed = reversed * 10 + original % 10;
original = Math.floor(original / 10);
}
if (num === reversed) {
results.push(num);
}
}
return results;
}
测试用例
/**
* 测试回文数函数
*/
import { getSymmetricNumbers1, getSymmetricNumbers2, getSymmetricNumbers3 } from './palindrome-number';
describe('回文数测试', () => {
it('正常范围测试', () => {
expect(getSymmetricNumbers1(100)).toEqual([1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99]);
expect(getSymmetricNumbers2(100)).toEqual([1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99]);
expect(getSymmetricNumbers3(100)).toEqual([1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99]);
});
it('负数范围测试', () => {
expect(getSymmetricNumbers1(-100)).toEqual([]);
expect(getSymmetricNumbers2(-100)).toEqual([]);
expect(getSymmetricNumbers3(-100)).toEqual([]);
});
});
