TS数据结构与算法之获取1-10000之前所有的对称数（回文数）

问题

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

思路1-使用数组反转、比较

• 数字转换为字符串，再转换为数组
• 数组 reverse, 再 join 为字符串
• 前后字符串进行对比

代码实现

/**
 * 查询1-max所有对称数（数组反转）
 */
export const findPalindromeNumbers1 = (max: number): number[] => {
  if (max <= 0) return [];

  const res = [];

  for (let i = 1; i <= max; i++) {
    const s = i.toString();
    // 反转后比较
    if (s === s.split('').reverse().join('')) {
      res.push(i);
    }
  }

  return res;
}

思路2-字符串头尾比较

• 数字转换为字符串
• 字符串头尾字符比较
• （也可以使用栈，像括号匹配，但要注意奇偶数）

代码实现

/**
 * 查询1-max所有对称数（字符串头尾比较）
 */
 export const findPalindromeNumbers2 = (max: number): number[] => {
  if (max <= 0) return [];

  const res = [];
  
  for (let i = 1; i <= max; i++) {
    const s = i.toString();
    // 字符串头尾比较
    let startIndex = 0; // 字符串开始位置
    let endIndex = s.length - 1; // 字符串结束位置
    let allEqual = true;

    while (startIndex < endIndex) {
      if (s[startIndex] !== s[endIndex]) {
        allEqual = false;
        break;
      }

      // 继续比较
      startIndex ++;
      endIndex --;
    }

    if (allEqual) {
      res.push(i);
    }
  }

  return res;
}

思路3 - 生成翻转数

• 使用 % 和 Math.floor 生成反转数
• 前后数字进行对比
• （全程操作数字，没有字符串类型）

代码实现

/**
 * 查询1-max所有对称数（翻转数字）
 */
 export const findPalindromeNumbers3 = (max: number): number[] => {
  if (max <= 0) return [];

  const res = [];
  
  for (let i = 1; i <= max; i++) {
    let n = i;
    // 存储翻转数
    let val = 0;

    // 生成翻转数 通过 %取余 获取到末端数,通过 /除法 进行降位
    while (n) {
      val = val * 10 + n % 10;
      n = Math.floor(n / 10);
    }

    if (val === i) {
      res.push(i);
    }
  }

  return res;
}

功能测试

export const findPalindromeFunctionalTest = () => {
  const res = findPalindromeNumbers3(200);
  console.log(res);
};

单元测试

/**
 * @description 查询对称数单元测试
 */
describe('查询对称数', () => {
  test('正常情况', () => {
    const res = findPalindromeNumbers3(200);
    expect(res.length).toBe(28);
  });

  test('max 小于等于 0', () => {
    const res = findPalindromeNumbers3(-1);
    expect(res).toEqual([]);
  });
});

执行 yarn jest:

PASS  tests/find-palindrome-numbers.test.ts
  查询对称数
    ✓ 正常情况 (4 ms)
    ✓ max 小于等于 0 (29 ms)

性能测试

分别使用三种方式查询100W以内所的对称数

export const findPalindromePerformanceTest = () => {
  console.time('findPalindromeNumbers1');
  findPalindromeNumbers1(100 * 10000);
  console.timeEnd('findPalindromeNumbers1');

  console.time('findPalindromeNumbers2');
  findPalindromeNumbers2(100 * 10000);
  console.timeEnd('findPalindromeNumbers2');

  console.time('findPalindromeNumbers3');
  findPalindromeNumbers3(100 * 10000);
  console.timeEnd('findPalindromeNumbers3');
}

结果：

* findPalindromeNumbers1: 631.39599609375 ms
* findPalindromeNumbers2: 49.354248046875 ms
* findPalindromeNumbers3: 37.335693359375 ms

性能分析

• 思路1 - 看似是 O(n)，但数组转换、操作都需要时间，所以慢
• 思路2 VS 思路3，操作数字更快（电脑原型就是计算器）
• 思路2要用栈，不合适。因为栈也一般用数组实现，会慢

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