给定一个非负回文数 号码 包含 N 位数。问题是对数字应用最多两个交换操作 号码 所以结果是最大可能的回文数。 例如：
null
Input : 4697557964Output : 9647557469In, 4697557964 the highlighted digits wereswapped to get the largest palindromic number 9647557469.Input : 54345Output : 54345No swapping of digits required.
方法： 如果n<3，那么 号码 它本身就是最大的回文数。否则计算 中间 =（n/2）–1。然后创建一个数组 rightMax[] 大小 （中期+1） . rightMax[i] 包含位于列表右侧的最大数字的索引 num[i] 也比 num[i] 0<=i<=mid。如果不存在这样的数字，则 rightMax[i] = -1. 现在，穿过 rightMax[] 从i=0到m进行数组，并找到第一个具有rightMax[i]！=-1.执行以下操作： 交换（num[i]，num[rightMax[i]] 和 交换（num[n–i–1]，num[n–rightMax[i]–1]） 手术和休息。
C++
// C++ implementation to form the largest palindromic // number using atmost two swaps #include <bits/stdc++.h> using namespace std; // function to form the largest palindromic // number using atmost two swaps void largestPalin( char num[], int n) { // if length of number is less than '3' // then no higher palindromic number // can be formed if (n <= 3) return ; // find the index of last digit // in the 1st half of 'num' int mid = n / 2 - 1; int rightMax[mid + 1], right; // as only the first half of 'num[]' is // being considered, therefore // for the rightmost digit in the first half // of 'num[]', there will be no greater right digit rightMax[mid] = -1; // index of the greatest right digit till the // current index from the right direction right = mid; // traverse the array from second right element // in the first half of 'num[]' up to the // left element for ( int i = mid - 1; i >= 0; i--) { // if 'num[i]' is less than the greatest digit // encountered so far if (num[i] < num[right]) rightMax[i] = right; else { // there is no greater right digit // for 'num[i]' rightMax[i] = -1; // update 'right' index right = i; } } // traverse the 'rightMax[]' array from left to right for ( int i = 0; i <= mid; i++) { // if for the current digit, greater right digit exists // then swap it with its greater right digit and also // perform the required swap operation in the right halft // of 'num[]' to maintain palindromic property, then break if (rightMax[i] != -1) { // performing the required swap operations swap(num[i], num[rightMax[i]]); swap(num[n - i - 1], num[n - rightMax[i] - 1]); break ; } } } // Driver program to test above int main() { char num[] = "4697557964" ; int n = strlen (num); largestPalin(num, n); // required largest palindromic number cout << "Largest Palindrome: " << num; return 0; } |
JAVA
// Java implementation to form the largest palindromic // number using atmost two swaps class GFG { // function to form the largest palindromic // number using atmost two swaps static void largestPalin( char num[], int n) { // if length of number is less than '3' // then no higher palindromic number // can be formed if (n <= 3 ) return ; // find the index of last digit // in the 1st half of 'num' int mid = n / 2 - 1 ; int []rightMax = new int [mid + 1 ]; int right; // as only the first half of 'num[]' is // being considered, therefore // for the rightmost digit in the first half // of 'num[]', there will be no greater right digit rightMax[mid] = - 1 ; // index of the greatest right digit till the // current index from the right direction right = mid; // traverse the array from second right element // in the first half of 'num[]' up to the // left element for ( int i = mid - 1 ; i >= 0 ; i--) { // if 'num[i]' is less than the greatest digit // encountered so far if (num[i] < num[right]) rightMax[i] = right; else { // there is no greater right digit // for 'num[i]' rightMax[i] = - 1 ; // update 'right' index right = i; } } // traverse the 'rightMax[]' array from left to right for ( int i = 0 ; i <= mid; i++) { // if for the current digit, greater right digit exists // then swap it with its greater right digit and also // perform the required swap operation in the right halft // of 'num[]' to maintain palindromic property, then break if (rightMax[i] != - 1 ) { // performing the required swap operations swap(num,i, rightMax[i]); swap(num,n - i - 1 , n - rightMax[i] - 1 ); break ; } } } static char [] swap( char []arr, int i, int j) { char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } // Driver code public static void main(String[] args) { char num[] = "4697557964" .toCharArray(); int n = num.length; largestPalin(num, n); // required largest palindromic number System.out.println( "Largest Palindrome: " + String.valueOf(num)); } } // This code has been contributed by 29AjayKumar |
Python 3
# Python implementation to form the largest # palindromic number using atmost two swaps # function to form the largest palindromic # number using atmost two swaps def largestPalin(num, n): # if length of number is less than '3' # then no higher palindromic number # can be formed if n < = 3 : return # find the index of last digit # in the 1st half of 'num' mid = n / / 2 + 1 rightMax = [ 0 ] * (mid + 1 ) # as only the first half of 'num[]' is # being considered, therefore # for the rightmost digit in the first half # of 'num[]', there will be no greater right digit rightMax[mid] = - 1 # index of the greatest right digit till the # current index from the right direction right = mid # traverse the array from second right element # in the first half of 'num[]' up to the # left element for i in range (mid - 1 , - 1 , - 1 ): # if 'num[i]' is less than the greatest digit # encountered so far if num[i] < num[right]: rightMax[i] = right else : # there is no greater right digit # for 'num[i]' rightMax[i] = - 1 # update 'right' index right = i # traverse the 'rightMax[]' array from left to right for i in range (mid + 1 ): # if for the current digit, greater right digit exists # then swap it with its greater right digit and also # perform the required swap operation in the right halft # of 'num[]' to maintain palindromic property, then break if rightMax[i] ! = - 1 : # performing the required swap operations num[i], num[rightMax[i]] = num[rightMax[i]], num[i] num[n - i - 1 ], num[n - rightMax[i] - 1 ] = num[n - rightMax[i] - 1 ], num[n - i - 1 ] break # Driver Code if __name__ = = "__main__" : num = "4697557964" n = len (num) # Required as string object do not # support item assignment num = list (num) largestPalin(num, n) # making string again from list num = ''.join(num) print ( "Largest Palindrome: " ,num) # This code is contributed by # sanjeev2552 |
C#
// C# implementation to form the largest // palindromic number using atmost two swaps using System; class GFG { // function to form the largest palindromic // number using atmost two swaps static void largestPalin( char []num, int n) { // if length of number is less than '3' // then no higher palindromic number // can be formed if (n <= 3) return ; // find the index of last digit // in the 1st half of 'num' int mid = n / 2 - 1; int []rightMax = new int [mid + 1]; int right; // as only the first half of 'num[]' is // being considered, therefore // for the rightmost digit in the first half // of 'num[]', there will be no greater right digit rightMax[mid] = -1; // index of the greatest right digit till the // current index from the right direction right = mid; // traverse the array from second right element // in the first half of 'num[]' up to the // left element for ( int i = mid - 1; i >= 0; i--) { // if 'num[i]' is less than the greatest // digit encountered so far if (num[i] < num[right]) rightMax[i] = right; else { // there is no greater right digit // for 'num[i]' rightMax[i] = -1; // update 'right' index right = i; } } // traverse the 'rightMax[]' array // from left to right for ( int i = 0; i <= mid; i++) { // if for the current digit, greater right // digit exists then swap it with its greater // right digit and also perform the required // swap operation in the right half of 'num[]' // to maintain palindromic property, then break if (rightMax[i] != -1) { // performing the required swap operations swap(num, i, rightMax[i]); swap(num, n - i - 1, n - rightMax[i] - 1); break ; } } } static char [] swap( char []arr, int i, int j) { char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } // Driver code public static void Main(String[] args) { char []num = "4697557964" .ToCharArray(); int n = num.Length; largestPalin(num, n); // required largest palindromic number Console.WriteLine( "Largest Palindrome: " + String.Join( "" , num)); } } // This code contributed by Rajput-Ji |
Javascript
<script> // JavaScript implementation to form the largest palindromic // number using atmost two swaps // function to form the largest palindromic // number using atmost two swaps function largestPalin(num,n) { // if length of number is less than '3' // then no higher palindromic number // can be formed if (n <= 3) return ; // find the index of last digit // in the 1st half of 'num' let mid = Math.floor(n / 2) - 1; let rightMax = new Array(mid + 1); let right; // as only the first half of 'num[]' is // being considered, therefore // for the rightmost digit in the first half // of 'num[]', there will be no greater right digit rightMax[mid] = -1; // index of the greatest right digit till the // current index from the right direction right = mid; // traverse the array from second right element // in the first half of 'num[]' up to the // left element for (let i = mid - 1; i >= 0; i--) { // if 'num[i]' is less than the greatest digit // encountered so far if (num[i] < num[right]) rightMax[i] = right; else { // there is no greater right digit // for 'num[i]' rightMax[i] = -1; // update 'right' index right = i; } } // traverse the 'rightMax[]' array from left to right for (let i = 0; i <= mid; i++) { // if for the current digit, greater right digit exists // then swap it with its greater right digit and also // perform the required swap operation in the right halft // of 'num[]' to maintain palindromic property, then break if (rightMax[i] != -1) { // performing the required swap operations swap(num,i, rightMax[i]); swap(num,n - i - 1, n - rightMax[i] - 1); break ; } } } function swap(arr,i,j) { let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } // Driver code let num = "4697557964" .split( "" ); let n = num.length; largestPalin(num, n); // required largest palindromic number document.write( "Largest Palindrome: " + (num).join( "" )); // This code is contributed by rag2127 </script> |
输出：
Largest Palindrome: 9647557469
时间复杂性： O（n）。 辅助空间： O（n）。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
