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

相关文章

来自专栏机器学习从入门到成神

Python中排序函数sort()和sorted()的区别(这是一个大坑)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

1781
来自专栏Fundebug

JavaScript正则表达式进阶指南

1068
来自专栏IT笔记

乐视2017暑假实习生笔试题二分查找之JAVA实现

试题 对一个含有20个元素的有序数组做二分查找,数组起始下标为1,则查找A[2]的比较序列的下标为() A. 9,5,4,2 B. 10, 5, 3, 2 C....

3747
来自专栏JackieZheng

初探JavaScript(四)——作用域链和声明提前

前言:最近恰逢毕业季,千千万万的学生党开始步入社会,告别象牙塔似的学校生活。往往在人生的各个拐点的时候,情感丰富,感触颇深,各种对过去的美好的总结,对未来的展望...

1835
来自专栏北京马哥教育

Python 的正则表达式彩蛋

虽然我觉得在 Python 的标准库里的确有不少很恶心的库,但是 re 库肯定不属于这种。尽管它真的有年头没有更新了,但是在我看来,仍不失为动态语言中最好的库...

2637
来自专栏企鹅号快讯

R包系列——stringr包

stringr包是Hadley Wickham大神贡献的R包之一,主要用于字符串的处理。对于经常需要对数据进行预处理的分析人员来说,简直是一把“利器”,可谓是上...

2236
来自专栏cmazxiaoma的架构师之路

一个Java小白通向数据结构算法之旅(5) - 选择排序

1034
来自专栏专知

关关的刷题日记12——Leetcode 189. Rotate Array 方法1、2、3

关小刷刷题12 – Leetcode 189. Rotate Array 方法1、2、3 题目 Rotate an array of n elements to...

3498
来自专栏程序猿DD

第四章 正则表达式回溯法原理

第四章 正则表达式回溯法原理 学习正则表达式,是需要懂点儿匹配原理的。 而研究匹配原理时,有两个字出现的频率比较高:“回溯”。 听起来挺高大上,确实还有很多人...

2076
来自专栏编程

从零基础开始学习PHP(七)

貌似有两周没有更新文章了、"忙"都是借口、不过我是真的忙、一天瞎忙活。希望多多理解。在这里我要感谢那些支持我的小伙伴、因为有你们的支持、我知道我要对我的文章以及...

1805

扫码关注云+社区