摘要:和三个方法的时间复杂度必须为两种解法,解法一,将最小值存入自有的数据结构中,如下所示原本的值最小值解法二,用两个栈
堆栈和队列统称线性表
简单的线性结构
数组和链表可以实现这两种数据结构
堆栈
基本理解
DFS
深度优先---按深度遍历
递归转非递归
队列
基本理解
BFS
广度优先---按层序遍历
出入栈的合法性
模拟出入栈的过程,不是入栈,就是出栈,不然就不合法
public boolean isPossible(int[] in, int[] out){ if(in.length != out.length){ return false; } Stacks = new Stack<>(); for(int i = 0, j = 0;j < out.length; j++){ //如果不是入栈的 while(s.isEmpty() && s.peek() != out[j]){ if(i >= in.length){ return false; } s.push(in[i++]); } //那就出栈 s.pop(); } return true; }
两个栈实现队列
public class MyQueue{ Stacks1 = new Stack<>(); Stack s2 = new Stack<>(); public void push(int x){ s1.push(x); } //负负得正 public int pop(){ if(s2.isEmpty()){ while(!s1.isEmpty()){ s2.push(s1.pop()); } } return s2.pop(); } public int peek(){ if(s2.isEmpty()){ while(!s1.isEmpty()){ s2.push(s1.pop()); } } return s2.peek(); } public boolean empty(){ return s1.isEmpty() && s2.isEmpty(); } }
两个队列实现栈
public class MyStack { Queuequeue1; Queue queue2; /** Initialize your data structure here. */ public MyStack() { queue1 = new LinkedList<>(); queue2 = new LinkedList<>(); } /** Push element x onto stack. */ public void push(int x) { if(!queue1.isEmpty()){ queue1.offer(x); }else{ queue2.offer(x); } } /** Removes the element on top of the stack and returns that element. */ public int pop() { if(queue1.size() != 0){ while(queue1.size() > 1){ queue2.add(queue1.peek()); queue1.poll(); } return queue1.remove(); }else{ while(queue2.size() > 1){ queue1.add(queue2.peek()); queue2.poll(); } return queue2.remove(); } } /** Get the top element. */ public int top() { if(queue1.size() != 0){ while(queue1.size() > 1){ queue2.add(queue1.poll()); } int res = queue1.peek(); queue2.add(queue1.poll()); return res; }else{ while(queue2.size() > 1){ queue1.add(queue2.poll()); } int res = queue2.peek(); queue1.add(queue2.poll()); return res; } } /** Returns whether the stack is empty. */ public boolean empty() { return queue1.isEmpty() && queue2.isEmpty(); } }
设计一个栈,除pop与push方法,还支持min方法,可返回栈元素中的最小值。push、pop和min三个方法的时间复杂度必须为O(1)
两种解法,解法一,将最小值存入自有的数据结构中,如下所示
public class MyStack extends Stack{ public void push(int value){ int newMin = Math.min(value, min()); super.push(new NodeWithMin(value, newMin)); } public int min(){ if(this.isEmpty()){ return Integer.MAX_VALUE; }else{ return peek().min; } } public int pop(){ super.pop().value; } } class NodeWithMin{ int value;//原本的值 int min;//最小值 public NodeWithMin(int value, int min){ this.value = value; this.min = min; } }
解法二,用两个栈
public class MyStack{ Stacks1 = new Stack<>(); Stack s2 = new Stack<>(); public void push(int i){ s1.push(i); if(s2.isEmpty() || min() >= i){ s2.push(i); } } public int pop(){ if(s1.peek() == min()){ s2.pop(); } return s1.pop(); } public int min(){ return s2.peek(); } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/70161.html
摘要:现状最近在写欢迎的时候,一直为错误的栈追踪而愁。由于送入队列的是函数,因此在的参数可以放心地使用。其次,这些函数并不是立即在中调用的,而是由专门的队列处理代码来调用。 本文的讲述都是以 Node.js 环境为例子,而 Node.js 使用的 JavaScript 引擎是 V8,因此理论上 Chrome 也能适用,其它浏览器我就不清楚了。 现状 最近在写 Rize(欢迎 star) 的时...
摘要:但是,实际中无法保证达到让步目的,因为让步的线程还有可能被线程调度程序再次选中。在大多数情况下,将导致线程从运行状态转到可运行状态,但有可能没有效果。 多线程编程 线程状态图 总是无法上传,稍后上传 常用函数 状态转换 运行中->阻塞 sleep(long millis) 在指定的毫秒数内让当前正在执行的线程休眠 join() 等待t线程终止 使用方式 Thread t =...
摘要:我自己总结的学习的系统知识点以及面试问题,已经开源,目前已经。面试官那你都了解里面的哪些东西呢我哈哈哈这可是我的强项,从,说到,,又说到线程池,分别说了底层实现和项目中的应用。 我自己总结的Java学习的系统知识点以及面试问题,已经开源,目前已经 35k+ Star。会一直完善下去,欢迎建议和指导,同时也欢迎Star: https://github.com/Snailclimb... ...
摘要:正确做法是给加索引,还有联合索引,并不能避免全表扫描。 前言:有收获的话请加颗小星星,没有收获的话可以 反对 没有帮助 举报三连 有心的同学应该会看到我这个noteBook下面的其它知识,希望对你们有些许帮助。 本文地址 时间点:2017-11 一个16年毕业生所经历的php面试 一、什么是面试 二、面试准备 1. 问:什么时候开始准备? 2. 问:怎么准备? 三、面试...
摘要:栈和队列是开发中最常用的两种数据结构。如果又有数据入栈,的值将增加到。如果一个数据从栈中被取出,的值将会减少为。队列与栈类似,队列也是一个线性数据结构。与栈不同的是,队列只删除最先添加的数据。现在,让我们将栈大小的实现应用到队列中。 翻译:疯狂的技术宅英文:https://code.tutsplus.com/art...说明:本文翻译自系列文章《Data Structures With...
阅读 3607·2021-10-09 09:58
阅读 1133·2021-09-22 15:20
阅读 2454·2019-08-30 15:54
阅读 3471·2019-08-30 14:08
阅读 857·2019-08-30 13:06
阅读 1776·2019-08-26 12:16
阅读 2628·2019-08-26 12:11
阅读 2463·2019-08-26 10:38