求1到2008080808之间含有数字7的个数总和? 其实没那么复杂

在CSDN上看到的题..看到很多人的算法都挺复杂的..

从小的数字看起..10里有1个100是10的10倍.但是100里还有70-79都是..所以就是 1*9+10=19个
那么1000就是  (1*9+10)*9+100
10000就是  ((1*9+10)*9+100)*9+1000嗯.是麻烦.所以要把公式提炼出来把这个算术式分析一下。就可以得到公式
这个东西算出来就是9*9*9+810+900+1000=9的三次方*10的0次方+9的2次方*10的一次方 + 9的1次方*10的2次方+9的0次方*10的3次方
                                                                  (9*9*9)              (810)                                (900)                           (1000)

如果把  求1到2008080808之间含有数字7的个数总和?  简化为 求 10000以内的含有数字7的数的应该这样9的3次方*10的0次方 + 9的2次方*10的1次方 + 9的1次方*10的2次方  +  9的0次方+10的3次方
其实就是要求N位数的含有某数字的个数先求出N为数的最小数a然后计算a以内有多少个acount=9的n-2次方*10的0次方 + .... + 9的0次方*10的n-2次方.
然后用该整数除以a得到该整数是a的b倍..再用b*acount.得出该整数减去该整数除以a的余数包含的所有包含该数字的数的数量依次类推..

这个可以一直做下去。 2008080808 = 2000000000  先求出 2000000000 包含的个数  8000000  再求8000000内包含的个数      800   ...        8  ...

(改天附上程序实现)


一下是程序实现:

package org.phyeas.demo;

public class Main {
    public static void main(String[] args) {
        System.out.println(lookUpForHasNumber(2008080808 , 7));
    }

    /** *//**
     * 查找从从1到end含有数字hasNumber的个数
     * 
     * @param end
     *            结束
     * @param hasNumber
     *            含有某数字
     * @return
     */
    public static int lookUpForHasNumber(long end, int hasNumber) {
        int count = 0;
        long less = getLess(end);
        while (less > 10) {
            int n = (int) Math.log10(less);
            long bei = end / less;
            int tempCount = 0;
            for (int i = n - 1, j = 0; i >= 0; i--, j++) {
                tempCount += Math.pow(9, i) * Math.pow(10, j);
            }
            if (bei >= 1) {
                if (bei > hasNumber) {
                    tempCount = (int) ((int) (tempCount * (bei - 1)) + less);
                } else if (bei == hasNumber) {
                    tempCount = (int) (tempCount * bei) + 1;
                } else {
                    tempCount = (int) (tempCount * bei);
                }
            }
            count += tempCount;
            
            end = end - less * bei;
            less = getLess(end);
        }
        if (less > hasNumber) {
            count = count + 1;
        }
//        System.out.println("count=" + count);
        return count;
    }

    /** *//**
     * 获取与这个数字位数相同的最小数
     * 
     * @param number
     * @return
     */
    public static long getLess(long number) {
        if (number > 10) {
            String str = String.valueOf(number);
            StringBuffer nStr = new StringBuffer("1");
            for (int i = 1; i < str.length(); i++) {
                nStr.append("0");
            }
            return Long.parseLong(nStr.toString());
        }
        return number;
    }
}

最后结果:1229473242