统计数字 1 出现的次数 - Java 代码实现

给定一个十进制正整数 n(1≤n≤10000)，写下从 1 到 n 的所有整数，然后数一下其中出现的数字“1”的个数。

例如当 n=2 时，写下 1,2。这样只出现了 1 个“1”；当 n=12 时，写下 1，2，3，4，5，6，7，8，9，10，11，12。这样出现了 5 个“1”。

输入描述

正整数 n。1 ≤ n ≤ 10000。

输出描述

一个正整数，即“1”的个数。

用例输入 1

12

用例输出 1

5

思路：

我们可以从 1 到 n 遍历每个数字，然后将每个数字转换为字符串，并计算字符串中出现的“1”的个数。

具体实现步骤如下：

1. 初始化计数器 count 为 0。
2. 循环从 1 到 n，每次迭代一个数字 num：
1. 将 num 转换为字符串 str。
2. 遍历字符串 str 的每个字符，如果字符是“1”，则将计数器 count 加 1。
3. 输出计数器 count 的值。

代码实现：

import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
    int count = 0;
    
    for (int num = 1; num <= n; num++) {
        String str = String.valueOf(num);
        
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '1') {
                count++;
            }
        }
    }
    
    System.out.println(count);
}

}

复杂度分析：

由于我们需要遍历从 1 到 n 的所有数字，并且将每个数字转换为字符串，所以时间复杂度为 O(n * log(n))。

在空间上，我们只需要保存一个计数器和每个数字的字符串表示，所以空间复杂度为 O(log(n))。

因此，总的时间和空间复杂度为 O(n * log(n))。