我是靠谱客的博主 专注小蜜蜂,最近开发中收集的这篇文章主要介绍数字1出现的个数(leetcode每日打卡)前言一、两手一摊,遍历与我无关二、痛定思痛总结,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

文章目录

  • 前言
  • 一、两手一摊,遍历与我无关
  • 二、痛定思痛
    • 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
注:这种取每位数字的方法很常用,比如把一个整数按位放进数组里。

测试用例很乐观,我以为我行了,谁知道:
timeout 一生之敌
在这里插入图片描述

这题也逐渐暴露出了他狠毒的面容。
很显然,最简单想到的方法行不懂,因为太复杂所以超时了。

二、痛定思痛

1.分析题目

一种思路是分析每位上1出现的次数
以n=123为例

  1. 个位

统计个位出现的1的次数的时候,
个位每从0~9完整循环一次,1就出现一次,
那问题就变成了:循环了几次呢?
循环一次会+10,问题就演变成123从0开始,一共加了几个10
很显然是12个
123=1210 + 3
最后个位
未循环完整*的一次即0~3也拨过了1,所以个位一共出现了12+1=13次1。

  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次

  1. 百位

最后来看百位
个位每循环一次整体+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每日打卡)前言一、两手一摊,遍历与我无关二、痛定思痛总结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(79)

评论列表共有 0 条评论

立即
投稿
返回
顶部