整数中 1 出现的次数

题目描述

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

解题思路

• 设定整数点（如 1、10、100 等等）作为位置点 i（对应 n 的各位、十位、百位等等），分别对每个数位上有多少包含 1 的点进行分析；

• 根据设定的整数位置，对 n 进行分割，分为两部分，高位 n/i，低位 n%i；

• 当 i 表示百位，且百位对应的数 >=2,如 n=31456,i=100，则 a=314,b=56，此时百位为 1 的次数有 a/10+1=32（最高两位 0~31），每一次都包含 100 个连续的点，即共有(a%10+1)*100 个点的百位为 1；

• 当 i 表示百位，且百位对应的数为 1，如 n=31156,i=100，则 a=311,b=56，此时百位对应的就是 1，则共有 a%10(最高两位 0-30)次是包含 100 个连续点，当最高两位为 31（即 a=311），本次只对应局部点 00~56，共 b+1 次，所有点加起来共有（a%10*100）+(b+1)，这些点百位对应为 1；

• 当 i 表示百位，且百位对应的数为 0,如 n=31056,i=100，则 a=310,b=56，此时百位为 1 的次数有 a/10=31（最高两位 0~30）；

• 综合以上三种情况，当百位对应 0 或 >=2 时，有(a+8)/10 次包含所有 100 个点，还有当百位为 1(a%10==1)，需要增加局部点 b+1；

• 之所以补 8，是因为当百位为 0，则 a/10==(a+8)/10，当百位 >=2，补 8 会产生进位位，效果等同于(a/10+1)。

代码

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int count = 0;
        int i = 1;
        for (; i <= n; i *= 10) {
            int a = n / i;
            int b = n % i;
            count += (a + 8) / 10 * i;
            if (a % 10 == 1)
                count += b + 1;
        }
        return count;
    }
}