5

問題の説明：与えられた正の数について、私はすぐ次の回文を見つけなければなりません。例えば：

For 808, output:818
2133, output:2222

私のコードがまったく効率的かどうか、そしてそれはどれくらい効率的か知りたいですか？これは問題を解決するための良い方法ですか？

論理の説明：私はi数字の左端の位置に設定しj、右端の位置に基本的に2つの数字を比較しています。私は常に割り当て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);
4

2 に答える 2

6

一定時間内に次の回文を見つけるのは比較的簡単です。

  • 入力を2つに分割します（長さが奇数の場合は前半が大きくなります）
  • 次の回文には、2つの候補があります。
    1. 前半を残し、後半を修正する
    2. 前半を1ずつ増やし、後半を修正します
  • 入力よりも大きい場合は最初の候補を選択し、そうでない場合は2番目の候補を選択します。

このBigIntegerタイプは、これを実装するのに役立ちます。

このアプローチでは、入力の長さが線形になります。つまり、数値のサイズが対数になります。

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();
}

ネイティブ実装と比較することにより、100000未満のすべての正の整数で動作するようにテストされています。

5番目のケースは見逃しがちです。数値がすべて9のsで構成されている場合、前半をインクリメントすると長さが変更され、現在の長さが奇数（、、 ...）の場合は追加の処理が必要になり9ます999。

于 2012-05-11T14:11:56.970 に答える
0

これが私がやった方法です。動作しているようです。

        private int FindNextPaladindrone(int value)
    {
        int result = 0;
        bool found = false;

        while (!found)
        {
            value++;
            found = IsPalindrone(value);
            if (found)
                result = value;
        }

        return result;
    }

    private bool IsPalindrone(int number)
    {
        string numberString = number.ToString();
        int backIndex;

        bool same = true;
        for (int i = 0; i < numberString.Length; i++)
        {
            backIndex = numberString.Length - (i + 1);
            if (i == backIndex || backIndex < i)
                break;
            else
            {
                if (numberString[i] != numberString[backIndex])
                {
                    same = false;
                    break;
                }
            }
        }
        return same;
    }
于 2012-05-11T13:57:42.333 に答える