按排列位数计算的最大回文数-yiteyi-C++库

给定N（非常大），任务是打印通过排列N的数字获得的最大回文数。如果无法生成回文数，则打印适当的消息。

null

例如：

Input : 313551Output : 531135Explanations : 531135 is the largest number which is a palindrome, 135531, 315513 and other numbers can also be formed but we need the highest of all of the palindromes. Input : 331Output : 313Input : 3444Output : Palindrome cannot be formed

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

天真的方法： 这个 缺乏经验的 方法将是尝试所有排列可能的话，打印出最大的这种组合，这是一个回文。

有效方法： 一个有效的方法是使用 贪婪算法。 由于数字较大，请将数字存储在字符串中。将给定数字中每个数字出现的次数存储在地图上。检查是否可以形成回文。如果给定数字的数字可以重新排列形成回文，则应用贪婪方法获得该数字。检查每个数字（9到0）是否出现，并将每个可用数字放在前面和后面。 最初，前面的指针将位于索引0处，因为最大的数字将放在第一位，使数字变大。 每走一步，将前指针向前移动1个位置。如果该数字出现奇数次，则将 中位数为一位，前后数为偶数。 .不断重复这个过程 （地图[数字]/2） 一个位数的次数。在前面和后面放置偶数次的特定数字后，将前面的指针向前移动一步。放置完成，直到map[数字]为0。在贪婪地放置完数字之后，char数组将拥有最大的回文数。在最坏的情况下，时间复杂度将是 O（10*（字符串长度/2）） ，以防数字在每个位置由相同的数字组成。以下是上述理念的实施情况：

