2015年7月16日星期四

[LeetCode] Number of Digit One

Problem:

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

Java Code:

public class Solution {
    public int countDigitOne(int n) {
        if (n <= 0) {
            return 0;
        }
        
        ArrayList<Integer> ones = new ArrayList<Integer>();
        ones.add(0, 0);
        for (int i = 0; Math.pow(10, i) < (double)Integer.MAX_VALUE; i++) {
            ones.add(i + 1, ones.get(i) * 10 + (int)Math.pow(10, i));
        }
        
        int result = 0;
        int k = n;
        for (int i = 0; k > 0; i++) {
            int digit = k % 10;
            if (digit == 1) {
                result += ones.get(i) + (n % ((int)Math.pow(10, i))) + 1;
            } else if (digit > 1) {
                result += digit * ones.get(i) + (int)Math.pow(10, i);
            }
            k = k / 10;
        }
        
        return result;
    }
}

Reference:

http://bookshadow.com/weblog/2015/07/08/leetcode-number-digit-one/

TuCao:

思路参考reference的解法一,交了24遍才AC,耻辱!

没有评论:

发表评论