[LC 233] Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

写一个我能看的懂的解题思路-_-

Go through each digit. Count the possible numbers under n if the current digit is 1.

例如一个数用abcdef表示,一共6位。假设现在已经scan到d的位置,这个数字可分割成三个部分(abc)d(ef)。有三种情况:

1 如果当前d是0。

例如(314)0(59)。若使d这一位为1,那么abc的位置可以取0-313, 一共314个选择。d是1。ef的位置可以取0-99所有可能,一共100个选择。加一起是abc * 100个可能的数字。

2 如果当前d是1.

例如(314)1(59)。若使d这一位为1,那么abc的位置可以取0-314,一共315个选择。d是1。ef的位置,当abc是0-313的时候,可以取0-99,当abc是314的时候,只能取0-59。所以加一起是abc * 100 + ef + 1个可能的数字。

3 如果当前d是>=2。

例如(314)2(59)。若使d这一位为1,那么abc的位置可以取0-314,一共315个选择。d是1。ef的位置可以取0-99,一共100个选择。加一起是(abc + 1)* 100

总结一下,对(abc)d(ef)
d == 0, count += abc * 100
d == 1, count += abc * 100 + ef + 1
d >= 2, count += abc * 100 + 100;

    public int countDigitOne(int n) {
        if (n <= 0) return 0;         
        int count = 0;         
        int x = 1;         
        int a = n;       
        while (a > 0) {
            int digit = a % 10;
            a /= 10;
            int b = n % x;
            if (digit == 0) count += a * x;
            else if (digit == 1) count += a * x + b + 1;                
            else count += (a + 1) * x;
            x *= 10;
        }
        return count;
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s