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.
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.
Solution 1: Iteravet the bits. for certain bit: [a1..aj]x[b1..bi]: a=[a1..aj], b=[b1..bi]. Depends on x>1, x=1 and x<1. Calculate the combinations add to result.
public class Solution {
public int countDigitOne(int n) {
if (n<=0) return 0;
int res=0;
for (long w=1; w<=n; w*=10) {
int a=(int)(n/(w*10)), b=(int)(n%w), x=(int)(n%(w*10)/w);
if (x>1) res+=(a+1)*w;
else if (x==1) res+=a*w+b+1;
else res+=a*w;
}
return res;
}
}
public class Solution {
public int countDigitOne(int n) {
int weight=1, res=0;
while (true) {
int t1=n/weight/10, t2=n%weight, dig=n/weight%10;
res+=t1*weight;
if (dig==1) res+=t2+1;
else if (dig>1) res+=weight;
if (t1==0) break;
weight*=10;
}
return res;
}
}
没有评论:
发表评论