劍指offer：整數(shù)中1出現(xiàn)的次數(shù)

題目描述
求出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ù)）。

創(chuàng)新互聯(lián)建站提供成都做網(wǎng)站、網(wǎng)站建設(shè)、外貿(mào)營銷網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計，品牌網(wǎng)站制作，廣告投放等致力于企業(yè)網(wǎng)站建設(shè)與公司網(wǎng)站制作，10年的網(wǎng)站開發(fā)和建站經(jīng)驗,助力企業(yè)信息化建設(shè)，成功案例突破上千多家,是您實現(xiàn)網(wǎng)站建設(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ī)律進(jìn)行歸納總結(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

新聞標(biāo)題：劍指offer：整數(shù)中1出現(xiàn)的次數(shù)
瀏覽地址：http://www.muchs.cn/article46/gehseg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App設(shè)計、微信公眾號、電子商務(wù)、建站公司、微信小程序、虛擬主機(jī)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)