【数据结构与算法】(16)：求回文数(对称数)

经典算法题：求 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

三、代码演示

1. 对称数 数组反转

// 对称数 数组反转

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
}

2. 对称数 字符串前后比较

// 对称数 字符串前后比较

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
}

3. 对称数 翻转数字

// 对称数 翻转数字

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')

运行


findPalindromeNumbers1 run time： 0

---

findPalindromeNumbers2 run time： 0

---

findPalindromeNumbers3 run time： 0

---

五、算法复杂度

三种方法整体复杂度都是 O(n)，但是方法1，需要数组转换、操作都需要耗时，增加性能消耗。

---

欢迎访问：天问博客

本文作者： Tiven
发布时间： 2023-07-24
最后更新： 2023-08-01
本文标题： 【数据结构与算法】(16)：求回文数(对称数)
本文链接： https://www.tiven.cn/p/6293d6d3/
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处！