剑指offer31整数中1出现的次数（从1到n整数中1出现的次数）

剑指offer31

1、暴力--直接双重循环
时间复杂度：O(n*m) 空间复杂度：O(1)

2、找规律，计数
//找规律：
// 1、个位上1出现的频率，从1开始，每10个数出现1次，每次出现持续1个数
// 2、10位上1出现的频率，从10开始，每100个数出现1次，每次出现持续10个数
// 3、百位上1出现的频率，从100开始，每1000个数出现1次，每次出现持续100个数
时间复杂度：O(m) m位数字n的位数，eg:11两位长度 空间复杂度：O（1）

个人调试代码

class Solution {
public:
    //找规律：
    //  1、个位上1出现的频率，从1开始，每10个数出现1次，每次出现持续1个数
    //  2、10位上1出现的频率，从10开始，每100个数出现1次，每次出现持续10个数
    //  3、百位上1出现的频率，从100开始，每1000个数出现1次，每次出现持续100个数
    int NumberOf1Between1AndN_Solution(int n) {
        int len=0;//统计n的位数长度，比如:11两位长度
        int cur=n;
        int count=0; //统计1个数
        while(cur)
        {
            cur/=10;
            ++len;
        }
         int digit=1; //位数和出现一次持续个数 初始个位1，每次出现持续一次
         int frq=10;  //出现频率，初始个位10个数出现一次
        for(int i=0;i<len;i++)
        {
            count+=n/frq*digit; //可以确定的出现次数
            //下面处理最后一次出现，最后一次出现不确定出现多少次的问题，可能0，digit,x-digit+1次
            int num=0;
            if(n%frq>=digit) //出现但不确定出现是否digit次，顶多digit次
                num=n%frq-digit+1;
            num=num>digit?digit:num;
            count+=num;
            digit*=10;
            frq*=10;
        }
        return  count;
    }
};