C++

                         // CPP program to print the largest palindromic                       
                         // number by permuting digits of a number                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                                   
                         // function to check if a number can be                       
                         // permuted to form a palindrome number                       
                         bool                                     possibility(unordered_map<                                     int                                     ,                                     int                                     > m,                       
                                                 int                                     length, string s)                       
                         {                       
                                                 // counts the occurrence of number which is odd                       
                                                 int                                     countodd = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < length; i++) {                       
           
                                                 // if occurrence is odd                       
                                                 if                                     (m[s[i] -                                     '0'                                     ] & 1)                       
                                                 countodd++;                       
                                   
                                                 // if number exceeds 1                       
                                                 if                                     (countodd > 1)                       
                                                 return                                     false                                     ;                       
                                                 }                       
                                   
                                                 return                                     true                                     ;                       
                         }                       
                                   
                         // function to print the largest palindromic number                       
                         // by permuting digits of a number                       
                         void                                     largestPalindrome(string s)                       
                         {                       
                                   
                                                 // string length                       
                                                 int                                     l = s.length();                       
                                   
                                                 // map that marks the occurrence of a number                       
                                                 unordered_map<                                     int                                     ,                                     int                                     > m;                       
                                                 for                                     (                                     int                                     i = 0; i < l; i++)                       
                                                 m[s[i] -                                     '0'                                     ]++;                       
                                   
                                                 // check the possibility of a palindromic number                       
                                                 if                                     (possibility(m, l, s) ==                                     false                                     ) {                       
                                                 cout <<                                     "Palindrome cannot be formed"                                     ;                       
                                                 return                                     ;                       
                                                 }                       
                                   
                                                 // string array that stores the largest                       
                                                 // permuted palindromic number                       
                                                 char                                     largest[l];                       
                                   
                                                 // pointer of front                       
                                                 int                                     front = 0;                       
                                   
                                                 // greedily start from 9 to 0 and place the                       
                                                 // greater number in front and odd in the                       
                                                 // middle                       
                                                 for                                     (                                     int                                     i = 9; i >= 0; i--) {                       
                                   
                                                 // if the occurrence of number is odd                       
                                                 if                                     (m[i] & 1) {                       
                                   
                                                 // place one odd occurring number                       
                                                 // in the middle                       
                                                 largest[l / 2] =                                     char                                     (i + 48);                       
                                   
                                                 // decrease the count                       
                                                 m[i]--;                       
                                   
                                                 // place the rest of numbers greedily                       
                                                 while                                     (m[i] > 0) {                       
                                                 largest[front] =                                     char                                     (i + 48);                       
                                                 largest[l - front - 1] =                                     char                                     (i + 48);                       
                                                 m[i] -= 2;                       
                                                 front++;                       
                                                 }                       
                                                 }                       
                                                 else                                     {                       
           
                                                 // if all numbers occur even times,                       
                                                 // then place greedily                       
                                                 while                                     (m[i] > 0) {                       
                                   
                                                 // place greedily at front                       
                                                 largest[front] =                                     char                                     (i + 48);                       
                                                 largest[l - front - 1] =                                     char                                     (i + 48);                       
                                   
                                                 // 2 numbers are placed, so decrease the count                       
                                                 m[i] -= 2;                       
                                   
                                                 // increase placing position                       
                                                 front++;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 // print the largest string thus formed                       
                                                 for                                     (                                     int                                     i = 0; i < l; i++)                       
                                                 cout << largest[i];                       
                         }                       
                                   
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 string s =                                     "313551"                                     ;                       
                                                 largestPalindrome(s);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // JAVA program to print the                       
                         // largest palindromic number                       
                         // by permuting digits of a number                       
                         import                                     java.util.*;                       
                         class                                     GFG{                       
                                   
                         // Function to check if a number can be                       
                         // permuted to form a palindrome number                       
                         static                                     boolean                                     possibility(HashMap<Integer,                       
                                                 Integer> m,                       
                                                 int                                     length, String s)                       
                         {                       
                                                 // counts the occurrence of number                       
                                                 // which is odd                       
                                                 int                                     countodd =                                     0                                     ;                       
                                   
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < length; i++)                       
                                                 {                       
                                                 // if occurrence is odd                       
                                                 if                                     (m.get(s.charAt(i) -                                     '0'                                     ) %                                     2                                     ==                                     1                                     )                       
                                                 countodd++;                       
           
                                                 // if number exceeds 1                       
                                                 if                                     (countodd >                                     1                                     )                       
                                                 return                                     false                                     ;                       
                                                 }                       
           
                                                 return                                     true                                     ;                       
                         }                       
                                   
                         // function to print the largest                       
                         // palindromic number by permuting                       
                         // digits of a number                       
                         static                                     void                                     largestPalindrome(String s)                       
                         {                       
                                                 // String length                       
                                                 int                                     l = s.length();                       
           
                                                 // map that marks the occurrence                       
                                                 // of a number                       
                                                 HashMap<Integer,                       
                                                 Integer> m =                                     new                                     HashMap<>();                       
                                   
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < l; i++)                       
                                                 if                                     (m.containsKey(s.charAt(i) -                                     '0'                                     ))                       
                                                 m.put(s.charAt(i) -                                     '0'                                     ,                       
                                                 m.get(s.charAt(i) -                                     '0'                                     ) +                                     1                                     );                       
                                                 else                       
                                                 m.put(s.charAt(i) -                                     '0'                                     ,                                     1                                     );                       
           
                                                 // check the possibility of a                       
                                                 // palindromic number                       
                                                 if                                     (possibility(m, l, s) ==                                     false                                     )                       
                                                 {                       
                                                 System.out.print(                                     "Palindrome cannot be formed"                                     );                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // String array that stores                       
                                                 // the largest permuted                       
                                                 // palindromic number                       
                                                 char                                     []largest =                                     new                                     char                                     [l];                       
           
                                                 // pointer of front                       
                                                 int                                     front =                                     0                                     ;                       
           
                                                 // greedily start from 9 to 0                       
                                                 // and place the greater number                       
                                                 // in front and odd in the middle                       
                                                 for                                     (                                     int                                     i =                                     9                                     ; i >=                                     0                                     ; i--)                       
                                                 {                       
                                                 // if the occurrence of                       
                                                 // number is odd                       
                                                 if                                     (m.containsKey(i) &&                       
                                                 m.get(i)%                                     2                                     ==                                     1                                     )                       
                                                 {                       
                                                 // place one odd occurring                       
                                                 // number in the middle                       
                                                 largest[l /                                     2                                     ] = (                                     char                                     )(i +                                     48                                     );                       
           
                                                 // decrease the count                       
                                                 m.put(i, m.get(i)-                                     1                                     );                       
           
                                                 // place the rest of                       
                                                 // numbers greedily                       
                                                 while                                     (m.get(i) >                                     0                                     )                       
                                                 {                       
                                                 largest[front] = (                                     char                                     )(i +                                     48                                     );                       
                                                 largest[l - front -                                     1                                     ] =                       
                                                 (                                     char                                     )(i +                                     48                                     );                       
                                                 m.put(i, m.get(i) -                                     2                                     );                       
                                                 front++;                       
                                                 }                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 // if all numbers occur even                       
                                                 // times, then place greedily                       
                                                 while                                     (m.containsKey(i) &&                       
                                                 m.get(i) >                                     0                                     )                       
                                                 {                       
                                                 // place greedily at front                       
                                                 largest[front] = (                                     char                                     )(i +                                     48                                     );                       
                                                 largest[l - front -                                     1                                     ] =                       
                                                 (                                     char                                     )(i +                                     48                                     );                       
           
                                                 // 2 numbers are placed,                       
                                                 // so decrease the count                       
                                                 m.put(i, m.get(i) -                                     2                                     );                       
           
                                                 // increase placing position                       
                                                 front++;                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // print the largest String                       
                                                 // thus formed                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < l; i++)                       
                                                 System.out.print(largest[i]);                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 String s =                                     "313551"                                     ;                       
                                                 largestPalindrome(s);                       
                         }                       
                         }                       
           
                         // This code is contributed by Rajput-Ji                       

Python3

                         # Python3 program to print the largest palindromic                       
                         # number by permuting digits of a number                       
                         from                                     collections                                     import                                     defaultdict                       
           
                         # Function to check if a number can be                       
                         # permuted to form a palindrome number                       
                         def                                     possibility(m, length, s):                       
           
                                                 # counts the occurrence of                       
                                                 # number which is odd                       
                                                 countodd                                     =                                     0                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , length):                       
           
                                                 # if occurrence is odd                       
                                                 if                                     m[                                     int                                     (s[i])] &                                     1                                     :                       
                                                 countodd                                     +                                     =                                     1                       
           
                                                 # if number exceeds 1                       
                                                 if                                     countodd >                                     1                                     :                       
                                                 return                                     False                       
                                   
                                                 return                                     True                       
           
                         # Function to print the largest palindromic                       
                         # number by permuting digits of a number                       
                         def                                     largestPalindrome(s):                       
           
                                                 # string length                       
                                                 l                                     =                                     len                                     (s)                       
           
                                                 # map that marks the occurrence of a number                       
                                                 m                                     =                                     defaultdict(                                     lambda                                     :                                     0                                     )                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , l):                       
                                                 m[                                     int                                     (s[i])]                                     +                                     =                                     1                       
           
                                                 # check the possibility of a                       
                                                 # palindromic number                       
                                                 if                                     possibility(m, l, s)                                     =                                     =                                     False                                     :                       
                                                 print                                     (                                     "Palindrome cannot be formed"                                     )                       
                                                 return                       
                                   
                                                 # string array that stores the largest                       
                                                 # permuted palindromic number                       
                                                 largest                                     =                                     [                                     None                                     ]                                     *                                     l                       
           
                                                 # pointer of front                       
                                                 front                                     =                                     0                       
           
                                                 # greedily start from 9 to 0 and place the                       
                                                 # greater number in front and odd in the middle                       
                                                 for                                     i                                     in                                     range                                     (                                     9                                     ,                                     -                                     1                                     ,                                     -                                     1                                     ):                       
           
                                                 # if the occurrence of number is odd                       
                                                 if                                     m[i] &                                     1                                     :                       
           
                                                 # place one odd occurring number                       
                                                 # in the middle                       
                                                 largest[l                                     /                                     /                                     2                                     ]                                     =                                     chr                                     (i                                     +                                     48                                     )                       
           
                                                 # decrease the count                       
                                                 m[i]                                     -                                     =                                     1                       
           
                                                 # place the rest of numbers greedily                       
                                                 while                                     m[i] >                                     0                                     :                       
                                                 largest[front]                                     =                                     chr                                     (i                                     +                                     48                                     )                       
                                                 largest[l                                     -                                     front                                     -                                     1                                     ]                                     =                                     chr                                     (i                                     +                                     48                                     )                       
                                                 m[i]                                     -                                     =                                     2                       
                                                 front                                     +                                     =                                     1                       
                                   
                                                 else                                     :                       
           
                                                 # if all numbers occur even times,                       
                                                 # then place greedily                       
                                                 while                                     m[i] >                                     0                                     :                       
           
                                                 # place greedily at front                       
                                                 largest[front]                                     =                                     chr                                     (i                                     +                                     48                                     )                       
                                                 largest[l                                     -                                     front                                     -                                     1                                     ]                                     =                                     chr                                     (i                                     +                                     48                                     )                       
           
                                                 # 2 numbers are placed,                       
                                                 # so decrease the count                       
                                                 m[i]                                     -                                     =                                     2                       
           
                                                 # increase placing position                       
                                                 front                                     +                                     =                                     1                       
           
                                                 # print the largest string thus formed                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , l):                       
                                                 print                                     (largest[i], end                                     =                                     "")                       
           
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
           
                                                 s                                     =                                     "313551"                       
                                                 largestPalindrome(s)                       
                                   
                         # This code is contributed by Rituraj Jain                       

C#

                         // C# program to print the largest                       
                         // palindromic number by permuting                       
                         // digits of a number                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         class                                     GFG{                       
           
                         // Function to check if a number can be                       
                         // permuted to form a palindrome number                       
                         static                                     bool                                     possibility(Dictionary<                                     int                                     ,                                     int                                     > m,                       
                                                 int                                     length,                                     string                                     s)                       
                         {                       
                                   
                                                 // Counts the occurrence of number                       
                                                 // which is odd                       
                                                 int                                     countodd = 0;                       
                                   
                                                 for                                     (                                     int                                     i = 0; i < length; i++)                       
                                                 {                       
                                   
                                                 // If occurrence is odd                       
                                                 if                                     ((m[s[i] -                                     '0'                                     ] & 1) != 0)                       
                                                 countodd++;                       
           
                                                 // If number exceeds 1                       
                                                 if                                     (countodd > 1)                       
                                                 return                                     false                                     ;                       
                                                 }                       
                                                 return                                     true                                     ;                       
                         }                       
           
                         // Function to print the largest palindromic                       
                         // number by permuting digits of a number                       
                         static                                     void                                     largestPalindrome(                                     string                                     s)                       
                         {                       
                                   
                                                 // string length                       
                                                 int                                     l = s.Length;                       
           
                                                 // Map that marks the occurrence of a number                       
                                                 Dictionary<                                     int                                     ,                       
                                                 int                                     > m =                                     new                                     Dictionary<                                     int                                     ,                       
                                                 int                                     >();                       
                                   
                                                 for                                     (                                     int                                     i = 0; i < 10; i++)                       
                                                 m[i] = 0;                       
                                   
                                                 for                                     (                                     int                                     i = 0; i < l; i++)                       
                                                 m[s[i] -                                     '0'                                     ]++;                       
           
                                                 // Check the possibility of a                       
                                                 // palindromic number                       
                                                 if                                     (possibility(m, l, s) ==                                     false                                     )                       
                                                 {                       
                                                 Console.Write(                                     "Palindrome cannot be formed"                                     );                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // string array that stores the largest                       
                                                 // permuted palindromic number                       
                                                 char                                     []largest =                                     new                                     char                                     [l];                       
           
                                                 // Pointer of front                       
                                                 int                                     front = 0;                       
           
                                                 // Greedily start from 9 to 0 and place the                       
                                                 // greater number in front and odd in the                       
                                                 // middle                       
                                                 for                                     (                                     int                                     i = 9; i >= 0; i--)                       
                                                 {                       
                                   
                                                 // If the occurrence of number is odd                       
                                                 if                                     ((m[i] & 1) != 0)                       
                                                 {                       
                                   
                                                 // Place one odd occurring number                       
                                                 // in the middle                       
                                                 largest[l / 2] = (                                     char                                     )(i +                                     '0'                                     );                       
           
                                                 // Decrease the count                       
                                                 m[i]--;                       
           
                                                 // Place the rest of numbers greedily                       
                                                 while                                     (m[i] > 0)                       
                                                 {                       
                                                 largest[front] = (                                     char                                     )(i +                                     '0'                                     );                       
                                                 largest[l - front - 1] = (                                     char                                     )(i +                                     '0'                                     );                       
                                                 m[i] -= 2;                       
                                                 front++;                       
                                                 }                       
                                                 }                       
                                                 else                       
                                                 {                       
                                   
                                                 // If all numbers occur even times,                       
                                                 // then place greedily                       
                                                 while                                     (m[i] > 0)                       
                                                 {                       
                                   
                                                 // Place greedily at front                       
                                                 largest[front] = (                                     char                                     )(i +                                     '0'                                     );                       
                                                 largest[l - front - 1] = (                                     char                                     )(i +                                     '0'                                     );                       
           
                                                 // 2 numbers are placed, so                       
                                                 // decrease the count                       
                                                 m[i] -= 2;                       
           
                                                 // Increase placing position                       
                                                 front++;                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // Print the largest string thus formed                       
                                                 for                                     (                                     int                                     i = 0; i < l; i++)                       
                                                 {                       
                                                 Console.Write(largest[i]);                       
                                                 }                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     Main(                                     string                                     [] args)                       
                         {                       
                                                 string                                     s =                                     "313551"                                     ;                       
                                   
                                                 largestPalindrome(s);                       
                         }                       
                         }                       
           
                         // This code is contributed by rutvik_56                       

Javascript

                         <script>                       
                         // Javascript program to print the largest palindromic                       
                         // number by permuting digits of a number                       
                                   
                         // function to check if a number can be                       
                         // permuted to form a palindrome number                       
                         function                                     possibility(m,length, s)                       
                         {                       
                                                 // counts the occurrence of number which is odd                       
                                                 var                                     countodd = 0;                       
                                                 for                                     (                                     var                                     i = 0; i < length; i++) {                       
                                   
                                                 // if occurrence is odd                       
                                                 if                                     (m.get(s.charCodeAt(i) - 48) & 1)                       
                                                 countodd++;                       
                                   
                                                 // if number exceeds 1                       
                                                 if                                     (countodd > 1)                       
                                                 return                                     false                                     ;                       
                                                 }                       
                                   
                                                 return                                     true                                     ;                       
                         }                       
                                   
                         // function to print the largest palindromic number                       
                         // by permuting digits of a number                       
                         function                                     largestPalindrome(s)                       
                         {                       
                                   
                                                 // string length                       
                                                 var                                     l = s.length;                       
                                   
                                                 // map that marks the occurrence of a number                       
                                                 var                                     m =                                     new                                     Map();                       
                                                 for                                     (                                     var                                     i = 0; i < l; i++){                       
                                                 if                                     (m.has(s.charCodeAt(i) - 48))                       
                                                 m.set(s.charCodeAt(i) - 48, m.get(s.charCodeAt(i) - 48)+1);                       
                                                 else                       
                                                 m.set(s.charCodeAt(i) - 48, 1);                       
                                   
                                                 }                       
                                   
                                                 // check the possibility of a palindromic number                       
                                                 if                                     (possibility(m, l, s) ==                                     false                                     ) {                       
                                                 document.write(                                     "Palindrome cannot be formed"                                     );                       
                                                 return                                     ;                       
                                                 }                       
                                   
                                                 // string array that stores the largest                       
                                                 // permuted palindromic number                       
                                                 var                                     largest =                                     new                                     Array(l);                       
                                   
                                                 // pointer of front                       
                                                 var                                     front = 0;                       
                                   
                                                 // greedily start from 9 to 0 and place the                       
                                                 // greater number in front and odd in the                       
                                                 // middle                       
                                                 for                                     (                                     var                                     i = 9; i >= 0; i--) {                       
                                   
                                                 // if the occurrence of number is odd                       
                                                 if                                     (m.has(i) & 1) {                       
                                   
                                                 // place one odd occurring number                       
                                                 // in the middle                       
                                                 largest[Math.floor(l / 2)] = String.fromCharCode(i + 48);                       
                                   
                                                 // decrease the count                       
                                                 m.set(i, m.get(i)-1);                       
                                   
                                                 // place the rest of numbers greedily                       
                                                 while                                     (m.get(i) > 0) {                       
                                                 largest[front] = String.fromCharCode(i + 48);                       
                                                 largest[l - front - 1] = String.fromCharCode(i + 48);                       
                                                 m.set(i, m.get(i)-2);                       
                                                 front++;                       
                                                 }                       
                                                 }                       
                                                 else                                     {                       
                                   
                                                 // if all numbers occur even times,                       
                                                 // then place greedily                       
                                                 while                                     (m.get(i) > 0){                       
                                   
                                                 // place greedily at front                       
                                                 largest[front] = String.fromCharCode(i + 48);                       
                                                 largest[l - front - 1] = String.fromCharCode(i + 48);                       
                                   
                                                 // 2 numbers are placed, so decrease the count                       
                                                 m.set(i, m.get(i)-2);                       
                                   
                                                 // increase placing position                       
                                                 front++;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 // print the largest string thus formed                       
                                                 for                                     (                                     var                                     i = 0; i < l; i++)                       
                                                 document.write(largest[i]);                       
                         }                       
                         // driver code                       
                         var                                     s =                                     "313551"                                     ;                       
                         largestPalindrome(s);                       
                         // This code contributed by shubhamsingh10                       
                         </script>                       

输出：

时间复杂性： O（n），其中n是字符串的长度。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章