与回文数相关的解题思路和题目示例。

回文数的重点是把握回文数的根，也就是回文数的左半部分，因为右半部分可以通过左半部分镜像来得到，比如回文数123321的根是123。

注意，以123为根的回文数不止有一个，而是有两个，分别是123321和12321，这也就说明，同一个根在长度为奇数和偶数情况下各自对应一个回文数。

回文数可以通过根来简化构造和判断，通过回文数的根可以解决下面这类的问题：

  • 判断N位的回文数一共有几个
  • 从小到大构造全部N位的回文数（或者说找出第n个长度为N的回文数）
  • 找出全部小于x的回文数

假设回文数的长度为N，则根的长度为root_len = (N / 2) + (N % 2)，根的范围是[pow(10, root_len-1), pow(10, root_len))，参考以下示例：

偶数长度示例：

  • 回文数长度为6。
  • 根的长度为3，根的范围是[100, 1000)。
  • 回文数从小到大的顺序为：100001，101101，102201，103301，... 999999。

奇数长度示例：

  • 回文数长度为5。
  • 根的长度为3，根的范围是[100, 1000)。
  • 回文数从小到大的顺序为：10001，10101，10201，10301，99999。


题目示例：

  • 5253. 找到指定长度的回文数 - 力扣（LeetCode）

    • 思路：根据回文数长度可以确定根的长度，从而得到根的范围，对于每个查询，如果超出了根的范围，直接返回-1，如果未超出，则先求出对应的根，再直接构造对应的回文数。

      class Solution {
    // 构造长度为len的第k个回文数，k从0开始计数
    long long buildKthPalindrome(int len, int k) {
        int root_len = (len / 2) + (len % 2);
        long long root = pow(10, root_len - 1) + k;
        string left = to_string(root);
        string right(left.rbegin(), left.rend());
        string all;
        if(len % 2 == 0) {
            all = left + right;
        } else {
            all = left + right.substr(1);
        }
        return stoll(all);
    }

public:
    vector<long long> kthPalindrome(vector<int>& queries, int intLength) {
        vector<long long> ans;
        int root_len = (intLength / 2) + (intLength % 2);
        int min_root = pow(10, root_len-1);
        int max_root = pow(10, root_len);
        for(auto &q : queries) {
            if(min_root + q > max_root) {
                ans.push_back(-1);
            } else {
                ans.push_back(buildKthPalindrome(intLength, q-1));
            }
        }
        return ans;
    }
};



  • 无标签