栈与队列(二)

本小节主要介绍栈与队列的基本应用,将结合实例进行讲解。一、队列的入队与出队操作队列属于一种特殊的线性表,只能在队首或者队尾对其操作。与栈不同的是,它要求先进先出。

例: n个人围成一圈顺序编号,从1号开始按1、2、3......顺序报数,报k者退出圈外,其余的人再从1、2、3开始报数,报k的人再退出圈外,以此类推,其中n、k均为有效值。 请按退出顺序输出每个退出人的原序号。

测试样例:

输入:7 3输出:3 6 2 7 5 1 4

分析:由于是最小的编号开始报数,每次报道k这出队,所以我们可以采用一个队列进行模拟。不过,队尾的后一个人是队首,因此这是一个特殊的队列,即循环队列。当然,由于约瑟夫环中每次出队后存在映射关系,因此本体还有一种采用数学公式的高效解法,有兴趣的可以进一步了解。

代码实现:

class Solution(object): def JosephusCircle(self, n, k): """ :type n, k: int :rtype: List """ res=[] circle=collections.deque() for i in range(n): circle.append(i+1) while len(circle): cnt=k-1 while cnt>0: tmp=circle.popleft() circle.append(tmp) cnt-=1 res.append(circle.popleft()) return res

二、栈的入栈与出栈操作与队列一样,栈也是一种特殊的线性表,它只能在栈顶操作,要求先进后出。

例:给一个字符串只包含'(', ')', '{', '}', '[' 和']',括号的使用必须符合标准,判断该输入字符串是否是有效的。

测试样例:

"()" 和"()[]{}" 有效的,而 "(]" and "([)]" 是无效的。

分析:这个是典型的栈使用问题,读入一个字符如果它是右半括号,则弹出栈顶与之匹配的左括号,如果这样的左括号不存在或者不为右括号,则将其入栈。最后判断栈是否为空,若为空则匹配,返回true;否则返回false。

代码实现:

class Solution: def isValid(self, s): """ :type s: str :rtype: bool """ if len(s)0: return False return True

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180525G06NXX00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

同媒体快讯

扫码关注云+社区

领取腾讯云代金券