Sword to Offer-43 整数1出现的次数 ❀❀

03 May 2020 in Algorithm

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

解题思路：

1、考虑每个位置出现1的次数如何计算，例如数字430156：
个位6>1,高位为0-43015时都可取到1，个位为1共（43015+1）*1个数;
十位5>1，高位为0-4301时都可取到10-19,十位为1共（4301+1）*10个数;
百位1，高位为0-429时都可取到100-199，高位为430时可取0-156，百位共（430）*100 +156 +1个数;
千位0，高位为0-42时都可取到1000-1999，高位为43时，千位取不到1，千位共（42+1）*1000个数;
万位3>1，高位为0-3时都可取到10000-19999，万位共（3 +1）*10000个数;
十万位4>1，高位为0，可取到100000-199999，十万位共（0 +1）*100000个数。

2、总结规律：
当前位为0，1出现次数为：高位数字 *该位对应的10的倍数；
当前位为1，1出现次数为：高位数字 *该位对应的10的倍数 +低位数字 +1；
当前位大于1，1出现次数为：（高位数字 +1） *该位对应的10的倍数。

3、如何依次取出某数的高低位，从低到高求解：
高位n/i/10，当前位n/i%10，低位n%i；
如n=1234，取百位时i=100，此时高位1234/100/10=1，当前位1234/100%10=2，低位1234%100=34。

问题图解：

AC代码：

// How Many 1 Appears From 0 To Number N

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int count = 0;
        if (n == 1) {
            return 1;
        }
        for (int i=1; i<=n; i*=10) {  //i=100
            int high = n / i / 10;  //430
            int cur = n / i % 10;  //1
            int low = n % i;  //156
            //判断该位是否大于1
            if (cur == 0) {
                count += high * i;
            }
            if (cur == 1) {
                count += high * i + low + 1;
            }
            if (cur > 1) {
                count += (high + 1) * i;
            }
        }
        return count;
    }
}

补充说明：

• 这里是牛客编码链接