• <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

            #面試編程題# 個不能少:有k個有序的數(shù)組,請找到一個最小的數(shù)字范圍。使得這k個有序數(shù)組中,每個數(shù)組都至少有一個數(shù)字在該范圍中。例如:1:{ 4, 10, 15, 24, 26 }2: { 0, 9, 12, 20 }3: { 5, 18, 22, 30 }。所得最小范圍為[20,24],其中,202中,223中,241中。

             

            剛看到這個問題的時候,感覺好難啊,這怎么才能找出來呢?有時候我覺得多看幾遍題目還是有好處的,讀書百遍其義自見啊。這個題目有幾個關(guān)鍵點:所有的數(shù)組是有序的、每個數(shù)組至少有一個數(shù)字出現(xiàn)在那個范圍里。

             

            圍繞著后面一點,我想,我們至少得維護一個kitem東西,然后每次從這個東西里面移掉一個放進去一個,尼瑪,這怎么感覺像是個隊列嘛。隊列?把最小的移掉,放進去它所在數(shù)組的后一個。咦,東西(隊列)里面是不是還是k個元素,并且來自k個數(shù)組?

             

            看上去可行,組織下思路。

             

            如果我們這里的數(shù)據(jù)結(jié)構(gòu)用隊列顯然是不能滿足要求的,因為我們不能很快得出隊列中最小和最大的值,也就得不到范圍,那么如果隊列是有序的,是不是可以解決這個問題呢?簡單的推敲下,答案是肯定的。我們用priority_queue應(yīng)該是可以解決這個問題的。

             

            1. 首先,我們把k個數(shù)組中的第一個元素都壓到p_q里面去,記下來最大的那個,因為最小的那個可以通過top()得到。只需要最大的那個就能得到range,對吧。如例中的:p_q: { 0, 4, 5 }, max_data: 5

             

            1. 然后,把第一個(最小的)彈出來,這個時候得到一個range,如果這個range比之前的小,用這個range。把彈出來的那個元素所在的數(shù)組的后一個壓進去,如果這個值比最大的那個大,把它標(biāo)成最大的。如例中:0出來,9進去,p_q: { 4, 5, 9 } max_data: 9, range {0, 5}

             

            1. 重復(fù)步驟2,直到某一個數(shù)組遍歷完畢即可。為什么?顯而易見嘛,沒東西壓了啊。:D

             

            為了能比較好的處理,定義了一些輔助的數(shù)據(jù)結(jié)構(gòu):data就是被壓的那個東西,用來定義某個數(shù)組的某個元素,方便找它對應(yīng)的下一個元素;range就是我們最終要求的范圍。

             

            有人會說,面試算法題,用庫里的數(shù)據(jù)結(jié)構(gòu)不太好吧。這個我同意,有些算法題確實用庫里的東西,直接就秒了。如果在面試過程中,面試官也提出類似的質(zhì)疑,那么我們自己實現(xiàn)個類似的數(shù)據(jù)結(jié)構(gòu)總OK吧?這里我們也可以很輕松的實現(xiàn)一個滿足要求的數(shù)據(jù)結(jié)構(gòu)啊。姑且稱之為,sorted_list


             1 template<typename T>
             2 struct node{
             3     T data;
             4     node *next;
             5 };
             6 
             7 template<typename T>
             8 class sorted_list {
             9 public:
            10     void push(const T& t);
            11     void pop();
            12     T top();
            13     // even we can provide both smallest & biggest value, by that way, we don't need to have max_data
            14     T bottom();
            15 private:
            16     node<T> head;
            17     node<T> tail;
            18 };

            部分代碼:
            get_shortest_range

            數(shù)據(jù)結(jié)構(gòu):
            data structures

            完整代碼

            附:出題人的分析。
            http://mp.weixin.qq.com/mp/appmsg/show?__biz=MjM5ODIzNDQ3Mw==&appmsgid=10000075&itemidx=1&sign=46da65072c3062638e80f16599498508
            我覺得本質(zhì)應(yīng)該跟我的算法是一樣的吧。:D, :P
            posted on 2013-07-18 10:14 everyday 閱讀(318) 評論(0)  編輯 收藏 引用 所屬分類: Algorithm
            久久AV高潮AV无码AV| 久久天天躁狠狠躁夜夜avapp | 久久精品国产一区二区 | 久久精品免费大片国产大片| 精品久久久久久无码人妻蜜桃| 久久久久久久亚洲精品 | 免费国产99久久久香蕉| 久久www免费人成看国产片| 欧洲性大片xxxxx久久久| 人妻少妇久久中文字幕 | 丁香色欲久久久久久综合网| 国内精品久久久久影院优| 99精品久久久久久久婷婷| 久久久久久久97| 久久国产美女免费观看精品 | 久久久久亚洲AV无码麻豆| 久久精品国产99久久丝袜| 日韩精品久久久久久免费| 久久精品中文字幕一区| 777米奇久久最新地址| 久久99久久99精品免视看动漫| 国产高潮国产高潮久久久| 偷偷做久久久久网站| 久久97久久97精品免视看| 东京热TOKYO综合久久精品| 久久精品国产亚洲av麻豆蜜芽| 精品久久久无码中文字幕| 69SEX久久精品国产麻豆| 亚洲精品美女久久久久99| 久久99热这里只有精品66| 久久久91人妻无码精品蜜桃HD| 亚洲欧美精品伊人久久| 成人国内精品久久久久影院| 亚洲国产另类久久久精品| 亚洲精品国精品久久99热一| 久久久久久精品久久久久| 亚洲国产成人精品无码久久久久久综合| 久久亚洲国产欧洲精品一| 国产精品毛片久久久久久久| 精品国产一区二区三区久久久狼 | 久久久久人妻精品一区二区三区|