且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

一个更好的算法来寻找一些字符串的下一个回文

更新时间:2021-12-30 06:31:35

这似乎是一个很大的code。您是否尝试过一个非常幼稚的做法吗?检查东西是否是一个回文其实很简单。

This seems like a lot of code. Have you tried a very naive approach yet? Checking whether something is a palindrome is actually very simple.

private boolean isPalindrome(int possiblePalindrome) {
    String stringRepresentation = String.valueOf(possiblePalindrome);
    if ( stringRepresentation.equals(stringRepresentation.reverse()) ) {
       return true;
    }
}

现在可能不是最高效的code,但它给你一个非常简单的出发点:

Now that might not be the most performant code, but it gives you a really simple starting point:

private int nextLargestPalindrome(int fromNumber) {
    for ( int i = fromNumber + 1; ; i++ ) {
        if ( isPalindrome( i ) ) {
            return i;
        }
    }
}

现在,如果觉得不够快,你可以​​把它作为一个参考实现,并在降低算法复杂度的工作。

Now if that isn't fast enough you can use it as a reference implementation and work on decreasing the algorithmic complexity.

有实际上应该是一个固定时间(以及其为线性上的输入的位数)的方式找到下一个最大的回文。我给一个算法,假定的数目是偶数的位长(但可扩展到的奇数个数字)。

There should actually be a constant-time (well it is linear on the number of digits of the input) way to find the next largest palindrome. I will give an algorithm that assumes the number is an even number of digits long (but can be extended to an odd number of digits).

  1. 找到小数重新输入号码(2133)presentation。
  2. 将它分成的左半部分和右半部分(21,33);
  3. 比较在左半和右半的第一个数字的最后一位数字。
    一个。如果右边是大于的左侧,增加左和停止。 (22)
    湾如果右边是小于左侧,停止。
    C。如果右边是等于的左侧,与第二最后一位数字的左和右的第二位(依此类推)重复步骤3。
  4. 取左半部分和附加左半逆转。这就是你的下一个最大的回文。 (2222)
  1. Find the decimal representation of the input number ("2133").
  2. Split it into the left half and right half ("21", "33");
  3. Compare the last digit in the left half and the first digit in the right half.
    a. If the right is greater than the left, increment the left and stop. ("22")
    b. If the right is less than the left, stop.
    c. If the right is equal to the left, repeat step 3 with the second-last digit in the left and the second digit in the right (and so on).
  4. Take the left half and append the left half reversed. That's your next largest palindrome. ("2222")

应用到更复杂的数:

1.    1234567887654322
2.    12345678   87654322
3.    12345678   87654322
             ^   ^         equal
3.    12345678   87654322
            ^     ^        equal
3.    12345678   87654322
           ^       ^       equal
3.    12345678   87654322
          ^         ^      equal
3.    12345678   87654322
         ^           ^     equal
3.    12345678   87654322
        ^             ^    equal
3.    12345678   87654322
       ^               ^   equal
3.    12345678   87654322
      ^                 ^  greater than, so increment the left

3.    12345679

4.    1234567997654321  answer

此似乎有点类似于你所描述的算法,但它开始于内的数字,并移动到外

This seems a bit similar to the algorithm you described, but it starts at the inner digits and moves to the outer.