Java教程

2021-10-29 剑指offer(队列&栈)

本文主要是介绍2021-10-29 剑指offer(队列&栈),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

剑指offer--队列&栈

    • JZ9 用两个栈实现队列
    • JZ30 包含min函数的栈
    • JZ31 栈的压入、弹出序列
    • JZ73 翻转单词序列
    • JZ59 滑动窗口的最大值

JZ9 用两个栈实现队列

题目地址
描述
用两个栈来实现一个队列,使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法,即保证pop操作时队列内已有元素。

数据范围:n≤1000
要求:存储n个元素的空间复杂度为 O(n) ,插入与删除的时间复杂度都是 O(1)
示例1

输入:
["PSH1","PSH2","POP","POP"]
返回值:
1,2
说明:
"PSH1":代表将1插入队列尾部
"PSH2":代表将2插入队列尾部
"POP“:代表删除一个元素,先进先出=>返回1
"POP“:代表删除一个元素,先进先出=>返回2 

示例2

输入:
["PSH2","POP","PSH1","POP"]
返回值:
2,1

思路
定义两个栈stack1(入口栈),stack2(出口栈),来用于完成push和pop操作。
push:直接调用stack1的push函数
pop:首先判断stack2是否为空,如果不为空:直接调用stack2的pop函数;如果为空,先将stack1中内容全部压入stack2中,再调用stack2的pop函数。
如下图,比如执行如下操作:
PUSH(1),PUSH(2),POP(),PUSH(3),PUSH(4),POP(),POP(),POP()。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

代码

import java.util.Stack;
public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();//入口栈
    Stack<Integer> stack2 = new Stack<Integer>();//出口栈
    public void push(int node) {
        stack1.add(node);
    }
    public int pop() {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.add(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

JZ30 包含min函数的栈

题目地址
描述
定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数,并且调用 min函数、push函数 及 pop函数 的时间复杂度都是 O(1)
push(value):将value压入栈中
pop():弹出栈顶元素
top():获取栈顶元素
min():获取栈中最小元素

示例:
输入: [“PSH-1”,“PSH2”,“MIN”,“TOP”,“POP”,“PSH1”,“TOP”,“MIN”]
输出: -1,2,1,-1
解析:
"PSH-1"表示将-1压入栈中,栈中元素为-1
"PSH2"表示将2压入栈中,栈中元素为2,-1
“MIN”表示获取此时栈中最小元素==>返回-1
"TOP"表示获取栈顶元素==>返回2
"POP"表示弹出栈顶元素,弹出2,栈中元素为-1
"PSH-1"表示将1压入栈中,栈中元素为1,-1
"TOP"表示获取栈顶元素==>返回1
“MIN”表示获取此时栈中最小元素==>返回-1

示例1

输入:
 ["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]
返回值:
-1,2,1,-1

思路
定义一个栈stack和一个附加栈minStack(即最小栈),记录当前栈中的最小元素。
PUSH
假如对元素nowVal执行push操作:
1.首先执行stack.push(nowVal)
2.如下

  • 若栈为(即第一次加入元素),minStack.push(nowVal)
  • 若栈不为空:若nowVal < 栈顶元素,则minStack.push(nowVal);否则minStack.push(栈顶元素)。

POP:stack和minStack分别执行POP操作
TOP:stack执行peek()函数
MIN:minStack执行peek()函数

代码

import java.util.Stack;
public class Solution {
    Stack<Integer> stack=new Stack<Integer>();
    Stack<Integer> minStack=new Stack<Integer>();
    public void push(int node) {
        stack.push(node);
        if(minStack.isEmpty()||minStack.peek()>node){
            minStack.push(node);
        }else{
            minStack.push(minStack.peek());
        }
    }
    
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int min() {
        return minStack.peek();
    }
}

JZ31 栈的压入、弹出序列

题目地址
描述
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)
示例1

输入:
[1,2,3,4,5],[4,3,5,1,2]
返回值:
false

代码
模拟法
因为弹出之前的值都会先入栈,所以使用栈来辅助。

  1. 初始化:用指针i指向pushV的第一个位置,指针j指向popV的第一个位置
  2. 如果pushV[i] != popV[j],那么应该将pushV[i]放入栈中, ++i
  3. 否则,pushV[i]==popV[j], 说明这个元素是放入栈中立马弹出,所以,++i,
    ++j,然后应该检查popV[j] 与栈顶元素是否相等,如果相等,++j, 并且弹出栈顶元素
  4. 重复2和3,如果i==pushV.size(), 说明入栈序列访问完。此时检查栈是否为空,如果为空,说明匹配;否则不匹配。
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack=new Stack<>();
        int i=0,j=0;
        while(i<pushA.length){
            if(pushA[i]!=popA[j]){
                stack.push(pushA[i++]);
            }else{
                i++;
                j++;
                while(!stack.isEmpty()&&j<popA.length&&stack.peek()==popA[j]){
                    j++;
                    stack.pop();
                }
            }
        }
        if(stack.isEmpty()){
            return true;
        }else{
            return false;
        }
    }
}

