咸宁住房和城乡规划建设局网站,记事本做网站怎么改字体颜色,网站建设及推广开发,适合穷人翻身的10个行业栈 描述 实现一个栈#xff0c;完成以下功能#xff1a; 入栈出栈询问栈中位置Y是谁 一开始栈为空。栈中的位置从1开始#xff08;即栈底位置为1#xff09;。 输入 第一行一个整数n#xff0c;表示操作个数。 接下来n行#xff0c;每行第一个数字表示操作#xff08;见… 栈 描述 实现一个栈完成以下功能 入栈出栈询问栈中位置Y是谁 一开始栈为空。栈中的位置从1开始即栈底位置为1。 输入 第一行一个整数n表示操作个数。 接下来n行每行第一个数字表示操作见描述 若为数字1则接下来有一串字符串X表示将X压入栈中。若为数字2表示弹出栈顶保证栈非空并输出出栈的这个人。若为数字3则接下来有一个整数Y表示询问栈中位置Y是谁保证位置Y合法并输出名字。 输出 将所有操作2和操作3输出一行一个。 输入样例 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限制 对于30%的数据1 ≤ n ≤ 2000 对于另30%的数据没有操作3 对于100%的数据1 ≤ n ≤ 100000。 数据中出现的字符串只包含26个小写字母无空格等分隔符且长度不超过15。 字符串有可能重复。正如现实中可能有重名一样。 时间2 sec 空间256 MB 提示 [入栈和出栈都是操作着栈顶。] [开一个大小为n的数组记录栈顶的位置入栈出栈就是将这栈顶加一减一栈中某个位置Y在数组相应的下标就是Y。] 实现代码 class Stack:def __init__(self):self.stack []def push(self, name):self.stack.append(name)def pop(self):if self.stack:return self.stack.pop()def peek(self, index):return self.stack[index - 1]stack Stack()n int(input())
output []for _ in range(n):operation input().split()if operation[0] 1:name operation[1]stack.push(name)elif operation[0] 2:popped stack.pop()if popped:output.append(popped)elif operation[0] 3:index int(operation[1])output.append(stack.peek(index))for item in output:print(item)队列 描述 实现一个队列完成以下功能 入列出列询问队列中位置Y是谁 一开始队列为空。队列中的位置从1开始即队头位置为1。 输入 第一行一个整数n表示操作个数。 接下来n行每行第一个数字表示操作见描述 若为数字1则接下来有一串字符串X表示将X加入队列。若为数字2表示出列保证队列非空并输出出列的这个人。若为数字3则接下来有一个整数Y表示询问队列中位置Y是谁保证位置Y合法并输出名字。 输出 将所有操作2和操作3输出一行一个。 输入样例 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
a
b
c
d限制 对于30%的数据1 ≤ n ≤ 2000 对于另30%的数据没有操作3 对于100%的数据1 ≤ n ≤ 100000。 数据中出现的字符串只包含26个小写字母无空格等分隔符且长度不超过15。 字符串有可能重复。正如现实中可能有重名一样。 时间2 sec 空间256 MB 提示 [队头出列队尾入列。] [开一个大小为n的数组记录队头和队尾的位置入列出列就是将这两个位置改变一下队列中某个位置Y在数组相应的下标为队头的位置Y-1。] 实现代码 class Queue:def __init__(self):self.queue []def enqueue(self, name):self.queue.append(name)def dequeue(self):if len(self.queue) 0:return Nonereturn self.queue.pop(0)def get_name_at_position(self, position):return self.queue[position - 1]# 读取输入
n int(input())
queue Queue()# 处理操作
for _ in range(n):operation input().split()if operation[0] 1:queue.enqueue(operation[1])elif operation[0] 2:print(queue.dequeue())elif operation[0] 3:position int(operation[1])print(queue.get_name_at_position(position))二叉树 描述 给定一个1到n的排列按顺序依次插入到一棵二叉排序树中请你将这棵二叉树前序遍历和后序遍历输出。 前序遍历的定义 后序遍历的定义 输入 第一行一个整数n。 接下来一行表示为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限制 对于50%的数据1 ≤ n ≤ 100 对于100%的数据1 ≤ n ≤ 100000。 保证建成的树的高度不超过50。 时间2 sec 空间256 MB 提示 [二叉树的操作基本都是递归操作只要想想如何在一个节点上判断是朝着左孩子走还是朝着右孩子走就行了。] 实现代码 class TreeNode:def __init__(self, val):self.val valself.left Noneself.right Nonedef insert_into_bst(root, val):if root is None:return TreeNode(val)if val root.val:root.left insert_into_bst(root.left, val)else:root.right insert_into_bst(root.right, val)return rootdef preorder_traversal(root):if root is None:return []return [root.val] preorder_traversal(root.left) preorder_traversal(root.right)def postorder_traversal(root):if root is None:return []return postorder_traversal(root.left) postorder_traversal(root.right) [root.val]# 读取输入
n int(input())
permutation list(map(int, input().split()))# 构建二叉排序树
bst_root None
for num in permutation:bst_root insert_into_bst(bst_root, num)# 输出前序遍历和后序遍历
preorder_result preorder_traversal(bst_root)
postorder_result postorder_traversal(bst_root)print( .join(map(str, preorder_result)))
print( .join(map(str, postorder_result)))
