专栏首页大闲人柴毛毛剑指 offer代码解析——面试题32统计1到n中1出现的次数

剑指 offer代码解析——面试题32统计1到n中1出现的次数

本题的分析过程均在代码注释中:

/**
 * 题目:输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。
 * @author 大闲人柴毛毛
 * @date 2016年3月22日
 */
public class CountOne {
	/**
	 * 分析:本题常规思路如下:
	 * 从1开始遍历这n个数,分别统计每个数中“1”出现的次数。
	 * 那么,问题就转化为“如何统计一个整数中1出现的次数?”
	 *
	 * 首先我们需要知道以下结论:
	 * 1.设整数为n,则n%10就能取到n的个位数;
	 * 2.n除以10后再取整其实就是把n的个位数砍掉。
	 * 基于上述结论,我们只要循环以下操作即可:
	 * 1.求整数n的余数;
	 * 2.判断余数是否为1,若为1则将计数器加1;
	 * 3.重复上述过程,直到n变成为0为止。
	 * 代码如下:
	 */
	
	/**
	 * 统计1-n中“1”出现的次数
	 * @param n
	 * @return 返回1出现的次数(若返回-1表示程序出错)
	 */
	public static int countOne(int n){
		//若n<1
		if(n<1){
			System.out.println("n<1!");
			return -1;
		}
		
		//创建计数器,用于统计1的个数
		int count = 0;
		
		//统计1-n中“1”出现的次数
		for(int i=1;i<=n;i++){
			//temp用于记录当前整数
			int temp = i;
			while(temp>0){
				//判断个位数是否为1
				if(temp%10==1)
					count++;
				//将temp的个位数砍掉
				temp /= 10;
			}
		}
		
		return count;
	}
	
	/**
	 * 上述方法需要对1-n分别进行扫描,而且对每个数还要进行m次扫描(m为数字的位数),因此效率并不高。
	 * 网上有一些大神提出了一些更高效的方法,但过于巧妙,只能就题论题,缺乏推广的价值,因此这里不再介绍。
	 * 若有更高效且具有推广价值的方法,欢迎交流。
	 */
	
	
	/**
	 * 测试
	 */
	public static void main(String[] args){
		System.out.println(countOne(13));
	}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java基础全面解析——Java语言基础

    高级编程语言的组成:关键字、标识符、注释、常量与变量、语句、函数、数组,下面一一介绍各个组成元素。 a)  关键字 i.  定义:关键字是一些英文单词,但在ja...

    大闲人柴毛毛
  • Java中被你忽视的四种引用

    正文开始前,有必要先了解下Java内存分配与回收,请见我的相关博文。 —————————————————————————————————— Java的数据类型分...

    大闲人柴毛毛
  • Linux软件安装(二)——RPM与YUM

    Linux软件管理程序 上一篇文章介绍了使用源码编译的方式安装Linux软件,虽然操作比较简单,但仍有如下不足之处: 1. 源码需要经过编译成二进制文件后...

    大闲人柴毛毛
  • JVM面试重点:虚拟机类加载机制

    类从被加载到虚拟机内存中开始,到卸载出内存为止,整个生命周期包括:加载、验证、准备、解析、初始化、使用、卸载;其中,验证、准备和解析统称为连接,如下图所示:

    三哥
  • HDU 2561 第二小整数

    第二小整数 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

    Angel_Kitty
  • 天天算法 LeetCode-96-不同的二叉搜索树

    https://leetcode-cn.com/problems/unique-binary-search-trees/

    灵魂画师牧码
  • 7-1 统计工龄 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • TP6验证器的使用

    4手机号码:不能为空,不能少于11个字符,不能多于11个字符,必须是数字,必须是可用的手机号码

    叫我可儿呀
  • P1508 Likecloud-吃、吃、吃

    题目背景 问世间,青春期为何物? 答曰:“甲亢,甲亢,再甲亢;挨饿,挨饿,再挨饿!” 题目描述 正处在某一特定时期之中的李大水牛由于消化系统比较发达,最近一直处...

    attack
  • 【hdu 5918】Sequence I(KMP)

    饶文津

扫码关注云+社区

领取腾讯云代金券