2396. 严格回文数

Medium

题目描述

如果一个整数 n 在所有介于 2 到 n - 2（包含边界）的进制 b 下，其字符串表示都是回文的，那么我们称这个整数 n 是严格回文的。

给定一个整数 n，如果 n 是严格回文的，返回 true；否则返回 false。

如果一个字符串正着读和反着读是一样的，那么这个字符串是回文的。

示例 1：

输入：n = 9
输出：false
解释：在 2 进制下：9 = 1001，这是回文的。
在 3 进制下：9 = 100，这不是回文的。
因此，9 不是严格回文的，我们返回 false。
注意，在 4、5、6、7 进制下，n = 9 也不是回文的。

示例 2：

输入：n = 4
输出：false
解释：我们只考虑 2 进制：4 = 100，这不是回文的。
因此，我们返回 false。

约束条件：

• 4 <= n <= 10^5

提示：

• 考虑给定数字在 n - 2 进制下的表示。
• 数字 n 在 (n - 2) 进制下总是 12，这不是回文的。

解题思路

这道题目乍看起来需要检查每个进制下的回文性，但实际上是一个数学脑筋急转弯问题。

核心观察： 题目要求检查从进制 2 到进制 (n-2) 的所有情况。根据提示，我们重点关注 n 在进制 (n-2) 下的表示。

对于任意 n ≥ 4，数字 n 在进制 (n-2) 下的表示总是 12：

• n = 1 × (n-2) + 2
• 因为 n-2 ≥ 2，所以 2 < (n-2)，这个表示是有效的

而字符串 "12" 显然不是回文的（正读是 12，反读是 21）。

结论推导： 既然对于所有 n ≥ 4，在进制 (n-2) 下 n 都表示为非回文的 "12"，那么就不存在严格回文数。因此答案总是 false。

验证：

• n = 4：在进制 2 下是 100，不回文
• n = 9：在进制 7 下是 12，不回文

这是一个巧妙的数学题，表面上需要复杂的进制转换和回文检查，实际上通过数学分析可以直接得出答案。

代码实现

class Solution {
public:
    bool isStrictlyPalindromic(int n) {
        return false;
    }
};

class Solution:
    def isStrictlyPalindromic(self, n: int) -> bool:
        return False

public class Solution {
    public bool IsStrictlyPalindromic(int n) {
        return false;
    }
}

/**
 * @param {number} n
 * @return {boolean}
 */
var isStrictlyPalindromic = function(n) {
    return false;
};

复杂度分析

相关题目

• . Palindrome Number (Easy)

• . Stone Game (Medium)