经典算法题：求 0 到 max 之间所有的回文数（对称数），下面将分别用数组反转、字符串前后比较、翻转数字的思路来实现。
一、回文数
回文 是指正读反读都能读通的句子，它是古今中外都有的一种修辞方式和文字游戏，如“我为人人，人人为我”等。在数学中也有这样一类数字有这样的特征，称为回文数，也叫对称数。
例如：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,202,212,222,...
二、题目描述
给定一个正整数 max ，求 0 到 max 之间所有的回文数。
示例 1：
- 输入：
max=10
- 输出：
1,2,3,4,5,6,7,8,9
示例 2：
- 输入：
max=100
- 输出：
1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99
三、代码演示
- 对称数 数组反转
// 对称数 数组反转
function findPalindromeNumbers1(max: number): number[] {
let res: number[] = []
if (max <= 0) return res
for (let i = 1; i <= max; i++) {
const s = `${i}`
if (s === s.split('').reverse().join('')) {
res.push(i)
}
}
return res
}
- 对称数 字符串前后比较
// 对称数 字符串前后比较
function findPalindromeNumbers2(max: number): number[] {
let res: number[] = []
if (max <= 0) return res
for (let i = 1; i <= max; i++) {
const s = `${i}`
const len = s.length
// 字符串头尾比较
let flag = true
let startIndex = 0
let endIndex = len - 1
while (startIndex < endIndex) {
if (s[startIndex] !== s[endIndex]) {
flag = false
break
} else {
// 继续比较
startIndex ++
endIndex --
}
}
if (flag) res.push(i)
}
return res
}
- 对称数 翻转数字
// 对称数 翻转数字
function findPalindromeNumbers3(max: number): number[] {
let res: number[] = []
if (max <= 0) return res
for (let i = 1; i <= max; i++) {
let n = i
let rev = 0 // 存储翻转数
// 生成翻转数
while (n > 0) {
rev = rev * 10 + n % 10
n = Math.floor(n / 10)
}
if (i === rev) res.push(i)
}
return res
}
四、性能测试
console.time('findPalindromeNumbers1')
console.log(findPalindromeNumbers1(100 * 10000))
console.timeEnd('findPalindromeNumbers1')
console.time('findPalindromeNumbers2')
console.log(findPalindromeNumbers2(100 * 10000))
console.timeEnd('findPalindromeNumbers2')
console.time('findPalindromeNumbers3')
console.log(findPalindromeNumbers3(100 * 10000))
console.timeEnd('findPalindromeNumbers3')
function findPalindromeNumbers1(max) {
let res = []
if (max <= 0) return res
for (let i = 1; i <= max; i++) {
const s = `${i}`
if (s === s.split('').reverse().join('')) {
res.push(i)
}
}
return res
}
// 对称数 字符串前后比较
function findPalindromeNumbers2(max) {
let res = []
if (max <= 0) return res
for (let i = 1; i <= max; i++) {
const s = `${i}`
const len = s.length
// 字符串头尾比较
let flag = true
let startIndex = 0
let endIndex = len - 1
while (startIndex < endIndex) {
if (s[startIndex] !== s[endIndex]) {
flag = false
break
} else {
// 继续比较
startIndex ++
endIndex --
}
}
if (flag) res.push(i)
}
return res
}
// 对称数 翻转数字
function findPalindromeNumbers3(max) {
let res = []
if (max <= 0) return res
for (let i = 1; i <= max; i++) {
let n = i
let rev = 0 // 存储翻转数
// 生成翻转数
while (n > 0) {
rev = rev * 10 + n % 10
n = Math.floor(n / 10)
}
if (i === rev) res.push(i)
}
return res
}
function run() {
let s1 = performance.now()
console.log(findPalindromeNumbers1(100 * 10000))
document.querySelector('.box1-ms').innerText = performance.now() - s1 + ' ms'
let s2 = performance.now()
console.log(findPalindromeNumbers2(100 * 10000))
document.querySelector('.box2-ms').innerText = performance.now() - s2 + ' ms'
let s3 = performance.now()
console.log(findPalindromeNumbers3(100 * 10000))
document.querySelector('.box3-ms').innerText = performance.now() - s3 + ' ms'
}
五、算法复杂度
三种方法整体复杂度都是 O(n)，但是方法1，需要数组转换、操作都需要耗时，增加性能消耗。
欢迎访问：天问博客
