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

43. 从 1 到 n 整数中 1 出现的次数

NowCoder

解题思路

创新解法：

装逼模式开启：

我们从一个5位的数字讲起，先考虑其百位为1的情况。分3种情况讨论：

1 百位数字>=2 example: 312**56** 当其百位为>=时，有以下这些情况满足(为方便起见，计312为a，56为b)：

100 ~ 199

1100 ~ 1199

​ …..

31100 ~ 31199

余下的都不满足！

因此，百位>=2的5位数字，其百位为1的情况有（a/10+1）*100个数字 （a/10+1）=>对应于 0 ~ 31，且每一个数字，对应范围是100个数（末尾0-99）

2 百位数字 ==1 example: 311**56** 当其百位为1时，有以下这些情况满足：

100 ~ 199

1100 ~ 1199

​ ……

30100 ~ 30199

31100 ~ 31156

因此，百位为1的5位数字，共有（a/10）*100+(b+1)

3 百位数字 ==0 example: 310**56** 当其百位为0时，有以下这些情况满足：

100 ~ 199

1100 ~ 1199

30100 ~ 30199

其余都不满足

因此，百位数为0的5位数字，共有(a/10)*100个数字满足要求

我们可以进一步统一以下表达方式，即当百位>=2或=0时，有[(a+8)/10]100，当百位=1时，有[(a+8)/10]100+(b+1)。用代码表示就是： [(a+8)/10]*100+(a%10==1)?(b+1):0；

为什么要加8呢？因为只有大于2的时候才会产生进位等价于（a/10+1），当等于0和1时就等价于(a/10)。另外，等于1时要单独加上(b+1)，这里我们用a对10取余是否等于1的方式判断该百位是否为1。

Question：有缺陷或逻辑错误吗？

有人可能会有疑惑，比如11100，这个数在考虑百位为1的时候算作了一次，在考虑千位的时候也算了一次，在考虑万位为1的时候又算了一次，一共计了3次，这不是明显重复吗？

我的回答是，不重复！

分析：题目中要我们统计出现的1的个数，那么我们可以看到11100一共是3个1,如果剔除了重复的情况只考虑一次才会是问题。换言之，在计算从1到n整数中1的出现次数时，我们把10位出现1的情况个数加上百位出现1的情况个数一直加到最高位是1的情况的个数，这里面一个数可能被统计过多次；11100百位出现1，千位和万位都为1，那么被重复统计了3次

#if 1 //O(logn)
/**
 * https://www.cnblogs.com/xuanxufeng/p/6854105.html
由第二种解法的解析 可进一步整理等式
例如num=31256  求百位的1的种类 令a =num/100= 312, b=num%100=56
第二种解法给出的思路：
1 考虑31-1 00100~30199组合：00-31 00-99 =32*100=(a/10)*100
2 考虑31   百位 = 0 ：0个1
           百位 = 1 ：31100~31156 = b + 1
           百位 > 1 : 31100~31199 = 100
若依次取n的个位到最高位 
for(int i = 1; i <= n; i *= 10)
{
    a = a/i, b = n % i;
}

可推算 a%10即为当前考虑位的状态 

a%10 == 0 ： (a/10) * i
a%10 == 1:   (a/10) * i + (b + 1)
a%10 >=2 :   (a/10) * i + i = (a/10 +1)*i

=>统一 (a + 8) / 10 <=> a = 0,1 :(a / 10)  a>=2 (a/10 +1)
sum += (a+8)/10 * i + (a%10==1) ? b+1 : 0
**/

class Solution {
public:
    int numberOf1Between1AndN_Solution(int n) {
        int count = 0;
        for (int i = 1; i <= n; i *= 10) {
            int a = n / i,b = n % i;  //依次求取
            //之所以补8，是因为当百位为0，则a/10==(a+8)/10，
            //当百位>=2，补8会产生进位位，效果等同于(a/10+1)
         count += (a + 8) / 10 * i + ((a % 10 == 1 ? b + 1 : 0));
        }
        return count;
    }
};

#endif

#if 0 //  O(logn)^2
/**
分析：依次查看每个位存在多少个1
1432：
千：1000-1432 = 433
百：0100-0199 = 100
    1100-1199 = 100
十：0010-1319 = 1310
    1410-1419 = 10
个：0001-142 9 = 1430
    1431-1432 = 2
    
=》公用
abcdef
1、拆分数据到数组
2、比如对应1的个数
left=c 前面的数ab；right =c 后面的数=def， t表示c后面数据个数v t=10^v
  一、ab-1
  001000~(ab-1)1999 =ab * t(组合 c前面有ab种选择，c后面有t种选择)  //(t=c后面的数据个数)   十00 10-13 19 = 1310
  二、ab
  c = 0 :o个1
  c = 1 :ab1000-ab1def def+1 个1
  c > 1 :ab1000-ab1999 t(t=c后面的数据个数)
  
  O(logn)^2
****/
class Solution {
public:
    int numberOf1Between1AndN_Solution(int n) {
        if(n <= 0) return 0;
        //分解n的每个数据位，从个位开始 每次除10 直到为零
        vector<int> v ;
        while(n) v.emplace_back(n % 10), n /= 10;
        //讨论
        int res = 0 ;
        for(int i = v.size() - 1; i >= 0; i --) //高位开始遍历
        {
            //i左边的数 右边的数 i的权值 （ixxx）t=1000
            int left = 0, right = 0, t = 1;
            //从头找 反向找直到i  初始left = 0
            for(int x = v.size() - 1; x > i; x --) left = left * 10 +v[x]; 
            for(int y = i - 1; y >=0 ; y --) right = right * 10 +v[y], t *= 10; 
            //cout << v[i] <<" " << left << " "<< right << " " << t ;
            //考虑第一种情况 ab-1
            //if(left > 0) res += left * t;
            res += left * t;
            //第二种情况讨论
            if(v[i] == 1) res += right + 1;
            else if(v[i] > 1) res += t;
            //cout <<" res:" << res<< endl;
            
            //结合一 二=》推出新的对应关系
        }
        return res;
    } 
};
#endif

Leetcode : 233. Number of Digit One