Tiven

Tiven

博观而约取,厚积而薄发

天问的个人网站(天问博客),专注于Node.js、Vue.js、React、Vite、Npm、Nginx等大前端技术。不断学习新技术,记录日常开发问题,持续分享coding,极客开源,共同进步。生命不息,奋斗不止... [ hexo blog ]

【数据结构与算法】(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
}
  1. 对称数 字符串前后比较
// 对称数 字符串前后比较

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
}
  1. 对称数 翻转数字
// 对称数 翻转数字

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,需要数组转换、操作都需要耗时,增加性能消耗。


欢迎访问:天问博客