# Digit Counts ### Source - leetcode: [Number of Digit One | LeetCode OJ](https://leetcode.com/problems/number-of-digit-one/) - lintcode: [(3) Digit Counts](http://www.lintcode.com/en/problem/digit-counts/) ~~~ Count the number of k's between 0 and n. k can be 0 - 9. Example if n=12, k=1 in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], we have FIVE 1's (1, 10, 11, 12) ~~~ ### 題解 leetcode 上的有點簡單，這里以 Lintcode 上的為例進行說明。找出從0至整數 n 中出現數位k的個數，與整數有關的題大家可能比較容易想到求模求余等方法，但其實很多與整數有關的題使用字符串的解法更為便利。將整數 i 分解為字符串，然后遍歷之，自增 k 出現的次數即可。 ### Java ~~~ class Solution { /* * param k : As description. * param n : As description. * return: An integer denote the count of digit k in 1..n */ public int digitCounts(int k, int n) { int count = 0; char kChar = (char)(k + '0'); for (int i = k; i <= n; i++) { char[] iChars = Integer.toString(i).toCharArray(); for (char iChar : iChars) { if (kChar == iChar) count++; } } return count; } } ~~~ ### 源碼分析 太簡單了，略 ### 復雜度分析 時間復雜度 O(n×L)O(n \times L)O(n×L), L 為n 的最大長度，拆成字符數組，空間復雜度 O(L)O(L)O(L).