Java剑指offer
第一天
1.使用双栈实现队列操作
题目要求:用两个栈实现一个双向队列,包含队列的插入(appendTail)以及删除(deleteHead),若队列中没有元素就返回-1.
思路分析:维护两个栈,第一个栈支持插入操作,第二个栈支持删除操作
成员变量
-
维护两个栈
stack1
和stack2
,其中stack1
支持插入操作,stack2
支持删除操作
构造方法 -
初始化
stack1
和stack2
为空
插入元素 -
stack1
直接插入元素
删除元素 - 如果 stack2 为空,则将 stack1 里的所有元素弹出插入到 stack2 里
- 如果 stack2 仍为空,则返回 -1,否则从 stack2 弹出一个元素并返回
复杂度分析
时间复杂度:对于插入和删除操作,时间复杂度均为 O(1)O(1)。插入不多说,对于删除操作,虽然看起来是 O(n)O(n) 的时间复杂度,但是只是进行第一个栈进入第二个栈的操作,之后直接弹出,因此均摊下来每个元素被删除的时间复杂度仍为 O(1)O(1)。
空间复杂度:O(n)O(n)。需要使用两个栈存储已有的元素
代码实现:
package com.sordfingeroffer;
import java.util.Deque;
import java.util.LinkedList;
public class CQueue {
//使用Deque做堆栈而不是stack,因为stack的方法是同步的
//Deque接口做堆栈实现的方法:push()、pop()、peek()(返回的是开头的元素)
Deque <Integer> stack1;
Deque <Integer> stack2;
public CQueue()
{
//LinkedList实现了Deque和list的接口
stack1=new LinkedList<Integer>();
stack2=new LinkedList<Integer>();
}
public void appendTail(int value)
{
stack1.push(value);
}
public int deleteHead()
{
if(stack2.isEmpty())
{
while(!stack1.isEmpty())
{
stack2.push(stack1.pop());
}
}
if(stack2.isEmpty())
return -1;
else
return stack2.pop();
}
public static void main(String[] args) {
CQueue q=new CQueue();
q.appendTail(10);
q.appendTail(20);
q.appendTail(30);
int param1=q.deleteHead();
int param2=q.deleteHead();
int param3=q.deleteHead();
System.out.println(param1);
System.out.println(param2);
System.out.println(param3);
}
}
2.包含Min的栈
题目要求:定义一个栈结构(pop、push、top基本操作)并且添加一个min函数,能够返回栈中最小的元素
普通栈的 push()
和 pop()
函数的复杂度为 O(1)O(1) ;而获取栈最小值 min() 函数需要遍历整个栈,复杂度为 O(N),所以我们需要建立一个辅助栈来降低复杂度
-
stack1:存储所有的元素,包括pop()、push()基本操作以及top()操作,保持题目正常逻辑
-
stack2:只是与min相关,里面的内容不必要遵循栈的基本操作,min()返回的是栈顶元素
函数设计:
-
push():stack1正常push,stack2的栈顶要与Push的值进行比较,把小的那个push进入stack2中(以便到时候pop出来的时候可以得到最小的值)
-
pop():stack1正常pop,若stack1中pop的值和stack2中的栈顶的值相同就pop,这就意味着将stack1中最小的元素pop出去了,所以stack2要进行同步pop
-
min():只需要返回stack2中的栈顶元素即可
代码实现:
package com.sordfingeroffer;
import java.util.Stack;
public class MiniStack {
//stack类是vector的子类,标准的后进先出的栈
//方法有:boolean empty()、Object peek( )、Object pop( )、Object push(Object element)、int search(Object element)-->查找对象在指定位置的值
Stack <Integer> stack1,stack2;
/** initialize your data structure here. */
public MiniStack() {
stack1=new Stack<Integer>();
stack2=new Stack<Integer>();
}
public void push(int x)
{
stack1.push(x);
if(stack2.isEmpty() || stack2.peek()>=x)
{
stack2.push(x);
}
}
public void pop()
{
if(stack1.pop().equals(stack2.peek()))
{
stack2.pop();
}
}
public int top() {
return stack1.peek();
}
public int min() {
return stack2.peek();
}
public static void main(String[] args) {
MiniStack minStack = new MiniStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
System.out.println(minStack.min());
minStack.pop();
System.out.println(minStack.top());
System.out.println(minStack.min());
}
}
评论(0)
您还未登录,请登录后发表或查看评论