文档章节

包含min函数的栈

F
 FollowMee
发布于 2017/06/24 20:36
字数 291
阅读 0
收藏 0

包含min函数的栈

题目内容:定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数

解法:对象中持有两个list,一个用来模拟栈结构保存数据,另外一个保存最小值

  • 常规写法
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.s1 = []
        self.s2 = []
        
    def push(self, node):
        # write code here
        if not self.s1 and not self.s2: #栈空间为空时插入
            self.s1.append(node)
            self.s2.append(node)
        else:
            self.s1.append(node)
            if node < self.s2[-1]: #插入值小于最小栈顶点值时
                self.s2.append(node)
            else:
                self.s2.append(self.s2[-1]) #插入值大于最小栈顶点值时
    def pop(self):
        # write code here
        if self.s1 and self.s2:
            self.s2.pop()
            return self.s1.pop()
        return None
    def top(self):
        # write code here
        if self.s1:
            return self.s1[-1]
        return None
    def min(self):
        # write code here
        if self.s2:
            return self.s2[-1]
        return None

注意:边界条件

  • Pythonic

直接使用一个list来模拟栈,最小值使用内置min函数得到

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.s = []
    def push(self, node):
        # write code here
        self.s.append(node)
    def pop(self):
        # write code here
        if self.s:
            return self.s.pop()
        return None
    def top(self):
        # write code here
        if self.s:
            return self.s[-1]
        return None
    def min(self):
        # write code here
        if self.s:
            return min(self.s)
        return None

 

© 著作权归作者所有

共有 人打赏支持
F
粉丝 1
博文 8
码字总数 2003
作品 0
面试题_设计包含 min函数的栈

设计包含 min函数的栈() 定义栈的数据结构,要求添加一个 minminmin函数,能够得到栈的最小元素。 要求函数 min、push以及 pop 的时间复杂度都是 O(1)。 #include <iostream>using namespa...

梦想游戏人
2015/07/01
0
0
C++学习笔记(六)

题目:栈的压入与弹出序列 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序,假设压入栈的所有数字均不相等。例如:序列1、2、3、4、5是某栈的压栈序列...

初雪之音
2016/01/21
18
0
包含min函数的栈

题目:定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中,调用min、push及pop的时间复杂度都是O(1)。 解题思路:把每次的最小元素都保存起来放到另外一个辅助...

许大树
2017/10/19
0
0
算法3-设计包含min函数的栈

题目:定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。 要求函数min、push以及pop的时间复杂度都是O(1)。 思路:使用一个辅助栈来保存最小元素,这个解法简单不失优雅。设该...

kuanshang
2014/03/06
0
0
Java面试题:栈和队列的实现

面试的时候,栈和队列经常会成对出现来考察。本文包含栈和队列的如下考试内容: (1)栈的创建 (2)队列的创建 (3)两个栈实现一个队列 (4)两个队列实现一个栈 (5)设计含最小函数min()...

umgsai
2016/09/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

OSChina 周三乱弹 —— 我居然在 osc 里追剧

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @舆情风控小组 :分享王菲的单曲《笑忘书》 《笑忘书》- 王菲 手机党少年们想听歌,请使劲儿戳(这里) @艾尔库鲁斯:如果给大家一个选择的机...

小小编辑
44分钟前
70
6
rabbitMq的客户端使用笔记

1、channel声明队列的queueDeclare方法的参数解析 durable: 是否持久化, 队列的声明默认是存放到内存中的,如果rabbitmq重启会丢失,如果想重启之后还存在就要使队列持久化,保存到Erlang自...

DemonsI
53分钟前
0
0
“全新” 编程语言 Julia开箱体验

本文共 851字,阅读大约需要 3分钟 ! 概 述 Julia 是一个 “全新”的高性能动态编程语言,前两天迎来了其 1.0 正式版的重大更新。Julia集 Python、C、R、Ruby 之所长,感觉就像一种脚本语言...

CodeSheep
今天
12
0
软件自动化测试初学者忠告

题外话 测试入门 很多受过高等教育的大学生经常问要不要去报测试培训班来入门测试。 答案是否。 高等教育的合格毕业生要具备自学能力,如果你不具备自学能力,要好好地反省一下,为什么自己受...

python测试开发人工智能安全
今天
5
0
java并发备忘

不安全的“先检查后执行”,代码形式如下: if(条件满足){ //这里容易出现线程安全问题//doSomething}else{//doOther} 读取-修改-写入 原子操作:使用CAS技术,即首先从V中读取...

Funcy1122
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部