• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            coding everyday

            編程面試題 https://interview.codeplex.com

            C++博客 首頁 新隨筆 聯(lián)系 聚合 管理
              12 Posts :: 2 Stories :: 7 Comments :: 0 Trackbacks
            微博上@陳利人會不定時的發(fā)一些程序員的面試題,覺得挺有意思,有時會去寫代碼做一下。最近他開了個微信公眾號:待字閨中 (id: daiziguizhongren),推送這些面試題目和網(wǎng)友的一些好的解答。看到他出的面試題目是促使我開這個博客的另一個重要原因。:)

            本文正是關于他出的題目:給一個整數(shù)數(shù)組,找到其中包含最多連續(xù)數(shù)的自己,比如給:15,7,12,6,14,13,9,11,則返回5:[11,12,13,14,15]。最簡單的方法是sort然后scan一遍,但是要O(nlgn)。有什么O(n)的方法嗎?

            跟他確認了下,對空間復雜度有沒有什么要求,能不能用map這樣的輔助數(shù)據(jù)結構,他說沒有限制。

            我的想法就是,用一個map<int, int>,它的key是一個起始的數(shù)字,value是這個起始數(shù)字起連續(xù)的個數(shù)。這樣這個數(shù)組遍歷一遍下來,只要map維護好了,自然就能得到最長的連續(xù)子串了,并且算法復雜度應該是O(n)。(不考慮map函數(shù)實現(xiàn)的復雜度)
            前面說了維護好map就可以了,那么怎么來維護這個map呢?
            1. 取出當前的整數(shù),在map里看一下是否已經存在,若存在則直接取下一個,不存在轉2 (為什么要看是否已經存在,因為題目沒有說不會有重復的數(shù)字。)
            2. 查看下map里面當前數(shù)字的前一個是否存在,如果存在,當前的最長長度就是前一個最長長度+1
            3. 查看下map里面當前數(shù)字的后一個是否存在,如果存在,那么就將以下一個數(shù)字開始的子串的最后一個更新下,因為本來沒有連上的2個子串,因為當前數(shù)字的出現(xiàn)連起來了
            4. 接著再看下前面數(shù)字是否存在,如果存在,就更新以這個數(shù)字結尾的子串的第一個數(shù)字的連續(xù)子串長度,原因同上
            算法就是如上所示了,我們拿例子演練一遍
            1)   首先給定15,這個時候map里面沒有15也沒有14和16,那么這個執(zhí)行完了之后map是map[15] = 1;
            2)   然后遇到7,同上,也沒有6,7和8,所以執(zhí)行玩了之后變成map[7]=1, map[15]=1;
            3)   12同上,map[7]=1, map[12]=1, map[15]=1;
            4)   接下來是6,6就不一樣了,因為7存在的,所以執(zhí)行上面第3步之后,map[6]=2,map[7]=2,map[12]=1,map[15]=1;
            5)   14的情況跟6一樣,結果是map[6]=2,map[7]=2,map[12]=1,map[14]=2,map[15]=2;
            6)   13的情況相對復雜一些,因為12和14都存在了 ,所以它會執(zhí)行以上1,2,3,4的所有4步:首先12存在,所以13的最長子串是2,14存在,所以會更新到14起始的最后一個數(shù)字的最長長度,這里就是15的長度=它自己的加上13的長度,也就是4,同時我們把13的長度也改成4,最后因為12存在,我們要更新以12結尾的連續(xù)子串的開始處,本例中就是12自己,12對應更新成4
            7)   最后是11,11的前面一個數(shù)字不存在,后一個數(shù)字存在,也就是要執(zhí)行以上1,3,第3步結束的時候已經是11和15都更新成5了。最后的結果也就是5,并且是從11起始的。

            下面上代碼:
              1 int find_longest_consecutive_items(int *list, int size) {
             2     map<intint> mapping;
             3     int max = 0;
             4     // The start point for the longest chain
             5     int start = 0;
             6 
             7     for (int i=0; i<size; i++) {
             8         if (mapping.find(list[i]) == mapping.end()) {
             9             int cur = list[i];
            10             // Set current position as the start point for this potential longest chain
            11             int cur_start = cur;
            12             mapping.insert(make_pair(cur, 1));
            13 
            14             map<intint>::iterator prev = mapping.find(cur - 1);
            15             map<intint>::iterator next = mapping.find(cur + 1);
            16 
            17             if (prev != mapping.end()) {
            18                 // If previous number exists, increase current consecutive count
            19                 mapping[cur] = prev->second + 1;
            20             }
            21 
            22             if (next != mapping.end()) {
            23                 // Update the last one in the chain with the consecutive count from the one before current position
            24                 int last = next->first + next->second - 1;
            25                 mapping[last] = mapping[cur] = mapping[cur] + mapping[last];
            26             }
            27 
            28             if (prev != mapping.end()) {
            29                 // Update the first one in the chain with the consecutive count from the one after current position
            30                 int first = prev->first - prev->second + 1;
            31                 mapping[first] = mapping[cur];
            32 
            33                 // Use the first one as the start point for the whole chain
            34                 cur_start = first;
            35             }
            36 
            37             if (mapping[cur_start] > max) {
            38                 start = cur_start;
            39                 max = mapping[cur_start];
            40             }
            41         }
            42     }
            43 
            44     cout << "Longest consecutive items:";
            45     for (int i=0; i<max; i++) {
            46         cout << " " << start + i;
            47     }
            48     cout << endl;
            49 
            50     return max;
            51 }

            完整代碼
            posted on 2013-07-01 22:05 everyday 閱讀(1704) 評論(4)  編輯 收藏 引用 所屬分類: 算法

            Feedback

            # re: 最多連續(xù)數(shù)的子集 2013-07-02 10:50 passinger
            這樣做map里面存儲過多冗余信息,比如從11到15,應該只存儲(11,5),而不是5個成員。  回復  更多評論
              

            # re: 最多連續(xù)數(shù)的子集 2013-07-03 06:23 everyday
            @passinger
            good catch. :) 謝謝。
            為什么這么做是因為方便找出是否存在當前這個數(shù)字的前一個和后一個,以便連接起來。比如一開始有11,12的出現(xiàn),如果只有一個entry是(11, 2)的話,這時出來13的話,要找連續(xù)會困難一些,但是如果有(11,2), (12, 2)的存在,O(1)就能找到。這里確實是以空間換時間。  回復  更多評論
              

            # re: 最多連續(xù)數(shù)的子集 2013-07-08 10:38 jun_deng
            map中的value到底代表的什么?  回復  更多評論
              

            # re: 最多連續(xù)數(shù)的子集 2013-07-12 14:30 everyday
            @jun_deng
            代表的是包含它的連續(xù)序列的長度,但不是每個都up to date的。只維護了那個序列中的開始和最后就夠了,中間沒有意義。  回復  更多評論
              

            亚洲七七久久精品中文国产| 亚洲国产精品无码久久九九| 伊人久久大香线蕉综合Av| 久久精品国产色蜜蜜麻豆| 久久久老熟女一区二区三区| 久久精品国产亚洲麻豆| 久久人人爽人人爽人人片AV麻豆| 麻豆久久久9性大片| AV色综合久久天堂AV色综合在| 精品无码久久久久久久动漫| 久久99精品国产麻豆宅宅| 99久久人妻无码精品系列蜜桃| 精品久久人人爽天天玩人人妻 | 国产女人aaa级久久久级| 国产精品成人久久久| 无码人妻久久一区二区三区蜜桃| 久久青青草原国产精品免费| 久久夜色精品国产噜噜亚洲AV| 热99RE久久精品这里都是精品免费| 亚洲欧洲日产国码无码久久99| 久久www免费人成看国产片| 青青草原精品99久久精品66| 青青草国产97免久久费观看| 久久电影网一区| 久久精品国产亚洲av影院| 久久精品无码一区二区WWW| 久久久久国产亚洲AV麻豆| 久久国产视频99电影| 国产91色综合久久免费分享| 99国产欧美精品久久久蜜芽| 无码八A片人妻少妇久久| 亚洲?V乱码久久精品蜜桃| 97久久精品国产精品青草| 一本一道久久综合狠狠老| 色天使久久综合网天天| 久久久久久国产精品美女 | 亚洲七七久久精品中文国产| 久久丝袜精品中文字幕| 久久久久综合中文字幕| 久久综合给合综合久久| 中文字幕亚洲综合久久菠萝蜜|