0

亲爱的朋友们：

  • 与字符串一样，一些数字也是回文。例如：1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, ... , 101, 111, ... ,753537, ... 等等。

  • 事情是这样的，我们需要想办法找到前 10.000 个回文数字，以便响应用户的输入。从第 1 到第 10000 个回文数开始。 例如，如果用户输入 12，则表示 1 到 10.000 之间的第 12 个回文数是多少？

  • 输入由一系列行组成，每行包含一个整数值 i (1 <= i <= 10000)。这个整数值 i 表示要写入输出的回文数的索引，其中索引 1 代表第一个回文数 (1)，索引 2 代表第二个回文数 (2)，依此类推。

前任：

输入 1 --> 输出应该是：1

输入 12 --> 输出应该是：33

输入 24 --> 输出应该是：151

    import java.util.Scanner;

    public class xth_palindrome
    {
        // Some Code may be here

        public static void main(String[] args)
        {
            @SuppressWarnings("resource")
            Scanner read = new Scanner(System.in);
            System.out.println("Enter values as much as you want. To stop Enter \"0\" ");

            int Xth;

            do
            {
                Xth = read.nextInt();

                // Some coding here 

                System.out.println(Xth + " palindromic num is " + "????");

            } while(Xth != 0);
        }
    }
  • 顺便说一句：时间限制是1秒。 考虑到这些因素解决这个问题的正确算法是什么？如果您能帮助我并在 Java 中明智地展示解决方案代码，我将不胜感激。感谢您的检查！
4

2 回答 2

0

也许不是“最好的方法”，但效果很好。

它在不到 1 秒的时间内完成工作（取决于您的硬件）。

我在这里测试过。

import java.util.Scanner;

public class HelloWorld{

     public static void main(String []args){

            Scanner read = new Scanner(System.in);
            System.out.println("Enter values as much as you want (lower than 100000).\n To stop Enter \"0\" ");

            int Xth;

            do
            {
                Xth = read.nextInt();


                // Some coding here 
                if (Xth > 100000)
                {
                    System.out.println("Type a number lower than 100000");
                    continue;
                }
                int count = 0;
                for (int i = 1; i <= 1000000000; i++)
                {
                    if (!isPalindrome(i))
                        continue;

                    count++;
                    if (count == Xth)
                    {
                        System.out.println(Xth + "th palindromic number is " + i);
                        break;
                    }
                }
                if (count != Xth)
                    System.out.println("I can't compute that!");


            } while(Xth != 0);
     }

     private static StringBuilder sb = new StringBuilder();

     private static boolean isPalindrome(int i)
     {
        sb.setLength(0);
        sb.append(i);
        return  sb.toString().equals(sb.reverse().toString());
     }
于 2014-12-04T14:02:00.393 回答
0

我们可以很快地遍历回文。注意

  1. 如果存在奇数回文 ABCBA，则下一个较大的回文将是 ABDBA，其中 D=C+1

  2. 如果存在偶数回文数 ABCCBA，则下一个较大的回文数将是 ABDDBA，其中 D=C+1

道理很简单。任何其他数字也将增加更大的 MSB，因此下一个更高的回文将在中心发生变化。

现在如果 C = 9，我们将需要增加 B 并将 C 重置为 0，使情况变为 AE0EA 和 AE00EA，其中 E=B+1。此方法易于扩展，您可以迭代回文。由于我们最多需要找到 10,000 个，因此对于迭代方法来说，一秒钟应该绰绰有余。

于 2014-12-03T22:05:35.597 回答