前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >剑指Offer - 面试题43. 1~n整数中1出现的次数(找规律+公式)

剑指Offer - 面试题43. 1~n整数中1出现的次数(找规律+公式)

作者头像
Michael阿明
发布2020-07-13 17:01:57
3410
发布2020-07-13 17:01:57
举报

1. 题目

输入一个整数 n ,求1~n这n个整数的十进制表示中1出现的次数。

例如,输入12,1~12这些整数中包含1 的数字有1、10、11和12,1一共出现了5次。

代码语言:javascript
复制
示例 1:
输入:n = 12
输出:5

示例 2:
输入:n = 13
输出:6
 
限制:
1 <= n < 2^31

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

leetcode 同题:233. 数字 1 的个数

2. 解题

代码语言:javascript
复制
class Solution {
public:
    int countDigitOne(int n) {
    	int i = 1, count = 0, high, cur, low;
    	while(n/i)//遍历每个位
    	{
    		high = n/(10*i);//高位
    		cur = (n/i)%10;//当前位
    		low = n-(n/i)*i;//低位
    		if(cur == 0)
    			count += high*i;
    		else if(cur == 1)
    			count += high*i+low+1;
    		else
    			count += (high+1)*i;
    		i *= 10;
    	}
    	return count;
    }
};

递归参考:leetcode题解

代码语言:javascript
复制
class Solution {	
public:
    int countDigitOne(int n) {
    	if(n <= 0)
    		return 0;
    	string s = to_string(n);
    	int high = s[0]-'0';
    	int Pow = pow(10, s.size()-1);
    	int last = n - high*Pow;
    	if(high == 1)
    		return countDigitOne(Pow-1)+countDigitOne(last)+last+1;
    		// 最高位是1,如1234, 此时pow = 1000,那么结果由以下三部分构成:
            // (1) dfs(pow - 1)代表[0,999]中1的个数;
            // (2) dfs(last)代表234中1出现的个数;
            // (3) last+1代表固定高位1有多少种情况。
    	else
    		return high*countDigitOne(Pow-1)+countDigitOne(last)+Pow;
    }
};
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-03-16 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 题目
  • 2. 解题
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档