解题思路

这是一道数位统计题目,主要思路如下:

  1. 问题分析:

    • 统计 中数字 出现的次数
    • 的范围很大,需要优化算法
    • 中包含 这些数字
    • 需要统计每个位置上 出现的次数
  2. 解决方案:

    • 按位计算,从个位开始
    • 对每一位,分三种情况:
      1. 当前位是0
      2. 当前位是1
      3. 当前位大于1

代码

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    long ans = 0;
    int idx = 0;  // 当前处理的位数
    int right = 0;  // 右边的数字
    
    while(n) {
        // 当前位的数字
        int cur = n % 10;
        // 左边的数字
        int left = n / 10;
        
        // 根据当前位的数字分三种情况
        if(cur == 0) {
            // 当前位是0,由左边数字决定
            ans += left * pow(10, idx);
        } else if(cur == 1) {
            // 当前位是1,需要考虑右边的数字
            ans += left * pow(10, idx) + right + 1;
        } else {
            // 当前位大于1
            ans += (left + 1) * pow(10, idx);
        }
        
        // 更新右边的数字
        right += cur * pow(10, idx);
        n /= 10;
        idx++;
    }
    
    cout << ans << endl;
    return 0;
}
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        long ans = 0;
        int idx = 0;
        int right = 0;
        
        while(n > 0) {
            int cur = n % 10;
            int left = n / 10;
            
            if(cur == 0) {
                ans += left * Math.pow(10, idx);
            } else if(cur == 1) {
                ans += left * Math.pow(10, idx) + right + 1;
            } else {
                ans += (left + 1) * Math.pow(10, idx);
            }
            
            right += cur * Math.pow(10, idx);
            n /= 10;
            idx++;
        }
        
        System.out.println(ans);
    }
}
def count_ones(n: int) -> int:
    ans = 0
    idx = 0
    right = 0
    
    while n:
        # 当前位的数字
        cur = n % 10
        # 左边的数字
        left = n // 10
        
        if cur == 0:
            ans += left * (10 ** idx)
        elif cur == 1:
            ans += left * (10 ** idx) + right + 1
        else:
            ans += (left + 1) * (10 ** idx)
        
        right += cur * (10 ** idx)
        n //= 10
        idx += 1
    
    return ans

def main():
    n = int(input())
    print(count_ones(n))

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法:数位统计
  • 时间复杂度: - 的位数
  • 空间复杂度: - 只需要常数空间