文档章节

包含min函数的栈

F
 FollowMee
发布于 2017/06/24 20:36
字数 291
阅读 0
收藏 0
点赞 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

C++学习笔记(六)

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

初雪之音 ⋅ 2016/01/21 ⋅ 0

包含min函数的栈

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

许大树 ⋅ 2017/10/19 ⋅ 0

算法3-设计包含min函数的栈

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

kuanshang ⋅ 2014/03/06 ⋅ 0

栈和队列的面试题Java实现【重要】

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

商者 ⋅ 2016/04/10 ⋅ 0

Java面试题:栈和队列的实现

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

umgsai ⋅ 2016/09/10 ⋅ 0

栈和队列的面试题Java实现

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

天蚕宝衣 ⋅ 2016/03/31 ⋅ 0

编程题——21~30

二十一、包含min函数的栈 定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中,调 用min、push及pop的时间复杂度都是O(1)。 二十二、栈的压入、弹出序列 输入两...

thanatos_y ⋅ 2016/07/22 ⋅ 0

设计包含min函数的栈

定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。 分析: 在栈里添加一个成员变量存放最小元素(或最小元素的位置)。每次p...

Zhang_H ⋅ 2014/04/09 ⋅ 0

[LeetCode] Min Stack 最小栈

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) -- Push element x onto stack. pop() -- Removes the element on top of th......

机器的心脏 ⋅ 2017/12/11 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Jenkins实践3 之脚本

#!/bin/sh# export PROJ_PATH=项目路径# export TOMCAT_PATH=tomcat路径killTomcat(){pid=`ps -ef | grep tomcat | grep java|awk '{print $2}'`echo "tom...

晨猫 ⋅ 今天 ⋅ 0

Spring Bean的生命周期

前言 Spring Bean 的生命周期在整个 Spring 中占有很重要的位置,掌握这些可以加深对 Spring 的理解。 首先看下生命周期图: 再谈生命周期之前有一点需要先明确: Spring 只帮我们管理单例模...

素雷 ⋅ 今天 ⋅ 0

zblog2.3版本的asp系统是否可以超越卢松松博客的流量[图]

最近访问zblog官网,发现zlbog-asp2.3版本已经进入测试阶段了,虽然正式版还没有发布,想必也不久了。那么作为aps纵横江湖十多年的今天,blog2.2版本应该已经成熟了,为什么还要发布这个2.3...

原创小博客 ⋅ 今天 ⋅ 0

聊聊spring cloud的HystrixCircuitBreakerConfiguration

序 本文主要研究一下spring cloud的HystrixCircuitBreakerConfiguration HystrixCircuitBreakerConfiguration spring-cloud-netflix-core-2.0.0.RELEASE-sources.jar!/org/springframework/......

go4it ⋅ 今天 ⋅ 0

二分查找

二分查找,也称折半查找、二分搜索,是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于...

人觉非常君 ⋅ 今天 ⋅ 0

VS中使用X64汇编

需要注意的是,在X86项目中,可以使用__asm{}来嵌入汇编代码,但是在X64项目中,再也不能使用__asm{}来编写嵌入式汇编程序了,必须使用专门的.asm汇编文件来编写相应的汇编代码,然后在其它地...

simpower ⋅ 今天 ⋅ 0

ThreadPoolExecutor

ThreadPoolExecutor public ThreadPoolExecutor(int corePoolSize, int maximumPoolSize, long keepAliveTime, ......

4rnold ⋅ 昨天 ⋅ 0

Java正无穷大、负无穷大以及NaN

问题来源:用Java代码写了一个计算公式,包含除法和对数和取反,在页面上出现了-infinity,不知道这是什么问题,网上找答案才明白意思是负的无穷大。 思考:为什么会出现这种情况呢?这是哪里...

young_chen ⋅ 昨天 ⋅ 0

前台对中文编码,后台解码

前台:encodeURI(sbzt) 后台:String param = URLDecoder.decode(sbzt,"UTF-8");

west_coast ⋅ 昨天 ⋅ 0

实验楼—MySQL基础课程-挑战3实验报告

按照文档要求创建数据库 sudo sercice mysql startwget http://labfile.oss.aliyuncs.com/courses/9/createdb2.sqlvim /home/shiyanlou/createdb2.sql#查看下数据库代码 代码创建了grade......

zhangjin7 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部