一,题目:输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。
例如输入n=12,从1到12这些整数中包含1
的数字有1,10,11和12,1一共出现了5次。
二,分析:这是一道广为流传的google面试题。
我们每次判断整数的个位数字是不是1。如果这个数字大于10,除以10之后再判断个位数字是不是1。
三,源码
这个思路有一个非常明显的缺点就是每个数字都要计算1在该数字中出现的次数,因此时间复杂度是O(n)。
当输入的n非常大的时候,需要大量的计算,运算效率很低。
下面是一个我看不懂的思路
char num[16];
int len, dp[16][16][2];
int dfs(int pos, int ct, int less)
{
if (pos == len)
return ct;
int &ret = dp[pos][ct][less];
if (ret != -1)
return ret;
ret = 0;
for (int d = 0; d <= (less ? 9 : num[pos] - '0'); d++)
ret += dfs(pos + 1, ct + (d == 1), less || d < num[pos] - '0');
return ret;
}
int NumOf1(int n)
{
sprintf(num, "%d", n);
len = strlen(num);
memset(dp, 0xff, sizeof(dp));
return dfs(0, 0, 0);
}
分享到:
相关推荐
20062 求m*m+1/m+(m+1)*(m+1)+1/(m+1)+(m+2)*(m+2)+1/(m+2)+......+n*n+1/n 13 20063 求1-2/3+3/5-4/7+5/9-6/11+…… 14 20064 求2^1+2^2+2^3+……+2^n 15 第4周(M4) 15 10007 显示图案 (复习...
说明:输入的第1个数表示学生人数(n=9),接着输入的9个成绩中,累加和为628.5(所有小数均保留一位小数输出),平均分为69.8分;平均分以上(A档)有4人,占44.4%,平均分以下(B档)有5人,占55.6%;A档的最低...
1.4.8. 计算 1 到 N 的十进制数中 1 的出现次数 ............................................. 97 1.4.9. 栈的 push、pop 序列[数据结构] .......................................................... 99 1.4.10....
每个学生有3门课(语文、数学、英语)的成绩,写一个程序接收从键盘输入学生的信息,输入格式为:name,30,30,30(姓名,三门课成绩),然后把输入的学生信息按总分从高到低的顺序写入到一个名称"stu.txt"文件中。...
内容及步骤: 1、 设有一个线性表(e0,e1,e2,e3,…,en-2,en-1)存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置,即将数组的前n个原地址内容置换为(en-1,en-2,…,e3,...
1、从弹框中,分两次输入两个数字,分别保存在 a 和 b中 2、如果 a 大于 b的话 ,则交换两个数字的位置 使用 短路&&,扩展赋值运算符,位运算 4、条件运算符(三目运算) 单目(一元)运算符 :++,--,! 双目(二元)...
调用函数求1/2+1/4+...+1/n 77.填空练习(指向指针的指针) 78.找到年龄最大的人 79.字符串排序 80.海滩猴子分桃 81.已知公式条件求数字 82.八进制转换为十进制 83.求0-7所能组成的奇数个数 84.由两个素数之和表示的...
13. 下面程序段中带有下划线的语句的执行次数的数量级是( ) 【合肥工业大学 2001 三、1(2分)】 i:=n*n WHILE i<>1 DO i:=i div 2; 14. 计算机执行下面的语句时,语句 s的执行次数为 _______ 。【南京理工大学 ...
用十进制整数来表示输出的最少位数。 若实际位数多于定义的宽度,则按实际位数输出, 若实际位数少于定义的宽度则补以空格或0。 4.精度 精度格式符以“.”开头,后跟十进制整数。本项的意义是:如果输出数字,则表示...
同样,输入 一个端口 P2,即是将 P2.7、P2.6 至 P2.0,读入到一个字节的 8 第一节: 第一节:单数码管按键显示 单片机最小系统的硬件原理接线图: 1. 2. 3. 4. 接电源:VCC(PIN40)、GND(PIN20)。加接退耦电容 ...
2、 编写并调试一个求(n为整数)的递归函数,希望能在程序运行过程中动态地显示递归函数被调用的轨迹。 [分析讨论] 1、 针对以上实验内容写出相应的参数传递过程并分析结果。 2、 讨论参数的传递的几种形式。 ...
参数 十进制转换数据, 长整数型 .子程序 GetAPIAddress, 整数型, 公开, 失败返回0 .参数 模块名, 文本型, , 如"user32.dll","kernel32.dll" .参数 API, 文本型, , 如“CreateWindowExA” .子程序 Hex2Bin, 字节集...
第三章 8086/8088的寻址方式和指令系统 练习题 一.单项选择题 1.设BX=2000H,SI=3000H,指令MOV AX,[BX+SI+8]的源操作有效地址为( )。 A.5000H B.5008H C.23008H D.32008H 2.设DS=1000H,ES=2000H,BX=...
\3 引用的是第三个代括号的子表达式.注意,由于子表达式可以嵌套在其它子表达式中, 所以它的位置是被计数的左括号的位置. 例如:在下面的正则表达式被指定为 \2: /([Jj]ava([Ss]cript)) \sis \s (fun\w*) / 对...
以“%”开头,[第几个数值$][flags][宽度][.精确度][格式] printf()的引入是为了照顾c语言程序员的感情需要 格式化输出 Formatter;格式化输入 Scanner;正则表达式 输出格式控制: 转义符: \ddd 1到3位8...
1.6.3 创建对多个工作表中相同单元格区域的三维引用 30 1.6.4 更新跨工作簿引用的公式 31 1.7 审核公式 31 1.7.1 使用公式错误检查器 32 1.7.2 定位特定类型的数据 33 1.7.3 追踪单元格之间的关系 33 1.7.4 ...
rs.absolutepage=N 将记录指针移到第N页的第一行 rs.pagesize=N 设置每页为N条记录 rs.pagecount 根据 pagesize 的设置返回总页数 rs.recordcount 返回记录总数 rs.bof 返回记录指针是否超出数据表首端,true表示是...
大括号:大括号用来精确指定匹配元字符出现的次数,例如"/pre{1,5}/"表示匹配的对象可以是"pre"、"pree"、"preeeee"这样在"pr"后面出现1个到5个"e"的字符串。或者"/pre{,5}/"代表pre出现0此到5次之间。 加号:"+...
1 逻辑类问题(A类)-指设计、编码中出现的计算正确性和一致性、程序逻辑控制等方面出现的问题,在系统中起关键作用,将导致软件死机、功能正常实现等严重问题; 接口类问题(B类)-指设计、编码中出现的函数和...
1.12 序列中出现次数最多的元素 1.13 通过某个关键字排序一个字典列表 1.14 排序不支持原生比较的对象 1.15 通过某个字段将记录分组 1.16 过滤序列元素 1.17 从字典中提取子集 1.18 映射名称到序列元素 1.19...