原文链接: https://leetcode-cn.com/problems/sum-of-k-mirror-numbers

英文原文

A k-mirror number is a positive integer without leading zeros that reads the same both forward and backward in base-10 as well as in base-k.

• For example, 9 is a 2-mirror number. The representation of 9 in base-10 and base-2 are 9 and 1001 respectively, which read the same both forward and backward.
• On the contrary, 4 is not a 2-mirror number. The representation of 4 in base-2 is 100, which does not read the same both forward and backward.

Given the base k and the number n, return the sum of the n smallest k-mirror numbers.

 

Example 1:

Input: k = 2, n = 5
Output: 25
Explanation:
The 5 smallest 2-mirror numbers and their representations in base-2 are listed as follows:
  base-10    base-2
    1          1
    3          11
    5          101
    7          111
    9          1001
Their sum = 1 + 3 + 5 + 7 + 9 = 25. 

Example 2:

Input: k = 3, n = 7
Output: 499
Explanation:
The 7 smallest 3-mirror numbers are and their representations in base-3 are listed as follows:
  base-10    base-3
    1          1
    2          2
    4          11
    8          22
    121        11111
    151        12121
    212        21212
Their sum = 1 + 2 + 4 + 8 + 121 + 151 + 212 = 499.

Example 3:

Input: k = 7, n = 17
Output: 20379000
Explanation: The 17 smallest 7-mirror numbers are:
1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596

 

Constraints:

• 2 <= k <= 9
• 1 <= n <= 30

中文题目

一个 k 镜像数字 指的是一个在十进制和 k 进制下从前往后读和从后往前读都一样的 没有前导 0 的 正 整数。

• 比方说，9 是一个 2 镜像数字。9 在十进制下为 9 ，二进制下为 1001 ，两者从前往后读和从后往前读都一样。
• 相反地，4 不是一个 2 镜像数字。4 在二进制下为 100 ，从前往后和从后往前读不相同。

给你进制 k 和一个数字 n ，请你返回 k 镜像数字中 最小 的 n 个数 之和 。

 

示例 1：

输入：k = 2, n = 5
输出：25
解释：
最小的 5 个 2 镜像数字和它们的二进制表示如下：
  十进制       二进制
    1          1
    3          11
    5          101
    7          111
    9          1001
它们的和为 1 + 3 + 5 + 7 + 9 = 25 。

示例 2：

输入：k = 3, n = 7
输出：499
解释：
7 个最小的 3 镜像数字和它们的三进制表示如下：
  十进制       三进制
    1          1
    2          2
    4          11
    8          22
    121        11111
    151        12121
    212        21212
它们的和为 1 + 2 + 4 + 8 + 121 + 151 + 212 = 499 。

示例 3：

输入：k = 7, n = 17
输出：20379000
解释：17 个最小的 7 镜像数字分别为：
1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596

 

提示：

• 2 <= k <= 9
• 1 <= n <= 30

通过代码

高赞题解

本质是三道简单题！！！

1. 已知一个十进制对称数，求下一个十进制对称数

2. 判断一个字符串是否对称

3. 将十进制数转换成k进制数字符串

• 这三个操作都要求$O(logn)$的时间复杂度
• 具体代码如下，写成了三个函数nextInt， isGood， tokstring

  typedef long long ll;
  
  // 获取下一个对称的十进制数
  ll nextInt(ll num){
      string s = to_string(num);
      int width = s.size();
      for(int i=width/2;i>=0;i--){
          if(s[i]!='9'){
              s[i]++;
              if(width-1-i != i){
                  s[width-1-i]++;
              }
              for(int j=i+1;j<=width/2;j++){
                  s[j] = '0';
                  s[width-1-j] = '0';
              }
              return stoll(s);
          }
      }
      ll ans = 1;
      for(int i=0;i<width;i++){
          ans *= 10;
      }
      ans += 1;
      return ans;
  }
  
  // 判断一个字符串是否是对称的
  bool isGood(string& s){
      int n = s.size();
      for(int i=0;i<n/2;i++){
          if(s[i] != s[n-1-i]){
              return false;
          }
      }
      return true;
  }
  
  // 将十进制数转换为k进制字符串
  string tokstring(ll num, int k){
      string ans = "";
      while(num != 0){
          ans += char(num%k+'0');
          num /= k;
      }
      return ans;
  }
  
  class Solution {
  public:
      long long kMirror(int k, int n) {
          ll ans = 0, num = 0;
          while(n!=0){
              num = nextInt(num);
              string s = tokstring(num, k);
              if(isGood(s)){
                  ans += num;
                  n--;
              }
          }
          return ans;
      }
  };

  典中典之比赛结束后一分钟提交
  

统计信息

通过次数	提交次数	AC比率
1936	5052	38.3%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言