2015年11月3日星期二

Leetcode 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.
For example:
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;
    }
 }  

没有评论:

发表评论