经典算法题:求 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')
<div> <button style='padding: 10px 20px; color: #00b1fb;' class='rotate-btn' onclick='run()'>运行</button> <br> <b>findPalindromeNumbers1 run time:</b> <span style='color: red;' class='box1-ms'>0</span> <hr> <b>findPalindromeNumbers2 run time:</b> <span style='color: red;' class='box2-ms'>0</span> <hr> <b>findPalindromeNumbers3 run time:</b> <span style='color: red;' class='box3-ms'>0</span> <hr> </div> <script> // 对称数 数组反转
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'
} </script>
五、算法复杂度
三种方法整体复杂度都是 O(n)
,但是方法1,需要数组转换、操作都需要耗时,增加性能消耗。
欢迎访问:天问博客