统计好整数的数目

题目

https://leetcode.cn/problems/find-the-count-of-good-integers/description/?envType=daily-question&envId=2025-04-12

给你两个 正 整数 n 和 k 。

如果一个整数 x 满足以下条件，那么它被称为 k 回文 整数 。

• x 是一个 回文整数 。
• x 能被 k 整除。

如果一个整数的数位重新排列后能得到一个 k 回文整数 ，那么我们称这个整数为 好 整数。比方说，k = 2 ，那么 2020 可以重新排列得到 2002 ，2002 是一个 k 回文串，所以 2020 是一个好整数。而 1010 无法重新排列数位得到一个 k 回文整数。

请你返回 n 个数位的整数中，有多少个 好 整数。

注意 ，任何整数在重新排列数位之前或者之后 都不能 有前导 0 。比方说 1010 不能重排列得到 101 。

实现

思路：遍历每个字符作为回文中心，向左右扩展寻找最长回文。 注意：奇偶情况

复杂度分析

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    if (s.length < 2) return s;
    
    let start = 0, maxLength = 1;
    
    // 中心扩展函数
    const expandAroundCenter = (left, right) => {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            const currentLength = right - left + 1;
            if (currentLength > maxLength) {
                maxLength = currentLength;
                start = left;
            }
            left--;
            right++;
        }
    };
    
    for (let i = 0; i < s.length; i++) {
        expandAroundCenter(i, i);    // 奇数长度回文（中心为单个字符）
        expandAroundCenter(i, i + 1); // 偶数长度回文（中心为两个字符）
    }
    
    return s.slice(start, start + maxLength);
};
 
// 辅助函数：判断是否为回文（修正版）
var isPalindrome = function(s) {
    return s === s.split('').reverse().join('');
};