【算法】从1到n中1出现的个数

缘由

买了两本算法方面的书，每次都是随便翻一翻，前两天睡前随便翻了下，看到这道题觉得很有意思，反复看了好几次看完全明白过来，然后今天趁周末没事在leetcode上面找到这道题自己写了写，特意记录下来。

1. 解法1

首先按照最自然的的思路就是从1到n求每个数字中1出现的个数，无非就是一个循环，然后通过while取模算每个数字的个位数字是否是1

if(n<1)
	return 0
int count=0
for(int i=0;i<=n;i++){
	count+=getCountOf1(i)
}
//计算数字n中1的个数
int getCountOf1(int n){
	int count=0
	while(n!=0){
		if(n%10==1){
			count++
		}
		n/=10
	}
}

大概的解法，基本可以直接pass，因为基本上最差的解法就算是错误解法，平庸即是原罪。

2. 解法2

如果不按照自然解法来解，那就只能通过观察规律的方式来求解。
例如随便整个数68412
首先分为两部分1-8412,8413到68412 ,

2.1 后半部分

8413到68412这部分可以再细分为两个部分：最高位和其他位

2.1.1最高位中出现1的次数

单独把最高位拿出来分析是因为最高位6表明出现的最高位只能是1-6，不像其他位可以是0-9，所以它的情况较为特殊，需要单独分析。

• 最高位中出现1的情况也就是1xxxx，一共就10000种（10000-19999）=10的4次方=10的（n长度-1）次方
• 更特殊的情况就是最高位是1，把这里的68412换成18412，这个时候最高位出现1的情况就只有8413种了即（10000-18412）=18412%10的4次方=n%10的（n长度-1）次方

2.1.2 除了最高位的其他位 出现1的次数

除了最高位，其他位共有四位，每个都可以是0-9，当其中一个数字确定为1了，其他三位的选择共有：10*10*10=1000=10的三次方=10的（n长度-2）次方 种，共有四个数字，则出现1的个数为 4*10*10*10=（n长度-1)*10的（n长度-2）次方

• 这里可以直接按照 “每个位都有0-9这10种选择” 这样计算是因为 8413-68412正好是互补的，60000-68412补齐了0-8412这段的空缺，这就是前面为什么这样成8413-68412的原因之一，万一分成9001-68412那么后半段出现1的个数就没办法这么计算，就得减去不在9001-68412的情况下1的个数，就会变得比较麻烦

2.3 前半部分

1-8412和8413-68412（可以看做1-60000）的情况时相似的，可以进行进行递归调用

整体算法

我在leetcode上用的kotlin，其实和java差不多，领会主要算法步骤就行了

class Solution {
    fun countDigitOne(n: Int): Int {
        if(n<1){
            return 0
        }
        if(n<10){
            return 1
        }
        val length=getLengthOfNum(n)
        //最高位数字
        val topPow = Math.pow(10.toDouble(),(length-1).toDouble()).toInt()
        val topIndex=n/topPow
        //最高位数量
        val topCount=if(topIndex>1) topPow else n%topPow+1
        
        //除了最高位
        val midCount=topIndex*(length-1)*(Math.pow(10.toDouble(),(length-2).toDouble()).toInt())
        //前半部分  递归调用
        val lastCount=countDigitOne(n%topPow)
        return topCount+midCount+lastCount
    }
    private fun getLengthOfNum(number:Int):Int{
        var len=0
        var temp=number
        while (temp!=0){
            len++
            temp /= 10
        }
        return len
    }
}