LeetCode——233. 数字 1 的个数[Number of Digit One][困难]——分析及代码[Java]
- 一、题目
- 二、分析及代码
- 1. 逐位统计
- (1)思路
- (2)代码
- (3)结果
- 三、其他
一、题目
给定一个整数 n,计算所有小于等于 n 的非负整数中数字 1 出现的个数。
示例 1:
输入:n = 13
输出:6
示例 2:
输入:n = 0
输出:0
提示:
- 0 <= n <= 2 * 10^9
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/number-of-digit-one
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
二、分析及代码
1. 逐位统计
(1)思路
依次统计所有小于等于 n 的非负整数中,在各个数位上 1 的出现次数。则对于第 x 位,设 digit = 10 ^ (x - 1),则:
- 由更高数位的值产生的当前数位 1 的出现次数,为 n / (digit * 10) * digit
- 如对整数 12145 的百位,由更高数位产生的部分,每 1000 个数中会出现 100 个百位的 1,即共有 12145 / 1000 * 100 = 12 * 100
- 由更低数位的值产生的当前数位 1 的出现次数,为 Math.min(Math.max((n % (digit * 10) - digit + 1), 0), digit)
- 如对整数 12145 的百位,由更低数位产生的部分,为 [100, 145] 共 46 个,即 Math.min(Math.max(12145 % 1000 - 100 + 1, 0), 100) = 46
(2)代码
class Solution {
public int countDigitOne(int n) {
long digit = 1L;//值为1, 10, 100, ..., 表示当前处理的十进制数位
int ans = 0;
while (n >= digit) {//枚举每一数位上1的个数
int cnt1 = (int)(n / (digit * 10) * digit);//由更高数位的值产生的当前数位1的出现次数
int cnt2 = Math.min(Math.max((int)(n % (digit * 10) - digit + 1), 0), (int)digit);//由更低数位的值产生的当前数位1的出现次数
ans += cnt1 + cnt2;//统计
digit *= 10L;//十进制数位左移1位
}
return ans;
}
}
(3)结果
执行用时 :0 ms,在所有 Java 提交中击败了 100.00% 的用户;
内存消耗 :35.2 MB,在所有 Java 提交中击败了 35.70% 的用户。
三、其他
暂无。