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,耻辱!
没有评论:
发表评论