剑指offer 从1到n整数中1出现的次数

题目描述

求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

class Solution {
public:
    int MakeNum(int n) {
        int ret = 1;
        while (n--) {
            ret *= 10;
        }
        return ret;
    }
    // 以21345举例分析
    int AssistFunc(string str) {
        // 将数字转换为字符串方便分析，取出最高位数字，并计算总数字总位数
        string first = str.substr(0, 1);
        int size = str.size();
        int f = stoi(first);    // 最高位数字
        int num = stoi(str);    
        
        // 数字只有一位
        if (num < 1) return 0;
        if (num < 10) return 1;
        
        // 先计算1346-21345中1的个数
        // 先计算最高位为1时 1的个数
        int numFirstDigit;
        if (f == 1)
            numFirstDigit = stoi(str.substr(1))+1;
        else
            numFirstDigit = MakeNum(size-1);
        
        // 处理其余部分，最高位取值个数（f）*其余位个数*其余位取值个数（10）
        int numOtherDigit = f*(size-1)*MakeNum(size - 2);
        
        // 处理一开始抛除的部分（1-1345） 进行递归处理，最终返回和
        int numDesertDigit = AssistFunc(str.substr(1));
        return numFirstDigit + numOtherDigit + numDesertDigit;
    }
    int NumberOf1Between1AndN_Solution(int n) {
        if (n <= 0) return 0;
        string str = to_string(n);
        return AssistFunc(str);
    }
};