java 如何找出所有回文数

How to find out all palindromic numbers

提问by Joe

A palindromic numberor numeral palindrome is a "symmetrical" number like 16461, that remains the same when its digits are reversed.

甲回文数或数字回文是像16461是“对称的”数量，即保持相同时，其数字是相反的。

The term palindromic is derived from palindrome, which refers to a word like rotor that remains unchanged under reversal of its letters.

palindromic 一词来源于palindrome，指的是像转子这样在字母颠倒后保持不变的词。

The first palindromic numbers (in decimal) are:

第一个回文数（十进制）是：

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22,
33, 44, 55, 66, 77, 88, 99, 101, 111,
121, 131, 141, 151, 161, 171, 181,
191, ...

How to find out all palindromic numbers below, say, 10000?

如何找出下面的所有回文数，比如 10000？

回答by M Platvoet

Revert your reasoning. Not try to find these numbers but instead create them. You can simply take any number and mirror it (which is always even in length) and for that same number simply add 0..9 in between (for the numbers with odd length).

还原你的推理。不要试图找到这些数字，而是创建它们。您可以简单地取任何数字并将其镜像（长度始终为偶数），对于相同的数字，只需在其间添加 0..9（对于奇数长度的数字）。

回答by aioobe

Generating all palindromes up to a specific limit.

生成达到特定限制的所有回文。

public static Set<Integer> allPalindromic(int limit) {

    Set<Integer> result = new HashSet<Integer>();

    for (int i = 0; i <= 9 && i <= limit; i++)
        result.add(i);

    boolean cont = true;
    for (int i = 1; cont; i++) {
        StringBuffer rev = new StringBuffer("" + i).reverse();
        cont = false;
        for (String d : ",0,1,2,3,4,5,6,7,8,9".split(",")) {
            int n = Integer.parseInt("" + i + d + rev);
            if (n <= limit) {
                cont = true;
                result.add(n);
            }
        }
    }

    return result;
}

Testing for palindromicity

测试回文性

Using Strings

使用字符串

public static boolean isPalindromic(String s, int i, int j) {
    return j - i < 1 || s.charAt(i) == s.charAt(j) && isPalindromic(s,i+1,j-1);
}

public static boolean isPalindromic(int i) {
    String s = "" + i;
    return isPalindromic(s, 0, s.length() - 1);
}

Using integers

使用整数

public static boolean isPalindromic(int i) {
    int len = (int) Math.ceil(Math.log10(i+1));
    for (int n = 0; n < len / 2; n++)
        if ((i / (int) Math.pow(10, n)) % 10 !=
            (i / (int) Math.pow(10, len - n - 1)) % 10)
            return false;
    return true;
}

回答by Priyank Bhatnagar

There is a brute force approach, that you loop through all the numbers and check whether they are palindrome or not. To check, reverse the number and compare. Complexity should be O(n log10(n)). [ Not that log10() matters, but for sake of completeness. ]

有一种蛮力方法，您可以遍历所有数字并检查它们是否为回文。要检查，请反转数字并进行比较。复杂度应该是 O(n log10(n))。[不是 log10() 重要，而是为了完整性。]

Other one is to, generate palindromes according to number of digits. Lets say you have to generate 5 digit palindromes, they are of the form ABCBA, so just loop through 0-9 and fill all the positions. Now, if you have generate palindromes below 10^4, then generate palindromes of 1,2,3 and 4 digits.

另一种是，根据位数生成回文。假设您必须生成 5 位数的回文，它们的形式为 ABCBA，因此只需循环 0-9 并填充所有位置。现在，如果您生成了 10^4 以下的回文，则生成 1、2、3 和 4 位数的回文。

I wrote quick(and dirty) C++ codes to test the speed of both the algorithms (8 digit palindrome). Brute force : Ideone.(3.4s) Better algorithm : Ideone.(0s)

我编写了快速（和肮脏）的 C++ 代码来测试这两种算法（8 位回文）的速度。蛮力：Ideone。(3.4s) 更好的算法：Ideone。(0s)

I have removed print statements, because Ideone doesn't allow this large data in output.

我已经删除了打印语句，因为 Ideone 不允许在输出中输入这么大的数据。

On my computer the times are :

在我的电脑上，时间是：

Brute force:
real    0m7.150s
user    0m7.052s
Better algorithm:
real    0m0.024s
user    0m0.012s

I know that you have mentioned language as Java, but i don't know Java and these codes simply show you the difference between the algorithms, and you can write your own Java code.

我知道你提到的语言是 Java，但我不知道 Java，这些代码只是向你展示了算法之间的区别，你可以编写自己的 Java 代码。

PS: I have tested my code for 8 digit palindromes with brute force, can't be sure if it produces wrong for above 8 digits, though the approach used is general. Also, i would have liked to give the links to code in comments, as correct approach is already mentioned, but i don't have required privileges.

PS：我已经用蛮力测试了我的 8 位回文代码，无法确定它是否会产生 8 位以上的错误，尽管使用的方法是通用的。另外，我希望在注释中提供代码链接，因为已经提到了正确的方法，但我没有所需的特权。

回答by amit

one approach is simply iterating over all numebrs, and checking each number: is it is a palyndrome or not, something like that:

一种方法是简单地迭代所有数字，并检查每个数字：它是否是回文，类似这样：

public static boolean isPalindrome(Integer x) {
        String s = x.toString();
        int len = s.length();
        for (int i = 0;i<len;i+=2) {
            if (s.charAt(i) != s.charAt(len-i-1)) return false;
        }
        return true;
    }
