马上美赛要来了,写两道题压压惊 😄

Stack

题目如下

问题描述 实现一个栈,完成以下功能: 入栈 出栈 查询栈中位置Y是谁 一开始栈为空,栈中的位置从1开始(即栈底位置为1)。

输入

第一行一个整数n,表示操作个数(1 <= n <= 100000) 接下来n行,每行第一个数字表示操作(见描述):

若为数字1,则接下来有一串字符串X,表示将X压入栈中。

若为数字2,表示弹出栈顶(保证栈非空),并输出出栈的这个人。

若为数字3,则接下来有一个整数Y,表示询问栈中位置Y是谁(保证位置Y合法),并输出名字。

输入样例 :
11                                                                                            
1  a
1  b
1  c
3  1
3  2
3  3
2
1  d
3  1
3  2
3  3
输出样例:
a
b
c
c
a
b
d

直接用最简单的数组模拟就ok了,其实用stl里面的应该也可以,这点时间应该不会卡,代码如下:

#include <bits/stdc++.h>
using namespace std;

string Stack[100005];
int top = 1;

void push(string name) {
    Stack[top++] = name;    
}

string pop() {
    return Stack[--top];
}

string query(int pos) {
	return Stack[pos];    
}

int main() {
    int n;
    scanf("%d", &n);
    char name[20];
    for (; n--; ) {
        int op;
        scanf("%d", &op);
        if (op == 1) {
            scanf("%s", name);
            push(name);
        } else if (op == 2) {
            printf("%s\n", pop().c_str());  //c_str的作用是将c++的string类型转化成c的字符串常量,使用%s输出
        } else {
            int pos;
            scanf("%d", &pos);
            printf("%s\n", query(pos).c_str());  
        }
    }
    return 0;
}

Queue

题目如下:

时间限制:2s,空间256MB
问题描述

实现一个队列,完成以下功能:入列 出列 查询队列中位置Y是谁

一开始队列为空,队列中的位置从1开始(即队头从1开始)。

输入 第一行一个整数n,表示操作个数(1 <= n <= 100000)接下来n行,每行第一个数字表示操作(见描述):

若为数字1,则接下来有一串字符串X,表示将X加入队列中。
若为数字2,表示出列(保证队列非空),并输出出列的这个人。
若为数字3,则接下来有一个整数Y,表示询问队列中位置Y是谁(保证位置Y合法),并输出名字。

数据中的字符串只包含26个小写字母(无空格灯分隔符),且长度不超过15

字符串可能有重复,正如现实中可能有重名。

输出
将所有操作2和操作3输出,一行一个。

输入样例
11
1 a
1 b
1 c
3 1
3 2
3 3
2
1 d
3 1
3 2
3 3
1
2
3
4
5
6
7
8
9
10
11
12
输出样例
a
b
c
a
b
c
d

直接用数组模拟,为了极简,并没有考虑边界情况,当然取模也是完全没有问题的。代码如下:

#include <bits/stdc++.h>
using namespace std;

string myqueue[100005];
int rear = 0 , front = 0;

void enqueue(string name) {
	myqueue[rear++] = name;
}

string dequeue() {
	return myqueue[front++];   
}

string query(int pos) {
    return myqueue[front+pos-1];
}

int main() {
    int n;
    scanf("%d", &n);
    char name[20];
    for (; n--; ) {
        int op;
        scanf("%d", &op);
        if (op == 1) {     //入队 
            scanf("%s", name);
            enqueue(name);
        } else if (op == 2) {    //出队 
            printf("%s\n", dequeue().c_str());
        } else {
            int pos;
            scanf("%d", &pos);    //查询 
            printf("%s\n", query(pos).c_str());
        }
    }
    return 0;
}

二叉排序树

在写这道题之前,先得搞清楚啥是二叉排序树,也叫二叉搜索树啥的。首先肯定是二叉树,再就是排序,规则就是对于一个根节点,左节点小于它,右节点大于它,并递归下去。举一个例子:

