入门力扣自学笔记4 C++ （题目编号479）_C

479. 最大回文数乘积

题目：

给定一个整数 n ，返回可表示为两个 n 位整数乘积的最大回文整数。

因为答案可能非常大，所以返回它对 1337 取余。

示例 1:

输入：n = 2
输出：987
解释：99 x 91 = 9009, 9009 % 1337 = 987

示例 2:

输入： n = 1
输出： 9

提示:

1 <= n <= 8

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-palindrome-product
著作权归领扣网络所有。

商业转载请联系官方授权，非商业转载请注明出处。

思路：

首先，当n为1的时候，最大为9。

（简单的特殊情况，要先列出来）

其次，当n为其他数的时候，n位的最大数是10ⁿ-1，而且两个n位数相乘的最大值为2n位的一个数，那么我们将从10ⁿ-1开始，列举回文串。

列举过程：先定一个一个字符串left，将这个数放进字符串中，这个就是回文串的左边，右边利用字符串left反向导入即可。

将这些列举好的字符串放进一个新的字符串中total，方便后序直接转换成数字进行检验。

最后，从n位的最大数开始，利用n*n>=num，进行循环，查找是否num和c取余等于0，如果等于0，那么这个数肯定是最大的回文串，这个回文串和1337取余输出。

（至于为什么只查找c*c，因为就比如99*99，如果这个数是大于num的，那么和99取余如果有合适的，就会直接输出。

我们不需要知道是99和那个数相乘等于的num，只要知道有就可以了。

以此类推，如果是98，那么最大就是98*98,98*99的情况在上面99*99中，如果98*99合适，那么取余就会直接输出了。

）

代码：

class Solution {
public:
    int largestPalindrome(int n) {
        if(n == 1)
        {
            return 9;
        }
        int max = pow(10 , n) - 1;
        for(int i = max;i>0;i--)
        {
            string left = to_string(i);
            string total = left;
            for(int j = left.length()-1;j>=0;j--)
            {
                total.push_back(left[j]);
            }
            long long num = stoll(total);
            for(long long c = max;c*c>=num;c--)
            {
                if(num%c == 0)
                {
                    return (num%1337);
                }
            }
        }
        return 0;
    }
};

注： 1.to_string()函数

这个函数是将括号里面的元素转换为字符串。

2.stoll()函数

此函数将在函数调用中作为参数提供的字符串转换为long int。

它解析str并将其内容解释为指定基数的整数，并将其作为long int类型的值返回。

long int stol（const string＆str，type * id，int base ）

id和base可以不使用

id就是type类型的指针，指向元素的下一个位置。

base是原来数字的进制。

就比如11111，这里base就是2，代表二进制。

例如是FFFF，这里base就是16，代表十六进制。

一般情况下默认10。