Men的博客

欢迎光临！

0%

栈

发表于

包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
可通过建立辅助栈实现，栈A用于存储所有元素，栈B中中存储栈 A中非严格降序 的元素，栈A中最小元素始终位于栈B的顶端
Stack<Integer> A, B;
    public MinStack() {
        A = new Stack<>();
        B = new Stack<>();
    }
    public void push(int x) {
        A.add(x);
        if(B.empty() || B.peek() >= x)
            B.add(x);
    }
    public void pop() {
        if(A.pop().equals(B.peek()))
            B.pop();
    }
    public int top() {
        return A.peek();
    }
    public int min() {
        return B.peek();
    }

用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]
class CQueue {
    Deque<Integer> stack1;
    Deque<Integer> stack2;

public CQueue() {
    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 {
        int deleteItem = stack2.pop();
        return deleteItem;
    }
}

}

栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
考虑借用一个辅助栈 stack ，模拟 压入 / 弹出操作的排列。根据是否模拟成功，即可得到结果。
 public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        for(int num : pushed) {
            stack.push(num); // num 入栈
            while(!stack.isEmpty() && stack.peek() == popped[i]) { // 循环判断与出栈
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }

栈排序

对栈进行排序使最小元素位于栈顶
用一个辅助栈

class SortedStack {

private Stack<Integer> data = new Stack<>();
private Stack<Integer> help = new Stack<>();

public SortedStack() {
    super();
}

public void push(int val) {
    if(isEmpty()) { // 如果data ，没有数据，添加数据，添加help中数据
        data.push(val);
        while(!help.isEmpty()) {
            data.push(help.pop());
        }
    } else { // 获取data 顶部元素。比较大小，如果大于，那么添加元素，否则help添加元素
        int top = peek();
        if(top >= val) {
            data.push(val);
            while(!help.isEmpty()) {
                data.push(help.pop());
            }
        } else {
            help.push(data.pop());
            push(val);
        }
    }
}

public void pop() {
    if(!isEmpty()) {
        data.pop();
    }
}

public int peek() {
    if(isEmpty()) {
        return -1;
    } else {
        return data.peek();
    }
}

public boolean isEmpty() {
    return data.isEmpty();
}
}

用队列实现栈

class MyStack {
           private Queue<Integer> q1 = new LinkedList<>();
           private Queue<Integer> q2 = new LinkedList<>();
           int top = 0;
           MyStack() {
           }
           public void push(int x) {
               q1.add(x);
               top = x;
           }
           public int pop() {
                while (q1.size() > 1) {
                       top = q1.remove();
                       q2.add(top);
               }
               int a = q1.remove();
               Queue<Integer> temp = q1;
               q1 = q2;  
               q2 = temp;
               return a;
           }
           public int top() {
               return top;
           }
           public boolean empty() {
               return q1.isEmpty();
           }
};

三合一

描述如何只用一个数组来实现三个栈。
首先要构建数组，3倍长度的size
然后让另一个3的数组，存放和管理下标
然后在根据结构分析
class TripleInOne {

int[] a;
int[] tt = new int[3];
int size;
public TripleInOne(int statckSize){
    a = new int[3 * statckSize + 10];
    size = statckSize;
    for(int i = 0; i < 3; i++){
        tt[i] = i * statckSize - 1;
    }
}

public boolean isFull(int stackNum){
    return tt[stackNum] >= size * (stackNum + 1) - 1;

}

public void push(int stackNum, int value){
    if(isFull(stackNum))    return;
    a[++tt[stackNum]] = value;
}

public int pop(int stackNum){
    if(isEmpty(stackNum)) return -1;
    tt[stackNum]--;
    return a[tt[stackNum] + 1];
}

public int peek(int stackNum){
    if(isEmpty(stackNum))   return -1;
    return a[tt[stackNum]];
}

public boolean isEmpty(int stackNum){
    return tt[stackNum] < stackNum * size;
}

}

汉诺塔问题

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。
解题思路：递归与分治
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        hanoi(A.size(), A, B, C);
    }

