基本思想:
进栈出栈变换形式:
举例来说,如果我们现在是有3个整形数字元素1、2、3依次进栈,会有那些出栈次序呢?
有没可能312这样的次序出栈呢?
答案肯定不可能
。因为3先出栈,就意味着,3曾经进过栈,既然3进栈了,那也就意味着,1和2页进栈了,此时2一定在1上面,就是更接近栈顶,那么出栈只可能是321,不然不满足123依次进栈的要求,所以不会出现1比2先出栈的情况。
先通过python实现栈
栈的python实现
栈支持以下操作:
Stack() 创建一个空栈。不需要参数,且会返回一个空栈。
push(item)将一个元素添加到栈的顶端。他需要一个参数item,且无返回值。 (即进栈)
#pop()将栈顶端的元素移除。它不需要参数,但会返回顶端的元素,并且修改栈的内容。 (即出栈)
peek()返回栈顶端的元素,但是并不移除该元素。他不需要返回参数,也不会修改栈的内容。
isEmpty() 检查栈是否为空。它不需要参数,且会返回一个布尔值。
size() 返回栈中元素的数目。它不需要参数,且会返回一个整数。
Class Stack: ##定义一个栈类
def __init__(self): ##初始化栈
self.items = []
def isEmpty(self): #判断是否为空
return self.items == []
def push(self,item): #进栈
self.items.append(item)
def pop(self): #出栈
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(slef): # 获取大小
return len(self.items)
进行调试
if __name__ == "__main__":
opstack = Stack() ## 建立一个空栈
a = [6,5,4]
opstack.push(a)
if not opstack.isEmpty():
print(opstack.pop())
运行结果:
[6, 5, 4]
“xyzyx”是一个回文字符串,所谓回文字符串就是指正读反读均相同的字符序列,如“席主席”、“记书记”、“aha”和“ahaha”均是回文,但“ahah”不是回文。通过栈这个数据结构我们将很容易判断一个字符串是否为回文。
mid = len / 2 -1
具体代码如下:
def Palindrome_str(my_str):
L = len(my_str) #字符串长度
mid = len(my_str)/2 -1 #找出中间节点
## 后部分开始的起点位置
if L % 2 == 0:
next = int(mid) + 1
else:
next = int(mid) + 2
palindstack = Stack() ##创建空栈
## 特殊情况
if L <= 1:
print("{}是回文字符串".format(my_str))
return True
else:
for i in range(int(mid)+1): ## 前半部分入栈
str_bef = my_str[i]
print(str_bef)
palindstack.push(str_bef)
## 判断是否为回文
for j in range(next,L):
str_after = my_str[j]
print(str_after)
if str_after == palindstack.peek():
palindstack.pop()
else:
return False
if palindstack.isEmpty():
print("{} 是 回文字符串".format(my_str))
return True
if __name__ == "__main__":
s = "上海自来水来自海上"
# s = "haah"
ans = Palindrome_str(s)
print(ans)
上海自来水来自海上 是 回文字符串
True
haah 是 回文字符串
True
或者使用python自带的后进先出队列
# palindstack = Stack() ##创建空栈
palindstack = queue.LifoQueue() ##创建空栈
# palindstack.push(str_bef)
palindstack.put(str_bef)
# if str_after == palindstack.peek():
# palindstack.pop()
# else:
# return False
if str_after == palindstack.get():
continue
else:
return False
将上述代码进行相应更改即可
利用其他方法实现
def isParlinromic(my_str):
L = len(my_str) # 字符串长度
mid = len(my_str) / 2 - 1 # 找出中间节点
for i in range(int(mid)+1):
if my_str[i] != my_str[L-i-1]:
return False
return True
def isParlinromic02(my_str):
ls = list(my_str)
ls.reverse()
return my_str == "".join(ls)
def isParlinromic03(my_str):
return my_str == "".join(reversed(my_str))
def isParlinromic04(my_str):
return my_str == my_str[::-1]
if __name__ == "__main__":
# s = "上海自来水来自海上"
# s = "haah"
s = "hastah"
ans = isParlinromic03(s)
print(ans)
星期天小哼和小哈约在一起玩桌游,他们正在玩一个非常古怪的扑克游戏——“小猫钓鱼”。游戏的规则是这样的:将一副扑克牌平均分成两份,每人拿一份。小哼先拿出手中的第一张扑克牌放在桌上,然后小哈也拿出手中的第一张扑克牌,并放在小哼刚打出的扑克牌的上面,就像这样两人交替出牌。出牌时,如果某人打出的牌与桌上某张牌的牌面相同,即可将两张相同的牌及其中间所夹的牌全部取走,并依次放到自己手中牌的末尾。当任意一人手中的牌全部出完时,游戏结束,对手获胜。
先出队尾的牌,收牌是从前往后收,即[3, 4, 5, 6, 4],比如受理的牌为[1,2 ,5] 则收完[4, 5, 6, 4] 变为 [4, 5, 6, 4,1,2,5];
在出牌出的是队尾的牌,即 出的是: 5。
代码如下:
"""生成牌"""
card = []
# 生成牌
for i in range(1, 14):
if i == 1:
i = "A"
elif i == 11:
i = "J"
elif i == 12:
i = "Q"
elif i == 13:
i = "K"
"""同种牌4张,故添加4次"""
card.append(str(i))
card.append(str(i))
card.append(str(i))
card.append(str(i))
"""洗牌"""
for i in range(1000):
random.shuffle(card) # 1000次洗牌 保证牌够乱
"""发牌"""
n = int(len(card) / 2)
playerHa = card[:n]
playerHeng = card[n:]
# ## 测试数据
# playerHa = [2,4,1,2,5,6]
# playerHeng = [3,1,3,5,6,4]
"""展示两个人的牌"""
print("小哈的牌:",playerHa)
print("小哼的牌:",playerHeng)
"""模拟游戏过程"""
tmp = []
playercount = 0 ##记录谁出的牌
# desk_card = Stack()
def addCard(n):
global playerHa,playerHeng,tmp,playercount
playercount += 1
if n not in tmp: ## 如果没有相同的牌则把牌添加到tmp中
tmp.append(n)
print("桌上的牌:",tmp)
else:
tmp.append(n) # 如果在 先把牌添加到桌面上
nIndex = tmp.index(n) # 获取相同牌的索引
print('桌上的牌', tmp)
if playercount % 2 == 1: ## # 根据出牌计数器来判断是谁出的牌
playerHa = tmp[nIndex:] + playerHa
print('小哈的牌:', playerHa)
else:
playerHeng = tmp[nIndex:] + playerHeng # 把赢的牌添加到小哼手里中
print('小哼的牌:', playerHeng)
tmp = tmp[:nIndex] # 把已经赢的牌剔除
while True:
# 简化的代码
addCard(playerHa.pop())
addCard(playerHeng.pop())
if len(playerHa) == 0 or len(playerHeng) == 0:
print('游戏结束'.center(30, '*'))
if len(playerHa) > len(playerHeng):
print('小哈胜利')
print('小哈的牌:', playerHa)
print('小哼的牌:', playerHeng)
print('桌上的牌', tmp)
break
else:
print('小哼胜利')
print('小哼的牌:', playerHeng)
print('小哈的牌:', playerHa)
print('桌上的牌', tmp)
break
出牌时:队首先出,如【2,13,4】先出的是2
收牌时:如桌上已有牌:【2,3,4,5】这时出牌为3,则收牌为5,4,3的顺序收。
代码如下
:
import pandas as pd
import numpy as np
import random
import queue
class Stack: ## 定义一个栈类
def __init__(self): ##初始化为空栈
self.items = []
def isEmpty(self): ## 判断空栈
return self.items == []
def push(self,item): ## 进栈
self.items.append(item)
def pop(self): ## 出栈
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(self): ## 获取大小长度
return len(self.items)
"""生成牌洗牌发牌"""
def get_card():
"""生成牌"""
card = []
# 生成牌
for i in range(1, 14):
if i == 1:
i = "A"
elif i == 11:
i = "J"
elif i == 12:
i = "Q"
elif i == 13:
i = "K"
"""同种牌4张,故添加4次"""
card.append(str(i))
card.append(str(i))
card.append(str(i))
card.append(str(i))
"""洗牌"""
for i in range(100):
random.shuffle(card) # 1000次洗牌 保证牌够乱
playerHa = queue.Queue()
playerHeng = queue.Queue()
n = int(len(card) / 2)
Ha = card[:n]
Heng = card[n:]
for j in range(len(Ha)):
playerHa.put(Ha[j])
playerHeng.put(Heng[j])
return playerHa,playerHeng
def get_str_num(t):
num = 0
if t == "A":
num = 1
elif t == "J":
num = 11
elif t == "Q":
num = 12
elif t == "K":
num = 13
else:
num = int(t)
return num
def who_win(playerHa,playerHeng):
S = []
book = np.zeros(14)
while playerHa.qsize() != 0 and playerHeng.qsize() != 0:
"""小哼出牌"""
t = playerHeng.get()
num = get_str_num(t) ## 字母转换为数字
if book[num] == 0:
book[num] = 1
S.append(t) ## 桌上的牌
else:
playerHeng.put(t)
nIndex = S.index(t)
print("桌上的牌:", S)
print("相同的牌:", S[nIndex:][::-1])
for i in S[nIndex:][::-1]:
num = get_str_num(i) ## 字母转换为数字
book[num] = 0
print(i)
playerHeng.put(i)
# print(playerHa)
del S[nIndex:]
"""小哈出牌"""
t = playerHa.get()
num = get_str_num(t) ## 字母转换为数字
if book[num] == 0:
book[num] = 1
S.append(t)
else:
playerHa.put(t)
# pai = S.pop()
nIndex = S.index(t)
print("桌上的牌:", S)
print("相同的牌:", S[nIndex:][::-1])
for i in S[nIndex:][::-1]:
num = get_str_num(i) ## 字母转换为数字
book[num] = 0
playerHa.put(i)
# print(playerHa)
del S[nIndex:]
if playerHa.qsize() == 0:
print('游戏结束'.center(40, '*'))
print("小哼赢牌")
print("小哼手里的牌:")
while playerHeng.qsize() !=0:
print(playerHeng.get(),end=" ")
print("\n")
if len(S) == 0:
print("桌上已经没有牌了")
else:
print("桌上的牌:",S)
elif playerHeng.qsize() == 0:
print('游戏结束'.center(30, '*'))
print("小哈赢牌")
print("小哈手里的牌:")
while playerHa.qsize() != 0:
print(playerHa.get(),end=" ")
print("\n")
if len(S) == 0:
print("桌上已经没有牌了")
else:
print("桌上的牌:",S)
if __name__ == "__main__":
"""发牌"""
playerHa = get_card()[0]
playerHeng = get_card()[1]
"""游戏开始"""
who_win(playerHa, playerHeng)
* 第二个代码是按照《啊 哈 算法》这本书中的思想进行实现的。
* 桌子上的牌用栈表示,先进后出;手中的牌用队列表示,先进先出;有相同牌是用数组表示,即桶排序的思想很像。
这些只是本人用来记录学习算法内容的一些笔记,用来监督自己学习的,有不对的地方望指正!
【参考文献】
文章浏览阅读3.5k次,点赞2次,收藏13次。为了从FTP服务器下载文件,需要要实现一个简单的FTP客户端。FTP(文件传输协议) 是 TCP/IP 协议组中的应用层协议。FTP协议使用字符串格式命令字,每条命令都是一行字符串,以“\r\n”结尾。客户端发送格式是:命令+空格+参数+"\r\n"的格式服务器返回格式是以:状态码+空格+提示字符串+"\r\n"的格式,代码只要解析状态码就可以了。读写文件需要登陆服务器,特殊用..._ftp 登录返回230
文章浏览阅读648次。前提:systemctl stop firewalld 关闭防火墙关闭selinux查看getenforce临时关闭setenforce 0永久关闭sed-i'/SELINUX/s/enforcing/disabled/'/etc/selinux/configselinux的三种模式enforcing:强制模式,SELinux 运作中,且已经正确的开始限制..._centos7 安装rabbitmq3.6.5
文章浏览阅读5.8k次。满意答案s55f2avsx2017.09.05采纳率:46%等级:12已帮助:5646人新版Android Studio/IntelliJ IDEA可以直接导入eclipse项目,不再推荐使用eclipse导出gradle的方式2启动Android Studio/IntelliJ IDEA,选择 import project3选择eclipse 项目4选择 create project f..._android studio 项目导入idea 看不懂安卓项目
文章浏览阅读860次,点赞2次,收藏6次。AI大模型技术已经在自然语言处理、计算机视觉、多模态交互等领域取得了显著的进展和成果,同时也引发了一系列新的挑战和问题,如数据质量、计算效率、知识可解释性、安全可靠性等。城市运维涉及到多个方面,如交通管理、环境监测、公共安全、社会治理等,它们需要处理和分析大量的多模态数据,如图像、视频、语音、文本等,并根据不同的场景和需求,提供合适的决策和响应。知识搜索有多种形式,如语义搜索、对话搜索、图像搜索、视频搜索等,它们可以根据用户的输入和意图,从海量的数据源中检索出最相关的信息,并以友好的方式呈现给用户。_ai大模型应用开发
文章浏览阅读8.2k次,点赞12次,收藏121次。为什么要测量阻抗呢?阻抗能代表什么?阻抗测量的注意事项... ...很多人可能会带着一系列的问题来阅读本文。不管是数字电路工程师还是射频工程师,都在关注各类器件的阻抗,本文非常值得一读。全文13000多字,认真读完大概需要2小时。一、阻抗测试基本概念阻抗定义:阻抗是元器件或电路对周期的交流信号的总的反作用。AC 交流测试信号 (幅度和频率)。包括实部和虚部。图1 阻抗的定义阻抗是评测电路、元件以及制作元件材料的重要参数。那么什么是阻抗呢?让我们先来看一下阻抗的定义。首先阻抗是一个矢量。通常,阻抗是_阻抗实部和虚部
文章浏览阅读955次。前面章节分享试用了pyzero,pygame但随着想增加更丰富的游戏内容,好多还要进行自己编写类,从今天开始解绍一个新的python游戏库arcade模块。通过此次的《连连看》游戏实现,让我对swing的相关知识有了进一步的了解,对java这门语言也有了比以前更深刻的认识。java的一些基本语法,比如数据类型、运算符、程序流程控制和数组等,理解更加透彻。java最核心的核心就是面向对象思想,对于这一个概念,终于悟到了一些。_arcade语言 like
文章浏览阅读1.1k次。源码简介与安装说明:2021增强版短视频去水印源码 去水印微信小程序源码网站 去水印软件源码安装环境(需要材料):备案域名–服务器安装宝塔-安装 Nginx 或者 Apachephp5.6 以上-安装 sg11 插件小程序已自带解析接口,支持全网主流短视频平台,搭建好了就能用注:接口是公益的,那么多人用解析慢是肯定的,前段和后端源码已经打包,上传服务器之后在配置文件修改数据库密码。然后输入自己的域名,进入后台,创建小程序,输入自己的小程序配置即可安装说明:上传源码,修改data/_去水印机要增强版
文章浏览阅读557次。1. 触发器是FPGA存储数据的基本单元2. 触发器作为时序逻辑的基本元件,官方提供了丰富的配置方式,以适应各种可能的应用场景。_fdre #(.init(1'b0) // initial value of register (1'b0 or 1'b1) ) fdce_osc (
文章浏览阅读560次。本该是不同编译器结果不同,但是尝试了g++ msvc都是先计算c,再计算b,最后得到a+b+c是经过赋值以后的b和c参与计算而不是6。由上表可知,将q复制到p数组可以表示为:*p++=*q++,*优先级高,先取到对应q数组的值,然后两个++都是在后面,该行运算完后执行++。在电脑端编译完后会分为text data bss三种,其中text为可执行程序,data为初始化过的ro+rw变量,bss为未初始化或初始化为0变量。_嵌入式面试笔试c语言知识点
文章浏览阅读2.3k次。57 Things I've Learned Founding 3 Tech CompaniesJason Goldberg, Betashop | Oct. 29, 2010, 1:29 PMI’ve been founding andhelping run techn_mature
文章浏览阅读1.9k次。问题:先讲下需求,有若干个文本文件(txt或者csv文件等),每行代表一条数据,现在希望能合并成 1 个文本文件,且需要去除重复行。分析:一向奉行简单原则,如无必要,绝不复杂。如果数据量不大,那么如下两条命令就可以搞定合并:cat a.txt >> new.txtcat b.txt >> new.txt……去重:cat new...._python 超大文本合并
文章浏览阅读489次。这个过渡页是第一次打开小程序展示的,点击某个小程序前把手机的开发者->network link conditioner->enable & very bad network 就会在停在此页。比如《支付宝运动》这个小程序先看这个类的.h可以看到它继承于DTViewController点击左上角返回的方法- (void)back;#import "DTViewController.h"#import "APBaseLoadingV..._类似支付宝页面过度加载页