一道数字统计的题

 不知道是不是 没事闲的，想出来一道题：

0 到 n 的数字中，有几个数字，包含某个个位数，如

0到11有    2个数包含 1 ------- 1, 11

               1个数包含 4 ------- 4

               2 个数包含 0 ------- 0，10

结果停不下来了，花了一晚上搞了个程序，我脑袋笨还是咋的，可累死了，不知道程序高不高效，总比一个个个数好，但 0统计没能整合在一起，怎么做啊，其他倒都可以了

 

public class NumberCount {

    public static void easy(int s, int n, int d) {

        System.out.println("-----------------------");
        int count = 0;
        for (int i = s; i <= n; i++) {
            if ((i + "").indexOf(d + "") != -1) {
                count++;
                //System.out.println(i);
            }
        }

        System.out.println(count);

        System.out.println("-----------------------");
    }

    public static void main2(String[] args) {
        Time t = new Time();
        t.start();
        System.out.println(coutD(98798, 0));
        System.out.println("duration :" + t.stop());
        t.start();
        easy(0, 98798, 0);
        System.out.println("duration :" + t.stop());
    }


    //0-n 有几个数字 包含 0
    public static int coutD(int n, int d) {


        String nstr = n + "";
        int l = nstr.length();
        if (d == 0) {
            throw new RuntimeException("error :d !=0 ");
        }
        int[] ar = generateN(l, d);
        int result = 0;

        for (int i = 0; i < l; i++) {
            String c = nstr.charAt(i) + "";

            int cnum = Integer.parseInt(c);
            if (cnum < d) {
            } else if (cnum == d) {
                result += ar[l - i];
                //直接把后面的算出来
                if (i != l - 1)
                    result += Integer.parseInt(nstr.substring(i + 1));
                break;
            } else {
                result += ar[l - i] + (cnum - d - 1) * ((ar[l - i] - 1) / d) + Math.pow(10, l - i - 1) - 1;
            }


        }

        return result;
    }


    //d  内 有几个 数 包含 d
    //d0    内 有几个 数 包含 d
    //d00   内 有几个 数 包含 d
    //d000     内 有几个 数 包含 d
    public static int[] generateN(int n, int d) {
        int[] narray = new int[n + 1];
        narray[1] = 1;

        for (int i = 2; i <= n; i++) {


            //ex:
            //1000  {0-100 101-199 200-999 1000}
            //2000  {0-200 201-299 300-999 1000}
            //   (narray[i - 1] + (int) Math.pow(10, i - 2) - 1 + (9 - d) * ((narray[i - 1] - 1) / d));
            //(narray[i - 1] - 1) / d)   每100 个 含的个数
            narray[i] = (narray[i - 1] + (int) Math.pow(10, i - 2) - 1 + (9 - d) * ((narray[i - 1] - 1) / d)) * d + 1;
            // System.out.println("narray[" + i + "]=" + narray[i]);
        }

        return narray;
    }


    //1 内 有几个 数 包含 d
    //10  内 有几个 数 包含 d
    //100  内 有几个 数 包含 d

    public static int[] generateN2(int n, int d) {


        int[] narray = new int[n + 2];
        narray[1] = d > 1 ? 0 : 1;

        narray[2] = d <= 1 ? 2 : 1;
        int base = 0;
        for (int i = 3; i <= n; i++) {
            base = narray[i - 1];

            //100，100，0-100 101-200 不一样
            if (d <= 1)
                base--;

            //0 特殊

            //假设 10000
            if (d != 0)
                //d=6
                //0-1000 6001-6999 区别考虑  ,6001-6999 都带 6,下面 乘的是 9    ,下面就不考虑  6001-6999
                narray[i] = (int) Math.pow(10, i - 2) - 1;
            else
                //0-1000 6001-7000 区别
                //00XX,10XX,20XX,....90XX 特殊于 0-1000  10 个  Math.pow(10, i - 3)
                //   但 0000,1000,2000,考虑过了、，减10

                //写出来 我都有点不懂 。。。。


                // narray[i] = ((int) Math.pow(10, i - 3) - 1)*10;
                narray[i] = (int) Math.pow(10, i - 2) - 10;
            narray[i] += 9 * base + 1;

            //0,1 边界特殊 100，1000，。。。
            if (d <= 1) narray[i]++;

        }

        return narray;
    }

    //0-n 有几个数字 包含 0
    public static int coutD2(int n, int d) {

        int base = 0;
        String nstr = n + "";
        int l = nstr.length();

        if (l == 1) {
            if (n >= d)
                return 1;
            return 0;
        }
        int[] ar = generateN2(l, d);
        int result = 0;

        for (int i = 0; i < l; i++) {
            String c = nstr.charAt(i) + "";

            int cnum = Integer.parseInt(c);
            if (cnum < d) {

                result += ar[l - i] * cnum;
            } else if (cnum == d) {

                result += d * ar[l - i];
                //直接把后面的算出来
                if (i != l - 1)
                    result += Integer.parseInt(nstr.substring(i + 1));
                //0,1 特殊
                if (d > 1)
                    result += 1;
                break;
            } else {
                base = ar[l - i];
                //0,1特殊
                if (d <= 1)
                    base--;
                result += (cnum - 1) * base;
                //0 特殊
                if (d != 0)
                    result += Math.pow(10, l - i - 1);
                else
                    result +=  ar[l - i] ;

            }


        }

        return result;
    }

    public static void main(String[] args) {


        /*int[] a1 = generateN(9, 1);
        System.out.println(Arrays.toString(a1));*/


       /*  int[] a2 = generateN2(9, 0);


        System.out.println(Arrays.toString(a2));*/
        Time t = new Time();
        t.start();
        System.out.println(coutD2(45645, 2));
        System.out.println("duration :" + t.stop());
        t.start();
        easy(0, 45645, 2);

        System.out.println("duration :" + t.stop());
    }

}