public void hanoi(int n, List<Integer> A, List<Integer> B, List<Integer> C){
    
    if(n == 1){
        C.add(A.get(A.size() - 1));
        A.remove(A.size() - 1);
    }else{
        //把A经过辅助C放到B上
        hanoi(n - 1, A, C, B);
        //把A放到C上
        C.add(A.get(A.size() - 1));
        A.remove(A.size() - 1);
        //把B经过辅助A放到C上
        hanoi(n - 1, B, A, C);
    }
}

队列

用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]
class CQueue {
    Deque<Integer> stack1;
    Deque<Integer> stack2;

public CQueue() {
    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 {
        int deleteItem = stack2.pop();
        return deleteItem;
    }
}
}

数据流中的中位数 （优先队列）

优先队列 / 堆， 小顶堆，保存较大的一半， 大顶堆，保存较小的一半，堆顶的平均数即为中位数
    class MedianFinder {
    Queue<Integer> A, B;
    public MedianFinder() {
        A = new PriorityQueue<>(); // 小顶堆，保存较大的一半
        B = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半
    }
    public void addNum(int num) {
        if(A.size() != B.size()) {
            A.add(num);
            B.add(A.poll());
        } else {
            B.add(num);
            A.add(B.poll());
        }
    }
    public double findMedian() {
        return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
    }
}

滑动窗口的最大值 单调队列

    我们维护一个单调的双向队列，窗口在每次滑动的时候，我就从队列头部取当前窗口中的最大值，每次窗口新进来一个元素的时候，我就将它与队列中的元素进行大小比较
    如果刚刚进来的元素比队列的尾部元素大，那么先将队列尾部的元素弹出，然后把刚刚进来的元素添到队列的尾部；
    如果刚刚进来的元素比队列的尾部元素小，那么把刚刚进来的元素直接添到队列的尾部即可。
    方法二：构建双端队列
       保持队列大小不超过窗口，以及最大值在出端
       读取新数据，入端操作，和之前的进入的数据比较，之前的数据小则剔除，直到比它大则停止，最大值还在出端
       循环上面步骤，直到结束
       public int[] maxSlidingWindow(int[] nums, int k) {
               if(nums.length == 0 || k == 0) return new int[0];
               Deque<Integer> deque = new LinkedList<>(); // 队列
               int[] res = new int[nums.length - k + 1];
               for(int j = 0, i = 1 - k; j < nums.length; i++, j++) {
                   if(i > 0 && deque.peekFirst() == nums[i - 1])
                       deque.removeFirst(); // 删除 deque 中对应的 nums[i-1]
                   while(!deque.isEmpty() && deque.peekLast() < nums[j])
                       deque.removeLast(); // 保持 deque 递减
                   deque.addLast(nums[j]);
                   if(i >= 0)
                       res[i] = deque.peekFirst();  // 记录窗口最大值
               }
               return res;
           }

队列的最大值

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
方法二：维护一个单调的双端队列
public class MaxQueue {

    Queue<Integer> queue;
    LinkedList<Integer> max;
    public MaxQueue() {
        queue = new LinkedList<>();
        max = new LinkedList<>();//LinkedList是双端链表
    }
    
    public int max_value() {
        return max.size()==0?-1:max.getFirst();
    }
    
    public void push_back(int value) {
        queue.add(value);
        while(max.size()!=0&&max.getLast()<value){//注意：这里第二个判断条件不能带等号，即max中对于当前queue中的具有相同值的元素会全部存储，而不是存储最近的那个。只添加递增
            max.removeLast();
        }
        max.add(value);
    }
    
    public int pop_front() {
        if(max.size()!=0&&queue.peek().equals(max.getFirst()))//Integer类型的值的比较不能直接使用==
            max.removeFirst();
        return queue.size()==0?-1:queue.poll();
    }
}

优先队列的主要操作
优先队列辅助操作
返回优先队列中键值为第k个最小最大的元素
返回优先队列的元素个数
基于键值的优先级将优先队列的元素进行排序
应用

最短路径算法：Dijkstra算法
最小生成树算法：Prim算法
事件驱动仿真：顾客排队算法
选择问题：查找第k个最小元素