剑指 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 条评论
登录 后参与评论

相关文章

来自专栏码匠的流水账

聊聊HystrixThreadPool

hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/HystrixThreadPool.java

921
来自专栏一个会写诗的程序员的博客

java.base.jmod

/Library/Java/JavaVirtualMachines/jdk-9.jdk/Contents/Home/jmods$ jmod list java....

1172
来自专栏码匠的流水账

spring security reactive获取security context

本文主要研究下reactive模式下的spring security context的获取。

2112
来自专栏前端儿

Web 前端颜色值--字体--使用,整理整理

颜色值 CSS 颜色使用组合了红绿蓝颜色值 (RGB) 的十六进制 (hex) 表示法进行定义。对光源进行设置的最低值可以是 0(十六进制 00)。最高值是 2...

2742
来自专栏linux驱动个人学习

高通Audio中ASOC的machine驱动

ASoC被分为Machine、Platform和Codec三大部分,其中的Machine驱动负责Platform和Codec之间的耦合以及部分和设备或板子特定的...

1K4
来自专栏ml

md5算法原理一窥(其一)

    首先,需要了解的事,md5并不是传说中的加密算法,只是一种散列算法。其加密的算法并不是我们说所的那样固定不变,只是一种映射的关系。 所以解密MD5没有现...

3957
来自专栏菩提树下的杨过

linq to sql取出随机记录/多表查询/将查询出的结果生成xml

在手写sql的年代,如果想从sqlserver数据库随机取几条数据,可以利用order by NewId()轻松实现,要实现多表查询也可以用select * f...

2236
来自专栏码匠的流水账

聊聊FilterSecurityInterceptor

本文就来研究一下spring security的FilterSecurityInterceptor

531
来自专栏c#开发者

XML Encryption in .Net

XML Encryption in .Net One of the new features being introduced with the Whidbey...

4457
来自专栏增长技术

App Guide相关

##TourGuide https://github.com/worker8/TourGuide

812

扫码关注云+社区