当前位置: 首页 > news >正文

[分类整理III]微软等100题系列V0.1版之三:栈、堆、队列面试题集锦

[整理III]微软等100题系列V0.1版之三:栈、堆、队列面试题集锦

July

==============

2.设计包含min函数的栈。
定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。


29.栈的push、pop序列
题目:输入两个整数序列。其中一个序列表示栈的push顺序,
判断另一个序列有没有可能是对应的pop顺序。
为了简单起见,我们假设push序列的任意两个整数都是不相等的。

比如输入的push序列是1、2、3、4、5,那么4、5、3、2、1就有可能是一个pop系列。
因为可以有如下的push和pop序列:
push 1,push 2,push 3,push 4,pop,push 5,pop,pop,pop,pop,
这样得到的pop序列就是4、5、3、2、1。
但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。


34.
实现一个队列。
队列的应用场景为:
一个生产者线程将int类型的数入列,一个消费者线程将int类型的数出列


35.
求一个矩阵中最大的二维矩阵(元素和最大).如:
1 2 0 3 4
2 3 4 5 1
1 1 5 3 0
中最大的是:
4 5
5 3
要求:(1)写出算法;(2)分析时间复杂度;(3)用C写出关键代码

57.用俩个栈实现队列。

题目:某队列的声明如下:

template<typename T> class CQueue
{
public:
CQueue() {}
~CQueue() {}

void appendTail(const T& node); // append a element to tail
void deleteHead(); // remove a element from head

private:
T> m_stack1;
T> m_stack2;
};

分析:从上面的类的声明中,我们发现在队列中有两个栈。
因此这道题实质上是要求我们用两个栈来实现一个队列。
相信大家对栈和队列的基本性质都非常了解了:栈是一种后入先出的数据容器,
因此对队列进行的插入和删除操作都是在栈顶上进行;队列是一种先入先出的数据容器,
我们总是把新元素插入到队列的尾部,而从队列的头部删除元素。

66.颠倒栈。
题目:用递归颠倒一个栈。例如输入栈{1, 2, 3, 4, 5},1在栈顶。
颠倒之后的栈为{5, 4, 3, 2, 1},5处在栈顶。

-----------------------------------------------------

1.关于本微软等公司数据结构+算法面试100题系列V0.1版的郑重声明
http://blog.csdn.net/v_JULY_v/archive/2010/12/02/6050133.aspx
2.完整100题,请参见,
[珍藏版]微软等数据结构+算法面试100题全部出炉[100题首次完整亮相]
http://blog.csdn.net/v_JULY_v/archive/2010/12/06/6057286.aspx
3.更多详情,请参见,本人博客:
My Blog:
http://blog.csdn.net/v_JULY_v
4.所有的资源(题目+答案)下载地址:
http://v_july_v.download.csdn.net/
5.本微软等100题系列V0.1版,永久维护(网友,思路回复)地址:
http://topic.csdn.net/u/20101126/10/b4f12a00-6280-492f-b785-cb6835a63dc9.html

作者声明:
本人July对本博客所有任何内容和资料享有版权,转载请注明作者本人July及出处。
永远,向您的厚道致敬。谢谢。July、二零一零年十二月十七日。

相关文章:

  • 正则表达式参考表
  • Ruby的GC机制源码分析(1)
  • NoSQL数据库 Couchbase Server - 分布式缓存
  • 二分搜索法(转载)
  • SEO
  • nginx配置
  • iOS 开发笔记-报错处理
  • 北理工 Java 技术与应用考试试题参考答案及点评(下)
  • Java学习笔记--Java8 Lambda表达式
  • 时间是幻觉?
  • getHibernateTemplate()与getSession()的区别
  • 宇宙最初几微秒
  • VirtualBox 自动挂载共享文件夹
  • 一切都是相对的标准
  • 本地通知UILocalNotification
  • hadoop入门学习教程--DKHadoop完整安装步骤
  • javascript从右向左截取指定位数字符的3种方法
  • Linux快速复制或删除大量小文件
  • MySQL Access denied for user 'root'@'localhost' 解决方法
  • SpiderData 2019年2月16日 DApp数据排行榜
  • Spring Cloud中负载均衡器概览
  • vue--为什么data属性必须是一个函数
  • 分类模型——Logistics Regression
  • 构建二叉树进行数值数组的去重及优化
  • 如何优雅地使用 Sublime Text
  • 删除表内多余的重复数据
  • 使用权重正则化较少模型过拟合
  • 400多位云计算专家和开发者,加入了同一个组织 ...
  • 阿里云ACE认证学习知识点梳理
  • ​flutter 代码混淆
  • ​如何在iOS手机上查看应用日志
  • %3cli%3e连接html页面,html+canvas实现屏幕截取
  • (C#)一个最简单的链表类
  • (day6) 319. 灯泡开关
  • (Ruby)Ubuntu12.04安装Rails环境
  • (删)Java线程同步实现一:synchronzied和wait()/notify()
  • .dwp和.webpart的区别
  • .net安装_还在用第三方安装.NET?Win10自带.NET3.5安装
  • .NET开源项目介绍及资源推荐:数据持久层
  • ?php echo ?,?php echo Hello world!;?
  • @property @synthesize @dynamic 及相关属性作用探究
  • [<事务专题>]
  • [20150321]索引空块的问题.txt
  • [20170705]diff比较执行结果的内容.txt
  • [2023年]-hadoop面试真题(一)
  • [AIGC] MySQL存储引擎详解
  • [BJDCTF2020]The mystery of ip
  • [bzoj2957]楼房重建
  • [C++]C++类基本语法
  • [C++]命名空间等——喵喵要吃C嘎嘎
  • [codevs 1515]跳 【解题报告】
  • [CUDA手搓]从零开始用C++ CUDA搭建一个卷积神经网络(LeNet),了解神经网络各个层背后算法原理
  • [flink总结]什么是flink背压 ,有什么危害? 如何解决flink背压?flink如何保证端到端一致性?
  • [HAOI2016]食物链
  • [IE9] IE9 RC版下载链接