第98题 获取1-10000之前所有的对称数（回文数）

• 求1-10000之间所有的对称数（回文）
• 例如：0,1,2,11,22,101,232,1221...

思路分析

• 思路1：使用数组反转比较
  • 数字转为字符串，在转为数组
  • 数组reverse，在join为字符串
  • 前后字符串进行对比
  • 看似是O(n),但数组转换、操作都需要时间，所以慢
• 思路2：字符串前后比较
  • 数字转为字符串
  • 字符串头尾字符比较
  • 思路2 vs 思路3，直接操作数字更快
• 思路3：生成翻转数
  • 使用%和Math.floor()生成翻转数
  • 前后数字进行对比
  • 全程操作数字，没有字符串类型

总结

• 尽量不要转换数据结构，尤其是数组这种有序结构
• 尽量不要用内置API，如reverse等不好识别复杂度
• 数字操作最快，其次是字符串

查询 1-max 的所有对称数（数组反转）

    /**
     * 查询 1-max 的所有对称数（数组反转）
     * @param max 最大值
     */
    function findPalindromeNumbers1(max) {
      const res = []
      if (max <= 0) return res
    
      for (let i = 1; i <= max; i++) {
        // 转换为字符串，转换为数组，再反转，比较
        const s = i.toString()
        if (s === s.split('').reverse().join('')) { // 反过来看是否和之前的一样就是回文
          res.push(i)
        }
      }
    
      return res
    }

查询 1-max 的所有对称数（字符串前后比较）

• 数字转为字符串
• 字符串头尾字符比较

    /**
     * 查询 1-max 的所有对称数（字符串前后比较）
     * @param max 最大值
     */
    function findPalindromeNumbers2(max) {
      const res = []
      if (max <= 0) return res
    
      for (let i = 1; i <= max; i++) {
        const s = i.toString()
        const length = s.length
    
        // 字符串头尾比较
        let flag = true // 标志字符串是否是回文
        let startIndex = 0 // 字符串开始
        let endIndex = length - 1 // 字符串结束
        while (startIndex < endIndex) {
          if (s[startIndex] !== s[endIndex]) { // 开始和结束不相等不是回文 跳出while循环
            flag = false
            break
          } else {
            // 继续比较，倒数第二个和第二个比较，倒数第三个和第三个比较...
            startIndex++ // 指针向后移动 ==>
            endIndex-- // 指针向前移动        <==
          }
        }
    
        if (flag) res.push(i)
      }
    
      return res
    }

查询 1-max 的所有对称数（生成翻转数）

    /**
     * 查询 1-max 的所有对称数（生成翻转数）
     * @param max 最大值
     */
    function findPalindromeNumbers3(max) {
      const res = []
      if (max <= 0) return res
    
      for (let i = 1; i <= max; i++) {
        let n = i
        let rev = 0 // 存储翻转数
        
        // 假设开始
        // i:123
        // n:123
    
        // 生成翻转数
        while (n > 0) {
          rev = rev * 10 + n % 10 // 第一轮 rev: 0*10 + 123 % 10 = 3 第二轮 rev: 3*10 + 12 % 10 = 32 第三轮 rev: 32*10 + 1 % 10 = 321
          n = Math.floor(n / 10) // 第一轮 n: 123 / 10 = 12 第二轮 n: 12 / 10 = 1 第三轮 n: 1 / 10 = 0
        }
        // 整个while循环结束后：n = 0，rev = 321
        // 此时 i = 123，rev = 321 不是回文数
        if (i === rev) res.push(i)
      }
    
      return res
    }

    // 功能测试
    console.info(findPalindromeNumbers3(200))

    // 性能测试
    
    // 查询 1-max 的所有对称数（数组反转）
    console.time('findPalindromeNumbers1')
    findPalindromeNumbers1(100 * 10000)
    console.timeEnd('findPalindromeNumbers1') // 408ms
    
    // 查询 1-max 的所有对称数（字符串前后比较）
    console.time('findPalindromeNumbers2')
    findPalindromeNumbers2(100 * 10000)
    console.timeEnd('findPalindromeNumbers2') // 53ms
    
    // 查询 1-max 的所有对称数（生成翻转数）
    console.time('findPalindromeNumbers3')
    findPalindromeNumbers3(100 * 10000)
    console.timeEnd('findPalindromeNumbers3') // 42ms