c# - 给定一个正整数，我的代码能有效地找出下一个回文吗？

Question

问题陈述:对于给定的正数，我必须找出紧接的下一个回文。例如:

For 808, output:818
2133, output:2222

我想知道我的代码是否高效，效率如何？这是解决问题的好方法吗？

逻辑解释:我将 i 设置到数字的最左边位置，将 j 设置到最右边的位置，我基本上是在比较这两个数字。我总是分配 num[j]=num[i]，并跟踪数字是否大于、小于或等于原始值。最后就是:j-i==1 or j==i，看这个数的位数是偶数还是奇数，看这个数是变大还是变大，再做决定相应地。

编辑:该数字的长度可达 100,000 位!...这是问题陈述的一部分，所以我试图避免使用蛮力方法。

int LeftNineIndex = 0, RightNineIndex = 0;
bool NumberLesser = false, NumberGreater = false;
string number = Console.ReadLine();
char[] num = number.ToCharArray();
int i, j, x, y;
for (i = 0, j = num.Length - 1; i <= j; i++, j--)
{
      char m;
      Int32.TryParse(num[i].ToString(),out x);
      Int32.TryParse(num[j].ToString(), out y);
      if (x > y)
      {
           NumberGreater = true;
           NumberLesser = false;
      }
      else if (x < y)
      {
           if (j - i == 1)
           {
                NumberGreater = true;
                NumberLesser = false;
                x = x + 1;
                Char.TryParse(x.ToString(), out m);
                num[i] = m;
           }
           else
           {
                NumberGreater = false;
                NumberLesser = true;
           }             
     }

     if ((j == i && NumberGreater == false) || (j - i == 1 && x == y &&  NumberGreater == false))
     {
           if (x != 9)  // if the number is 9, then i can't add 1 to it
           {
                x = x + 1;
                Char.TryParse(x.ToString(), out m);
                num[i] = m;
           }
           else
           {
                if (num.Length != 1)
                {
                    Int32.TryParse(num[LeftNineIndex].ToString(), out x);
                    Int32.TryParse(num[RightNineIndex].ToString(), out y);
                    x = x + 1;
                    Char.TryParse(x.ToString(), out m);
                    num[LeftNineIndex] = m;
                    num[RightNineIndex] = m;
                }
                else
                {
                    // user has entered just '9', in which case I've hard-coded
                    Console.WriteLine("11");
                }
           }
     }
     num[j] = num[i];
     if (x != 9)  //gives us the index of the number closest to the middle, which is not 9
     {
          LeftNineIndex = i;
          RightNineIndex = j;
     }
}
Console.WriteLine(num);

Answer 1

在常数时间内找到下一个回文相对简单:

• 将输入分成两半(如果长度为奇数，则前半部分较大)
• 现在对于下一个回文有两个候选项:
  1. 保持上半场，修复下半场
  2. 前半部分加1，后半部分固定
• 如果大于输入，则选择第一个候选者，否则选择第二个候选者。

BigInteger type 对于实现这个很有用:

这种方法的成本与输入的长度成线性关系，即它与数字的大小成对数关系。

public static BigInteger NextPalindrome(BigInteger input)
{
    string firstHalf=input.ToString().Substring(0,(input.ToString().Length+1)/2);
    string incrementedFirstHalf=(BigInteger.Parse(firstHalf)+1).ToString();
    var candidates=new List<string>();
    candidates.Add(firstHalf+new String(firstHalf.Reverse().ToArray()));
    candidates.Add(firstHalf+new String(firstHalf.Reverse().Skip(1).ToArray()));
    candidates.Add(incrementedFirstHalf+new String(incrementedFirstHalf.Reverse().ToArray()));
    candidates.Add(incrementedFirstHalf+new String(incrementedFirstHalf.Reverse().Skip(1).ToArray()));
    candidates.Add("1"+new String('0',input.ToString().Length-1)+"1");
    return candidates.Select(s=>BigInteger.Parse(s))
              .Where(i=>i>input)
              .OrderBy(i=>i)
              .First();
}

通过与 native 实现进行比较，测试可以处理所有小于 100000 的正整数。

第五种情况很容易漏掉。如果数字由所有 9 组成，增加前半部分会改变长度，如果当前长度为奇数(9，999，...)。