我正在研究一个问题,我需要操作大量的回文列表到一定数量的数字.这应该适用于15位数的数字.我见过的最常见的方法是迭代每个数字并检查每个数字是否为回文然后将其添加到列表中.这是我在java中的实现,它工作正常.
public class Palindrome {
public ArrayList<Long> List = new ArrayList<Long>();
public double d;
public Palindrome(double digits) {
this.d = digits;
long dig = (int)(Math.pow(10,digits));
for (long i = 1; i <= dig; i++) {
long a = i;
long b = inverse(a);
if (a == b) {
List.add(a);
}
}
public long inverse(long x){
long inv = 0;
while (x > 0) {
inv = inv * 10 + x % 10;
x = x / 10;
}
return inv;
}
}
唯一的问题是,当我达到10位以上的回文时,它会非常缓慢.我一直在考虑创建这个列表的其他方法,我已经考虑过生成回文列表而不是遍历每个数字并检查它是否是回文.
我还在纸上工作,但模式不像我想的那样明显我会发现变成伪代码.我正在研究n个数字,从i到n,如果数字是偶数,则生成从1到[10 ^(i/2 + 1) - 1]的数字.然后将每个数字的反向追加到自身.有点坚持如何为奇数位做.这就是我现在所处的位置.
如果我想出来并实现代码,我将回过头来回答我的问题,但与此同时,我想知道是否有人之前已经这样做了,或者有一种我忽略的替代方法会更有效率.
UPDATE
因此,我确实设法通过你的所有建议来解决问题.我决定使用数字作为字符串,但与我的意图相反,这实际上增加了运行时:/
public class Palindrome2 {
public ArrayList<Long> List = new ArrayList<Long>();
public double d;
public Palindrome2(double digits) {
this.d = digits;
for (long n = 1; n <= d; n++) {
if (n == 1) {
for (long i = 1; i < 10; i++) {
List.add(i);
}
}
if (n % 2 != 0 && n != 1) {
long max = (long) Math.pow(10, (n + 1) / 2);
long min = (long) Math.pow(10, Math.floor(n / 2));
for (long i = min; i < max; i++) {
String str = Long.toString(i);
str = str + removeFirst(reverse(str));
Long x = Long.parseLong(str);
List.add(x);
}
} else if (n % 2 == 0) {
long max = (long) (Math.pow(10, Math.floor((n + 1) / 2)) - 1);
long min = (long) Math.pow(10, (n / 2) - 1);
for (long i = min; i <= max; i++) {
String str = Long.toString(i);
str = str + reverse(str);
Long x = Long.parseLong(str);
List.add(x);
}
}
}
}
public String reverse(String x) {
String rev = new StringBuffer(x).reverse().toString();
return rev;
}
public String removeFirst(String x) {
return x.substring(1);
}
}
再次,准确但仍然缓慢:(
在开始开发之前，您需要粗略地分析算法的常规模式，这将节省大量时间，例如：
each 1 digit is 1 palindrome, e.g: 1
each 2 digits has 1 palindrome, e.g: 11.
each 3 digits has 10 palindromes, e.g: 101,111,...,191.
each 4 digits has 10 palindromes, e.g: 1001, 1111, ..., 1991.
each 5 digits has 100 palindromes, e.g: 10001, 11011, ..., 19091, ..., 19991.
each 6 digits has 100 palindromes, e.g: 100001, 110011, ..., 190091, ..., 199991.
each 7 digits has 1000 palindromes, e.g: 1000001, ...,1900091,...,1090901, ..., 1999991.
each 8 digits has 1000 palindromes, e.g: 10000001, ...,19000091,...,10900901, ..., 19999991.
....
那么你可以编写一些排列算法来实现这一点。
但我可以告诉你这个实现可以进一步优化，如果你使用缓存来保存从低位数字生成的回文palindromes(2)，那么任何高位数字都palindromes(n>2)可以重用它。
也许它并不健壮，但它通过了我在github上的所有测试。我把剩下的工作和优化留给了你，我希望你能自己完成。
private static List<Integer> palindromes(int digits) {
return palindromes(digits, 0);
}
private static List<Integer> palindromes(int digits, int shifts) {
List<Integer> result = new ArrayList<>();
int radix = (int) Math.pow(10, digits - 1);
int renaming = digits - 2;
boolean hasRenaming = renaming > 0;
for (int i = start(digits, shifts); i <= 9; i++) {
int high = i * radix;
int low = low(digits, i);
if (hasRenaming) {
for (Integer m : palindromes(renaming, shifts + 1)) {
int ret = high + m * 10 + low;
if (ret < 0) {
return result;
}
result.add(ret);
}
} else {
result.add(high + low);
}
}
return result;
}
private static int low(int digits, int high) {
return digits > 1 ? high : 0;
}
private static int start(int digits, int shifts) {
return digits > 1 && shifts == 0 ? 1 : 0;
}
那么你可以收集所有回文数，如下所示：
// v--- min:0, max: 2147447412, count: 121474
List<Integer> all = IntStream.rangeClosed(1, 10)
.mapToObj(PalindromeTest::palindromes)
.flatMap(List::stream)
.collect(Collectors.toList());
时间成本：
191毫秒
public class Palindromes {
private static final int[] startingNonZerosTable = {
0,// 0
0, 1,// 1 2
10, 10,//3 4
100, 100, //5 6
1000, 1000,//7 8
10000, 10000,// 9 10
100000, 100000,//11 12
1000000, 1000000,//13 14
10000000, 10000000,//15 16
100000000, 100000000,//17 18
1000000000, 1000000000//19 20
};
private static final int MAX_DIGIT = 9;
private static final int MIN_DIGIT = 0;
private static final int RADIX = MAX_DIGIT - MIN_DIGIT + 1;
private static final int LONG_MAX_DIGITS = 19;
private static volatile long[][] cache = new long[LONG_MAX_DIGITS + 1][];
// includes palindromes(0) ---^
static {
cache[0] = new long[0];
cache[1] = new long[]{0L, 1L, 2L, 3L, 4L, 5L, 6L, 7L, 8L, 9L};
cache[2] = new long[]{0L, 11L, 22L, 33L, 44L, 55L, 66L, 77L, 88L, 99L};
}
public static LongStream since1(int end) {
return between(1, end);
}
public static LongStream between(int start, int end) {
return IntStream.rangeClosed(start, end)
.mapToObj(Palindromes::of)
.flatMapToLong(identity());
}
public static LongStream of(int digits) {
return Arrays.stream(palindromes0(digits))
.skip(startingNonZerosTable[digits]);
}
private final static long[] palindromes0(int digits) {
if (cache[digits] != null) {
return cache[digits];
}
long[] result = new long[sizeOf(digits)];
int size = 0;
long high = (long) Math.pow(RADIX, digits - 1);
for (int i = MIN_DIGIT; i <= MAX_DIGIT; i++) {
for (long mid : palindromes0(digits - 2)) {
long value = i * high + mid * RADIX + i;
if (value < 0) {//overflow
return cache[digits] = Arrays.copyOf(result, size);
}
result[size++] = value;
}
}
return cache[digits] = result;
}
private static int sizeOf(int digits) {
return MAX_DIGIT * (int) Math.pow(RADIX, (digits - 1) >>> 1)
+ startingNonZerosTable[digits];
}
// v--- java -Xms1024m -Xmx2048m test.algorithm.Palindromes
public static void main(String[] args) {
Duration duration = timing(() -> {
// palindromes[1..15] ---v
LongSummaryStatistics result = since1(15).summaryStatistics();
long max = result.getMax();
long count = result.getCount();
System.out.printf("Max: %d, Count: %d%n", max, count);
});
System.out.printf("Time Elapsed:%s%n", duration);
// ^--- time elapsed: 4s
}
private static Duration timing(Runnable task) {
long starts = System.currentTimeMillis();
task.run();
return Duration.ofMillis(System.currentTimeMillis() - starts);
}
}
时间成本：
回文[1..15] 已用时间：4s