首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
整数中1出现的次数(从1到n整数中1出现的次数)
[编程题]整数中1出现的次数(从1到n整数中1出现的次数)
热度指数:400964
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 64M,其他语言128M
算法知识视频讲解
输入一个整数 n ,求 1~n 这 n 个整数的十进制表示中 1 出现的次数
例如, 1~13 中包含 1 的数字有 1 、 10 、 11 、 12 、 13 因此共出现 6 次
注意:11 这种情况算两次
数据范围:
进阶:空间复杂度
,时间复杂度
示例1
输入
13
输出
6
示例2
输入
0
输出
0
马上挑战
算法知识视频讲解
提交运行
算法知识视频讲解
添加笔记
邀请回答
收藏(3462)
分享
提交结果有问题?
0个回答
162篇题解
添加回答
515
推荐
咩咩jiang
class Solution {
public:
int NumberOf1Between1AndN_Solution(int n)
{
//主要思路:设定整数点(如1、10、100等等)作为位置点i(对应n的各位、十位、百位等等),分别对每个数位上有多少包含1的点进行分析
//根据设定的整数位置,对n进行分割,分为两部分,高位n/i,低位n%i
//当i表示百位,且百位对应的数>=2,如n=31456,i=100,则a=314,b=56,此时百位为1的次数有a/10+1=32(最高两位0~31),每一次都包含100个连续的点,即共有(a%10+1)*100个点的百位为1
//当i表示百位,且百位对应的数为1,如n=31156,i=100,则a=311,b=56,此时百位对应的就是1,则共有a%10(最高两位0-30)次是包含100个连续点,当最高两位为31(即a=311),本次只对应局部点00~56,共b+1次,所有点加起来共有(a%10*100)+(b+1),这些点百位对应为1
//当i表示百位,且百位对应的数为0,如n=31056,i=100,则a=310,b=56,此时百位为1的次数有a/10=31(最高两位0~30)
//综合以上三种情况,当百位对应0或>=2时,有(a+8)/10次包含所有100个点,还有当百位为1(a%10==1),需要增加局部点b+1
//之所以补8,是因为当百位为0,则a/10==(a+8)/10,当百位>=2,补8会产生进位位,效果等同于(a/10+1)
int count=0;
long long i=1;
for(i=1;i<=n;i*=10)
{
//i表示当前分析的是哪一个数位
int a = n/i,b = n%i;
count=count+(a+8)/10*i+(a%10==1)*(b+1);
}
return count;
}
};
编辑于 2015-08-18 23:21:43
回复(86)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
基础数学
来自:
编程题练习卷
难度:
0条回答
3462收藏
184215浏览
热门推荐
通过挑战的用户
查看代码
薄砂马拉丁大
2023-02-27 12:46:35
Elastic...
2023-02-05 18:55:56
十八+
2022-12-25 13:20:30
Crazycuo
2022-12-03 14:41:56
牛客34890...
2022-10-09 21:53:31
相关试题
牛牛的超市
动态规划
基础数学
评论
(5)
车站建造问题
基础数学
评论
(40)
线段树编号问题
基础数学
评论
(2)
左旋转字符串
字符串
评论
(1870)
来自
编程题练习卷
调整数组顺序使奇数位于偶数前面
数组
评论
(3240)
来自
编程题练习卷
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题
import java.util.*; public class Solution { public int NumberOf1Between1AndN_Solution(int n) { } }
class Solution { public: int NumberOf1Between1AndN_Solution(int n) { } };
# -*- coding:utf-8 -*- class Solution: def NumberOf1Between1AndN_Solution(self, n): # write code here
class Solution { public int NumberOf1Between1AndN_Solution(int n) { // write code here } }
function NumberOf1Between1AndN_Solution(n) { // write code here } module.exports = { NumberOf1Between1AndN_Solution : NumberOf1Between1AndN_Solution };
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param n int整型 # @return int整型 # class Solution: def NumberOf1Between1AndN_Solution(self , n: int) -> int: # write code here
package main /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param n int整型 * @return int整型 */ func NumberOf1Between1AndN_Solution( n int ) int { // write code here }
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 * @return int整型 */ int NumberOf1Between1AndN_Solution(int n ) { // write code here }
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # @param n int整型 # @return int整型 # class Solution def NumberOf1Between1AndN_Solution(n) # write code here end end
object Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param n int整型 * @return int整型 */ def NumberOf1Between1AndN_Solution(n: Int): Int = { // write code here } }
object Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param n int整型 * @return int整型 */ fun NumberOf1Between1AndN_Solution(n: Int): Int { // write code here } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param n int整型 * @return int整型 */ public int NumberOf1Between1AndN_Solution (int n) { // write code here } }
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param n int整型 * @return int整型 */ export function NumberOf1Between1AndN_Solution(n: number): number { // write code here }
public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param n int整型 * @return int整型 */ func NumberOf1Between1AndN_Solution ( _ n: Int) -> Int { // write code here } }
struct Solution{ } impl Solution { fn new() -> Self { Solution{} } /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param n int整型 * @return int整型 */ pub fn NumberOf1Between1AndN_Solution(&self, n: i32) -> i32 { // write code here } }
13
6
0
0