LeetCode 155 Min Stack 使用一个单链表解法

大家的解法都是使用两个栈,一个正常栈,一个最小栈,当有新的最小值时则同时压入最小栈,当弹出的值等于最小值时则同时弹出最小栈栈顶。时间复杂度为O(1),空间复杂度为O(n+k)(k为最小栈的长度)。

我用单链表A了这道题,单链表表头存放最小值,push时从表头插入,模拟入栈,并比较最小值,随时更新表头的最小值;pop时,弹出第二个节点,若popped的值为最小值,则遍历整个链表,更新新的最小值;通过访问链表第二个节点得到栈顶元素,访问表头得到最小值。push,top,getMin的时间复杂度均为O(1),但pop的时间复杂度为O(n),空间复杂度为O(n),此解法对于内存限制的情况有用。

继续阅读LeetCode 155 Min Stack 使用一个单链表解法

STL sort()函数用法 & 杭电OJ2020

#include<iostream>
#include<math.h>
#include<algorithm>//头文件
using namespace std;
bool cmp(int a,int b)//比较函数
{
    return abs(a)>abs(b);//从大至小排序,整数取绝对值用abs(),浮点型取绝对值用fabs(),千万不要搞混,否则OJ判Compilation Error
}
int main()
{
    int n,i;
    while(cin>>n)
    {
        if(0==n)
            break;
        int a[105];
        for(i=0;i<n;i++)
        {
            cin>>a[i];
        }
        sort(a,a+n,cmp);//函数内顺序依次为:排序首地址,排序尾地址,比较函数
        cout<<a[0];
        for(i=1;i<n;i++)
            cout<<" "<<a[i];
        cout<<endl;
    }
    return 0;
}

括号匹配(c/c++&&hrbust 1054)

  括号匹配,基本思路:扫描每个字符,遇到圆、中、花的左括号进栈,遇到圆、中、花的右括号时检查栈顶元素是否为相应的左括号,若是,退栈,否则配对错误。最后栈如果不为空也错误。

#include<iostream>
#include<stack>//STL栈模板
using namespace std;
bool BracketsCheck(char *str)
{
	stack<char> s;//定义char栈
	int i=1;
	s.push(str[0]);
	while(str[i]!='\0')
	{
		switch(str[i])
		{
		//左括号入栈
		case '(':s.push('(');break;
		case '[':s.push('[');break;
		case '{':s.push('{');break;
		//遇到右括号,检测栈顶
		case ')':
			if(s.empty()) return false;
			if(s.top()!='(')	return false;
			s.pop();break;
		case ']':
			if(s.empty()) return false;
			if(s.top()!='[')	return false;
			s.pop();break;
		case '}':
			if(s.empty()) return false;
			if(s.top()!='{')	return false;
			s.pop();break;

		default:break;
		}
		
		i++;
	}
	if(!s.empty())
		return false;
	return true;
}
int main()
{
	char str[100];
	cin>>str;
	if(BracketsCheck(str))
		cout<<"括号匹配"<<endl;
	else
		cout<<"括号不匹配"<<endl;
	return 0;
}

哈工大acm括号匹配原题
http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1054

#include<iostream>
#include<stack>
using namespace std;
bool BracketsCheck(char *str)
{
	stack<char> s;
	int i=1;
	s.push(str[0]);
	while(str[i]!='\0')
	{
		switch(str[i])
		{
		case '(':s.push('(');break;
		case '[':s.push('[');break;
		case '{':s.push('{');break;

		case ')':
			if(s.empty()) return false;
			if(s.top()!='(')	return false;
			s.pop();break;
		case ']':
			if(s.empty()) return false;
			if(s.top()!='[')	return false;
			s.pop();break;
		case '}':
			if(s.empty()) return false;
			if(s.top()!='{')	return false;
			s.pop();break;

		default:break;
		}
		i++;
	}
	if(!s.empty())
		return false;
	return true;
}
int main()
{
	char str[200];
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>str;
		if(BracketsCheck(str))
			cout<<"Valid"<<endl;
		else
			cout<<"Invalid"<<endl;
	}
	return 0;
}

  

考研——ACM下(个人暂时考研复习计划)

此文前段时间在复习高数时就想写了,可惜中途写了会,觉得光有想法,文笔思路不行,一直搁浅。

今天上午是我们学院的程序设计大赛选拔赛,有幸和几个同学一起去监考,情况大致和去年差不太多。又领了考研辅导班的听课证,回到寝室,想休息一下,索性就继续把这篇文章写下去吧。

去年暑假,在学校参加ACM暑假培训,每天朝八晚九,顶着烈日,找资料,学算法,练题目,内部选拔,模拟备战,在他校OJ上比赛,省赛……

今年,准备考研,我想那么就再继续一个“ACM”吧。

暑假前,朝七晚九,坚持去图书馆自习,看书,做题。

数学:教材过一遍,每章过后都梳理重点定理、公式、解题方法,(如果时间允许,开始复习全书)。

英语:单词过两遍,长难句解决,(如果时间允许,每天一至两篇真题阅读)。

政治:暂无计划。

专业课:如果可以,就着辅导书和课本过一遍。

虽然都很单调,但是也有惊喜。那就是每天早上能坚持7点5分在去自习室的路上“吹风淋雨”,那种感觉真的很每秒;背单词脑子立马显现单词的各种意思;数学习题一次完全匹配正确答案。加油吧,fightingO(∩_∩)O~

2012/3/18更新:

每天计划,早上7点10-8点50读英语,然后去图书馆,中午12点20-12点50单词软件记单词,下午2点钟到图书馆,下午5点15左右去吃饭,最迟6点30去图书馆,晚上9点50-10点30单词软件记单词。(上课时间上课,天气好下午打球。。。)