剑指 Offer 43. 1～n整数中1出现的次数

题目描述

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

示例 1：

输入：n = 12

输出：5

示例 2：

输入：n = 13

输出：6

限制：

1 <= n < 2^31

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof

代码实现

class Solution {

public:

    int countDigitOne(int n) {

        int right_num = 0;

        int curre_num = 0;

        int one_count = 0;

        unsigned long cur_digit = 1;

        while(n > 0) {

            curre_num = n % 10;

            n /= 10;

            if(curre_num == 0)

                one_count += n * cur_digit;

            else if(curre_num == 1)

                one_count += n * cur_digit + right_num + 1;

            else

                one_count += (n + 1) * cur_digit;

            right_num += curre_num * cur_digit;

            cur_digit *= 10;

        }

        return one_count;

    }

};