最近2018中文字幕在日韩欧美国产成人片_国产日韩精品一区二区在线_在线观看成年美女黄网色视频_国产精品一区三区五区_国产精彩刺激乱对白_看黄色黄大色黄片免费_人人超碰自拍cao_国产高清av在线_亚洲精品电影av_日韩美女尤物视频网站

題目描述

數(shù)字以 0123456789101112131415…的格式序列化到一個(gè)字符序列中。在這個(gè)序列中，第 5 位（從下標(biāo) 0 開(kāi)始計(jì)數(shù)）是 5，第 13 位是 1，第 19 位是 4，等等。

請(qǐng)寫(xiě)一個(gè)函數(shù)，求任意第 n 位對(duì)應(yīng)的數(shù)字。

• 0 <= n < 2^31

題目樣例

示例

• 輸入：n = 3

• 輸出：3

• 輸入：n = 11

• 輸出：0

題目思考

1. 能否找到什么規(guī)律?

解決方案

思路

• 觀察序列本身:
• 0~9 只占 1 位, 共 10 個(gè)
• 10~99 占 2 位, 共 90 個(gè)
• 100~999 占 3 位, 共 900 個(gè)
• 1000~9999 占 4 位, 共 9000 個(gè)
• ...
• 為了保持一致, 我們可以將 1 位的時(shí)候改成從 1 開(kāi)始, 把 n=0 作為特殊情況, 這樣 1 位也只有 9 個(gè), 即 1~9
• 這樣我們就很容易發(fā)現(xiàn)規(guī)律, 假設(shè)當(dāng)前位數(shù)是 le:
• 每一位的開(kāi)始值 start 是                  pow(10, le-1)
• 每一位的數(shù)字?jǐn)?shù)目是                  9*start
• 每一位的字符總數(shù)則是                  9*start*le (因?yàn)槊總€(gè)數(shù)字有 le 個(gè)字符)
• 所以我們可以逐漸增加位數(shù), 統(tǒng)計(jì)當(dāng)前總共的字符個(gè)數(shù)
• 假設(shè) le 位數(shù)下的字符總數(shù)是 cnt, le+1 下的字符總數(shù)是 nextcnt, 那么如果 n 在                 [cnt, nextcnt)范圍內(nèi), 那就說(shuō)明 n 落在的數(shù)字一定有 le 位
• 這樣一來(lái), 我們只需要定位 n 具體對(duì)應(yīng)到的數(shù)字, 以及所在數(shù)字的第幾位即可
• 而由于每個(gè)數(shù)字占有 le 位, 所以 n 對(duì)應(yīng)的數(shù)字就是                 start+(n-cnt)/le, 而具體 n 是在該數(shù)字的第幾位, 則是                 (n-cnt)%le
• 下面的代碼對(duì)必要步驟有詳細(xì)的解釋, 方便大家理解

復(fù)雜度

• 時(shí)間復(fù)雜度                 O(logN)
• 只需要按位數(shù)遍歷即可, n 的位數(shù)是 logN
• 空間復(fù)雜度                 O(1)
• 只使用了常數(shù)個(gè)變量

代碼

class Solution:
    def findNthDigit(self, n: int) -> int:
        if n == 0:
            return 0
        # 初始化計(jì)數(shù)值為1, 因?yàn)閟tart最開(kāi)始是1, 此時(shí)已經(jīng)有1個(gè)字符了
        cnt = 1
        # 初始化位數(shù)為1位
        le = 1
        while n >= cnt:
            # 求當(dāng)前位數(shù)下的start
            start = 10**(le - 1)
            # 求當(dāng)前位數(shù)+1情況下的字符總數(shù)
            nexcnt = cnt + 9 * start * le
            if n <= nexcnt:
                # 當(dāng)前n落在范圍內(nèi), 找對(duì)應(yīng)的數(shù)字和該數(shù)字中n對(duì)應(yīng)的位(偏移量)
                i, offset = divmod(n - cnt, le)
                num = start + i
                # 將數(shù)字轉(zhuǎn)成字符串, 其偏移量下標(biāo)對(duì)應(yīng)的位即為所求
                return int(str(num)[offset])
            # 更新字符總數(shù), 同時(shí)位數(shù)加1, 繼續(xù)循環(huán)
            cnt = nexcnt
            le += 1