您好,登錄后才能下訂單哦!
題目描述
求出1~13的整數(shù)中1出現(xiàn)的次數(shù),并算出100~1300的整數(shù)中1出現(xiàn)的次數(shù)?為此他特別數(shù)了一下1~13中包含1的數(shù)字有1、10、11、12、13因此共出現(xiàn)6次,但是對于后面問題他就沒轍了。ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負(fù)整數(shù)區(qū)間中1出現(xiàn)的次數(shù)(從1 到 n 中1出現(xiàn)的次數(shù))。
# -*- coding: utf-8 -*-
# @Time : 2019-07-09 16:50
# @Author : Jayce Wong
# @ProjectName : job
# @FileName : numberOf1Between1AndN.py
# @Blog : https://blog.51cto.com/jayce1111
# @Github : https://github.com/SysuJayce
class Solution:
"""
要計算從1到n的數(shù)字中“1”出現(xiàn)的個數(shù),暴力解題的時間復(fù)雜度很高,因此需要先觀察規(guī)律進行歸納總結(jié)。
對于個位數(shù): 0-9有1個,以10為間隔,即10-19有1個,20-29有1個。
對于十位數(shù):10-19有10個,以100為間隔,即110-119有10個
對于百位數(shù):100-199有100個,以1000為間隔,即1100-1199有100個
……
因此觀察寫出通項公式:
(n // (i * 10)) * i + min(max(n % (i * 10) - i + 1, 0), i)
"""
def NumberOf1Between1AndN_Solution(self, n):
if n < 1:
return 0
count = 0
i = 1
while i <= n:
count += n // (i * 10) * i + min(max(n % (i * 10) - i + 1, 0), i)
i *= 10
return count
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。