题意

计算从 1 到 n 整数中 1 出现的次数

分析

数位 dp 模板

class Solution {
public:
    int numberOf1Between1AndN_Solution(int n) {
       vector<int> nums;
       while(n) nums.push_back(n % 10), n /= 10;
       int len = nums.size();
       int ans = 0;
       for(int i = len-1; i >= 0; i --){
           int left = 0, right = 0, power10 = 1;
           for(int j = len-1; j > i; j --)left = left * 10 + nums[j];
           for(int j = i - 1; j >= 0; j --)right = right*10 + nums[j], power10 *= 10;
           ans += left * power10;

           if(nums[i] == 1)ans += right + 1;
           else if(nums[i] > 1)ans += power10;
       }

       return ans;
    }
};