精华内容
下载资源
问答
  • #!/usr/bin/env python # encoding: utf-8 ''' Python程序员面试算法宝典---解题总结: 第二章 栈、队列与哈希 2.5 如何用O(1)的时间复杂度求栈中最小元素 ...那么问题的关键就是如何在压入元素的时候确保最小元素在...
    #!/usr/bin/env python
    # encoding: utf-8
    
    '''
    Python程序员面试算法宝典---解题总结:  第二章 栈、队列与哈希 2.5 如何用O(1)的时间复杂度求栈中最小元素
    
    分析:
    O(1)时间查找到最小的元素最容易实现的方式就是将最小元素始终放在栈顶,
    这样每次只需要获取栈顶元素,即可获取最小元素。
    那么问题的关键就是如何在压入元素的时候确保最小元素在栈顶。
    一种思路就是设置两个栈,对两个栈进行操作。
    举例如下: 假设入栈序列为: 5,3,4,2,1
    假设有栈1为s1,栈2为s2。
    将5压入s1,此时压入3之前,判断s1的栈顶元素为5,此时因为3小于5,就继续把元素3压入到s1中,
    此时s1从站顶到栈顶序列如下:
    s1     s2
    3
    5
    此时判断4大于s1的栈顶元素3,此时不能插入s1中,此时将
    s1中的元素全部压入s2中,直到s1的栈顶元素大于当前待压入元素4,
    最后将元素4压入到s2中,此时s1,s2中元素如下:
    s1      s2
    5       4
            3
    最后每次取出s2栈顶元素压入s2中,直到s2为空,此时s1,s2如下:
    s1      s2
    3
    4
    5
    
    总结:
    算法步骤:
    步骤1: 若栈s1为空,则将当前待压入元素压入到s1中;
    步骤2: 否则,如果s1非空
        2.1 如果当前待压入元素小于s1的栈顶元素,则将当前待压入元素,压入到s1中
        2.2 2.2.1) 否则,只要当前待压入元素大于s1栈顶元素,就弹出s1栈顶元素并压入到栈s2中;
            重复步骤2.2,直到s1为空或者当前待压入元素小于s1栈顶元素;
            2.2.2) 最后将当前待压入元素压入到s2中;
            2.2.3) 只要s2不空,就将s2的栈顶元素不断弹出并压入到s1中。
    通过以上步骤,确保了s1中的栈顶元素始终是最小的元素,即可满足O(1)时间复杂度获取栈中最小元素
    
    弄错了,这个是修改了栈的入栈顺序,弹出栈会出错。
    
    书上的解法:
    用另外一个栈记录最小元素。
    一个元素栈保存原来的真实入栈序列;用一个min栈,
    如果min栈为空,则压入当前待压入元素;
    否则,如果当前待压入元素比min栈的栈顶元素小,则将当前
    待压入元素压入到min栈中。
    出栈的时候,真实入栈序列直接弹出栈顶元素;
    对于min栈,如果待弹出元素和min栈栈顶元素相同,则弹出min栈的栈顶元素。
    
    
    关键:
    1 用另外一个栈记录最小元素。
    一个元素栈保存原来的真实入栈序列;用一个min栈,
    如果min栈为空,则压入当前待压入元素;
    否则,如果当前待压入元素比min栈的栈顶元素小,则将当前
    待压入元素压入到min栈中。
    出栈的时候,真实入栈序列直接弹出栈顶元素;
    对于min栈,如果待弹出元素和min栈栈顶元素相同,则弹出min栈的栈顶元素。
    
    2 用两个栈来回倒腾实现的是排序栈的功能
    
    3 记录一个min栈记录最小元素序列即可。
    当前待插入元素比min栈的栈顶小就插入到min栈中。
    
    
    参考:
    Python程序员面试算法宝典
    '''
    
    class Stack(object):
        def __init__(self):
            self.data = list()
    
        def empty(self):
            result = False if self.data else True
            return result
    
        def push(self, data):
            self.data.append(data)
    
        def pop(self):
            if not self.empty():
                self.data.pop()
            else:
                info = "stack is empty, it can not pop"
                print info
    
        def top(self):
            if not self.empty():
                return self.data[-1]
            else:
                info = "stack is empty, it can not get top element"
                print info
    
    
    class SortStack(object):
        def __init__(self):
            self.stack1 = Stack()
            self.stack2 = Stack()
    
        def empty(self):
            return self.stack1.empty()
    
        def push(self, data):
            if not self.empty():
                while not self.empty() and self.stack1.top() < data:
                    top = self.stack1.top()
                    if top is not None:
                        self.stack2.push(top)
                        self.stack1.pop()
                self.stack2.push(data)
                while not self.stack2.empty():
                    top = self.stack2.top()
                    self.stack2.pop()
                    if top is not None:
                        self.stack1.push(top)
            else:
                self.stack1.push(data)
    
        def pop(self):
            if not self.empty():
                self.stack1.pop()
            else:
                info = "stack is empty, it can not pop"
                print info
    
        def min(self):
            if not self.empty():
                return self.stack1.top()
            else:
                info = "stack is empty, it can not get min element"
                print info
    
    
    class MinStack(object):
        def __init__(self):
            self.elementStack = Stack()
            self.minStack = Stack()
    
        def empty(self):
            return self.elementStack.empty()
    
        def push(self, data):
            self.elementStack.push(data)
            if self.minStack.empty():
                self.minStack.push(data)
            else:
                if data < self.minStack.top():
                    self.minStack.push(data)
    
        def min(self):
            if self.minStack.empty():
                return
            else:
                return self.minStack.top()
    
        def pop(self):
            if self.elementStack.empty():
                info = "stack is empty, it can not pop"
                print info
                return
            data = self.elementStack.top()
            self.elementStack.pop()
            if data == self.min() and self.min is not None:
                self.minStack.pop()
    
    def process():
        data = [5, 3, 4, 2, 1]
        minStack = MinStack()
        for value in data:
            minStack.push(value)
            min = minStack.min()
            print min
        print "####"
        while not minStack.empty():
            minStack.pop()
            print minStack.min()
    
    
    if __name__ == "__main__":
        process()

     

    展开全文
  • 如何在数组寻找元素,对应 underscore 的 _.findIndex,_.findLastIndex,_.indexOf,_.lastIndexOf 以及 _.sortIndex 方法。 等等,是不是有点眼熟,没错,...
  • 思路与分析:遇到问题之前,我们先来思考一个问题,如果题目仅仅是问:给你一个数据栈,要你编码实现去查找栈中最小的元素。那么你要如何实现?这个问题很简单,我们马上就能把代码写出来:package cn.csu; ...

    思路与分析:

    在遇到问题之前,我们先来思考一个问题,如果题目仅仅是问:给你一个数据栈,要你编码实现去查找栈中最小的元素。那么你要如何实现?这个问题很简单,我们马上就能把代码写出来:

    package cn.csu;
    
    import java.util.Stack;
    import java.util.Iterator;
    
    
    public class StackFindMin {
        public int min(Stack<Integer> stack){
            int min = stack.peek();
            Iterator iterator = stack.iterator();
            while (iterator.hasNext()){
                int value = (int)iterator.next();
                if(value<=min){
                    min =value;
                }
            }
            return min;
        }
    
    }
    

    上述代码就实现了对给定栈最小元素的查找。但是,在上述代码的min方法中,通过时间复杂度分析,min方法的时间复杂度为O(n),显然不符合这个题要考察的内容。

    那么如何才能实现在时间复杂度为O(1)的方法中实现查找最小数呢?

    思路:我们借助一个辅助栈,给定栈我们成为数据栈。当有元素入栈时,我们比较入栈元素与原最小元素的大小,如果入栈元素比原最小元素大,那么把该元素入数据栈,把原最小元素入辅助栈。如果入栈元素比原最小元素小,那么把该元素分别入数据栈和辅助栈。这样就保证了辅助栈的栈顶一直都是最小元素。

    我们来看看具体代码实现:

    package cn.csu;
    
    
    import java.util.Stack;
    
    public class StackMin<T extends Comparable<T>> {
        //数据栈
        private Stack<T> dataStack;
        //辅助栈
        private Stack<Integer> supStack;
    
        public StackMin(){
            this.dataStack = new Stack<>();
            this.supStack = new Stack<>();
        }
    
        public T pop(){
            if(dataStack.isEmpty()){
                throw new RuntimeException("数据栈是空的");
            }
            //这里说明一下,如果有数据,那么按照我们的思路可以知道,辅助栈和数据栈的元素个数是相等的
            //这里我们让两个栈都进行出栈操作
            supStack.pop();
            return dataStack.pop();
        }
    
        /**
         * 入栈操作
         * @param t
         */
        public void push(T t){
            //如果入栈元素为空,则跑出异常
            if(t== null) {
                throw new RuntimeException("入栈元素不能为空!");
            }
            if(dataStack.isEmpty()){//如果数据栈是空的,将元素入栈,同时更新最小栈中的数据
                dataStack.push(t);
                supStack.push(0);
            }else{
                //获取数据栈中最小的元素(入栈之前的最小元素)
                T e = dataStack.get(supStack.peek());
                //将t入栈
                dataStack.push(t);
                //比较t和e
                if(t.compareTo(e)<0){//如果t比e小,将t所在的位置(下标)入辅助栈
                    supStack.push(dataStack.size()-1);
    
                }else{
                    // 插入的元素不比原来的最小元素小,复制最小栈栈顶元素,将其入栈
                    supStack.push(supStack.peek());
                }
            }
    
        }
    
        public T min(){
            //如果辅助栈为空,则说明数据栈也为空,则跑出异常
            if(supStack.isEmpty()){
                throw new RuntimeException("栈中没有元素!");
            }
    
            return dataStack.get(supStack.peek());
        }
    
        public static void main(String[] args) {
            StackMin<Integer> stack = new StackMin<>();
            stack.push(3);
            System.out.println(stack.min() == 3);
            stack.push(4);
            System.out.println(stack.min() == 3);
            stack.push(2);
            System.out.println(stack.min() == 2);
            stack.push(3);
            System.out.println(stack.min() == 2);
            stack.pop();
            System.out.println(stack.min() == 2);
            stack.pop();
            System.out.println(stack.min() == 3);
            stack.push(0);
            System.out.println(stack.min() == 0);
        }
    }
    


    展开全文
  • 数据结构--、队列

    2020-08-23 19:59:42
    物理结构: 怎么计算机中如何存 线性结构: 列表 一个挨着一个 数据机构分类 线性机构:一对一 树结构:一对多 图:多对多 线性结构 列表 1.元素怎么存的? 顺序存储,存储一块连续的内存。 2. 按...

    数据结构: 变量怎么存。 数据结构: 数据 + 关系

    算法: 程序怎么运行

     

    数据结构

    物理结构: 怎么在计算机中如何存

    线性结构: 列表  一个挨着一个

     

    数据机构分类

    线性机构:一对一

    树结构:一对多

    图:多对多

     

     

    线性结构

    列表 

    1.元素怎么存的?    顺序存储,存储在一块连续的内存。 

    2. 按下标查找,插入,删除,时间复杂度是多少?   查找、append O(1)     插入删除 O(n)

    3. python的列表是怎么实现的?   说白了 python列表中存储的是地址, 32位计算机,地址占用4字节

     

     

    数组和列表的区别:

    1. 数组元素类型一致

    2. 数组长度固定

     

    栈: 先进后出 , 后进先出

    栈基本操作:

    进栈push,  出栈pop, 取栈顶 gettop

     

     

     

     

    展开全文
  • 学号20162310林臻《程序设计与数据结构》第6周学习总结 教材学习内容总结 本章讨论队列的处理 ...问题1:采用数组实现队列的时候,如何避免移动全部的元素呢 问题1解决方案:书给出了答案,将数组看成一个环形 ...

    学号20162310林臻《程序设计与数据结构》第6周学习总结

    教材学习内容总结

    • 本章讨论队列的处理
    • 队列ADT的学习
    • 与栈进行比较性学习
    • 队列的目标是保持原来的顺序
    • 了解队列在Caesar密码中的运用
    • 模拟票务柜台
    • 学习通过链表实现队列
    • 使用循环数组实现队列

      教材学习中的问题和解决过程

    • 问题1:采用数组实现队列的时候,如何避免移动全部的元素呢
    • 问题1解决方案:书中给出了答案,将数组看成一个环形

    • 问题2:队列和栈的区别在哪儿呢?
    • 问题2解决方案:
    • 队列是先进先出:就像一条路,有一个入口和一个出口,先进去的就可以先出去。
    • 而栈就像一个箱子,后放的在上边,所以后进先出。

    • 问题3:队列有哪儿些用途呢?
    • 问题3解决方案:网络上查了一下,看到了一个很不错的博客,详细分析了队列的应用

      代码调试中的问题和解决过程

    • 问题1:没有明白import javafoundas.exceptions.*;为什么一直报错,尝试了将程序放在javafoundations包下,将异常文件放入exceptions文件中还是会报错。
    • 问题1解决方案:问了同学后得知这是书本上自己的包,所以可以忽略。

      排序课堂作业及课下作业

    • 使用顺序查找和二分查找查找数据
      1064024-20171019222111740-1433961904.png
    • 使用快速排序排序数据
      1064024-20171019222120021-1007938885.png
    • 排序课下作业,用选择排序,插入排序,希尔排序,冒泡排序,快速排序,归并排序分别对数据进行排序
      1064024-20171019222349427-1017326244.png

    用链表实现队列

    • 给出deque,first,isEmpty,size和toString的定义,并用Junit进行单元测试
      1064024-20171019214419162-1493399364.png
      1064024-20171019214435662-236050720.png
    • 遇到的问题就是书上写的抛出的异常EmptyCollectionException借鉴了娄老师

      用数组实现循环队列

      1064024-20171019214907724-1881327674.png
      1064024-20171019214919959-290127454.png

      上周考试错题总结

    本周结对学习情况

    • 20162314
    • 结对照片
    • 结对学习内容

    其他(感悟、思考等,可选)

    加油加油!!!!!!
    脚踏实地!!!!!!

    学习进度条

    代码行数(新增/累积) 博客量(新增/累积) 学习时间(新增/累积) 重要成长
    目标 5000行 30篇 400小时
    第一周 200/200 1/1 20/20
    第二周 200/200 1/1 20/20
    第三周 200/200 1/1 22/22
    第四周 1000/1000 1/1 30/30
    第五周 1000/1000 1/1 22/22
    第六周 1300/1300 4/4 20/20

    转载于:https://www.cnblogs.com/shuailinzhen/p/7674520.html

    展开全文
  • 而只是让每个元素知道它下一个元素的位置哪里。 3.6.1 顺序存储结构不足的解决 办法 55 3.6.2 线性表链式存储结构定义 56 3.6.3 头指针与头结点的异同 58 3.6.4 线性表链式存储结构代码描述 58 3.7 单链表的读取 ...
  • python基本数据结构

    2019-10-06 07:03:08
    列表元素如何存储的:顺序存储 列表的基本操作:按下标查找、插入元素、删除元素... 这些操作的很少见复杂度时多少:查找O(1)、查找 删除O(n) (Stack)是一个数据集合,可以理解为只能一端进行插入或...
  • 读者将学习如何打开文件,以进行输入和输出,如何在文件追加数据,如何使用二进制文件,如何获得 对文件的随机访问权。最后,还将学习如何使用标准的I/O方法来读取和写入字符串。 附录A:计数系统 本附录讨论...
  • 读者将学习如何打开文件,以进行输入和输出,如何在文件追加数据,如何使用二进制文件,如何获得 对文件的随机访问权。最后,还将学习如何使用标准的I/O方法来读取和写入字符串。 附录A:计数系统 本附录讨论...
  • 读者将学习如何打开文件,以进行输入和输出,如何在文件追加数据,如何使用二进制文件,如何获得 对文件的随机访问权。最后,还将学习如何使用标准的I/O方法来读取和写入字符串。 附录A:计数系统 本附录讨论...
  • 我们如何把现实大量存在而复杂的问题以*特定的数据类型和特定的存储结构保存到主存储器(内存),以及此基础上为实现某个功能(例如:查找某个元素、删除某个元素,对所有元素进行排序)而执行的相应操作,这...
  • 需求 假设一个写字楼要统计所有公司的电话,要做成一个通讯录 ...不改变数组的位置时,仅仅是数组添加某个元素,删除某个元素,而其他元素不做改动的前提下,数组的添加、删除只需要找到该元素
  • 数据结构

    2018-12-25 19:31:08
    我们如何把现实大量面复杂的问题以特定的数据 类型和特定的存储结构保存到主存储器(内存),以及此基础上为实现某个功能(比如查找某个元素,删除某个元素,对所有元素进行排序)而执行的相应操作,这个相应...
  • HashMap源码分析图解

    千次阅读 2020-11-14 16:39:17
    我们知道,数据结构的物理存储结构只有两种:顺序存储结构和链式存储结构(像,队列,树,图等是从逻辑结构去抽象的,映射到内存,也这两种物理组织形式),而上面我们提到过,数组根据下标查找某个元素,...
  • 10.31课程.this指向

    2018-10-31 19:19:00
    都可以提前声明,然后js由上到下逐级执行,有就使用,没有就它的父级元素中查找。这就叫做作用域链。 this指向: this是js中的一个关键字,指定一个对象然后去代替他 this的查找: 看这个函数带不带 "." 如何函数的...
  • 数据结构基本理解

    2020-04-15 13:27:01
    2、我们如何把现实大量而复杂的问题以特定的数据类型和特定存储结构保存到住存储器(内存),以及此基础上为实现某个功能、(比如查找某个元素、删除某个元素、对所有元素进行排序)而执行的相应操作,这个...
  •    我们如何把现实大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器(内存),以及此基础上为实现某个功能(比如查找某个元素,删除某个元素等)而执行的操作,这个相应的操作也叫算法。...
  • 在栈中,一端是封闭的,既不允许进行插入元素,也不允许删除元素;另一端是开口的,允许插入和删除元素。通常称插入、删除的这一端为栈顶,另一端为栈底。当表中没有元素时称为空栈。栈顶元素总是最后被插入的元素,...
  • 面试题3:二维数组查找:对于一个每一行从左到右依次递增,每一列从上到下依次递增的二维数组查找一个元素,可以选择从数组左上角开始查找array[i][j],如果目标元素大于array[i][j],i+=1,如果元素小于array...
  • LRU/LeetCode 146

    2020-05-25 16:25:04
    关键是如何再设计一个数据结构去O(1)删除和插入,这样子的话很明显必须是个线性结构了(链表、、队列(这俩个只能头尾)等),但是发现我们可能需要线性结构中间删除某个元素(当key相同的时候,我们需要更新...
  • 数据结构演示软件

    2013-06-02 21:32:36
    右侧下窗口为递归工作栈,栈中每个记录含6个数据项,其中 adr 指示调用语句行号,k 指示步数,(x,y) 表示当前坐标,i 指示路径方向(起始方向为 1,顺时针方向旋转搜索)。 5. 皇后问题 左侧图示窗口包含棋盘和...
  • 右侧下窗口为递归工作栈,栈中每个记录含6个数据项,其中 adr 指示调用语句行号,k 指示步数,(x,y) 表示当前坐标,i 指示路径方向(起始方向为 1,顺时针方向旋转搜索)。 5. 皇后问题 左侧图示窗口包含棋盘和...
  • 大话数据结构

    2019-01-10 16:35:22
    而只是让每个元素知道它下一个元素的位置哪里。 3.6.1顺序存储结构不足的解决 办法 55 3.6.2线性表链式存储结构定义 56 3.6.3头指针与头结点的异同 58 3.6.4线性表链式存储结构代码描述 58 3.7单链表的读取 60 3.8...
  • 大话数据结构 程杰

    2018-09-01 10:06:43
    而只是让每个元素知道它下一个元素的位置哪里。 3.6.1顺序存储结构不足的解决 办法 55 3.6.2线性表链式存储结构定义 56 3.6.3头指针与头结点的异同 58 3.6.4线性表链式存储结构代码描述 58 3.7单链表的读取 60 3.8...
  • 而只是让每个元素知道它下一个元素的位置哪里。 3.6.1顺序存储结构不足的解决 办法 55 3.6.2线性表链式存储结构定义 56 3.6.3头指针与头结点的异同 58 3.6.4线性表链式存储结构代码描述 58 3.7单链表的读取 60 3.8...
  • 而只是让每个元素知道它下一个元素的位置哪里。 3.6.1顺序存储结构不足的解决 办法 55 3.6.2线性表链式存储结构定义 56 3.6.3头指针与头结点的异同 58 3.6.4线性表链式存储结构代码描述 58 3.7单链表的读取 60 3.8...
  • 大话数据结构-程杰

    2014-07-13 23:45:52
    而只是让每个元素知道它下一个元素的位置哪里。 3.6.1 顺序存储结构不足的解决 办法 55 3.6.2 线性表链式存储结构定义 56 3.6.3 头指针与头结点的异同 58 3.6.4 线性表链式存储结构代码描述 58 3.7 单链表的...
  • 3.2.6 IP地址如何在数据库存储? 3.2.7 new/delete和malloc/free的底层实现? 3.2.8 overload、override、overwrite的介绍? 3.2.9 小端/大端机器? 3.3.0 守护进程 3.3.1 多线程的优缺点 3.3.2 长连接与短连接 ...

空空如也

空空如也

1 2 3 4
收藏数 75
精华内容 30
关键字:

如何在栈中查找元素