算法题：数字 1 的个数
n，你需要统计从 1 到 n 的数字中，数字 1 出现的次数。这里的数字 1 不单指整数中的“1”，而是指所有从 1 到 n 这个范围内，出现的每个数字 1。简单暴力解法
public class CountOnes {
public static int countDigitOne(int n) {
int count = 0;
for (int i = 1; i <= n; i++) {
String numStr = String.valueOf(i);
for (char c : numStr.toCharArray()) {
if (c == '1') {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
int n = 13;
System.out.println("1的个数是: " + countDigitOne(n));
}
}
高效算法：数学分析
x = 13，我们可以把它分解为以下几部分：百位（高位）：0 或 1 十位：0-9 个位：0-9
更高效的解法
public class CountOnes {
public static int countDigitOne(int n) {
int count = 0;
for (long factor = 1; factor <= n; factor *= 10) {
long lowerNumbers = n - (n / factor) * factor;
long currentDigit = (n / factor) % 10;
long higherNumbers = n / (factor * 10);
if (currentDigit == 0) {
count += higherNumbers * factor;
} else if (currentDigit == 1) {
count += higherNumbers * factor + lowerNumbers + 1;
} else {
count += (higherNumbers + 1) * factor;
}
}
return count;
}
public static void main(String[] args) {
int n = 13;
System.out.println("1的个数是: " + countDigitOne(n)); // 输出结果应该是 6
}
}
代码解析
循环每一位：通过 factor（即 10 的幂次方）逐位检查数字。比如，从个位开始，再到十位、百位，以此类推。三部分拆解：对于每一位，我们将数字拆解为三部分：低位数字（ lowerNumbers）、当前位数字（currentDigit）和高位数字（higherNumbers）。然后根据currentDigit的值来判断 1 在当前位上出现的次数。
如果当前位数字是 0，那么当前位上不会有 1，次数等于高位部分的次数乘以当前位的因子。 如果当前位数字是 1，那么当前位上会有额外的 1，次数等于高位部分的次数乘以当前位的因子再加上低位数字加一。 如果当前位数字大于 1，说明当前位上肯定有 1，次数等于高位部分的次数加一，再乘以当前位的因子。
性能分析
-END-
以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。
