Digit Counts

Question

  1. Count the number of k's between 0 and n. k can be 0 - 9.
  3. Example
  4. if n=12, k=1 in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],
  5. we have FIVE 1's (1, 10, 11, 12)

题解

leetcode 上的有点简单，这里以 Lintcode 上的为例进行说明。找出从0至整数 n 中出现数位k的个数，与整数有关的题大家可能比较容易想到求模求余等方法，但其实很多与整数有关的题使用字符串的解法更为便利。将整数 i 分解为字符串，然后遍历之，自增 k 出现的次数即可。

C++

  1. class Solution {
  2. public:
  3.     /*
  4.      * param k : As description.
  5.      * param n : As description.
  6.      * return: How many k's between 0 and n.
  7.      */
  8.     int digitCounts(int k, int n) {
  9.         char c = k + '0';
  10.         int count = 0;
  11.         for (int i = k; i <= n; i++) {
  12.             for (auto s : to_string(i)) {
  13.                 if (s == c) count++;
  14.             }
  15.         }
  16.         return count;
  17.     }
  18. };

Java

  1. class Solution {
  2.     /*
  3.      * param k : As description.
  4.      * param n : As description.
  5.      * return: An integer denote the count of digit k in 1..n
  6.      */
  7.     public int digitCounts(int k, int n) {
  8.         int count = 0;
  9.         char kChar = (char)(k + '0');
  10.         for (int i = k; i <= n; i++) {
  11.             char[] iChars = Integer.toString(i).toCharArray();
  12.             for (char iChar : iChars) {
  13.                 if (kChar == iChar) count++;
  14.             }
  15.         }
  17.         return count;
  18.     }
  19. }

源码分析

太简单了，略

复杂度分析

时间复杂度 O(n \times L), L 为n 的最大长度，拆成字符数组，空间复杂度 O(L).