2217. 找到指定长度的回文数（Rating 1822）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

2217. 找到指定长度的回文数

Rating 1822

思路

找规律，回文数通常只需要考虑一半

• intLength为1时
  • 序列为：1，2，3，4，5，6，7，8，9
  • 一半为：1，2，3，4，5，6，7，8，9
  • 总数量：9 - 1 + 1 = 9
• intLength为2时
  • 序列为：11，22，33，44，55，66，77，88，99
  • 一半为：1，2，3，4，5，6，7，8，9
  • 总数量：9 - 1 + 1 = 9
• intLength为3时
  • 序列为：101，111，121，131，141，…，999
  • 一半为：10，11，12，13，14，…，99
  • 总数量：99 - 10 + 1 = 90
• intLength为4时
  • 序列为：1001，1111，1221，1331，1441，…，9999
  • 一半为：10，11，12，13，14，…，99
  • 总数量：99 - 10 + 1 = 90

按规律代码即可。

• 注意当intLength=1时，最小的回文数是1不是0
• 注意queries有可能超过回文数数量，此时需要根据总数量判断一下，超出时返回-1

代码

class Solution:
    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:
        n = len(queries)
        ret = [0] * n
        b = (intLength + 1) // 2
        mx = 9 * 10 ** (b - 1) # 总数量规律
        for idx, q in enumerate(queries):
            if q > mx: # 超出数量
                ret[idx] = -1
                continue
            num = 10 ** (b - 1) + q - 1 # 回文数一半
            m = num
            if intLength % 2 > 0:
                m //= 10
            while m: # 补全另一半
                num = 10 * num + (m % 10)
                m //= 10
            ret[idx] = num
        return ret