Czy mój kod jest skuteczny w znalezieniu następnego palindromu z dodatnią liczbą całkowitą?

Question

Opis problemu: Dla danej liczby pozytywnej muszę znaleźć natychmiast następny palindrom. Np .:

For 808, output:818 
2133, output:2222 

Chcę wiedzieć, czy mój kod jest w ogóle wydajny i jak skuteczny jest? Czy to dobry sposób na rozwiązanie problemu?

Objaśnienie logiczne: Ustawiłem i na najbardziej wysuniętą na lewo pozycję numeru, j w skrajne prawe położenie i zasadniczo porównuję 2 liczby. Zawsze przypisuję num[j]=num[i] i śledzę, czy liczba jest większa od wartości początkowej, czy mniejsza, lub równa. W końcu to jest: j-i==1 or j==i, w zależności od liczby cyfr liczby równej lub nieparzystej, widzę, czy liczba stała się większa, czy nie, podejmując decyzję odpowiednio.

EDYCJA: Liczba może wynosić do 100 000 cyfr! ... To była część opisu problemu, więc staram się unikać metod brutalnej siły.

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

To stosunkowo proste do znalezienia następnego palindrom w stałym czasie:

• Podział wejście na dwie połowy (pierwsza połowa większych jeśli długość jest nieparzysta)
• Teraz na następny palindromu istnieją dwóch kandydatów:
  1. Przechowywać w pierwszej połowie, a druga połowa naprawić
  2. przyrost pierwszą połowę o 1, i naprawić drugą połowę
• Wybierz pierwszego kandydata, jeśli jest większy niż dane wejściowe, w przeciwnym razie wybierz drugiego kandydata.

typu BigInteger jest przydatna do realizacji tego:

To podejście ma liniową kosztów w odniesieniu do długości wkładu, to znaczy znajduje się w logarytmicznej wielkości numeru.

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

Testowane do pracy ze wszystkimi dodatnimi liczbami całkowitymi poniżej 100000 przez porównanie z natywną implementacją.

Piąty przypadek można łatwo przeoczyć. Jeśli liczba składa się ze wszystkich 9 s, inkrementowanie pierwszej połowy powoduje zmianę długości i wymaga dodatkowej obsługi, jeśli bieżąca długość jest nieparzysta (9, 999, ...).

Answer 2

Tak to zrobiłem. Wydaje się działać.

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