Given an integer n
, count the total number of digit 1
appearing in all non-negative integers less than or equal to n
.
Example 1:
Input: n = 13 Output: 6
Example 2:
Input: n = 0 Output: 0
Constraints:
0 <= n <= 109
数字 1 的个数。
给定一个整数 n
,计算所有小于等于 n
的非负整数中数字 1
出现的个数。举个例子,比如当 n = 13,结果是 6,因为 1 出现在了如下数字中:1, 10, 11, 12, 13。
这是一道数学题,我给出一个我觉得比较好理解的思路吧,我参考了这个帖子。对于一个数字比如 abcde,整体的思路是我们需要按 digit 逐位讨论 1 出现的次数,比如如果我们要统计当 c 是 1 的情况下满足题意的数字的个数的话,分如下情况,
- 当 c 前面的部分 < ab,即范围为 [0, ab),此时必然满足「大小要求」,因此后面的部分可以任意取,即范围为 [0, 99]。根据「乘法原理」,可得知此时数量为 ab * 100;
- 当 c 前面的部分 = ab,这时候「大小关系」主要取决于 c:
- 当 c = 0,必然不满足「大小要求」,数量为 0;
- 当 c = 1,此时「大小关系」取决于后部分,后面的取值范围为 [0, de],数量为 1 * (de + 1);
- 当 c > 1,必然满足「大小关系」,后面的部分可以任意取,即范围为 [0, 99],数量为 1 * 100;
- 当 c 前面的部分 > ab,必然不满足「大小要求」,数量为 0。
时间O(n) - 字符长度
空间O(1)
Java实现
1 class Solution { 2 public int countDigitOne(int n) { 3 String s = String.valueOf(n); 4 int m = s.length(); 5 // corner case 6 if (m == 1) { 7 return n > 0 ? 1 : 0; 8 } 9 10 // normal case 11 // 计算第 i 位前缀代表的数值,和后缀代表的数值 12 // 例如 abcde 则有 before[2] = ab; after[2] = de 13 int[] before = new int[m]; 14 int[] after = new int[m]; 15 after[0] = Integer.parseInt(s.substring(1)); 16 for (int i = 1; i < m - 1; i++) { 17 before[i] = Integer.parseInt(s.substring(0, i)); 18 after[i] = Integer.parseInt(s.substring(i + 1)); 19 } 20 before[m - 1] = Integer.parseInt(s.substring(0, m - 1)); 21 // 分情况讨论 22 int ans = 0; 23 for (int i = 0; i < m; i++) { 24 // x 为当前位数值,len 为当前位后面长度为多少 25 int x = s.charAt(i) - '0'; 26 int len = m - i - 1; 27 int prefix = before[i]; 28 int suffix = after[i]; 29 int tot = 0; 30 tot += prefix * Math.pow(10, len); 31 if (x == 0) { 32 } else if (x == 1) { 33 tot += suffix + 1; 34 } else { 35 tot += Math.pow(10, len); 36 } 37 ans += tot; 38 } 39 return ans; 40 } 41 }