posts - 5, comments - 40, trackbacks - 0, articles - 0

一道Google面试题的解答

Posted on 2008-02-17 11:23 Wang Jinbo 阅读(3991) 评论(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;
}



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理