文章目录
- 前言
- 1.卡片游戏?♂?
-
- 问题描述
- 问题分析
- 代码实现
- 2.铁轨问题?♂?
-
- 问题描述
- 问题分析
- 代码实现
- 3.移动小球??♂?
-
- 问题描述
- 问题分析
- 代码实现
- ????????
前言
两日不见，超级想念。由于在学校比较忙停更了两天,但是算法题还是在继续写的。今天分享一下在与队列栈相关的算法题。在Python中是没有内置的栈结构的,不像C++中的STL容器,但是我们可以自己实现一个栈。对于队列的话Python内置的collections中有成熟的双端队列,使用起来超级方便。1.卡片游戏?♂? 问题描述
卡片游戏：使用到的知识与队列有关,直接进行模拟即可
铁轨问题：使用的知识是有关栈的知识。
移动小球：题目的原意考验我们对链表的掌握情况,但是在Python中可以使用相关的语言特点轻松完成。
栈与队列数据结构今天咱就不在这细说拉,直接开始如何使用Python实现栈，如何使用Python的双端队列。
桌上有一叠牌，从第一张牌(即位于顶面的牌)开始从上往下依次编号为1~n。当至问题分析
少还剩两张牌时进行以下操作:把第一张牌扔掉， 然后把新的第一张放到整叠牌的最后。
输入n,输出每次扔掉的牌，以及最后剩下的牌。
样例输入: 7
样例输出: 1 3 5 7 4 2 6
题目比较简单,不用思考直接对题目进行模拟就可以。代码实现
这里使用的是collections模块的deque包
在这个下面是一个双端队列,可以很轻松的从两端删除、添加数据。
老规矩先上运行结果：
文章图片
from collections import deque
dq=deque()
n=int(input())
for i in range(1,n+1):
dq.appendleft(i)while len(dq)>=2:
print(dq.pop(),end=" ")
dq.appendleft(dq.pop())print(dq.pop(),end="")
2.铁轨问题?♂? 问题描述
某城市有一火车站，铁轨铺设如图所示。有n节车厢从A方向驶入车站，按进问题分析
站顺序编号为1~n。你的任务是让它们按照某种特定的顺序进入B方向的铁轨并驶出车站。
为了重组车厢，你可以借助中转站C。这是一个可以停放任意多节车厢的车站，但由于末端
封顶，驶入C的车厢必须按照相反的顺序驶出C。对于每个车厢，旦从A移入C， 就不
能再回到A了; 一旦从C移入B，就不能回到C了。换句话说，在任意时刻，只有两种选
择: A→C和C→B。
文章图片
样例输入:
5
1 2 3 4 5
5
5 4 1 2 3
6
6 5 4 3 2 1
样例输出:
Yes
No
Yes
铁轨问题就是如果进行暴力解决的话会很复杂,因为你不知道有几种情况组合代码实现
好在题目给出了样例输出,也就是说咱们可以将输入的数据与栈内的数据最终结果进行匹配
如果等原始队列中的数据抽完了,并且栈内的元素没有与最终结果相匹配的
就进行输出No，否则原始队列与栈都为空的时候匹配成功输出Yes
这个题目自己实现一个栈并不是必须的,也可以使用列表进行判空判栈顶元素。
老规矩先上运行结果：
文章图片
class Stack(object):
"""栈"""
def __init__(self):
self.items = []
def is_empty(self):
"""判断是否为空"""
return self.items == []
def push(self, item):
"""加入元素"""
self.items.append(item)
def pop(self):
"""弹出元素"""
return self.items.pop()
def top(self):
"""返回栈顶元素"""
return self.items[len(self.items)-1]
def size(self):
"""返回栈的大小"""
return len(self.items)
if __name__ == "__main__":
s= Stack()
n=int(input())
# 输入的最终序列
num=sys.stdin.readline().strip().split()
num=[int(x) for x in num]
# 生成原始序列
ansnum=[i for i in range(1,n+1)]# print(num)
# print(ansnum)# 记录初始跟后续队列位置
i1=0
i2=0
flag=True
while i23.移动小球??♂? 问题描述
你可以执行两种指令。其中，A X Y表示把小球x移动到小球Y左边，问题分析
B X Y表示把小球X移动到小球Y右边。指令保证合法，即X不等于Y。
输入小球个数n，指令条数m和m条指令，从左到右输出最后的序列。注意，n可能
高达500000,而m可能高达100000。
样例输入:
6 2
A 1 4
B 3 5
样例输出:
214536
对于本问题直接进行模拟即可,使用C++或者C语言可能创建一个链表可以更加轻松地完成任务代码实现
对于Python而言合理的使用列表的方法可能会事半功倍。
老规矩先上运行结果：
文章图片
import sys
m,n=sys.stdin.readline().strip().split()
m,n=int(m),int(n)
ls=[]
for i in range(1,m+1):
ls.append(i)
for i in range(n):
q,w,e=sys.stdin.readline().strip().split()
w=int(w)
e=int(e)
# print(w,e)
if q=='A':
ls.remove(w)
ls.insert(ls.index(e),w)
else:
ls.remove(w)
ls.insert(ls.index(e)+1,w)
# print(ls)
for i in ls:
print(i,end="")???????? ???? ? ???? ????
今日分享的算法题你了吗？
推荐阅读
- Python从入门到精通|【Python 百练成钢】高精度加法、阶乘计算、矩阵幂运算、矩阵面积交
- 算法|「推荐系统中的特征工程」02（推荐系统与特征工程）
- 计算机组成原理学习------第四章数据运算
- milvus|PaddleRec与Milvus深度结合，手把手带你体验工业级推荐系统召回速度
- 计算机组成原理|计算机组成原理-第二章（10）浮点数-整章
- 搞笑整活系列|Python基础-“百钱百鸡”入门逻辑题（刚开始的建议藏起来）
- 蓝桥杯|蓝桥python——玩具蛇
- 蓝桥杯|蓝桥python——方格分割【2017 第四题】
- CTF|2021DASCTF八月挑战赛Writeup