C++版 - 剑指offer 面试题32：从1到n整数中1出现的次数(leecode233. Number of Digit One) 题解

#include<iostream>
using namespace std;

class Solution {
public:
int NumberOf1Between1AndN_Solution(int n) {
    if(n<=0) return 0;
    long mod = 1;   // 记录置1的位置处于个位、十位、百位、千位等...  
    int count = 0;  // 记录1的数量
    long front, back;
    int curDigit;     // 记录当前位置的数字 
    while(mod <= n){
        front = n/(mod*10);  // 得到某一个位数置1后的商，即当前数之前的部分 
        back = n % mod;          // 得到某一位数置1后的余数，即当前数之后的部分
        curDigit = (n/mod)%10;  // 当前置1的位置原来(置1之前)的数

        if(curDigit > 1)
		{
            count += (front+1)*mod; // 当前位置的数字>1时 
        }
        if(curDigit == 1)   // 当前位置的数字=1时 
		{
            count += (front*mod+back+1);
        }
        if(curDigit == 0)   // 当前位置的数字=0时 
		{
            count += front*mod;
        }
        mod *= 10;     
    }
    return count;
}
};
// 以下为测试部分
int main()
{
	Solution sol;
	int num1=1350;
	int num2=13;
	int num3=-10;
	cout<<sol.countDigitOne(num1)<<endl;
	cout<<sol.countDigitOne(num2)<<endl;
	cout<<sol.countDigitOne(num3)<<endl;	
	return 0;
}

#include<cstdio>
class Solution {
public:
    int countDigitOne(int n) {
    if(n<=0) return 0;
	int curDig, count=0;
	long front, back, mod=1;  // mod用来记录置1的位置处于个位、十位、百位、千位等...     
    while(mod<=n)  // mod每次乘10相对于从低位向高位方向逐一移动，直到超过n时结束循环 
    {
		front=n/(mod*10);
		back=n%mod;
		curDig=(n/mod)%10; 
		
		if(curDig==0) count += front*mod;	      // 以20169为例来验证	
		if(curDig==1) count += front*mod+back+1;		
		if(curDig>1)  count += (front+1)*mod;
		
		mod *= 10;		       	
	}       
    return count;
    }
};

// 以下为测试部分
int main()
{
	Solution sol;
	int num1=sol.countDigitOne(20169);
	int num2=sol.countDigitOne(13);
	int num3=sol.countDigitOne(-10);
	printf("%d\n",num1);  // printf比cout快，OJ提交时建议用printf 
	printf("%d\n",num2);
	printf("%d\n",num3);		
	return 0;
}

class Solution {
public:
    int countDigitOne(int n)
	{
    if(n<=0) return 0;
	long mod=1;  // mod用来记录置1的位置处于个位、十位、百位、千位等...     
    int countOne=0;
        while(mod <= n)
		{
            countOne += (n/mod+8)/10*mod + (n/mod%10 == 1)*(n%mod + 1);
            mod *= 10;
		}
        return countOne;
    }
};

#coding=utf-8
class Solution(object):
    def countDigitOne(self, n):
        countOne, mod = 0, 1
        while mod <= n:
            countOne += (n/mod + 8) / 10 * mod + (n/mod % 10 == 1) * (n%mod + 1)
            mod *= 10
        return countOne
# following is testing part(以下为测试部分)        
sol=Solution();
num1=sol.countDigitOne(20169)
num2=sol.countDigitOne(12)  
num3=sol.countDigitOne(-6)       
print num1,'\n', num2,'\n', num3,'\n'

// import java.io.*;
class Solution
{
	public int NumberOf1Between1AndN_Solution(int n)
	{
	    if(n<=0) return 0;
	    int count = 0; 
	    for(int i=0; i <= n; i++)
	    {
	        String str = String.valueOf(i);
	        for(int j = 0; j < str.length(); j++)
	        {
	            if (str.charAt(j) == '1')
	            {
	                count ++;
	            }
	        }
	    }
    return count;
    }
}

public class offer32
{
	// 以下main()为测试部分
    public static void main(String[] args)
    {
    	Solution sol=new Solution();
    	long num1=sol.NumberOf1Between1AndN_Solution(1350);
    	long num2=sol.NumberOf1Between1AndN_Solution(13);   
    	long num3=sol.NumberOf1Between1AndN_Solution(-5);       		 	
    	System.out.println(num1);
		System.out.println(num2);
		System.out.println(num3);		    	
    }
}