public static void main(String[] args) {
        int N = 10000;
        for (Integer x = 0;x<N;x++) { 
            if (isPalindrome(x)) System.out.println(x);
        }
    } 

回答by b_erb

Brute force approach: Make a foreach loop from 1…10000 and test against the constraints. Even easier, convert the number to string, reverse it and compare it to the original value. This is inefficient and lame.

蛮力方法：从 1 到 10000 进行 foreach 循环并针对约束进行测试。更简单的是，将数字转换为字符串，将其反转并将其与原始值进行比较。这是低效和蹩脚的。

Better approach: Think about the patterns of a palindrome. Think about the different possibilities there are for palindromes, depending on the length of the number. Now provide a method that generates palindromes of the given length. (I will not do this, because it's obviously homework.)

更好的方法：想想回文的模式。考虑回文的不同可能性，这取决于数字的长度。现在提供一种生成给定长度的回文的方法。（我不会这样做，因为这显然是家庭作业。）

回答by aashima

Loops similar to the one below can be used to print palindrome numbers:

类似于下面的循环可用于打印回文数：

for(int i = 1; i <= 9; i++) {
        for(int j = 0; j <= 9; j++) {
            for(int k = 0; k <= 9; k++) {
                System.out.println("" + i + j + k + j + i);
            }
        }
    }

回答by Koustav Chatterjee

import Queue
import copy

def printPalindromesTillK(K):
    q = Queue.Queue(K);
    for i in range(0, 10):
        q.put(str(i));
        q.put(str(i) + str(i));
    while(not q.empty()):
        elem = q.get();
        print  elem;
        for i in range(1, 10):
            item = str(i) + elem + str(i);
            if int(item) <= K:
               q.put(item); 

print printPalindromesTillK(10000);

回答by user1031307

I wrote these methods in C# which may be of some help. The main method builds a definitive list of all palindromic numbers up to the given number of digits. Its fast and commented throughout to help explain the processes I have used.

我用 C# 编写了这些方法，这可能会有所帮助。主要方法建立一个确定的所有回文数列表，直到给定的位数。它的速度很快，并在整个过程中进行了评论，以帮助解释我使用的流程。

I've also included some support methods including a fast palindromic test and its worth pointing out that pow10[x] is an array of the powers of 10 to further improve speed.

我还包含了一些支持方法，包括快速回文测试，值得指出的是 pow10[x] 是 10 的幂数组，以进一步提高速度。

                    lhs *= 10;
                    rhs /= 10;
                }
                palindrome = MathExt.Concat( lhs * 10, MathExt.ReverseDigits( rhs ) );      // Multiplying the lhs by 10 is equivalent to adding b == 0
                result.Add( palindrome );       // Add numbers of the form aaa + 0 + aaa

                lhs = a;
                for ( ulong b = 1; b != 10; b++ )
                {
                    rhs = a * 10 + b; // Adding b before we reverse guarantees that there is no trailing 0s
                    palindrome = MathExt.Concat( lhs, MathExt.ReverseDigits( rhs ) );       // Works except when b == 0
                    result.Add( palindrome );       // Add numbers of the form aaa + b + aaa
                }
                a++;
            }
            pow *= 10;        // Each pass of the outer loop add an extra digit to aaa
        } 
        return (result);
    }


    /// <summary>
    ///  Reverses the digits in a number returning it as a new number. Trailing '0's will be lost.
    /// </summary>
    /// <param name="n">The number to reverse.</param>
    /// <param name="radix">The radix or base of the number to reverse.</param>
    /// <returns>The reversed number.</returns>
    static public ulong ReverseDigits( ulong n, uint radix = 10 )
    {
        // Reverse the number
        ulong result = 0;
        do
        {
            // Extract the least significant digit using standard modular arithmetric
            result *= radix;
            result += n % radix;
            n /= radix;
        } while ( n != 0 );
        return (result);
    }


/// <summary>
    /// Concaternates the specified numbers 'a' and 'b' forming a new number 'ab'.
    /// </summary>
    /// <example>If a = 1234 and b = 5678 then Concat(a,b) = 12345678.</example>
    /// <param name="a">The first number.</param>
    /// <param name="b">The second number.</param>
    /// <returns>The concaternated number 'ab'.</returns>
    public static ulong Concat( this ulong a, ulong b )
    {
        // Concaternate the two numbers by shifting 'a' to the left by the number of digits in 'b' and then adding 'b'
        return (a * pow10[NumberOfDigits( b )] + b);
    }

    /// <summary>
    /// Evaluate whether the passed integer is a palindrome in base 10 or not.
    /// </summary>
    /// <param name="n">Integer to test.</param>
    /// <returns>True - Palindrome, False - Non palindrome.</returns>
    static public bool IsPalindrome( this ulong n )
    {
        uint divisor = NumberOfDigits( n ) - 1;
        do
        {
            // Extract the most and least significant digits of (n)
            ulong msd = n / pow10[divisor];
            ulong lsd = n % 10;

            // Check they match!
            if ( msd != lsd )
                return (false);

            // Remove the msd and lsd from (n) and test the next most and least significant digits.
            n -= msd * pow10[divisor];  // Remove msd
            n /= 10;                    // Remove lsd
            divisor -= 2;               // Number has reduced in size by 2 digits 
        } while ( n != 0 );
        return (true);
    }