【题目描述】

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

【思路】
常规思路是枚举1~n 然后 分离位数统计1出现的次数。但最后一个样例过不了；

只过 10/11代码

class Solution {
    public int get_one(int x){
        int res = 0;
        while( x > 0){
            if( x % 10 == 1) res ++;
            x /= 10;
        }
        return res;
    }
    public int numberOf1Between1AndN_Solution(int n) {
        int ans = 0;
        for(int i = 1; i <= n; i ++)
        {
            ans += get_one(i);
        }
        return ans;

    }
}

AC代码

按位统计每一位出现1的情况数。假设统计数字abcdefg中的1的个数。按照下面计算方式：
以统计千位出现1的个数为例：则所有_ _ d _ _都符合，不妨用xxxdyyy代替，方便表示。
1、当 xxx为 000 ~ abc - 1，yyy可以是0 ~ 999,则这种情况千位是1的方案有 abc * 1000
2、 当xxx =abc 时，有以下三种情况：
（1）、 d = 0，则千位是1的方案数为0。
（2）、 d = 1，则yyy可以是 0 ~ efg，千位是1的方案数为 efg + 1。
（3）、 d > 1，则yyy可以是 0 ~ 999，千位是1的方案数为1000。

【思路】
数位dp

class Solution {

    public int numberOf1Between1AndN_Solution(int n) {
        if( n == 0) return n;
        int len = String.valueOf(n).length();
        int number [] = new int[len];
        //分离位数
        for(int i = 0; i < len; i ++){
            number[i] = n % 10;
            n /= 10;
        }

        int res = 0;
        for(int i = len - 1; i >= 0; i --)
        {
            int left = 0, right = 0, t = 1;
            for(int j = len - 1; j > i; j --) left = left * 10 + number[j];
            for(int j = i - 1; j >= 0; j --){
                right = right * 10 + number[j];
                t *= 10;
            }
            res += left * t;

            if(  number[i] == 1 ) res += right + 1;
            else if( number[i] > 1) res += t;
        }
        return res;

    }
}