400. Nth Digit

每次做題的時(shí)候都會(huì)發(fā)覺(jué)自己真是菜得一逼寺董,這不這道easy題就沒(méi)做出來(lái)失暂。

題目描述

在數(shù)字隊(duì)列1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11....的無(wú)窮隊(duì)列里找到第nth個(gè)數(shù)绸硕,比如第11個(gè)數(shù)是數(shù)字0盯拱。

我(超)的(時(shí))解法

public class Solution {
    public static int findNthDigit(int n) {
        if (n <= 9) {
            return n;
        } else {
            int x = 0, i = 1;
            while (x <= n) {
                x += count(i);
                if (x == n) {
                    break;
                }
                if (x <= n) {
                    i++;
                }
            }
            int off = x - n;

            if (off != 0) {
                return findNthDigitInNum(i, off);

            } else {
                return (i % 10);
            }

        }

    }

    public static int count(int num) {
        int count = 1;
        while (num / 10 != 0) {
            num /= 10;
            count++;
        }
        return count;
    }

    public static int findNthDigitInNum(int num, int nth) {
        int x = 0, s = 10;
        for (int i = 0; i <= nth; i++) {
            x = num % 10;
            num /= 10;
        }

        return x;
    }
}

思路蠻簡(jiǎn)單瓢对,定一個(gè)變量初始值為0宴咧,每次加上新的數(shù)字的長(zhǎng)度拳喻,最后如果超出了給定的結(jié)果姜盈,就退回若干位去找該位上的數(shù)字低千,如果剛好等于給定的長(zhǎng)度,對(duì)當(dāng)前的數(shù)字求最低位馏颂。
在測(cè)試用例1000000000的時(shí)候超時(shí)了....沒(méi)想到什么好的解決方法示血,又無(wú)恥的去看了下Top Solution

Top Solution

Top Solution里的解法跟我的解法思想上是類似,但是他用了很不錯(cuò)的技巧

public int findNthDigit(int n) {
        int len = 1;
        long count = 9;
        int start = 1;

        while (n > len * count) {
            n -= len * count;
            len += 1;
            count *= 10;
            start *= 10;
        }

        start += (n - 1) / len;
        String s = Integer.toString(start);
        return Character.getNumericValue(s.charAt((n - 1) % len));
    }

我的解法里是一個(gè)一個(gè)疊加數(shù)字的長(zhǎng)度救拉,他則是把相同位數(shù)的數(shù)字一次性減掉难审,這里效率高了很多。再看start += (n-1) / len亿絮,這里的n-1是為了不跳到下一個(gè)數(shù)字去告喊,這個(gè)語(yǔ)句可以得出滿足條件的最后一個(gè)數(shù)字是什么。(n-1) % len這個(gè)表達(dá)式的作用是求出最后一個(gè)數(shù)字是第幾位上的派昧,這里的n-1是因?yàn)?code>s.charAt()的開始下標(biāo)是0黔姜。
舉個(gè)列子,假設(shè)輸入:n=11蒂萎,那么執(zhí)行上面這個(gè)表達(dá)式時(shí)(2-1) % 2秆吵,即返回最大數(shù)字的第二位,此時(shí)start的值為10五慈,所以結(jié)果為0帮毁。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市豺撑,隨后出現(xiàn)的幾起案子烈疚,更是在濱河造成了極大的恐慌,老刑警劉巖聪轿,帶你破解...
    沈念sama閱讀 219,490評(píng)論 6 508
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件爷肝,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)灯抛,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,581評(píng)論 3 395
  • 文/潘曉璐 我一進(jìn)店門金赦,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人对嚼,你說(shuō)我怎么就攤上這事夹抗。” “怎么了纵竖?”我有些...
    開封第一講書人閱讀 165,830評(píng)論 0 356
  • 文/不壞的土叔 我叫張陵漠烧,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我靡砌,道長(zhǎng)已脓,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,957評(píng)論 1 295
  • 正文 為了忘掉前任通殃,我火速辦了婚禮度液,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘画舌。我一直安慰自己堕担,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,974評(píng)論 6 393
  • 文/花漫 我一把揭開白布曲聂。 她就那樣靜靜地躺著霹购,像睡著了一般。 火紅的嫁衣襯著肌膚如雪句葵。 梳的紋絲不亂的頭發(fā)上厕鹃,一...
    開封第一講書人閱讀 51,754評(píng)論 1 307
  • 那天,我揣著相機(jī)與錄音乍丈,去河邊找鬼剂碴。 笑死,一個(gè)胖子當(dāng)著我的面吹牛轻专,可吹牛的內(nèi)容都是我干的忆矛。 我是一名探鬼主播,決...
    沈念sama閱讀 40,464評(píng)論 3 420
  • 文/蒼蘭香墨 我猛地睜開眼请垛,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼催训!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起宗收,我...
    開封第一講書人閱讀 39,357評(píng)論 0 276
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤漫拭,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后混稽,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體采驻,經(jīng)...
    沈念sama閱讀 45,847評(píng)論 1 317
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡审胚,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,995評(píng)論 3 338
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了礼旅。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片膳叨。...
    茶點(diǎn)故事閱讀 40,137評(píng)論 1 351
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖痘系,靈堂內(nèi)的尸體忽然破棺而出菲嘴,到底是詐尸還是另有隱情,我是刑警寧澤汰翠,帶...
    沈念sama閱讀 35,819評(píng)論 5 346
  • 正文 年R本政府宣布龄坪,位于F島的核電站,受9級(jí)特大地震影響奴璃,放射性物質(zhì)發(fā)生泄漏悉默。R本人自食惡果不足惜城豁,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,482評(píng)論 3 331
  • 文/蒙蒙 一苟穆、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧唱星,春花似錦雳旅、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,023評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至哎榴,卻和暖如春型豁,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背尚蝌。 一陣腳步聲響...
    開封第一講書人閱讀 33,149評(píng)論 1 272
  • 我被黑心中介騙來(lái)泰國(guó)打工迎变, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人飘言。 一個(gè)月前我還...
    沈念sama閱讀 48,409評(píng)論 3 373
  • 正文 我出身青樓衣形,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親姿鸿。 傳聞我的和親對(duì)象是個(gè)殘疾皇子谆吴,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,086評(píng)論 2 355

推薦閱讀更多精彩內(nèi)容