入门力扣自学笔记4 C++ (题目编号479)

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。不需要设置。

你可能感兴趣的