• <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>
            posts - 5, comments - 40, trackbacks - 0, articles - 0

            一道Google面試題的解答

            Posted on 2008-02-17 11:23 Wang Jinbo 閱讀(4089) 評論(9)  編輯 收藏 引用 所屬分類: 算法與數學

            題目:對現在的Stack(棧)數據結構進行改進,加一個min()功能,使之能在常數,即O(1)時間內給出棧中的最小值。可對push()和pop()函數進行修改,但要求其時間復雜度都只能是O(1)。

            題目是在http://akalius.javaeye.com/blog/162156看到的,提供了兩種方法。不幸的是第一種方法是錯誤的,第二種方法也不完全正確。都沒有考慮到連續壓入、彈出和有相同元素的情況。我用的方法是基于第一種的,即在push操作前先將要壓入的數值和當前棧中的最小值“打包”成一個結點再壓入,如果棧為空,則和自身一起打包。這樣在彈出一個元素后,棧中的最小元素可直接由彈出的結點獲得。
            其實這個算法寫起來很簡單,我順便復習了一下C++的模板方面的東西。C++平時用得不多,模板這玩意兒更不常用,以至于發現手生多了。
            #include <vector>   
            #include 
            <utility>   
            using namespace std;   
              
            template
            <class T>   
            class Stack{   
                vector
            <pair<T,T> > stack;   
                T minimum;   
            public:   
                vector
            <pair<T,T> >& push(T e);   
                vector
            <pair<T,T> >& pop();   
                T min();   
            };   
            template
            <class T>   
            vector
            <pair<T,T> >& Stack<T>::push(T e){   
                
            if (stack.empty()){   
                    minimum
            =e;   
                }   
                pair
            <T,T> node(e,minimum);   
                stack.push_back(node);   
                
            if (e<minimum){   
                    minimum
            =e;   
                }   
            }   
            template
            <class T>   
            vector
            <pair<T,T> >& Stack<T>::pop(){   
                pair
            <T,T> node=stack.back();   
                minimum
            =node.second;   
                stack.pop_back();   
            }   
            template
            <class T>   
            T Stack
            <T>::min(){   
                
            return minimum;   
            }
            手生多了,這么點兒東西寫了有20分鐘。我測試了幾組數據,應該沒什么問題。在JavaEye上有些朋友提到了最小堆,但難以實現push和pop的O(1)操作。其實根本沒有必要,有些問題看似很難,很多時候是我們想復雜了。

            Feedback

            # re: 一道Google面試題的解答  回復  更多評論   

            2008-02-17 13:09 by Zeus2
            對,就是弄個結構把次小值都記住了。

            # re: 一道Google面試題的解答  回復  更多評論   

            2008-02-18 10:07 by w2001
            其實沒有很難,就是翻來覆去考智力

            # re: 一道Google面試題的解答  回復  更多評論   

            2008-02-18 15:37 by DeathKnight
            棧為空時 你的min返回的結果是無意義的 應該在min中加一個邊界判斷

            # re: 一道Google面試題的解答  回復  更多評論   

            2008-02-19 07:40 by Encoh
            確實是智力大比拼啊,呵呵。

            # re: 一道Google面試題的解答  回復  更多評論   

            2008-02-19 09:45 by 游客
            這個實現緩存了一個對象副本,效率不高,緩存指針更好一些。

            # re: 一道Google面試題的解答[未登錄]  回復  更多評論   

            2008-02-19 13:01 by kevin
            hash

            # re: 一道Google面試題的解答  回復  更多評論   

            2008-02-22 14:45 by hehe
            I c~~

            # re: 一道Google面試題的解答  回復  更多評論   

            2008-03-02 09:24 by Santa
            哈哈,就是再添加上一個保存最小值的stack嘛,在 push pop的時候適當添加最小值棧頂的元素即可。不過要注意會出現多個最小值的情況,適當的計數一下會好些

            # re: 一道Google面試題的解答[未登錄]  回復  更多評論   

            2009-04-09 22:53 by jerry
            1. 把樓主的程序稍微簡化了一下。
            2. 加了一個main文件。

            文件MyStack.h:

            #ifndef MYSTACK_H_
            #define MYSTACK_H_

            #include <vector>
            #include <utility>
            using std::vector;
            using std::pair;

            template<class T>
            class MyStack {
            private:
            vector< pair<T, T> > stack;
            T minimum;
            public:
            MyStack();
            virtual ~MyStack();

            void push(T e);
            void pop();
            T top();
            T min();
            };


            template<class T>
            MyStack<T>::MyStack() {
            // TODO Auto-generated constructor stub
            }

            template<class T>
            MyStack<T>::~MyStack() {
            // TODO Auto-generated destructor stub
            }

            template<class T>
            void MyStack<T>::push(T e) {
            if (stack.empty()) {
            minimum = e;
            }

            stack.push_back( pair<T, T>(e, minimum) );
            if (e < minimum) {
            minimum = e;
            }
            }
            template<class T>
            void MyStack<T>::pop() {
            minimum = stack.back().second;
            stack.pop_back();
            }

            template<class T>
            T MyStack<T>::top() {
            return stack.back().first;
            }

            template<class T>
            T MyStack<T>::min() {
            return minimum;
            }

            #endif /* MYSTACK_H_ */

            文件Main.cpp:
            #include <iostream>
            using namespace std;

            #include "MyStack.h"

            int main() {
            cout << "Hello World!" << endl;

            MyStack<int> stack;
            stack.push(34);
            stack.push(343);
            stack.push(1);
            cout << "Min value: " << stack.min() << endl;
            cout << "Top value: " << stack.top() << endl;

            stack.pop();
            cout << "Min value: " << stack.min() << endl;
            cout << "Top value: " << stack.top() << endl;

            return 0;
            }


            久久精品成人免费看| 青青草原综合久久大伊人导航| 国产精品成人99久久久久91gav| 久久96国产精品久久久| 久久不射电影网| 精品久久久久久久国产潘金莲 | 色婷婷综合久久久久中文一区二区 | 97久久精品人妻人人搡人人玩 | 久久综合噜噜激激的五月天| 久久国产色AV免费观看| 久久伊人精品青青草原日本| 久久久精品人妻一区二区三区蜜桃 | 国产日韩久久久精品影院首页| 四虎国产精品成人免费久久| 国产精品久久久久久久久鸭 | 漂亮人妻被中出中文字幕久久 | 亚洲午夜无码AV毛片久久| 久久久综合九色合综国产| 久久久精品国产sm调教网站 | 国产精品伊人久久伊人电影| 亚洲中文精品久久久久久不卡| 久久WWW免费人成—看片| 人人狠狠综合久久亚洲婷婷| 97视频久久久| 久久国产免费直播| 久久精品国产亚洲5555| 狠狠狠色丁香婷婷综合久久五月| 久久婷婷五月综合色奶水99啪| 2020国产成人久久精品 | 日本欧美久久久久免费播放网| 久久久久无码专区亚洲av| 久久精品人人做人人爽电影| 麻豆亚洲AV永久无码精品久久 | 一本久道久久综合狠狠躁AV| 久久精品国产亚洲精品| 久久91综合国产91久久精品| 久久精品国产亚洲AV无码麻豆| 99久久夜色精品国产网站| 99久久精品免费国产大片| 国产一区二区精品久久| 色综合久久久久综合体桃花网 |