从图中可以看到,不管是12这个节点,还是7这个节点,左边的孩子都小于它,右边的孩子都大于它。

题目:

问题描述
给定一个1到n的排列(无重复元素),按顺序依次插入到一棵二叉排序树中,请你将这棵二叉树前序遍历和后序遍历输出。
保证树高不超过50 。

输入
第一行一个整数n。(1 ≤ n ≤ 100000)

接下来一行表示为n个整数,代表1到n的一个排列。

输出
输出所建成的二叉树的前序遍历和后序遍历。

输入样例
10
2 6 9 3 5 7 10 8 4 1

输出样例
2 1 6 3 5 4 9 7 8 10
1 4 5 3 8 7 10 9 6 2

测试输入
20
8 6 4 13 15 17 11 12 19 18 16 10 7 1 2 7 3 5 9 14

测试输出
8 6 4 1 2 3 5 7 7 13 11 10 9 12 15 14 17 16 19 18
3 2 1 5 4 7 7 6 9 10 12 11 14 16 18 19 17 15 13 8

代码实现:

#include<iostream>
#include<vector>
using namespace std;

int n;
const int N = 100005;

//构造树的结构,用数组维护 
struct node {
	int r , l , val;
}t[N];

int root, cnt;  //树的根节点和整体的高度 

int insert(int v , int x) {  //生成二叉排序树 
	if(x == 0) {    //如果发现是空节点
		x = ++cnt;
		t[x].val = v;
		t[x].l = 0;
		t[x].r = 0;  		
		return x;			
	}   //如果当前值比根节点小,去左边去找,否则去右边
	if(v < t[x].val)
		t[x].l = insert(v , t[x].l);
	else
		t[x].r = insert(v , t[x].r);
	
	return x;  //将对应的编号进行根更新	
}

void pre_visit(int x, vector<int> & ans)
{
	if(x)
	{
		ans.push_back(t[x].val);  //将前序结果保存到vector中
		pre_visit(t[x].l, ans);
		pre_visit(t[x].r, ans);	
	}
}

void last_visit(int x, vector <int> & ans)  //将后序节点保存到vector中
{
	if(x)
	{	
		last_visit(t[x].l, ans);
		last_visit(t[x].r, ans);			
		ans.push_back(t[x].val); 
	}
}
vector <int> getAnswer(vector <int> v) {
	root = cnt = 0;
	
	//将序列中的元素插入到二叉排序树中 
	for(int i = 0 ; i < int(v.size()); ++i) {
		root = insert(v[i] , root);
	} 
	
	vector<int> ans;
	pre_visit(root, ans);
	last_visit(root, ans);
	
	return ans;
} 

int main() {
	vector<int> V;
	scanf("%d", &n);
	for(int i = 0 ; i < n ; ++i) {
		int tmp;
		scanf("%d", &tmp);
		V.push_back(tmp);
	}
	
	vector<int> ans = getAnswer(V);
	
	for(int i = 0 ; i < n ; ++i)
		printf("%d%c", ans[i], " \n"[i == n - 1]);
	for(int i = 0 ; i < n ; ++i)
		printf("%d%c", ans[i + n], " \n"[i == n - 1]);
		
	return 0;	
}

首先将序列保存到一个向量中,调用getAnswer函数,在getAnswer函数内部,会首先调用insert函数,将vector中的每个数据递归地插入到二叉排序中,这块有许多细节需要注意,比如如果是一个空节点的情况,对应节点的l,r和val肯定都是需要更新的。但更重要的是,如何给每个节点进行编号,这里使用cnt来操作,每插入一个节点,都要更新一下cnt的值,然后赋值给相应的x,以免在插入的过程中,有值被覆盖。最后就是先序遍历和后序遍历的结果保存在ans向量中,这块学过数据结构的应该都会操作。

最后还有一个比较骚的操作就是" \n"[i == n - 1],应该把它看作一个整体,方框表示数组索引,当i=n-1的时候,这个表达式的值为真,结果为1,所以就会输出\n,否则会输出空格。

立志成为一名攻城狮
最后更新于 2020-03-11