栈:当我踏上算法之路,我发现...

2020.09.09 15:09:37
83
阅读约 1 分钟

img
LeetCode几乎成了现在每个人找工作前都要刷的"新手村"的怪,每一个找工作的人面试之前都要都会去刷一刷。闲话不多说,此贴记录刷题过程中的部分题目的固定解法,方便快速回忆。

#

每日温度–单调栈解法 #

img

class Solution {
    public static int[] dailyTemperatures(int[] T) {

        int[] ints = new int[T.length];

        ArrayDeque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < T.length; i++) {
            while (deque.size()!=0 && T[deque.peek()]<T[i]){
                int pop = deque.pop();
                 ints[pop] = i-pop;
            }
            deque.addFirst(i);
        }
        return ints;
    }
}
n ints;
    }

用两个栈实现队列 #

题干:
用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTaildeleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )
例子:

输入:
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出:[null,null,3,-1]

解题思路:维护一个辅助栈
img
解法:

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;
        }
    }
}
阅读:83 . 字数:248 发布于 3 个月前
Copyright 2018-2020 Siques