526互联

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

发布时间 2023-04-09 10:03:16作者: zhangk1988

题目描述

给了一个正整数k，表示长度是k的所有回文数字
再给了和很多q，问第q小的数字是多少？

f1 数学关系+构造

基本分析

  1. 从q之间的相互关系考虑还是单独考虑某个q和结果的关系？后者
  2. 长度是k的回文数字有啥特性？前一半数字是固定的,half = k + 1 >> 2, str[num][:half]
  3. 以上性质和q有啥关系？前一半数字可以通过q构造出来。base = 10 ** （half - 1） - 1，比如k=5， half=2，base = 99，第1小的3位数字是100，构造出第1小的5位是100001；
  4. 奇偶不同会影响啥？（1）half的长度，（2）构造出来前一半后恢复会原来数字的方式
  5. 为啥奇偶不同不会影响前半部分的大小，毕竟位数不一样？对给定的k，前半部分half也是相同的，大家比的位数是一样的
  6. 有没有不存在的可能，如何考虑？有，比如q很大，不存在；base + q不能超过位数的限制，也就是base + q 最大是 10 ** half - 1

代码

class Solution:
    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:
        half = (intLength + 1) // 2

        base = 10 ** (half - 1) - 1
        limit = 10 ** half - 1

        def recover(intLength, num):
            if intLength % 2 == 0:
                return int(str(num) + str(num)[::-1])
            else:
                return int(str(num)[:-1] + str(num)[::-1])

        ans = []
        for q in queries:
            num = base + q
            if not num > limit:
                ans.append(recover(intLength, num))
            else:
                ans.append(-1)
        
        return ans

总结

  1. 利用回文的性质找前一半，满足严格增的关系
  2. 利用q和base构造出前一半，注意有上限
  3. 恢复前一半