LintCode刷题1312

描述

中文English

给定整数n，计算出现在小于等于n的所有非负整数中的数字1的总数。

您在真实的面试中是否遇到过这个题？是

题目纠错

样例

样例1

输入: 13
输出: 6
说明:
有以下五个数字包含"1"： 1, 10, 11(两个1), 12, 13

样例2

输入: 100
输出: 21

第一个版本：

时间超过

public static int countDigitOne(int n) {
        int count = 0;
        for (int i = 1; i <= n; i++) {
            int temp = i;
            while (temp > 0) {
                if (temp % 10 == 1)
                    count++;
                temp /= 10;
            }
        }
        return count;
    }

第二个版本：

public class Solution {

    static int param_totle[] = new int[10];
    static int param_special[] = new int[10];

    public static void param_totle_num() {
        param_totle[0] = 2;
        int PTP=1;
        for (int i = 1; i < 10; i++) {
            PTP *=10;
            int x = i;
            param_totle[i] = (i+1)*PTP+1;
        }
        param_special[0]=0;
        for(int i = 1;i<10;i++){
            param_special[i]=param_totle[i]-9*param_totle[i-1]+7;
        }
    }

    public static int countDigitOne(int n) {
        param_totle_num();
        int count = 0;
        //数组对应的索引
        int index = 0;

        //临时变量
        int temp_n = n/10;
        int temp_head = 0;
        int startNum = 1;
        while (temp_n>0){
            temp_head = temp_n%10;
            temp_n/=10;
            index++;
            startNum*=10;
        }
        startNum*=temp_head;

        if(temp_head==9){
            count=param_totle[index-1]*2+param_special[index]+(param_totle[index-1]-1)*6;
        }else if(temp_head==1){
            count=param_totle[index-1];
        }else if(temp_head==2){
            count=param_totle[index-1]+param_special[index];
        }else if(temp_head==0){
            count=0;
        }else{//temp=3,4,5,6,7,8
            count=param_totle[index-1]+param_special[index]+(temp_head-2)*(param_totle[index-1]-1);
        }
        System.out.println("count: "+count+" startNum: "+startNum);

        //3001-3333
        for (int i = startNum+1; i <= n; i++) {
            int temp = i;
            while (temp > 0) {
                if (temp % 10 == 1)
                    count++;
                temp /= 10;
            }
        }
        return count;

    }


    public static void main(String[] args) {
        System.out.println("start:" + System.currentTimeMillis() / 1000);
        System.out.println("count:" + countDigitOne(328524377));

        //328524377
        //370170378

        //110208530
        //97620675
        System.out.println("end:" + System.currentTimeMillis() / 1000);
    }
}