Wo ist der Fehler in meinem Algorithmus, um das größte Palindrom ist eine Zeichenfolge Darstellung einer Zahl?

Question

Ich versuche, das größte Palindrom zu bekommen, das durch k Ersetzungen von Ziffern in der Zeichenfolge number gebildet werden kann.

z.B.

number="3943",k=1 --> "3993" 

Aus diesem genauen Testfall I "393" und für einige Testfälle wie erhalte ich eine Störung erhalte

Unbehandelte Ausnahme: System.InvalidOperationException: Sequenz enthält keine Elemente in System.Linq. Enumerable.Last [TSource] (IEnumerable`1 Quelle) < 0x414ec920 + 0x001ab> in: 0 bei Solution.LargestPalindrome (System.String numstr, Int32 k) [0x00197] in solution.cs: 74 bei Lösung + c__AnonStorey0 . <> m__0 (System.String str) [0x00009] in solution.cs: 61

using System; 
using System.Collections.Generic; 
using System.IO; 
using System.Linq; 
class Solution 
{ 
    static bool IsPalindrome(string s) 
    { 
     // returns true or false depending on whether the string 
     // s is a palindrome 
     // e.g. "abba" --> true, "acba" --> false 
     for(int i = 0, j = s.Length - 1; i < j; ++i, --j) 
     { 
      if(s[i] != s[j]) 
       return false; 
     } 
     return true; 
    } 

    static string Replace(string s, int i, char c) 
    { 
     // returns a copy of s with the character at index i 
     // replaced by character c 
     // e.g. "george",2,"x" --> "gexrge" 
     string part1 = s.Length > 0 ? s.Substring(0, i) : string.Empty; 
     string part2 = i < (s.Length - 1) ? c.ToString() : string.Empty; 
     string part3 = (i + 1) < (s.Length - 1) ? s.Substring(i + 1, s.Length - i - 1) : string.Empty; 
     return part1 + part2 + part3; 
    } 

    static string LargestPalindrome(string numstr, int k) 
    { 
     // numstr: string representation of number 
     // k: maximum number of digit replacements allowed 

     // if no digit replacements allowed, return same string 
     if(k == 0) 
      return numstr; 

     // digrange will be {'0', '1', ..., '9'} 
     List<char> digrange = new List<char>(); 
     for(char c = '0'; c <= '9'; ++c) 
      digrange.Add(c); 

     // possibilities will be all possibilities of replacing one digit from numstr 
     // e.g. numstr="02" --> possibilities={"12","22","32",...,"92","00","01","03","09"} 
     List<string> possibilities = new List<string>();   
     for(int i = 0; i < numstr.Length; ++i) 
     {   
      foreach(char dig in digrange.Where(d => d != numstr[i])) 
      { 
       possibilities.Add(Replace(numstr,i,dig)); 
      } 
     } 

     // if k = 1, get all the strings in cumulativePossiblities that are palindromes; 
     // else, transform each into the largest palindrome formed by k - 1 character 
     // replacements of itself 
     var cumulativePossibilities = k == 1 
      ? possibilities.Where(str => IsPalindrome(str)) 
      : possibilities.Select(str => LargestPalindrome(str, k - 1)).Where(str => IsPalindrome(str)); 

     // sort cumulativePossibilities in ascending order of the integer representation 
     // of the strings 
     cumulativePossibilities.ToList().Sort((s1,s2) => { 
      Int64 i1 = Int64.Parse(s1), 
        i2 = Int64.Parse(s2); 
      return (i1 > i2) ? 1 : ((i1 == i2) ? 0 : -1); 
     }); 

     // get the last element of the now-sorted cumulativePossibilities, 
     // which will be the largest number represented by the possible strings 
     // or will be null if there are none 
     string largest = cumulativePossibilities.Last(); 

     // return the largest or "-1" if there were none 
     return largest != null ? largest : "-1"; 
    } 

    static void Main(String[] args) 
    { 
     string[] tokens_n = Console.ReadLine().Split(' '); 
     int k = Convert.ToInt32(tokens_n[1]); 
     string number = Console.ReadLine(); 
     // use brute force algorithm to find largest palindrome of the string 
     // representation of the number after k replacements of characters 
     Console.WriteLine(LargestPalindrome(number,k)); 
    } 
} 

Answer 1

Nicht sehr effiziente Methode, aber einfach zu implementieren; das Hauptmerkmal PalindromeSubstitutions (Zählen wie viele Zeichen Substitutionen verhindert Zeichenfolge aus Palindrom ist) statt IsPalindrome verwendet (nur eine Tatsache, wenn der String Palindrom oder nicht)

// How many characters should be substituted in order to 
// turn the string into palindrom 
private static int PalindromeSubstitutions(string value) { 
    if (string.IsNullOrEmpty(value)) 
    return 0; 

    int result = 0; 

    for (int i = 0; i < value.Length/2; ++i) 
    if (value[i] != value[value.Length - 1 - i]) 
     result += 1; 

    return result; 
} 

// Let's test all substrings of size Length, Length - 1, ... , 2, 1 
// until we find substring with required tolerance 
private static string BestPalindromeSubstitutions(string value, int tolerance) { 
    for (int size = value.Length; size >= 1; --size) 
    for (int start = 0; start <= value.Length - size; ++start) 
     if (PalindromeSubstitutions(value.Substring(start, size)) <= tolerance) 
     return value.Substring(start, size); 

    return ""; 
} 

private static string SubstituteToPalindrome(string value) { 
    if (string.IsNullOrEmpty(value)) 
    return value; 

    StringBuilder sb = new StringBuilder(value); 

    for (int i = 0; i < value.Length/2; ++i) 
    sb[value.Length - 1 - i] = sb[i]; 

    return sb.ToString(); 
} 

Test:

string input = "73943"; 
string best = BestPalindromeSubstitutions(input, 1); 
string report = 
    string.Format("Best palindrome {0} -> {1}", best, SubstituteToPalindrome(best)); 

Ausgabe

Best palindrome 3943 -> 3993 

Answer 2

Die pr Oblem ist ein recht einfaches Beispiel für Greedy-Algorithmus. Lassen Sie uns zuerst zählen, wie viele Permutationen (mindestens) erforderlich sind, um die Zahl in Palindrom umzuwandeln.

int req = 0; 
for(int i = 0; i <= (s.length()-1)/2; i++){ 
    if (s[i] != s[s.length()-1-i] && i != s.length()-1-i) req++; 
} 

Nun, wenn es fertig ist, lassen Sie sich durch Ziffern geht von links nach rechts noch einmal: i geht durch 0-(s.length()-1)/2 inklusive. Betrachten Sie die folgenden Fälle (hier i ist nicht der mittlere Buchstabe, dass Fall betrachten wir separat):

• s[i] == s[s.length()-i-1], ist es nicht in req gezählt wurde, also wenn k >= req + 2 und s[i] != '9', wir beide Briefe an '9' ändern, und reduzieren k von 2, req bleibt unverändert. Aber beachten Sie, dass wir garantiert, dass es genügend Operationen sicherstellen links kann diese Zahl in Palindrom gedreht werden (wenn es zunächst möglich war)
• s[i] != s[s.length()-i-1] - jetzt, wenn k == req oder einen der Buchstaben ist '9', dann gehen Sie wie folgt vor: s[i]=s[s.length()-i-1]=max({s[i], s[s.length()-i-1]}) . Reduzieren Sie sowohl k als auch req durch 1.
• Nun, wenn k > req und beide Buchstaben nicht '9' sind, ändern wir sie beide zu 9. k -= 2, req -= 1.Jetzt

wenn i = s.length()-i-1 und k > 0, ändern Sie diesen Brief s[i]-'9'.

Das Ergebnis am Ende ist, was Sie suchen.

Gesamtkomplexität ist O(n).