LeetCode题解——栈和队列

た 入场券 2023-02-18 11:50 105阅读 0赞

文章目录

    • 用栈实现队列
      • 解法
    • 用队列实现栈
      • 解法
    • 最小栈
      • 解法
    • 有效的括号
      • 解法
    • 每日温度
      • 解法
    • 下一个更大元素 II
      • 解法
        • 推荐阅读

用栈实现队列

使用栈实现队列的下列操作:

  1. push(x) -- 将一个元素放入队列的尾部。
  2. pop() -- 从队列首部移除元素。
  3. peek() -- 返回队列首部的元素。
  4. empty() -- 返回队列是否为空。
  5. 示例:
  6. MyQueue queue = new MyQueue();
  7. queue.push(1);
  8. queue.push(2);
  9. queue.peek(); // 返回 1
  10. queue.pop(); // 返回 1
  11. queue.empty(); // 返回 false
  12. 说明:
  13. 你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, is empty 操作是合法的。
  14. 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
  15. 假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)。

解法

  1. class MyQueue {
  2. /** Initialize your data structure here. */
  3. public MyQueue() {
  4. }
  5. private Deque<Integer> in = new LinkedList<>();
  6. private Deque<Integer> out = new LinkedList<>();
  7. /** Push element x to the back of queue. */
  8. public void push(int x) {
  9. in.addFirst(x);
  10. }
  11. /** Removes the element from in front of queue and returns that element. */
  12. public int pop() {
  13. in2out();
  14. return out.removeFirst();
  15. }
  16. /** Get the front element. */
  17. public int peek() {
  18. in2out();
  19. return out.peekFirst();
  20. }
  21. /** Returns whether the queue is empty. */
  22. public boolean empty() {
  23. return out.isEmpty() && in.isEmpty();
  24. }
  25. private void in2out() {
  26. if (out.isEmpty()) {
  27. while(!in.isEmpty()) {
  28. out.addFirst(in.removeFirst());
  29. }
  30. }
  31. }
  32. }
  33. /**
  34. * Your MyQueue object will be instantiated and called as such:
  35. * MyQueue obj = new MyQueue();
  36. * obj.push(x);
  37. * int param_2 = obj.pop();
  38. * int param_3 = obj.peek();
  39. * boolean param_4 = obj.empty();
  40. */

用队列实现栈

使用队列实现栈的下列操作:

  1. push(x) -- 元素 x 入栈
  2. pop() -- 移除栈顶元素
  3. top() -- 获取栈顶元素
  4. empty() -- 返回栈是否为空
  5. 注意:
  6. 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, is empty 这些操作是合法的。
  7. 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
  8. 你可以假设所有操作都是有效的(例如, 对一个空的栈不会调用 pop 或者 top 操作)。

解法

  1. class MyStack {
  2. Deque<Integer> queue;
  3. /** Initialize your data structure here. */
  4. public MyStack() {
  5. queue = new LinkedList<>();
  6. }
  7. /** Push element x onto stack. */
  8. public void push(int x) {
  9. queue.offer(x);
  10. int size = queue.size();
  11. while (size-- > 1) {
  12. queue.offer(queue.poll());
  13. }
  14. }
  15. /** Removes the element on top of the stack and returns that element. */
  16. public int pop() {
  17. return queue.poll();
  18. }
  19. /** Get the top element. */
  20. public int top() {
  21. return queue.peek();
  22. }
  23. /** Returns whether the stack is empty. */
  24. public boolean empty() {
  25. return queue.isEmpty();
  26. }
  27. }
  28. /**
  29. * Your MyStack object will be instantiated and called as such:
  30. * MyStack obj = new MyStack();
  31. * obj.push(x);
  32. * int param_2 = obj.pop();
  33. * int param_3 = obj.top();
  34. * boolean param_4 = obj.empty();
  35. */

最小栈

设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。

  1. push(x) —— 将元素 x 推入栈中。
  2. pop() —— 删除栈顶的元素。
  3. top() —— 获取栈顶元素。
  4. getMin() —— 检索栈中的最小元素。
  5. 示例:
  6. 输入:
  7. ["MinStack","push","push","push","getMin","pop","top","getMin"]
  8. [[],[-2],[0],[-3],[],[],[],[]]
  9. 输出:
  10. [null,null,null,null,-3,null,0,-2]
  11. 解释:
  12. MinStack minStack = new MinStack();
  13. minStack.push(-2);
  14. minStack.push(0);
  15. minStack.push(-3);
  16. minStack.getMin(); --> 返回 -3.
  17. minStack.pop();
  18. minStack.top(); --> 返回 0.
  19. minStack.getMin(); --> 返回 -2.
  20. 提示:
  21. poptop getMin 操作总是在 非空栈 上调用。

