做文案公众号策划兼职网站,淘宝京东拼多多购物券网站怎么做,建设一个打鱼游戏网站,就业服务网站建设方案【问题描述】 【解答思路】
1. 两个栈实现
1.1、辅助栈和数据栈同步
特点#xff1a;编码简单#xff0c;不用考虑一些边界情况#xff0c;就有一点不好#xff1a;辅助栈可能会存一些“不必要”的元素。
1.2、辅助栈和数据栈不同步
特点#xff1a;由“辅助栈和数据…【问题描述】 【解答思路】
1. 两个栈实现
1.1、辅助栈和数据栈同步
特点编码简单不用考虑一些边界情况就有一点不好辅助栈可能会存一些“不必要”的元素。
1.2、辅助栈和数据栈不同步
特点由“辅助栈和数据栈同步”的思想我们知道当数据栈进来的数越来越大的时候我们要在辅助栈顶放置和当前辅助栈顶一样的元素这样做有点“浪费”。基于这一点我们做一些“优化”但是在编码上就要注意一些边界条件。
1辅助栈为空的时候必须放入新进来的数
2新来的数小于或者等于辅助栈栈顶元素的时候才放入特别注意这里“等于”要考虑进去因为出栈的时候连续的、相等的并且是最小值的元素要同步出栈
3出栈的时候辅助栈的栈顶元素等于数据栈的栈顶元素才出栈。
总结一下出栈时最小值出栈才同步入栈时最小值入栈才同步。
1.1、辅助栈和数据栈同步
import java.util.Stack;public class MinStack {// 数据栈private StackInteger data;// 辅助栈private StackInteger helper;/*** initialize your data structure here.*/public MinStack() {data new Stack();helper new Stack();}// 思路 1数据栈和辅助栈在任何时候都同步public void push(int x) {// 数据栈和辅助栈一定会增加元素data.add(x);if (helper.isEmpty() || helper.peek() x) {helper.add(x);} else {helper.add(helper.peek());}}public void pop() {// 两个栈都得 popif (!data.isEmpty()) {helper.pop();data.pop();}}public int top() {if(!data.isEmpty()){return data.peek();}throw new RuntimeException(栈中元素为空此操作非法);}public int getMin() {if(!helper.isEmpty()){return helper.peek();}throw new RuntimeException(栈中元素为空此操作非法);}
}
1.2、辅助栈和数据栈不同步
import java.util.Stack;public class MinStack {// 数据栈private StackInteger data;// 辅助栈private StackInteger helper;/*** initialize your data structure here.*/public MinStack() {data new Stack();helper new Stack();}// 思路 2辅助栈和数据栈不同步// 关键 1辅助栈的元素空的时候必须放入新进来的数// 关键 2新来的数小于或者等于辅助栈栈顶元素的时候才放入特别注意这里等于要考虑进去// 关键 3出栈的时候辅助栈的栈顶元素等于数据栈的栈顶元素才出栈即出栈保持同步就可以了public void push(int x) {// 辅助栈在必要的时候才增加data.add(x);// 关键 1 和 关键 2if (helper.isEmpty() || helper.peek() x) {helper.add(x);}}public void pop() {// 关键 3data 一定得 pop()if (!data.isEmpty()) {// 注意声明成 int 类型这里完成了自动拆箱从 Integer 转成了 int因此下面的比较可以使用 运算符// 参考资料https://www.cnblogs.com/GuoYaxiang/p/6931264.html// 如果把 top 变量声明成 Integer 类型下面的比较就得使用 equals 方法int top data.pop();if(top helper.peek()){helper.pop();}}}public int top() {if(!data.isEmpty()){return data.peek();}throw new RuntimeException(栈中元素为空此操作非法);}public int getMin() {if(!helper.isEmpty()){return helper.peek();}throw new RuntimeException(栈中元素为空此操作非法);}}
2. 一个栈辅助
当有更小的值来的时候要把之前的最小值入栈当前更小的值再入栈即可。当这个最小值要出栈的时候下一个值便是之前的最小值了。
入栈 2 同时将之前的 min 值 3 入栈再把 2 入栈同时更新 min 2
| 2 | min 2
| 3 |
| 5 |
|_3_|
stack 入栈 6
| 6 | min 2
| 2 |
| 3 |
| 5 |
|_3_|
stack 出栈 6
| 2 | min 2
| 3 |
| 5 |
|_3_|
stack 出栈 2
| 2 | min 2
| 3 |
| 5 |
|_3_|
stack
class MinStack {int min Integer.MAX_VALUE;StackInteger stack new StackInteger();public void push(int x) {//当前值更小if(x min){ //将之前的最小值保存stack.push(min);//更新最小值minx;}stack.push(x);}public void pop() {//如果弹出的值是最小值那么将下一个元素更新为最小值if(stack.pop() min) {minstack.pop();}}public int top() {return stack.peek();}public int getMin() {return min;}
}
3. 链表同步法
链表头插法实现基本功能最小值实现在 Node 节点中增加一个 min 字段每次加入一个节点的时候只要确定它的 min 值即可。
class MinStack {class Node{int value;int min;Node next;Node(int x, int min){this.valuex;this.minmin;next null;}}Node head;//每次加入的节点放到头部public void push(int x) {if(nullhead){head new Node(x,x);}else{//当前值和之前头结点的最小值较小的做为当前的 minNode n new Node(x, Math.min(x,head.min));n.nexthead;headn;}}public void pop() {if(head!null)head head.next;}public int top() {if(head!null)return head.value;return -1;}public int getMin() {if(null!head)return head.min;return -1;}
}
【总结】
1.思路总结 最小栈 两个栈/一个栈一个额外存储 / 链表实现
2. 包装类的用法
这里只讨论六种数字基本类型对应的包装类因为它们是使用最频繁的这些类中常用的方法可分为两类一种是本类型与其它基本类型之间的转换另一种是字符串与本类型和基本类型之间的转换。如下图是Integer类中的一些常用方法 其中的前五个都是属于第一种即与其它基本类型之间的转换。下面的三个则属于第二种是字符串与本类型及基本类型之间的转换。
A、本类型与其它类型转换
示例如下 Integer temp1 new Integer(45);int temp2 45;byte t1 temp1.byteValue(); //包装类的转换byte t2 (byte)temp2; //基本数据类型的强制类型转换B、本类型和对应基本类型转换
JDK1.5引入了自动装箱和拆箱的机制那么什么是装箱和拆箱呢
装箱就是将基本类型转换成包装类分为自动装箱和手动装箱。同样地拆箱就是将包装类型转换成基本类型也分为自动拆箱和手动拆箱。
示例如下
int a14;//手动装箱
Integer aI1 new Integer(a1);
//自动装箱
Integer aI2 a1;//手动拆箱
int ai1 aI1.intValue();
//自动拆箱
int ai2 aI2;C、字符串和基本类型转换
c1.基本类型转换成字符串类型
c1a. 包装类 的toString()方法
c1b. String 类的valueOf()方法
c1c. 空字符串加一个基本类型变量
//基本类型转换成字符串类型有三种方法int b 1;String b1 Integer.toString(b);String b2 String.valueOf(b);
String b3 b;
System.out.println(b1: b1b2: b2b3: b3);c2.字符串转换成基本类型
c2a. 包装类的parse***()静态方法
c2b. 包装类的valueOf()方法
//字符串转换成基本类型的方法有两种 String b “121”; int c1 Integer.parseInt(b); int c2 Integer.valueOf(b);
3. java基本类型 包装类 异同 3.Integer与int数据的比较 public class TestInteger {public static void main(String[] args) {int t1 46;int t2 46;Integer t3 46;Integer t4 new Integer(46);Integer t5 t1;Integer t6 new Integer(t2);System.out.println(t1 t2 (t1 t2));System.out.println(t1 t3 (t1 t3));System.out.println(t1 t4 (t1 t4));System.out.println(t1 t5 (t1 t5));System.out.println(t1 t6 (t1 t6));System.out.println(t4 t2 (t4 t2));System.out.println(t5 t2 (t5 t2));System.out.println(t6 t2 (t6 t2));System.out.println(t4 t3 (t4 t3));System.out.println(t5 t3 (t5 t3));System.out.println(t6 t3 (t6 t3));System.out.println(t3 equals t4 (t3.equals(t4)));System.out.println(t3 equals t5 (t3.equals(t5)));System.out.println(t3 equals t6 (t3.equals(t6)));System.out.println(t3 equals t4 (t3.equals(t4)));System.out.println(t4 equals t5 (t4.equals(t5)));System.out.println(t4 equals t6 (t4.equals(t6)));System.out.println(t5 equals t6 (t5.equals(t6))); }
}转载链接https://leetcode-cn.com/problems/min-stack/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-38/ 转载链接https://leetcode-cn.com/problems/min-stack/solution/shi-yong-fu-zhu-zhan-tong-bu-he-bu-tong-bu-python-/ 参考链接https://www.cnblogs.com/GuoYaxiang/p/6931264.html
