打印字符的排列位置，使其成为回文-yiteyi-C++库

您将获得一个长度为n的字符串s（仅小写字母）。打印它必须获取的字符串的每个字符的位置，以便形成一个回文字符串。

null

例如：

Input  : c b b a aOutput : 3 1 5 2 4To make string palindrome 'c' must be at position 3,'b' at 1 and 5, 'a' at 2 and 4.Input : a b cOutput : Not PossibleAny permutation of string cannot form palindrome.

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

其想法是创建一个向量数组（或动态大小数组），存储每个角色的所有位置。存储位置后，我们检查奇数字符的计数是否超过一个。如果是，我们返回“不可能”。否则，我们首先打印数组的前半个位置，然后打印奇数字符的一个位置（如果存在），最后打印后半个位置。

C++

                         // CPP program to print original                       
                         // positions of characters in a                       
                         // string after rearranging and                       
                         // forming a palindrome                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Maximum number of characters                       
                         const                                     int                                     MAX = 256;                       
           
                         void                                     printPalindromePos(string &str)                       
                         {                       
                                                 // Insert all positions of every                       
                                                 // character in the given string.                       
                                                 vector<                                     int                                     > pos[MAX];                       
                                                 int                                     n = str.length();                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 pos[str[i]].push_back(i+1);                       
           
                                                 /* find the number of odd elements.                       
                                                 Takes O(n) */                       
                                                 int                                     oddCount = 0;                       
                                                 char                                     oddChar;                       
                                                 for                                     (                                     int                                     i=0; i<MAX; i++) {                       
                                                 if                                     (pos[i].size() % 2 != 0) {                       
                                                 oddCount++;                       
                                                 oddChar = i;                       
                                                 }                       
                                                 }                       
           
                                                 /* A palindrome cannot contain more than 1                       
                                                 odd characters */                       
                                                 if                                     (oddCount > 1)                       
                                                 cout <<                                     "NO PALINDROME"                                     ;                       
           
                                                 /* Print positions in first half                       
                                                 of palindrome */                       
                                                 for                                     (                                     int                                     i=0; i<MAX; i++)                       
                                                 {                       
                                                 int                                     mid = pos[i].size()/2;                       
                                                 for                                     (                                     int                                     j=0; j<mid; j++)                       
                                                 cout << pos[i][j] <<                                     " "                                     ;                       
                                                 }                       
           
                                                 // Consider one instance odd character                       
                                                 if                                     (oddCount > 0)                       
                                                 {                       
                                                 int                                     last = pos[oddChar].size() - 1;                       
                                                 cout << pos[oddChar][last] <<                                     " "                                     ;                       
                                                 pos[oddChar].pop_back();                       
                                                 }                       
           
                                                 /* Print positions in second half                       
                                                 of palindrome */                       
                                                 for                                     (                                     int                                     i=MAX-1; i>=0; i--)                       
                                                 {                       
                                                 int                                     count = pos[i].size();                       
                                                 for                                     (                                     int                                     j=count/2; j<count; j++)                       
                                                 cout << pos[i][j] <<                                     " "                                     ;                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 string s =                                     "geeksgk"                                     ;                       
                                                 printPalindromePos(s);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // JAVA program to print original                       
                         // positions of characters in a                       
                         // String after rearranging and                       
                         // forming a palindrome                       
                         import                                     java.util.*;                       
           
                         class                                     GFG                       
                         {                       
           
                         // Maximum number of characters                       
                         static                                     int                                     MAX =                                     256                                     ;                       
           
                         static                                     void                                     printPalindromePos(String str)                       
                         {                       
                                                 // Insert all positions of every                       
                                                 // character in the given String.                       
                                                 Vector<Integer> []pos =                                     new                                     Vector[MAX];                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < MAX; i++)                       
                                                 pos[i] =                                     new                                     Vector<Integer>();                       
                                                 int                                     n = str.length();                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 pos[str.charAt(i)].add(i +                                     1                                     );                       
           
                                                 /* find the number of odd elements.                       
                                                 Takes O(n) */                       
                                                 int                                     oddCount =                                     0                                     ;                       
                                                 char                                     oddChar =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < MAX; i++)                       
                                                 {                       
                                                 if                                     (pos[i].size() %                                     2                                     !=                                     0                                     )                       
                                                 {                       
                                                 oddCount++;                       
                                                 oddChar = (                                     char                                     ) i;                       
                                                 }                       
                                                 }                       
           
                                                 /* A palindrome cannot contain more than 1                       
                                                 odd characters */                       
                                                 if                                     (oddCount >                                     1                                     )                       
                                                 System.out.print(                                     "NO PALINDROME"                                     );                       
           
                                                 /* Print positions in first half                       
                                                 of palindrome */                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < MAX; i++)                       
                                                 {                       
                                                 int                                     mid = pos[i].size() /                                     2                                     ;                       
                                                 for                                     (                                     int                                     j =                                     0                                     ; j < mid; j++)                       
                                                 System.out.print(pos[i].get(j) +                                     " "                                     );                       
                                                 }                       
           
                                                 // Consider one instance odd character                       
                                                 if                                     (oddCount >                                     0                                     )                       
                                                 {                       
                                                 int                                     last = pos[oddChar].size() -                                     1                                     ;                       
                                                 System.out.print(pos[oddChar].get(last) +                                     " "                                     );                       
                                                 pos[oddChar].remove(pos[oddChar].size() -                                     1                                     );                       
                                                 }                       
           
                                                 /* Print positions in second half                       
                                                 of palindrome */                       
                                                 for                                     (                                     int                                     i = MAX -                                     1                                     ; i >=                                     0                                     ; i--)                       
                                                 {                       
                                                 int                                     count = pos[i].size();                       
                                                 for                                     (                                     int                                     j = count /                                     2                                     ; j < count; j++)                       
                                                 System.out.print(pos[i].get(j) +                                     " "                                     );                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 String s =                                     "geeksgk"                                     ;                       
                                                 printPalindromePos(s);                       
                         }                       
                         }                       
           
                         // This code is contributed by 29AjayKumar                       

