面试题 43：1 _ n 整数中 1 出现的次数.md

试题链接：56. 从1到n整数中1出现的次数 - AcWing题库

方法一：数学

• 思路：遍历每一个数位，计算当其为 1 时有多少种情况，最后将所有情况相加即可。以数位 abcd 为例，（1）考虑数位 a，若 a 为 1，则右侧数位可以取 0 ~ bcd 共 bcd + 1 种情况；（2）考虑数位 b，当左侧取 0 ~ a - 1 时，右侧可以任意取 0 ~ 99 的数，共 a × 100 种情况，当左侧取 a 时，若 b 为 1，则右侧可取 0 ~ cd 共 cd + 1 种情况，若 b 大于 1，则可将 b 取 1，右侧可以任意取 0 ~ 99 共 100 中情况，以此类推，最后的和就是 1 ~ n 中 1 出现的次数。
• 时间复杂度：O(logn)
• 空间复杂度：O(1)

class Solution {
public:
    int numberOf1Between1AndN_Solution(int n) {
        int ans = 0;
        int left = 0, right = n, mask = 1;
        
        vector<int> digit;
        while (n) {
            digit.push_back(n % 10);
            n /= 10;
            mask *= 10;
        }
        
        reverse(digit.begin(), digit.end());
        
        for (int i = 0; i < digit.size(); i++) {
            mask /= 10;
            ans += left * mask;
            if (digit[i] == 1) {
                ans += 1 + right % mask;
            } else if (digit[i] > 1) {
                ans += mask;
            }
            left = left * 10 + digit[i];
            right = right % mask;
        }
        
        return ans;
    }
};