Wednesday, July 8, 2015

Number of Digit One ~~~~~~~~~

Q:
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.
A:
就是每一位计算有多少个。
分为高一位 有多少个导致现在重复的。  和现在位有多少个1

public class Solution {
    public int countDigitOne(int n) {
        long num1s = 0;
        for(int i =0;i<32;i++){// for each digit
            long div = (long)Math.pow(10,i);
            if(div > n)
                break;
            num1s +=  n/(div*10)* div + helper(n%(div*10),div); // number of repeats  + at this position
        }
        return (int)num1s;
    }
    private long helper(long x,long powerOf10){// get the number of 1s at x's first digit (x/powerOf10 < 10)
        long res = x/powerOf10;
        if(res==0)
            return 0;
        if(res >1)
            return powerOf10;
        return x - res * powerOf10 + 1; // for case x = 10,
    }
}

 这里的关键点是: 如何分解这个答案:  我们的分解方式是:
1: 从低到高,每一位计算
2: 对数字位 i(i = 0 to 31);
     2.1 )看高于它的数字位, 会导致有多少个重复1(在i位上)的。
     2.2) 看改位置:会有多少个重复的1 出现。    也就是 hepler函数。(这里又分为: 该位是否 为  1.    看1 的位置重复完了没有。   )
 


Mistakes:
1:  刚开始 计算高位重复的,给减了一




No comments:

Post a Comment