剑指offer 面试题32:从1到n整数中1出现的次数(Leecode233. Number of Digit One)
提交网址: http://www.nowcoder.com/practice/bd7f978302044eee894445e244c7eee6?tpId=13&tqId=11184
题目:
输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。
例如输入12,从1到12这些整数中包含1的数字有1,10,11,12。所以1一共出现了5次。
样例输入:
12 -3 样例输出: 5 0
233. Number of Digit One
提交网址: https://leetcode.com/problems/number-of-digit-one/
Total Accepted: 18383 Total Submissions: 74646 Difficulty: Hard ACrate: 24.6%
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.
Hint:
分析:
可以用统计学方法来计算,假设从个位开始,每次假设某一位的数字是1,然后统计剩下位数的数字中满足条件的可能情况数。其时间复杂度为O(log n).
考虑把某一个位的数字设成1后,分析他位置有多少种选择。然后把每个数字位取1而有的选择都加起来就可以了。将输入的整数n分割成3部分:当前位之前部分front, 当前位curDigit和当前位之后部分back. 比如: n=1350, 考虑将倒数第2个数字5置为1, 此时mod = 102-1= 101 = 10, front = 13, back = 0, curDigit =5=(n/mod)%10=(1350/10)%10 (当前位被置为1的数原来为5).
然后来分析其他位置有多少种选择:
(1) 如果将n的个位数置为1,xxx1
该位的数字置1之前为0,
card({000, 001...134}),满足条件的数共有135个
(2) 如果将n的十位数置为1,xx1x
该位的数字置1之前5>1,
card({000, 001...139}),共140个
(3) 如果将n的百位数置为1,x1xx
该位的数字置1之前3>1,
2*card({00, 01...99}),共200个
(4) 如果将n的千位数置为1,1xxx
该位的数字置1之前=1,
card({000,001...350}),共351个
于是所求的值count=135+140+200+351=826个1
牛客网OJ AC代码(C++版):
#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;
}
简洁版 leetcode上已AC(代码A):
#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;
}
最简洁的写法(C++版):
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;
}
};
最简洁的写法(Python版):
#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'
Python中加入中文注释: 在文件头上写入:#coding=gbk 或 #coding=utf-8 虽然#这个符号在python中表示注释,其实如果用pydev或者别的其他IDE来编写程序的时候,如果开头不声明保存编码格式,会默认使用ASCII码保存,那么代码中有中文就会有问题,即使你的中文是在注释里面。
很明显,关键在这句: countOne += (n/mod+8)/10*mod + (n/mod%10 == 1)*(n%mod + 1); 简而言之,这是上述代码A的缩写。依旧是根据当前位置的数字curDig做判断,恰有三种需要考虑,0,1,>=2. (1) 如果当前位curDig=0,n/mod得到的值,最后一个肯定是0,front部分假如加上了8,就是xxx8这样的数字。然后n/mod%10就是0,刚好除尽。所以此时 (n/mod+8)/10*mod + (n/mod%10 == 1)*(n%mod + 1)就等价于: front*mod 商*10^(i-1) 【当前位的数curDig为n中倒数第i个数字】 (2) 如果当前位curDig=1,n/mod得到的值,最后一个肯定是1,front部分假如加上了8,就是xxx9这样的数字,依旧不变。然后n/mod%10就是1,刚好是1。所以此时 (n/mod+8)/10*mod + (n/mod%10 == 1)*(n%mod + 1)就等价于: front*mod + back+ 1 商*10^(i-1) + 余数 + 1. (其实不用判断首位是不是1得可能性,因为首位是1的时候,会得到(1+8)/10*mod,9/10 是0)。 (3) 如果当前位curDig>1,front部分假如加上了8,(n/mod+8)/10肯定进位,而当前位n/mod%10==1必然不成立,此时(n/mod%10 == 1)*(n%mod + 1)=0。故此时(n/mod+8)/10*mod + (n/mod%10 == 1)*(n%mod + 1)就等价于: (front+1)*mod (商+1)*10^(i-1)
牛客网OJ AC代码(Java版):
文件名: offer32.java
// 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);
}
}
Java版的时间复杂度略高,在leetcode中提交会TLE: Status: Time Limit Exceeded Last executed input: 824883294