刷leetcode系列之数字中的1
刷leetcode系列之数字中的1
公众号guangcity
发布于 2019-09-20 15:31:40
发布于 2019-09-20 15:31:40
数字中的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)
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-02-22，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录