我目前是C++的学生,并且我是C++的基础知识,所以如果这对您来说看起来很简单,请原谅,但我发现这是我遇到过的最困难的问题:
给出的数字n恰好是8位数字。查找通过重新排列n的所有数字获得的最大回文数。
示例:21523531 => 53211235
我知道 vector ,以及如何检查数字是否是回文数,我也知道如何从数字中删除每个数字,直到给我一个回文数,但是我不知道如何重新排列所有数字。
最佳答案
我认为后续代码会起作用:
int func(int x) // returns 0 if there is no valid palindrome
{
int arr[10]{};
while (x)
{
arr[x%10]++;
x /= 10;
}
for (int it : arr)
if (it % 2)
return 0;
int ret = 0;
for (int i = 9; i >= 0; i--)
for (int j = 0; j < arr[i]/2; j++)
ret = ret * 10 + i;
for (int i = 0; i < 10; i++)
for (int j = 0; j < arr[i]/2; j++)
ret = ret * 10 + i;
return ret;
}
这是学生更容易理解的版本:
int func(int x) // returns 0 if there is no valid palindrome
{
int arr[10] = {0,0,0,0,0,0,0,0,0,0}; // it is digits counter
while (x) // this is executed for each digit in the number
{
arr[x%10]++; // here x%10 is equal to current digit
x /= 10; // remove rightmost digit
}
for (int i = 0; i < 10; i++)
{
if (arr[i] % 2) // Every digit must be repeated 0,2,4,6 or 8 times. If it's not, then there is no valid palindrome
{
return 0;
}
}
int ret = 0; // this is our future result
// Now we just take largest digit that appears in source number and add it to the result. If it appears twice, we add it once. If it appears 4 times, we add it twice and so on.
for (int i = 9; i >= 0; i--)
{
for (int j = 0; j < arr[i]/2; j++)
{
ret = ret * 10 + i;
}
}
// Now we're doing same thing in the reverse direction.
for (int i = 0; i < 10; i++)
{
for (int j = 0; j < arr[i]/2; j++)
{
ret = ret * 10 + i;
}
}
return ret; // we're done now
}
希望您会发现此答案有用,并且可以不盲目使用它。