概述
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
文章目录
- 前言
- 一、两手一摊,遍历与我无关
- 二、痛定思痛
- 1.分析题目
- 2.分析一个比大部分答案简单易懂的答案
- 总结
前言
这是一道leetcode上题,原题链接数字1的个数。题目描述仅有一行却被标为困难让我着实有些不解。不解的同时却又十分惊喜于“有朝一日我也能做一道困难了?”
但做下来发现并不是那么简单
一、两手一摊,遍历与我无关
最简单的思路,最复杂的步骤。
int countDigitOne(int n){
int result=0;
for(int i=0;i<=n;i++){//遍历一遍
int number=i;
while(number!=0){//分割每位数字
if(number%10==1)
result++;
number=number/10;
}
}
return result;
}
该程序的大体思路是遍历从0到n的所有整数,每个整数都从末位到高位数一遍出现1的个数,数字上出现一个1则在result上加一。
为保持控制循环的计数器i不在循环中被改变
故将i赋给number
则number是当前遍历到的数
再用number%10来取出最末位
例:123%10=3
最后再让number/10来让原先的倒数第二位成为末位。
例:123/10=12
注:这种取每位数字的方法很常用,比如把一个整数按位放进数组里。
测试用例很乐观,我以为我行了,谁知道:
这题也逐渐暴露出了他狠毒的面容。
很显然,最简单想到的方法行不懂,因为太复杂所以超时了。
二、痛定思痛
1.分析题目
一种思路是分析每位上1出现的次数
以n=123为例
- 个位
统计个位出现的1的次数的时候,
个位每从0~9完整循环一次,1就出现一次,
那问题就变成了:循环了几次呢?
循环一次会+10,问题就演变成123从0开始,一共加了几个10
很显然是12个
123=1210 + 3
最后个位未循环完整*的一次即0~3也拨过了1,所以个位一共出现了12+1=13次1。
- 十位
现在来看十位。
同样的思路,
统计个位的时候我们考虑的是0~9完整循环了几次
统计十位的时候我们要考虑的就是10~90循环了几次
十位每循环一次整体就会加100
123=1*100+23
所以十位上0~9循环了1次,仅出现过一个1。
所以整体每+100,十位出现一遍1.
对吗? 当十位的数字为1的时候,开始一个一个的往上加
11
12
13
.
.
.
19
百位一次,相当于十位十次。
所以整体加100的时候。
所以十位上的1出现了10次
对吗
#别忘了还有未完整循环的23
虽然没有循环完整,但是只要十位>=2,
就相当于出现了10次
- 百位
最后来看百位
个位每循环一次整体+10
十位每循环一次整体+100
那么
百位每循环一次整体+1000
123=0 *1000+123
所以从千位来看百位,百位1出现了零次
再从低位看百位
100(百位上第一次出现1)到123(百位上最后出现1),
百位上的1一共出现了24次
所以13+20+24=57
总结:当前位上出现的1的个数取决于完整循环的次数和未完整循环的“漏网之鱼”
假设n=K1K2K3K4K5…Kn。Kn为个位
那么第i(1<=i<=n)位上1出现的次数要看从1到i-1和从i到n两个部分
即左边的所有高位,右边的所有低位
左边的高位控制该位上0~9完整的循环次数
右边的低位控制未完整循环的次数
如果该位上等于1,则未完整循环次数为K(i-1)K(i-2)…Kn
如果该位上大于1,则次数为Ki0000…0(n-i个零)
2.分析一个比大部分答案简单易懂的答案
没错,是分析,是从评论区扒过来的,不是自己写的啊。
这里有三个问题
第一:计数器i从1开始以10为倍数变化是为什么?
第二:res+=(n/i*10)*i的逻辑是什么?
第三:条件判断语句里是拿谁在和1比?为什么和1比?
答一:从个位开始到最高位结束,以位为单位统计1出现的个数
答二:在统计当前位上完整循环所出现1的个数
我们以n=123为例来分析
我们就先看循环内的第一行
第一遍循环i=1:123/10=12;
个位上0~9完整循环了12次。
第二遍循环i=10:(123/(10*10))10=10;
十位上0~9完整循环了一次,相当于出现10次1
第三遍循环i=100: (123/(10010))10=0
百位上0~9完整循环了零次,出现零个1
所以第一行的res+=(n/i*10)*i
就是在统计当前位上因完整循环,所出现的1的个数
所以下面的条件判断后的执行体就是在统计因未完整循环所出现的1的个数喽
答三:(1)在拿当前位的值和1比
他取出当前位的方法就是先整除10的幂,让当前位变成个位,然后再取模10,得到当前位。
(2)因为等于1意味着,当前位1出现的次数要由低位数控制,res+=低位数+1
取低位数的方法:n%当前位位权(即i),所以res+=n%i+1
;
大于1意味着可以直接加加当前位的位权,而当前位的位权就是i,所以res+=i;
总结
这道题分为三个步骤
1.分割每位数
2.统计完整循环次数(从高位看)
3.统计未完整循环次数(从低位看)
然后让我们来!合上别人家的答案,自己写一遍!
于是
int countDigitOne(int n){
int number=n;
int result=0;
for(long i=1;i<=n;i*=10){
result += number/(10)*i;//number每次循环都会右移一位,原有的末尾舍弃,同样是 保留当前位高位的数字和整体的位数 的操作
if(number%10>1)
result+=i;
else if(number%10==1){
result+=n%i+1;
}
number=number/10;//右移一位,原有的末尾舍弃
}
return result;
}
ps:我对number=number/10怕是有什么执念。。。
希望我有讲明白
虽然这题可能对于好多人来讲太简单了
感觉也没什么单拎出来讲解的必要
但是是困扰了我一阵子的题
是不用接触数据结构就能懂的方法
对我这种没学过数据结构的同学很友好
是很清一色的答案
于是拿出来分享给大家看
感谢你看到这里,希望有帮助到你
如果觉得对你有帮助的话可以点个赞哦
最后
以上就是专注小蜜蜂为你收集整理的数字1出现的个数(leetcode每日打卡)前言一、两手一摊,遍历与我无关二、痛定思痛总结的全部内容,希望文章能够帮你解决数字1出现的个数(leetcode每日打卡)前言一、两手一摊,遍历与我无关二、痛定思痛总结所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复