数字1出现的个数（leetcode每日打卡）前言一、两手一摊，遍历与我无关二、痛定思痛总结

87 阅读 0 评论 58 点赞

我是靠谱客的博主专注小蜜蜂，最近开发中收集的这篇文章主要介绍数字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的次数的时候，
个位每从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;
}