解法

  1. class MinStack {
  2. private Deque<Integer> stack;
  3. private Deque<Integer> minStack;
  4. private int min;
  5. /** initialize your data structure here. */
  6. public MinStack() {
  7. stack = new LinkedList<>();
  8. minStack = new LinkedList<>();
  9. min = Integer.MAX_VALUE;
  10. }
  11. public void push(int x) {
  12. stack.offerFirst(x);
  13. min = Math.min(min, x);
  14. minStack.offerFirst(min);
  15. }
  16. public void pop() {
  17. stack.pollFirst();
  18. minStack.pollFirst();
  19. min = minStack.isEmpty() ? Integer.MAX_VALUE : minStack.peekFirst();
  20. }
  21. public int top() {
  22. return stack.peekFirst();
  23. }
  24. public int getMin() {
  25. return minStack.peekFirst();
  26. }
  27. }
  28. /**
  29. * Your MinStack object will be instantiated and called as such:
  30. * MinStack obj = new MinStack();
  31. * obj.push(x);
  32. * obj.pop();
  33. * int param_3 = obj.top();
  34. * int param_4 = obj.getMin();
  35. */

有效的括号

给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

  1. 示例 1:
  2. 输入: "()"
  3. 输出: true
  4. 示例 2:
  5. 输入: "()[]{}"
  6. 输出: true
  7. 示例 3:
  8. 输入: "(]"
  9. 输出: false
  10. 示例 4:
  11. 输入: "([)]"
  12. 输出: false
  13. 示例 5:
  14. 输入: "{[]}"
  15. 输出: true

解法

  1. class Solution {
  2. public boolean isValid(String s) {
  3. Deque<Character> stack = new LinkedList<>();
  4. for (char c : s.toCharArray()) {
  5. if (c == '(' || c == '[' || c == '{') {
  6. stack.addFirst(c);
  7. } else {
  8. if (stack.isEmpty()) {
  9. return false;
  10. }
  11. char tmp = stack.removeFirst();
  12. boolean flag1 = c == ')' && tmp != '(';
  13. boolean flag2 = c == ']' && tmp != '[';
  14. boolean flag3 = c == '}' && tmp != '{';
  15. if (flag1 || flag2 || flag3) {
  16. return false;
  17. }
  18. }
  19. }
  20. return stack.isEmpty();
  21. }
  22. }

每日温度

请根据每日 气温 列表,重新生成一个列表。对应位置的输出为:要想观测到更高的气温,至少需要等待的天数。如果气温在这之后都不会升高,请在该位置用 0 来代替。

例如,给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示:气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度,都是在 [30, 100] 范围内的整数。

解法

  1. class Solution {
  2. public int[] dailyTemperatures(int[] T) {
  3. int n = T.length;
  4. int[] dist = new int[n];
  5. Deque<Integer> stack = new LinkedList<>();
  6. for (int curIndex = 0; curIndex < n; curIndex++) {
  7. while (!stack.isEmpty() && T[curIndex] > T[stack.peekFirst()]) {
  8. int preIndex = stack.pollFirst();
  9. dist[preIndex] = curIndex - preIndex;
  10. }
  11. stack.addFirst(curIndex);
  12. }
  13. return dist;
  14. }
  15. }

下一个更大元素 II

给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素),输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出 -1。

  1. 示例 1:
  2. 输入: [1,2,1]
  3. 输出: [2,-1,2]
  4. 解释: 第一个 1 的下一个更大的数是 2
  5. 数字 2 找不到下一个更大的数;
  6. 第二个 1 的下一个最大的数需要循环搜索,结果也是 2
  7. 注意: 输入数组的长度不会超过 10000

解法

  1. class Solution {
  2. public int[] nextGreaterElements(int[] nums) {
  3. int n = nums.length;
  4. int[] next = new int[n];
  5. Arrays.fill(next, -1);
  6. Deque<Integer> stack = new LinkedList<>();
  7. for (int i = 0; i < n * 2; i++) {
  8. int num = nums[i % n];
  9. while (!stack.isEmpty() && nums[stack.peekFirst()] < num) {
  10. next[stack.pollFirst()] = num;
  11. }
  12. if (i < n) {
  13. stack.addFirst(i);
  14. }
  15. }
  16. return next;
  17. }
  18. }

推荐阅读

  • 机器学习资料汇总
  • 吴恩达《机器学习》视频、作业、源码
  • 106页《Python进阶》中文版正式发布
  • 李航《统计学习方法》第二版完整课件
  • 机器学习数学全书,1900页PDF下载

format_png

发表评论

表情:
评论列表 (有 0 条评论,105人围观)

还没有评论,来说两句吧...

相关阅读