首页 > 试题广场 >

整数中1出现的次数（从1到n整数中1出现的次数）

[编程题]整数中1出现的次数（从1到n整数中1出现的次数）
  • 热度指数：402619 时间限制：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
算法知识视频讲解
开通博客
头像 江南好___
发表于 2021-06-19 19:20:39
精华题解 描述 题目描述 输入一个整数 n ，求1～n 这 n 个整数的十进制表示中1出现的次数。例如，1~13 中包含1的数字有1、10、11、12、13 因此共出现6次。 示例 输入：n = 13 输出：6这道题简单意思就是：找出小于等于 n 的非负整数中数字 1 出现的个数。 初看这道题，无非都会想到一 展开全文
去ta的博客 赞 (20) 回复(7) 收起
头像 LaN666
发表于 2021-06-19 11:24:36
精华题解 解题思路： 我们看到题目要求 “输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数”。其实就是求从1-n这n个数中，每一个数的计数位上出现的1的个数的总和。 所以我们只需要知道在某个计数位上面1出现次数的计算方法即可求解这道题目，下面我们分为几种情况讨论： 1、当前位上的值等于0 我 展开全文
去ta的博客 赞 (20) 回复(3) 收起
头像 牛客题解官
发表于 2022-04-25 19:08:57
精华题解 题目的主要信息： 输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数 举一反三： 学习完本题的思路你可以解决如下题目： JZ17. 打印从1到最大的n位数 JZ15. 二进制中1的个数 方法一：按位统计法（推荐使用） 思路： 数字都是由位数组成，某一位上面是1的个数是一定的，因此我 展开全文
去ta的博客 赞 (7) 回复(0) 收起
头像 Peterliang
发表于 2021-07-18 21:18:41
精华题解 题意分析 给出1-n之间的数字，我们需要找出所有的数里面的1个数位的个数有多少。 思路分析 解法一 暴力求解 直接暴力写法，从1-n开始进行遍历，我们对每个数进行数位的拆解，然后统计1的个数就行了。 代码如下 我们从1-n进行遍历直接判断，时间复杂度为O(n) 我们的代码只开了少部分变量存 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 小明同学#
发表于 2019-10-01 17:10:25
public int NumberOf1Between1AndN_Solution(int n) {     int cnt = 0;     for 展开全文
去ta的博客 赞 (147) 回复(12) 收起
头像 猪客
发表于 2019-10-08 09:15:19
#java 为什么大家要想的这么复杂呢 虽然我的方法比较low,可能慢 但是我2分钟就写完了呀(#^.^#) import java.util.*; public class Solution { public int NumberOf1Between1AndN_Solution(in 展开全文
去ta的博客 赞 (76) 回复(29) 收起
头像 Ironxin
发表于 2020-03-11 15:11:11
思路1：将所有数字转换成字符串，再遍历每个字符串的每一位。当n位数较大时，时间复杂度会比较高思路2：与思路1相似，每次对10取模，然后判断个位数是否为1，当n位数大时，时间复杂度也比较高.思路3及4：既然蛮力不好用，自然需要找规律，也就是1出现的规律。 首先附上一段思路1和2的代码，然后对思路3进 展开全文
去ta的博客 赞 (70) 回复(3) 收起
头像 偏执先森
发表于 2019-12-05 16:02:50
双指针6行代码，对于每一个数求1的个数，然后加起来。对于每一个数来说求个位只需要mod10就好，然后将原数/10 替换 原数，再mod10求得十位，以此类推，可得各十百千。。。位。 然后循环--即可 public int NumberOf1Between1AndN_Solution(int n) { 展开全文
去ta的博客 赞 (44) 回复(5) 收起
头像 常喝水
发表于 2019-12-24 10:58:50
将一个数字中1出现的次数拆成个、十、百位中1出现次数的和以321为例： cnt = 32 + 1，把321拆成高位32和1，固定个位是1，高位的取值可以是0~31共32个数，由于低位为1大于0，所以高位还可以取32（即数字321），则个位上1出现的次数是32+1=33 cnt = 30 + 10 展开全文
去ta的博客 赞 (24) 回复(4) 收起
头像 我真搞不懂
发表于 2019-07-28 22:23:56
public class Solution {     public int NumberOf1Between1AndN_Solution(int n) {         //根据当前位置为各位1 十位10 百位100等 来计算 &nbs 展开全文
去ta的博客 赞 (13) 回复(0) 收起
头像 科学研究院_李彬
发表于 2020-01-19 23:45:16
本人太菜没有看懂大部分人推崇的方法，试了下数学归纳法，发现也不错。先来做如下归纳：0-9中有1个1；10-19中有1+10=11个1；20-29中有1个1；...0-99中有11*1+1*9=20个1；100-199中有20+100=120个1；（希望大家认真理解为什么是+100）0-999中有20 展开全文
去ta的博客 赞 (13) 回复(3) 收起
头像 AJSpade
发表于 2020-04-16 11:55:41
思路是依次计算每个位上的1的个数。算法复杂度O(logN) 首先拿n = 190举例，理解这么做是可行的，然后再想办法用代码实现它。 1）首先，求个位上出现1的个数，即个位固定为1，那么就是1，11，21，31，...... ，181，这里个位上共有19个1。 2）接下来，求十位上出现的1的个数，即 展开全文
去ta的博客 赞 (9) 回复(0) 收起
头像 一叶浮尘
发表于 2019-08-18 12:07:12
求出1-13的整数中1出现的次数,并算出100-1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1 展开全文
去ta的博客 赞 (9) 回复(5) 收起
头像 NekoMan
发表于 2021-10-07 04:41:52
找规律，数学问题，求公式就对了 我们把0-n(0-n和1-n结果一样)位数字低位对齐排列，为了更直观一点，我们将高位的0也补全，例如： 不难发现，如上图蓝色标记，个位的数字是0-9（出现1次）循环的，10个数一个周期，那么十位呢？ 0-9（出现10次）循环的，100个数一个周期;百位0-9（出现 展开全文
去ta的博客 赞 (7) 回复(0) 收起

问题信息

基础数学
来自：编程题练习卷
难度：
1276条回答 186485浏览

热门推荐

通过挑战的用户

查看代码

相关试题

整数中1出现的次数（从1到n整数中1出现的次数）

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号