剑指 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笔记1-用python解决小学生数学题

前几天有人在群里给小编出了个数学题: 假设你有无限数量的邮票,面值分别为6角,7角,8角,请问你最大的不可支付邮资是多少元? 小编掰着手指头和脚趾头算了下,答案...

2769
来自专栏灯塔大数据

每周学点大数据 | No.30前序计数

No.30期 前序计数 Mr. 王:我们再来说说父子关系判定的应用。前序计数是一种非常常用的对树进行处理的方法。前序计数实现的就是对各个节点按照其前序遍...

3317
来自专栏计算机视觉与深度学习基础

Leetcode 22 Generate Parentheses 搜索与DP的纠结

Given n pairs of parentheses, write a function to generate all combinations of ...

1779
来自专栏追不上乌龟的兔子

[多少懂点位运算】续·一行代码解决LeetCode268缺失数字

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。

1494
来自专栏Leetcode名企之路

【Leetcode】54. 螺旋矩阵

给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。 示例 1:

722
来自专栏JavaQ

HashMap扩容拾遗

JDK8中HashMap扩容涉及到的加载因子和链表转红黑树的知识点经常被作为面试问答题,本篇将对这两个知识点进行小结。

682
来自专栏数据结构与算法

洛谷P3807 【模板】卢卡斯定理exgcd

题目背景 这是一道模板题。 题目描述 给定n 求  保证P为prime C表示组合数。 一个测试点内包含多组数据。 输入输出格式 输入格式: 第一行...

3046
来自专栏章鱼的慢慢技术路

牛课堂算法直播题目

1968
来自专栏云霄雨霁

字符串排序----键索引记数法

890
来自专栏数据结构与算法

1005. 存款收益

1005. 存款收益 (Standard IO) 时间限制: 1000 ms  空间限制: 262144 KB  具体限制  题目描述 按年利率R%存入本钱X...

2816

扫描关注云+社区