回文数字

问题描述

给定一个正整数n，找出所有小于等于n的回文数字。回文数字是指正读和反读都相同的数字。

示例：

输入: 100
输出: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99]

解题思路

/**
 * 使用数组的方式翻转来判断， 虽然是O(n)的时间复杂度，但是reverse的操作会增加时间复杂度
 * @param num 
 * @returns 
 */
export function findSymmetricNumberByArray(num: number): number[] {
    const res: number[] = [];
    for (let i = 0; i < num; i++) {
       (i + "").split("").reverse().join("") === i + "" ? res.push(i) : null;
    }
    return res;
}

/**
 * 使用字符串的方式翻转来判断
 * @param num
 * @returns
 */
export function findSymmetricNumberByStrCompare(num: number): number[] {
    const res: number[] = [];
    for (let i = 0; i < num; i++) {
        const str = i + "";
        const len = str.length;
        let flag = true;
        let start = 0;
        let end = len - 1;
        while (start < end) {
            if (str[start] !== str[end]) {
                flag = false;
                break;
            }
            start++;
            end--;
        }
        if (flag) {
            res.push(i);
        }
    }
    return res;
}

/**
 * 使用数学的方式翻转来判断, 时间复杂度为O(n)。
 * @param num
 * @returns
 **/
export function findSymmetricNumberByMath(num: number): number[] {
    const res: number[] = [];
    for (let i = 0; i < num; i++) {
        let n = i;
        let rev = 0;
        while (n > 0) {
            rev = rev * 10 + n % 10;
            n = Math.floor(n / 10);
        }
        if (rev === i) {
            res.push(i);
        }
    }
    return res;
}