刷leetcode系列之数字中的1
- 2019 年 10 月 6 日
- 筆記
数字中的1
0.导语
今天开始继续刷leetcode，每两天刷一道题！今天上菜第一道难题：数字中的1。
1.两种暴力破解
1.1 个人精简版
【思想】
暴力法的思想很简单，该精简版为我自己写的，思路是直接循环一次，然后将循环的所有数字先转为字符串，然后转为list，使用list的count方法统计1的个数，累加求和即可实现。
【实现】
class Solution: def countDigitOne(self, n: 'int') -> 'int': total= 0 for i in range(1,n+1): total+=list(str(i)).count('1') return total s = Solution() s.countDigitOne(8888888)
1.2 通俗版
【思想】
这个思想更简单，直接循环，然后获取当前的数，根据1的特性，利用整除来实现，然后统计整除的个数就行。
【实现】
class Solution: def countDigitOne(self, n: 'int') -> 'int': total=0 for i in range(1,n+1): t=i while t: if t%10==1: total+=1 t//=10 return total s = Solution() s.countDigitOne(8888888)
2.精华版
【思想】
该题实际上是一道找规律题，而规律的演变如下面所示：
- 1位数
1-9中，1共出现1次。
- 2位数
10-99中出现的次数，一眼看不出来，就得拆分，如何拆分？
10几都包含1，所以分开，10到19中共10*1=10个(没包含11的个位数1，只计算了高位)，而对于10-19，20-29等等，每个区间段都有一个低位1，所以共有9个区间，有9*1=9个，总共有19个。
- 3位数
100-999，分解为100到199(有10**2=100个)，100-199,200-299…等区间段(有9*20个)。
最后上述的规律为：
f(1) = 1 f(2) = 10 * f(1) + 10 ** 1 f(3) = 10 * f(2) + 10 ** 2 f(n) = 10 * f(n-1) + 10 ** (n-1)
代码实现位：
def get_1number(self,n): if n <= 0: return 0 if n == 1: return 1 return 10 * self.get_1number(n-1) + 10 ** (n-1)
上述的结果只能确定：例如34567这个5位数，10000之前的数中包含的个数是确定的。但是10000到34567中的1怎么确定呢？
首先判断高位是不是1，如果是1，例如34567改为13456，那就是3456+1，如果最高位不是1，那么需要计算0到9999,然后是10000到19999，再然后是20000到29999，最后是30000到34567，分成这几部分求1出现的个数，叠加即可。10000到19999与20000到29999总结为(高位数-1)乘以(0到9999中1的个数)。而30000到34567则为求4567中1的个数，而这部分直接递归即可！
【实现】
class Solution: def countDigitOne(self, n: 'int') -> 'int': if n < 10: return 1 if n >= 1 else 0 weishu = 0 t = n while t: weishu += 1 t //=10 # 获取该数的位数 # 0到9999中1的个数(假设n=34567)，也就是获取位数减一的1的总数 pre_number = self.get_1number(weishu-1) # 取n的最高位 high = int(str(n)[0]) # 取低位数据(还是n=34567，low就是4567) low = n - high * 10 ** (weishu-1) # 高位是1，直接就是非高位数+1(假设n=13456,则10000到13456的出现1的个数就是3457) if high == 1: h_number = low + 1 mid_numbers = h_number else: # 最高位不是1，例如n=34567，那么需要计算0到9999,然后是10000到19999，再然后是20000到29999，最后是30000到34567，分成这几部分求1出现的个数，叠加即可。 # 而下面则是实现从10000到29999中1的个数，那就是高位减一(也就是2)乘以0到9999中1出现的次数。 h_number = 10 ** (weishu - 1) mid_numbers = h_number + pre_number * (high - 1) # 最高位大于1的话，统计每个多位数后面包含的1 # 最后将0到9999中1的个数加上10000到29999中1的个数，然后再加上30000到34567中1的个数就是最终的结果。而最后一部分直接递归即可！ return pre_number + mid_numbers + self.countDigitOne(low) def get_1number(self,n): if n <= 0: return 0 if n == 1: return 1 return 10 * self.get_1number(n-1) + 10 ** (n-1)
