题目:输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。
例如输入12,从1到12这些整数中包含1
的数字有1,10,11和12,1一共出现了5次。
分析:这是一道广为流传的google面试题。用最直观的方法求解并不是很难,但遗憾的是效率不是很高;而要得出一个效率较高的算法,需要比较强的分析能力,并不是件很容易的事情。当然,google的面试题中简单的也没有几道。
首先我们来看最直观的方法,分别求得1到n中每个整数中1出现的次数。而求一个整数的十进制表示中1出现的次数,就和本面试题系列的第22题很相像了。我们每次判断整数的个位数字是不是1。如果这个数字大于10,除以10之后再判断个位数字是不是1。基于这个思路,不难写出如下的代码:
int NumberOf1(unsigned int n);
/////////////////////////////////////////////////////////////////////////////
// Find the number of 1 in the integers between 1 and n
// Input: n - an integer
// Output: the number of 1 in the integers between 1 and n
/////////////////////////////////////////////////////////////////////////////
int NumberOf1BeforeBetween1AndN_Solution1(unsigned int n)
{
int number = 0;
// Find the number of 1 in each integer between 1 and n
for(unsigned int i = 1; i <= n; ++ i)
number += NumberOf1(i);
return number;
}
/////////////////////////////////////////////////////////////////////////////
// Find the number of 1 in an integer with radix 10
// Input: n - an integer
// Output: the number of 1 in n with radix
/////////////////////////////////////////////////////////////////////////////
int NumberOf1(unsigned int n)
{
int number = 0;
while(n)
{
if(n % 10 == 1)
number ++;
n = n / 10;
}
return number;
}
这个思路有一个非常明显的缺点就是每个数字都要计算1在该数字中出现的次数,因此时间复杂度是O(n)。当输入的n非常大的时候,需要大量的计算,运算效率很低。我们试着找出一些规律,来避免不必要的计算。
我们用一个稍微大一点的数字21345作为例子来分析。我们把从1到21345的所有数字分成两段,即1-1235和1346-21345。
先来看1346-21345中1出现的次数。1的出现分为两种情况:一种情况是1出现在最高位(万位)。从1到21345的数字中,1出现在10000-19999这10000个数字的万位中,一共出现了10000(104)次;另外一种情况是1出现在除了最高位之外的其他位中。例子中1346-21345,这20000个数字中后面四位中1出现的次数是2000次(2*103,其中2的第一位的数值,103是因为数字的后四位数字其中一位为1,其余的三位数字可以在0到9这10个数字任意选择,由排列组合可以得出总次数是2*103)。
至于从1到1345的所有数字中1出现的次数,我们就可以用递归地求得了。这也是我们为什么要把1-21345分为1-1235和1346-21345两段的原因。因为把21345的最高位去掉就得到1345,便于我们采用递归的思路。
分析到这里还有一种特殊情况需要注意:前面我们举例子是最高位是一个比1大的数字,此时最高位1出现的次数104(对五位数而言)。但如果最高位是1呢?比如输入12345,从10000到12345这些数字中,1在万位出现的次数就不是104次,而是2346次了,也就是除去最高位数字之后剩下的数字再加上1。
基于前面的分析,我们可以写出以下的代码。在参考代码中,为了编程方便,我把数字转换成字符串了。
#include <iostream>
#include "string.h"
#include "stdlib.h"
#include <stdio.h>
using namespace std;
int NumberOf1(const char* strN);
int PowerBase10(unsigned int n);
/////////////////////////////////////////////////////////////////////////////
// Find the number of 1 in an integer with radix 10
// Input: n - an integer
// Output: the number of 1 in n with radix
/////////////////////////////////////////////////////////////////////////////
int NumberOf1BeforeBetween1AndN_Solution2(int n)
{
if(n <= 0)
return 0;
// convert the integer into a string
char strN[50];
sprintf(strN, "%d", n);
return NumberOf1(strN);
}
/////////////////////////////////////////////////////////////////////////////
// Find the number of 1 in an integer with radix 10
// Input: strN - a string, which represents an integer
// Output: the number of 1 in n with radix
/////////////////////////////////////////////////////////////////////////////
int NumberOf1(const char* strN)
{
if(!strN || *strN < '0' || *strN > '9' || *strN == '\0')
return 0;
int firstDigit = *strN - '0';
unsigned int length = static_cast<unsigned int>(strlen(strN));
// the integer contains only one digit
if(length == 1 && firstDigit == 0)
return 0;
if(length == 1 && firstDigit > 0)
return 1;
// suppose the integer is 21345
// numFirstDigit is the number of 1 of 10000-19999 due to the first digit
int numFirstDigit = 0;
// numOtherDigits is the number of 1 01346-21345 due to all digits
// except the first one
int numOtherDigits = firstDigit * (length - 1) * PowerBase10(length - 2);
// numRecursive is the number of 1 of integer 1345
int numRecursive = NumberOf1(strN + 1);
// if the first digit is greater than 1, suppose in integer 21345
// number of 1 due to the first digit is 10^4. It's 10000-19999
if(firstDigit > 1)
numFirstDigit = PowerBase10(length - 1);
// if the first digit equals to 1, suppose in integer 12345
// number of 1 due to the first digit is 2346. It's 10000-12345
else if(firstDigit == 1)
numFirstDigit = atoi(strN + 1) + 1;
return numFirstDigit + numOtherDigits + numRecursive;
}
/////////////////////////////////////////////////////////////////////////////
// Calculate 10^n
/////////////////////////////////////////////////////////////////////////////
int PowerBase10(unsigned int n)
{
int result = 1;
for(unsigned int i = 0; i < n; ++ i)
result *= 10;
return result;
}
int main()
{
int num = NumberOf1BeforeBetween1AndN_Solution2(112452);
cout<<num<<endl;
}
分享到:
相关推荐
题:输入一个整数n,求1~n这n个整数的十进制表示中1出现的次数。例如,输入12,1~12这些整数中包含1的数字有1,10,11,12一共出现了5次。 解题思路一:直接累加1~n中每个整数中1出现的次数。 class Solution: def ...
n: 1-9 或 01-99 或 001-999。 3.增加固定图像的背景色可以透明。 splashimage [--offset=[type]=[x]=[y]] FILE 类型[type]:bit 7: 透明背景 2016-02-14(yaya) setmenu 函数增加菜单项目背景短/满参数(默认...
“-n发送数据次数”;“-t”指一直ping。 ping -t -l 65550 ip 死亡之ping(发送大于64K的文件并一直ping就成了死亡之ping) ipconfig (winipcfg) 用于windows NT及XP(windows 95 98)查看本地ip地址,ipconfig可用...
【算法 1-1-2】N! 的质因子分解--方法 2 1.建立按从小到大排序的N以下的质数表 2.将所有的质数出现次数表项清零 3.对从2到N之间所有的质数进行遍历,并对每一个质数P进行下列操作:3.1 将质数Pi放入存储单元A中 3.2用...
一个简单的程序,用于计算无法直接加载到内存(1GB)的大文件(100GB)中最常出现的url的topn。 用法 生成测试数据 make data 使用1GB网址进行测试 make test 使用100GB网址运行 make run 算法 根据hash(url)将...
hadoop k-means算法实现java工程的... +"\t<iterTimes>:循环最大次数\n" +"\t<threshold>:聚类中心变化阈值\n" +"\t<K>:聚类中心数目\n" +"\t<vNum>:原始数据属性数目\n" +"\t<numReduce>:reduce数目");
用法当系统中安装了多种打印机时,在Windows 95中PrintSetup()函数打开如图2-1所示的对话框,单击“Setup”按钮设置打印机各种特性。如果系统中只有一个打印机,则直接打开该打印机的打印设置对话框。需要注意的是,...
(1)若队列未满,直接把该页面号a[i]存入队列 (2)若队列已满,删除并返回队头元素,然后把该页面号a[i]存入队列 3、输出置换次数,依次输出置换出的页面 三、程序设计 #define SIZE 4 //SIZE等于分配的内存...
内容及步骤: 1、 设有一个线性表(e0,e1,e2,e3,…,en-2,en-1)存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置,即将数组的前n个原地址内容置换为(en-1,en-2,…,e3,...
include #define maxint 999999 void Dijkstra(int n,int v,int dist[],int prev[],int **table) { //其中n指n个节点,v指起点,dist[i]记录... //将该点的前一个点赋为0,应为它不与v点直接相连 else prev[i] = v;
计数1S(满N秒后执行程序) FLAG_1S EQU 50H ;满1秒取反标志(1秒执行程序1,另一秒执行程序2) FLAG_ADD EQU 51H ;时间设置标记(1代表FLAG对应的时段加1) FLAG_CLOSE EQU 52H ;闪烁显示标记(为0不闪烁) DATE_...
2019.03.25更新:新增“n倍生命值上限”功能,不喜欢直接锁血无敌的玩家可以选择使用。 2019.03.24更新:修正“无限物品”在开启二周目时会保留一周目剧情道具的问题。已经测试至通关,现在“无限物品”应该不会再...
#class sklearn.cluster.KMeans(n_clusters=8, init=’k-means++’, n_init=10, max_iter=300, tol=0.0001, precompute_distances=’auto’, verbose=0, random_state=None, copy_x=True, n_jobs=1, algorithm=’...
input_test = data((aaaaaa+bbbbbb+1):m,1:n-1); output= data(1:aaaaaa,n); output_test = data((1+aaaaaa+bbbbbb):m,n); M=size(input,2); %输入节点个数 N=size(output,2); %输出节点个数 n=6; %隐形节点个数 ...
另外,该工具在统计SQL执行信息时,会对SQL语句进行一定的变换, 如果SQL语句中含有数据或字符型等常量,这些常量将会被变换成$1,$2, ..., $n。 例如: select * from test where size > 100 将会被变换成 select *...
当出现提示符(如#时)开始操作 # cd /etc # cp passwd.old passwd (就是你刚刚保存的那个文件) # chown root:security passwd # reboot //查看内存信息两部曲: # lsdev -C | grep mem mem0 Available 00-00 Memory #...
例如,用户登录后,按一下“Alt+ F2”键,用户就可以看到上面出现的“login:”提示符,说明用户看到了第二个虚拟控制台。然后只需按“Alt+ F1”键,就可以回到第一个虚拟控制台。一个新安装的Linux系统允许用户使用...
特征可以是'百度一下')验证超时 : 验证代理超时 默认=12 (秒)尝试验证次数 : 尝试验证次数 默认=1 (次)代理生命值 : 提取的代理能被获取几次 默认=1 (次) (比如采集东西的时候就可以设置10-50次)代理最长存活...
图2-1 电子商务数据库E-R图 ----------------------- 电子商务数据库设计全文共3页,当前为第1页。 电子商务数据库设计全文共3页,当前为第2页。 商品一级分类 商品二级分类 商品三级分类 1:N 1:N 从属 编号 ...
编制任意2的整数次幂点数的基-2DIT-FFT和DIF-FFT通用c/c++程序,验证其正确性,并与直接计算DFT比较点数为2的N次方(N=10~16)时运行时间的差异。