intellij idea汉化 leetcodeLCP 反射 webview vuejs2 variant pyqt jquery循环遍历 python编程练习题 linuxmysql启动命令 kubernetes视频 python读取数据库 java语法 java运算 java可变参数 linux系统安装 php入门例子 金山wps2003 acmecadconverter 0x0000004e volist 倒计时计时器 考试练习系统 程序员面试宝典 win10有几个版本 古风头像女动漫 办公室复印机使用方法 汽车配件查询软件 大势至usb监控 alert换行 cad2008汉化包 内存条有什么用 pr抠图 数据库同步解决方案 mysql联合查询 dll下载站 视频下载高手 OPPO投屏 101图集电子版 编程开发软件
当前位置: 首页 > 学习教程  > 编程语言

微软算法面试(2):设计包含min函数的栈(栈)

2021/1/28 23:22:11 文章标签:

定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。 要求函数min、push以及pop的时间复杂度都是O(1)。 这个题的关键是设计min时间复杂度为O(1)的函数,通常min函数的复杂度为O(n)。 可以使用空间换时间的策略,加一个…

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

这个题的关键是设计min时间复杂度为O(1)的函数,通常min函数的复杂度为O(n)。

可以使用空间换时间的策略,加一个栈来维护min函数值,每一次pop栈,min函数对应的栈也相应进行操作。

下面看个例子:
push:
7,5,2,8,3,1

对应min栈的为:
7,5,2,2,2,1

程序实现如下:

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;

template <int maxsize=1024> 
class Stack{
private:
	int data1[maxsize];
	int data[maxsize];
	int end;
	int m;
public:
	Stack():end(0),m(0){}
	bool empty()
	{
		if( end == 0)
			return true;
		else
			return false;
	}
	bool full()
	{
		if( end == maxsize -1) return true;
		else
			return false;
	}
	bool pop(int& t)
	{
		if(empty()) return false;
		end = end -1;
		t = data[end];
		return true;
	}
	bool push(int t)
	{
		if(full()) return false;
		if(empty() || m>t) m = t;
		data1[end] = m;
		data[end] = t;
		end += 1;
		return true;
	}
	int min()
	{
		if(empty()) return -1;
		else
			return data1[end -1];
	}
};

int main()
{
	Stack<1024> s;
	//7,5,2,8,3,1
	s.push(7);
	s.push(5);
	s.push(2);
	s.push(8);
	s.push(3);
	s.push(1);
	string fstr = "7,5,2,8,3,1";
	string str;
	string mstr;
	while(!s.empty())
	{
		int i = 0;
		int m = 0;
		char chr[10];
		string str1 = "";
		m = s.min();
		memset(chr, 0, 10);
		sprintf(chr, "%d", m);
		str1 = chr;
		mstr += str1 + ",";
		s.pop(i);
		memset(chr, 0, 10);
		sprintf(chr, "%d", i);
		str1 = chr;
		str += str1 + ",";
		
		//cout << i << ",";
	}
	cout << "begin status: " << fstr.c_str() << endl;
	cout << "pop: " << str.c_str() << endl;
	cout << "min: " << mstr.c_str() << endl;
	return 0;
}

打印结果为:

begin status: 7,5,2,8,3,1
pop: 1,3,8,2,5,7,
min: 1,2,2,2,5,7,

本文链接: http://www.dtmao.cc/news_show_650185.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?