获取1-max所有的对称数（回文数）

发表于 更新于 分类于
获取1-max所有的对称数（回文数）

题目如下

  • 获取1-max所有的对称数（回文数）

思路如下

  • 数组反转
  • 字符串前后比较
  • 翻转数字
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/**
 * @description 对称数
 * @author sola-grj
 */

/**
 * 查询 1-max 的所有对称数（数组反转）
 * @param max 最大值
 */
export function findPalindromeNumbers1(max: number): number[] {
    const res: number[] = []
    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 的所有对称数（字符串前后比较）
 * @param max 最大值
 */
export function findPalindromeNumbers2(max: number): number[] {
    const res: number[] = []
    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]) {
                flag = false
                break
            } else {
                // 继续比较
                startIndex++
                endIndex--
            }
        }

        if (flag) res.push(i)
    }

    return res
}

/**
 * 查询 1-max 的所有对称数（翻转数字）
 * @param max 最大值
 */
export function findPalindromeNumbers3(max: number): number[] {
    const 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.info(findPalindromeNumbers3(200))

// 性能测试
console.time('findPalindromeNumbers1')
findPalindromeNumbers1(100 * 10000)
console.timeEnd('findPalindromeNumbers1') // 408ms

console.time('findPalindromeNumbers2')
findPalindromeNumbers2(100 * 10000)
console.timeEnd('findPalindromeNumbers2') // 53ms

console.time('findPalindromeNumbers3')
findPalindromeNumbers3(100 * 10000)
console.timeEnd('findPalindromeNumbers3') // 42ms

单元测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @description 对称数 test
 * @author sola-grj
 */

import { findPalindromeNumbers1, findPalindromeNumbers2, findPalindromeNumbers3 } from './palindrome-number'

describe('对称数', () => {
    it('正常情况', () => {
        const numbers = findPalindromeNumbers3(200)
        expect(numbers.length).toBe(28)
    })
    it('max 小于等于 0', () => {
        const numbers = findPalindromeNumbers3(0)
        expect(numbers).toEqual([])
    })
})