最大の回文を得るためのアルゴリズムの欠陥は、数字の文字列表現です。

Question

私は文字列numberの数字の代わりにkによって形成される最大のパリンドロームを得ようとしています。

その正確なテストケースについては

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

私は"393"を取得していますし、いくつかのテストケースのために私は

未処理の例外のようなエラーを取得しています：System.InvalidOperationExceptionが：シーケンス はSystem.Linqのでは何の要素が含まれていません。 Enumerable.Last [TSOURCE] （IEnumerable`1源）< 0x414ec920 + 0x001ab>：0 Solution.LargestPalindrome（可能System.String numstr、のInt32 K） では[0x00197] solution.csで74 ソリューション+ c__AnonStorey0で。 <> m__0（可能System.String STR） [0x00009] 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

非常に効率的ではない方法が、実装が単純。 PalindromeSubstitutionsを使用している重要な特徴は、代わりのIsPalindrome（回文であることから、文字列を防ぐどのように多くの文字の置換カウント）（単に事実を文字列が回文であるかどうか）

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

テスト：

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

出力

Best palindrome 3943 -> 3993 

Answer 2

PR oblemはgreedyアルゴリズムの非常に簡単な例です。数を回文に変換するために必要な置換の数を最初に数えましょう。それが行われた後

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

さて、左から右にもう一度に桁を手放す：iは包括(s.length()-1)/2に0を通過します。 k >= req + 2とs[i] != '9'あれば、我々は'9'に、両方の文字を変更するよう

• s[i] == s[s.length()-i-1]が、それは、reqではカウントされませんし、次の例を考えてみましょう（ここでiは真ん中の文字はありませんが、その場合は、私たちは、別途検討します） kを2だけ減らすと、reqは変更されません。しかし、我々は十分な操作は（それが最初にできた場合）、その数は
• s[i] != s[s.length()-i-1]回文に変換することができますことを確認するために残っていることを保証することに注意してください - そして、次の操作を行い、今k == req場合や文字の一つが'9'です：s[i]=s[s.length()-i-1]=max({s[i], s[s.length()-i-1]}) 。 kとreqの両方を1で減らしてください。
• k > reqと両方の文字が'9'でない場合、両方を9に変更します。 k -= 2,req -= 1。i = s.length()-i-1とk > 0場合

さて、'9'にこの手紙s[i]を変更。

最後に得られる結果は、あなたが探しているものです。

合計複雑度はO(n)です。