問題
- 求 1-10000 之間的所有對稱數(shù)（回文）
- 如：1，2段多，11首量，22，101进苍，232加缘，1221...
思路1-使用數(shù)組反轉(zhuǎn)、比較
- 數(shù)字轉(zhuǎn)換為字符串觉啊，再轉(zhuǎn)換為數(shù)組
- 數(shù)組 reverse, 再 join 為字符串
- 前后字符串進行對比
代碼實現(xiàn)
/**
* 查詢1-max所有對稱數(shù)（數(shù)組反轉(zhuǎn)）
*/
export const findPalindromeNumbers1 = (max: number): number[] => {
if (max <= 0) return [];
const res = [];
for (let i = 1; i <= max; i++) {
const s = i.toString();
// 反轉(zhuǎn)后比較
if (s === s.split('').reverse().join('')) {
res.push(i);
}
}
return res;
}
思路2-字符串頭尾比較
- 數(shù)字轉(zhuǎn)換為字符串
- 字符串頭尾字符比較
- （也可以使用棧生百，像括號匹配，但要注意奇偶數(shù)）
代碼實現(xiàn)
/**
* 查詢1-max所有對稱數(shù)（字符串頭尾比較）
*/
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; // 字符串結(jié)束位置
let allEqual = true;
while (startIndex < endIndex) {
if (s[startIndex] !== s[endIndex]) {
allEqual = false;
break;
}
// 繼續(xù)比較
startIndex ++;
endIndex --;
}
if (allEqual) {
res.push(i);
}
}
return res;
}
思路3 - 生成翻轉(zhuǎn)數(shù)
- 使用 % 和 Math.floor 生成反轉(zhuǎn)數(shù)
- 前后數(shù)字進行對比
- （全程操作數(shù)字柄延，沒有字符串類型）
代碼實現(xiàn)
/**
* 查詢1-max所有對稱數(shù)（翻轉(zhuǎn)數(shù)字）
*/
export const findPalindromeNumbers3 = (max: number): number[] => {
if (max <= 0) return [];
const res = [];
for (let i = 1; i <= max; i++) {
let n = i;
// 存儲翻轉(zhuǎn)數(shù)
let val = 0;
// 生成翻轉(zhuǎn)數(shù) 通過 %取余 獲取到末端數(shù),通過 /除法 進行降位
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 查詢對稱數(shù)單元測試
*/
describe('查詢對稱數(shù)', () => {
test('正常情況', () => {
const res = findPalindromeNumbers3(200);
expect(res.length).toBe(28);
});
test('max 小于等于 0', () => {
const res = findPalindromeNumbers3(-1);
expect(res).toEqual([]);
});
});
執(zhí)行 yarn jest:
PASS tests/find-palindrome-numbers.test.ts
查詢對稱數(shù)
? 正常情況 (4 ms)
? max 小于等于 0 (29 ms)
性能測試
分別使用三種方式查詢100W以內(nèi)所的對稱數(shù)
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');
}
結(jié)果：
* findPalindromeNumbers1: 631.39599609375 ms
* findPalindromeNumbers2: 49.354248046875 ms
* findPalindromeNumbers3: 37.335693359375 ms
性能分析
- 思路1 - 看似是 O(n)蚀浆，但數(shù)組轉(zhuǎn)換、操作都需要時間搜吧，所以慢
- 思路2 VS 思路3市俊，操作數(shù)字更快（電腦原型就是計算器）
- 思路2要用棧，不合適滤奈。因為棧也一般用數(shù)組實現(xiàn)摆昧，會慢
盡量不要轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)，尤其數(shù)組這種有序結(jié)構(gòu)蜒程，盡量不要用內(nèi)置API绅你，如reverse，不好識別復(fù)雜度昭躺。數(shù)字操作最快忌锯，其次是字符串。
