【LeetCode】233. 数字 1 的个数（同剑指Offer43）

一、题目

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例:

输入: 13 输出: 6 解释: 数字 1 出现在以下数字中: 1, 10, 11, 12, 13 。

二、解决

1、暴力破解

思路：

看完题目，然后可直接写出代码，but 该方法超时。

代码：

class Solution { public int countDigitOne(int n) { int cnt = 0; for (int i = 1; i <= n; i++) { String str = Integer.toString(i); for (char c : str.toCharArray()) { if (c == '1') cnt++; } } return cnt; } }

时间复杂度： $O(nlogn)$ 空间复杂度： $O(logn)$

2、动态规划

版本1

思路：

主要参考3，具体分析如下：

数Y是X位数，各位（个、十、百、千、万……）数字组成为$n_x{n}_{x-1}\cdots n_2{n}_1$。其中

1个数：cnt；当前位：$n_i$，记为cur；高位：$n_x{n}_{x-1}\dots n_{i+1}$，记为high；低位：$n_{i-1}\dots n_2{n}_1$，记为low；位因子：$10^i$，记为factor。

1. if cur = 0，then cnt = high×digit

e.g. 求2304十位，即facor=10时，1出现的个数。

另一种推导：十位固定位1 1) 千位选{0，1}，百位{0，1，...，9}，个位{0，1，...，9}，cnt = 2*10*10=200; 2) 千位选2，百位{0，1，2}，个位{0，1，...，9}，cnt = 1*3*10=30; 总计：200+30=230. 可推出公式：cnt = high×digit

2. if cur = 1，then cnt = high×digit+low+1

e.g. 求2314十位，即facor=10时，1出现的个数。

另一种推导：十位固定位1 1) 千位选{0，1}，百位{0，1，...，9}，个位{0，1，...，9}，cnt = 2*10*10=200; 2) 千位选2， 百位{0，1，2}， 个位{0，1，...，9}，cnt = 1*3*10=30; 3）千位选2， 百位选3， 个位{0，1，...，4}，cnt = 5; 总计：200+30+5=235. 可推出公式：cnt = high×digit+low+1

3. if cur > 1，then cnt = (high+1)×digit

e.g. 求2324十位，即facor=10时，1出现的个数。

另一种推导：十位固定位1 1) 千位选{0，1}，百位{0，1，...，9}，个位{0，1，...，9}，cnt = 2*10*10=200; 2) 千位选2， 百位{0，1，2，3}， 个位{0，1，...，9}，cnt = 1*4*10=40; 总计：200+40=240. 可推出公式：cnt = (high+1)×digit

代码：

class Solution { public int countDigitOne(int n) { int res = 0; long a = 0; long b = 0; for(long m=1;m<=n;m*=10){ a = n/m; b = n%m; if(a % 10 > 1){ res += a/10 * m + m; }else if( a%10 == 1){ res += a/10 * m + b + 1; }else{ res += a/10 * m; } } return res; } }

时间复杂度： $O(logn)$ 空间复杂度： $O(1)$

版本2

思路： 对上面的推导公式进一步优化。 代码：

// V1.0 class Solution { public int countDigitOne(int n) { if (n <= 0) return 0; long ones = 0; for (long i = 1, q = n; i <= n; i *= 10, q /= 10) { long pre = n / (i * 10), cur = q % 10, suf = n % i; ones += pre * i; ones += (1 < cur ? i : (1 == cur ? suf + 1: 0)); } return (int) ones; } } // V2.0 class Solution { public int countDigitOne(int n) { if (n <= 0) return 0; int ones = 0; for (long m = 1; m <= n; m *= 10) ones += (n/m + 8) / 10 * m + (n/m % 10 == 1 ? n%m + 1 : 0); return ones; } }

时间复杂度： $O(logn)$ 空间复杂度： $O(1)$

三、参考

1、数字 1 的个数 2、4+ lines, O(log n), C++/Java/Python 3、面试题43. 1～n 整数中 1 出现的次数（清晰图解） 4、Runtime: 0 ms, faster than 100.00% of Java online 5、Java中int转String 和 String转int 各方法效率对比