- 浏览: 741457 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
u011487470:
感觉就是知识采集一样,博主能不能整理一下
基于Web的IM简介 -
whxtbest:
whxtbest 写道2里面:如果T本身就是重复的话 比如 ...
关于后缀树的一些理解 -
whxtbest:
2里面:如果T本身就是重复的话 比如S是aaab,T是aa ...
关于后缀树的一些理解 -
刘亮love小雪:
谢谢啦
Java 2D高级绘图 -
bluky999:
收集的资料挺多的 哈哈
基于Web的IM简介
题目:对现在的Stack(栈)数据结构进行改进,加一个min()功能,使之能在常数,即O(1),时间内给出栈中的最小值。可对push()和pop()函数进行修改,但要求其时间复杂度都只能是O(1)。
分析:要使pop,push,min都是O(1),所以肯定要牺牲点空间
思路:1:在stack的数据结构中加两个个字段,如
typedef struct {
int data[MAX];
int top;
int min;
int second;
}stack;
pop,push的时候都去栈顶元素,所以是O(1)
min的时候取stack的min字段,所以也是O(1)
每次push的时候进行比较,如果当前push的元素比stack->min小,则用当前元素替换stack->min,用原来的min替换second。如果当前push的元素比stack->min大,但比second小,则用当前元素替换stack->second。于是达到了取min的效果,程序如下
int push(stack * s,int x){
ASSERT(s!=NULL);
if(s->top>=MAX)
{
printf("Stack overload!");
return -1;
}
s->data[s->top++]=x;
if(x<s->min)
s->min=x;
return 0;
}
每次pop的时候进行比较,如果pop的元素为min,则用second替换min。于是达到了取min的效果,程序如下
int pop(stack *s,int *x)
{
ASSERT(s!=NULL);
if(s->top<=0)
{
printf("Stack Empty!");
return -1;
}
(*x)=s->data[s->top--];
if(x==s->min) s->min=s->second;
return 0;
}
int min( stack *s,int *x )
{
ASSERT(s!=NULL);
(*x)=s->min;
return 0;
}
思路2:设置辅助栈ass,记录每个状态下的最小值,每次插入时,得到辅助栈当前值,和插入的值比较
如果小则插入到最小值栈的就是它,否则就是原来的最小值,通过这种方式,pop,push,min三个都是
O(1)算法的。
typedef struct {
int data[MAX];
int top;
}stack;
STATIC int push_stack(stack *s,int x)
{
ASSERT((s!=NULL));
if(s->top>=MAX)
{
printf("Stack overload");
return -1;
}
s->data[s->top++]=x;
return 0;
}
STATIC int pop_stack(stack *s,int *x)
{
ASSERT(s!=NULL);
if(s->top<=0)
{
printf("Stack Empty");
return -1;
}
(*x)=s->data[s->top--];
return 0;
}
int push(stack *main,stack *ass,int x)
{
ASSERT((main!=NULL)&&(ass!=NULL));
int temp;
pop_stack(ass,&temp);
push_stack(main,x);
if(x<temp)
{
push_stack(ass,temp);
push_stack(ass,x);
}
else
{
push_stack(ass,temp);
push_stack(ass,temp);
}
return 0;
}
int pop(stack *main,stack *ass,int *x)
{
ASSERT((main!=NULL)&&(ass!=NULL));
int temp;
pop_stack(ass,&temp);
pop_stack(main,x);
return 0;
}
int min(stack *ass,int *x)
{
ASSERT((main!=NULL)&&(ass!=NULL));
pop_stack(ass,x);
push_stack(ass,(*x));
return 0;
}
You're right!
RE,我就是这个意思……
连续push 5个数 然后连续pop 3次,second 是什么值???
光用一个second就能起到排序的作用??? 明显不对的!
分析:要使pop,push,min都是O(1),所以肯定要牺牲点空间
思路:1:在stack的数据结构中加两个个字段,如
typedef struct {
int data[MAX];
int top;
int min;
int second;
}stack;
pop,push的时候都去栈顶元素,所以是O(1)
min的时候取stack的min字段,所以也是O(1)
每次push的时候进行比较,如果当前push的元素比stack->min小,则用当前元素替换stack->min,用原来的min替换second。如果当前push的元素比stack->min大,但比second小,则用当前元素替换stack->second。于是达到了取min的效果,程序如下
int push(stack * s,int x){
ASSERT(s!=NULL);
if(s->top>=MAX)
{
printf("Stack overload!");
return -1;
}
s->data[s->top++]=x;
if(x<s->min)
s->min=x;
return 0;
}
每次pop的时候进行比较,如果pop的元素为min,则用second替换min。于是达到了取min的效果,程序如下
int pop(stack *s,int *x)
{
ASSERT(s!=NULL);
if(s->top<=0)
{
printf("Stack Empty!");
return -1;
}
(*x)=s->data[s->top--];
if(x==s->min) s->min=s->second;
return 0;
}
int min( stack *s,int *x )
{
ASSERT(s!=NULL);
(*x)=s->min;
return 0;
}
思路2:设置辅助栈ass,记录每个状态下的最小值,每次插入时,得到辅助栈当前值,和插入的值比较
如果小则插入到最小值栈的就是它,否则就是原来的最小值,通过这种方式,pop,push,min三个都是
O(1)算法的。
typedef struct {
int data[MAX];
int top;
}stack;
STATIC int push_stack(stack *s,int x)
{
ASSERT((s!=NULL));
if(s->top>=MAX)
{
printf("Stack overload");
return -1;
}
s->data[s->top++]=x;
return 0;
}
STATIC int pop_stack(stack *s,int *x)
{
ASSERT(s!=NULL);
if(s->top<=0)
{
printf("Stack Empty");
return -1;
}
(*x)=s->data[s->top--];
return 0;
}
int push(stack *main,stack *ass,int x)
{
ASSERT((main!=NULL)&&(ass!=NULL));
int temp;
pop_stack(ass,&temp);
push_stack(main,x);
if(x<temp)
{
push_stack(ass,temp);
push_stack(ass,x);
}
else
{
push_stack(ass,temp);
push_stack(ass,temp);
}
return 0;
}
int pop(stack *main,stack *ass,int *x)
{
ASSERT((main!=NULL)&&(ass!=NULL));
int temp;
pop_stack(ass,&temp);
pop_stack(main,x);
return 0;
}
int min(stack *ass,int *x)
{
ASSERT((main!=NULL)&&(ass!=NULL));
pop_stack(ass,x);
push_stack(ass,(*x));
return 0;
}
评论
11 楼
loveofgod
2008-02-18
在push时将每个数包装成一个结点,如果这样的话,当push的点很大时,空间复杂度会很高
10 楼
loveofgod
2008-02-18
ddbird,那你说pop push min的复杂度多少,嗯对,push没问题,pop的时候会出问题
9 楼
JohnnyJian
2008-02-16
引用
我认为min() O(1)的做法应该是在push时将每个数包装成一个结点,结点中两个数,一个是要压入的数,另一个记录压入前已经在栈中的的最小值。后面的就容易了,我不说了。
You're right!
8 楼
ggggqqqqihc
2008-02-15
我认为min() O(1)的做法应该是在push时将每个数包装成一个结点,结点中两个数,一个是要压入的数,另一个记录压入前已经在栈中的的最小值。后面的就容易了,我不说了。
7 楼
zuroc
2008-02-15
这个好像很简单?
还是我的理解有问题.........
还是我的理解有问题.........
6 楼
JohnnyJian
2008-02-15
引用
min是O(1) 用堆就可以了,但是要pop push min 都 O(1) 似乎有难度。
RE,我就是这个意思……
5 楼
ddbird
2008-02-15
min是O(1) 用堆就可以了,但是要pop push min 都 O(1) 似乎有难度。
4 楼
ddbird
2008-02-15
引用
每次pop的时候进行比较,如果pop的元素为min,则用second替换min。于是达到了取min的效果,程序如下
int pop(stack *s,int *x)
int pop(stack *s,int *x)
连续push 5个数 然后连续pop 3次,second 是什么值???
光用一个second就能起到排序的作用??? 明显不对的!
3 楼
loveofgod
2008-02-15
请问哪里错了?上面的解答难道不是O(1)吗?
2 楼
JohnnyJian
2008-02-14
而且我怀疑求min是否有O(1)的算法,因为即使用优先队列,也要O(logN)的复杂度……
1 楼
JohnnyJian
2008-02-14
这是官方的答案吗?好像都是错的哦……
发表评论
-
求交集和并集的线性算法
2011-10-24 23:00 5304对于给定的两个集合,使用哈希表可以在线性时间复杂度内得到他们的 ... -
关于后缀树的一些理解
2008-10-01 21:07 9010要理解suffix tree就首先 ... -
面试题集锦
2008-09-29 17:24 35631. 时针分针重合几次 表面上有60个小格,每小格代表一分钟, ... -
词频统计的C++实现
2008-03-10 16:01 3746#include <map> # ... -
Google面试题(九)
2008-02-20 00:13 275325匹马赛跑,5个跑道,怎么以最少的比赛次数来决出最快的3匹, ... -
数据结构面试大全
2008-02-19 12:50 44731.判断链表是否存在环 ... -
Google面试题(七)
2008-02-14 03:35 3037很多Google考生出来,也 ... -
Google面试题(五)
2008-02-14 02:30 2663几星期前,一个朋友接 ... -
Google面试题(四)
2008-02-13 22:07 226126个英文字母从新排序(未知的顺序alphabet),然后用这 ... -
google面试题(三)
2008-02-13 06:22 2499算法题一:Given 1 GB memory, input a ... -
google面试题(二)
2008-02-11 01:43 3484平面上N个点,求一条直线,穿过的点数最多 思路:2点确定一条 ... -
google面试题(一)
2008-02-11 01:27 2484有一个random number generator,是生成真 ... -
数据结构和算法中容易忽略的要点总结[未完待续]
2008-02-10 23:44 14391。递归需要有个递归出口,否则会是infinite的递归 -
矩阵求逆的快速算法
2008-02-10 20:40 3895算法介绍 矩阵求逆在3D ... -
约瑟夫问题
2008-02-10 09:57 1995有n个人围成一圈,顺序编号。从第一个人开始报数,凡报到m的人退 ... -
hash函数学习总结,以及与hashcode()、hashMap的关系
2008-02-10 06:21 7435以前一直觉得hash函数很 ... -
突然发现没真正领悟哈希表
2008-02-10 05:11 2554在一个字符串中找到第 ... -
[微软面试题]请把一个整形数组中重复的数字去掉
2008-02-10 04:08 4354请把一个整形数组a中重复的数字去掉 方法一: for i ... -
Java版堆排序
2008-02-09 23:41 1151/** * author Akalius Kung 2008 ... -
Java版插入排序
2008-02-09 04:40 1471/** * author Akalius Kung 2008 ...
相关推荐
google面试题google面试题
每年招聘的时候,做笔试难免会遇到一些经典的面试题,而好多是google已经出过的
Google21道面试题 Google公司的面试 google面试题2 GOOGLE面试题--答案
11谷歌面试题精讲
程序员面试题精选 C++ 算法 微软 google 程序员面试题精选 C++ 算法 微软 google
google的面试题,很有挑战性...........
微软公司面试人员的面试题解答,google微软等大公司面试题,软件架构师的设计。
15个Google面试题以及答案。对于的相关职位产品经理、软件工程师等。
Google面试题
真正的谷歌笔试面试题,让你领略互联网最伟大公司的风采,也为自己进入这些最著名的IT企业找准方向,明白哪些知识和技能是现代IT企业最渴求的!!
08_谷歌面试题_
C++基础面试题.docx C++开发工程师面试题库.docx C++技能测试试卷一及答案.docx C++技能测试试卷二及答案.docx c++笔试题汇总.pdf C++经典面试题库 附带参考答案.docx C++语言程序设计试题.docx C++面试题笔试题 CC+...
常见算法笔试或面试题 笔试面试专栏:字符串 数组 vc题集 十道海量数据处理面试题与十个方法大总结 google全程面试题 其他一些公司的面试题
mit 的教授教你如何攻克谷歌面试题。 里面包含了谷歌经典题型和解答。 不错的复习材料。。。
21道经典的Google面试题,全英文题目,涉及到多方面的知识
经典谷歌,微软部分面试题的详细分析过程解答,另外还有一些锻炼思维能力的数学趣题。以上题目均节选源自《果壳网》,我已将上述试题转成PDF格式,便于下载和阅读。
微软google面试题
名牌有名牌的理由,就连招聘也与众不同,各个企业的面试题成了招聘后期的压轴好戏。今年的企业面试题目,说它百般刁难的有之,说它独出机杼的有之,说它故弄玄虚的有之。你怎么看呢?还是先来了解一下,看看面对这些...
这是Google的15道面试题与答案,word文档!大家感兴趣的看看吧!呵呵!希望对各位有帮助!