JZ73 翻转单词序列

题目地址
描述
牛客最近来了一个新员工Fish,每天早晨总是会拿着一本英文杂志,写些句子在本子上。同事Cat对Fish写的内容颇感兴趣,有一天他向Fish借来翻看,但却读不懂它的意思。例如,“nowcoder. a am I”。后来才意识到,这家伙原来把句子单词的顺序翻转了,正确的句子应该是“I am a nowcoder.”。Cat对一一的翻转这些单词顺序可不在行,你能帮助他么?

数据范围:1≤ n ≤ 100
进阶:空间复杂度 0(n) ,时间复杂度 0(n) ,保证没有只包含空格的字符串
示例1

输入:
"nowcoder. a am I"
返回值:
"I am a nowcoder."

示例2

输入:
""
返回值:
""

代码
先根据空格,将字符串分割为一个个单词,然后利用栈进行翻转。

import java.util.*;
public class Solution {
    public String ReverseSentence(String str) {
        String[] strs=str.split(" ");
        Stack<String> stack=new Stack<>();
        for(int i=0;i<strs.length;i++){
            stack.push(strs[i]);
        }
        String res="";
        while(!stack.isEmpty()){
            res+=stack.pop();
            if(!stack.isEmpty()){
                res+=" ";
            }
        }
        return res;
    }
}

JZ59 滑动窗口的最大值

题目地址
描述
给定一个长度为 n 的数组 num 和滑动窗口的大小 size ,找出所有滑动窗口里数值的最大值。

例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}; 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]}。

窗口大于数组长度或窗口长度为0的时候,返回空。

数据范围: 1≤n≤10000,0≤size≤10000,数组中每个元素的值满足 ∣val∣≤10000
要求:空间复杂度 O(n),时间复杂度 O(n)

示例1

输入:
[2,3,4,2,6,2,5,1],3
返回值:
[4,4,6,6,6,5]

示例2

输入:
[9,10,9,-7,-3,8,2,-6],5
返回值:
[10,10,9,8]

示例3

输入:
[1,2,3,4],5
返回值:
[]

解题思路
准备一个双端队列qmax,维持从队首到队尾降序排列,元素从队尾加入,从队头取出元素。

  1. 遍历数组的每一个元素
  2. 如果容器为空,则直接将当前元素加入到容器中。
  3. 如果容器不为空,则让当前元素和容器的最后一个元素比较,如果大于,则将容器的最后一个元素删除,然后继续讲当前元素和容器的最后一个元素比较
  4. 如果当前元素小于容器的最后一个元素,则直接将当前元素加入到容器的末尾
  5. 如果容器头部的元素已经不属于当前窗口的边界,则应该将头部元素删除
    示例如下:
    针对数组{2,3,4,2,6,2,5,1},窗口大小为3。那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}; 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]}。
    按照算法,执行如下:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

代码

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> res=new ArrayList<>();
        if(num==null||size<1||size>num.length){
            return res;
        }
        LinkedList<Integer> qmax=new LinkedList<>();
        for(int i=0;i<num.length;i++){
            while(!qmax.isEmpty()&&num[qmax.peekLast()]<=num[i]){
                qmax.pollLast();
            }
            qmax.offerLast(i);
            if(qmax.peekFirst()==i-size){
                qmax.pollFirst();
            }
            if(i>=size-1){
                res.add(num[qmax.peekFirst()]);
            }
        }
        return res;
    }
}
这篇关于2021-10-29 剑指offer(队列&栈)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!