C#

                         // C# program to print original                       
                         // positions of characters in a                       
                         // String after rearranging and                       
                         // forming a palindrome                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         class                                     GFG                       
                         {                       
           
                         // Maximum number of characters                       
                         static                                     int                                     MAX = 256;                       
           
                         static                                     void                                     printPalindromePos(String str)                       
                         {                       
                                                 // Insert all positions of every                       
                                                 // character in the given String.                       
                                                 List<                                     int                                     > []pos =                                     new                                     List<                                     int                                     >[MAX];                       
                                                 for                                     (                                     int                                     i = 0; i < MAX; i++)                       
                                                 pos[i] =                                     new                                     List<                                     int                                     >();                       
                                                 int                                     n = str.Length;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 pos[str[i]].Add(i + 1);                       
           
                                                 /* find the number of odd elements.                       
                                                 Takes O(n) */                       
                                                 int                                     oddCount = 0;                       
                                                 char                                     oddChar = (                                     char                                     )0;                       
                                                 for                                     (                                     int                                     i = 0; i < MAX; i++)                       
                                                 {                       
                                                 if                                     (pos[i].Count % 2 != 0)                       
                                                 {                       
                                                 oddCount++;                       
                                                 oddChar = (                                     char                                     ) i;                       
                                                 }                       
                                                 }                       
           
                                                 /* A palindrome cannot contain more than 1                       
                                                 odd characters */                       
                                                 if                                     (oddCount > 1)                       
                                                 Console.Write(                                     "NO PALINDROME"                                     );                       
           
                                                 /* Print positions in first half                       
                                                 of palindrome */                       
                                                 for                                     (                                     int                                     i = 0; i < MAX; i++)                       
                                                 {                       
                                                 int                                     mid = pos[i].Count / 2;                       
                                                 for                                     (                                     int                                     j = 0; j < mid; j++)                       
                                                 Console.Write(pos[i][j] +                                     " "                                     );                       
                                                 }                       
           
                                                 // Consider one instance odd character                       
                                                 if                                     (oddCount > 0)                       
                                                 {                       
                                                 int                                     last = pos[oddChar].Count - 1;                       
                                                 Console.Write(pos[oddChar][last] +                                     " "                                     );                       
                                                 pos[oddChar].RemoveAt(pos[oddChar].Count - 1);                       
                                                 }                       
           
                                                 /* Print positions in second half                       
                                                 of palindrome */                       
                                                 for                                     (                                     int                                     i = MAX - 1; i >= 0; i--)                       
                                                 {                       
                                                 int                                     count = pos[i].Count;                       
                                                 for                                     (                                     int                                     j = count / 2; j < count; j++)                       
                                                 Console.Write(pos[i][j] +                                     " "                                     );                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     Main(String[] args)                       
                         {                       
                                                 String s =                                     "geeksgk"                                     ;                       
                                                 printPalindromePos(s);                       
                         }                       
                         }                       
           
                         // This code is contributed by 29AjayKumar                       

Javascript

                         <script>                       
           
                         // Javascript program to print original                       
                         // positions of characters in a                       
                         // string after rearranging and                       
                         // forming a palindrome                       
           
                         // Maximum number of characters                       
                         var                                     MAX = 256;                       
           
                         function                                     printPalindromePos(str)                       
                         {                       
                                                 // Insert all positions of every                       
                                                 // character in the given string.                       
                                                 var                                     pos = Array.from(Array(MAX), ()=>Array());                       
                                                 var                                     n = str.length;                       
                                                 for                                     (                                     var                                     i = 0; i < n; i++)                       
                                                 pos[str[i].charCodeAt(0)].push(i+1);                       
           
                                                 /* find the number of odd elements.                       
                                                 Takes O(n) */                       
                                                 var                                     oddCount = 0;                       
                                                 var                                     oddChar;                       
                                                 for                                     (                                     var                                     i=0; i<MAX; i++) {                       
                                                 if                                     (pos[i].length % 2 != 0) {                       
                                                 oddCount++;                       
                                                 oddChar = i;                       
                                                 }                       
                                                 }                       
           
                                                 /* A palindrome cannot contain more than 1                       
                                                 odd characters */                       
                                                 if                                     (oddCount > 1)                       
                                                 document.write(                                     "NO PALINDROME"                                     );                       
           
                                                 /* Print positions in first half                       
                                                 of palindrome */                       
                                                 for                                     (                                     var                                     i=0; i<MAX; i++)                       
                                                 {                       
                                                 var                                     mid = pos[i].length/2;                       
                                                 for                                     (                                     var                                     j=0; j<mid; j++)                       
                                                 document.write( pos[i][j] +                                     " "                                     );                       
                                                 }                       
           
                                                 // Consider one instance odd character                       
                                                 if                                     (oddCount > 0)                       
                                                 {                       
                                                 var                                     last = pos[oddChar].length - 1;                       
                                                 document.write( pos[oddChar][last] +                                     " "                                     );                       
                                                 pos[oddChar].pop();                       
                                                 }                       
           
                                                 /* Print positions in second half                       
                                                 of palindrome */                       
                                                 for                                     (                                     var                                     i=MAX-1; i>=0; i--)                       
                                                 {                       
                                                 var                                     count = pos[i].length;                       
                                                 for                                     (                                     var                                     j=count/2; j<count; j++)                       
                                                 document.write( pos[i][j] +                                     " "                                     );                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         var                                     s =                                     "geeksgk"                                     ;                       
                         printPalindromePos(s);                       
           
           
                         </script>                       

输出：

2 1 4 5 7 6 3

时间复杂性 ：O（n）

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

THE END

技术文章