题目(hard)
外星文明中，异次元ABA星人的文字非常有特点，他们输出的文字翻译成地球上可见的字符串后，必定有英文字母，且正着看还是倒着看都是一样的，亦即 ：对于长度为n的字符串s，若i+j == n+1， 那么s[i] = s[j], 其中i，j均为字符串位置下标，1<=i,j<=n，且n>=3
ABA星人于是将他们的间谍信息隐藏在地球字符中，便于传递消息，请你识别以下给出的几组字符串，并判断是否隐藏有ABA星文，有则输出能够匹配到的最长ABA星文的长度m，否则输出0。
给定长度为n的字符串L，1<=n<=10000, L由大小写字母和数字组成，其中ABA星文，其星文长度3<=m<=n。若找不到匹配的ABA星文，输出0
输入格式:
L,R。例如4,1000
输出格式:
[L, R]范围内的超级回文数，例如[4, 9, 121, 484]
输入样例:
在这里给出一组输入。例如：
4,1000
输出样例:
以数组的形式打印符合条件的超级回文数，例如：
[4, 9, 121, 484]
思路
题目有个坑 [ ] 中间不能留空格。
依次生成回文数，然后判断平方数是否也回文的思路。
巧就巧在用了观察法得知，回文数中间的数只有满足0、1、2，他们的平方数才可能是超级回文数，除了特例3的平方9。
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
| var fs = require('fs');
var buf = '';
function reverse(n) {
let res = 0;
while (n > 0) {
res = 10 * res + (n % 10);
n = Math.floor(n / 10);
}
return res;
}
function isPlindrome(n) {
return n === reverse(n);
}
function findSuperPlindrome(arr) {
const [L, R] = arr.split(',');
const lb = Math.floor(Math.sqrt(Number(L)));
const rb = Math.ceil(Math.sqrt(Number(R)));
const res = lb <= 3 ? [9] : [];
const queue = [
{
x: 1,
len: 1,
},
{
x: 2,
len: 1,
},
];
while (true) {
const { x, len } = queue.shift();
const y = x * x;
if (x > rb) {
break;
}
if (x >= lb && isPlindrome(y)) {
res.push(y);
}
const n = Math.floor((len + 1) / 2);
const w = Math.pow(10, n);
const r = x % w;
const l = x - (len % 2 === 1 ? x % (w / 10) : r);
if (len % 2 === 1) {
queue.push({
x: 10 * l + r,
len: len + 1
});
} else {
for(i = 0; i <= 2; i++) {
queue.push({
x: 10 * l + w * i + r,
len: len + 1
});
}
}
};
return `[${res.sort((a, b) => a - b).join(', ')}]`;
}
process.stdin.on('readable', function () {
var chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});
process.stdin.on('end', function () {
buf.split('\n').forEach(function (line) {
if (line) {
console.log(findSuperPlindrome(line));
}
});
});
|
时间复杂度: O(n^2)。
空间复杂度: O(1)。
