当前位置： 首页>后端>正文

Java栈队列堆算法题-00

后端2024-04-29 11:59:36

用两个栈实现队列

用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。

  1. 栈先入后出，队列先进先出。
    所以入栈一次出一次，序列相反。再入栈一次出栈一次，成序列相同。
    第一次：入1-2-3 出3-2-1
    第二次：入3-2-1 出1-2-3
   Stack<Integer> in = new  Stack<Integer>();
   out.isEmpty()
   in.push(node);
   out.push(in.pop());

https://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6?tpId=13&tqId=11158&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=cyc_github

包含 min 函数的栈

实现一个包含 min() 函数的栈，该方法返回当前栈中最小的值。

  1. 2个栈，一个直接放数据。一个进行比较，将较小的数据放入第二个栈中去。
minStack.push(minStack.isEmpty() node : Math.min(minStack.peek(), node));

//感觉像固定写法
public void pop() {
    dataStack.pop();
    minStack.pop();
}

https://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49?tpId=13&tqId=11173&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=cyc_github

栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。

  1. 入栈的时候比较一下是不是出栈序列的当前值，是的话，出了，不是的话，继续加。到最后看有没有出完即可。
return stack.isEmpty();

https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&tqId=11174&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=cyc_github

最小的 K 个数

给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
要求：空间复杂度 O(n)O(n) ，时间复杂度 O(nlogn)O(nlogn)

  1. 大小为k的最小堆
  • 构建一个大顶堆，取大顶堆前几位。
  • 初始化实现大顶堆，不设置则默认为小顶堆。
  • PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
  • 输出第一个数，并删除。
maxHeap.poll();

返回堆的队列

return new ArrayList<>(maxHeap);
  1. 快排
    • 快速排序的方法，找到第K的数的位置。
    • 每执行一次快排，某个数之前一定是小于它的，之后一定是大于它的。

https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf?tpId=13&tqId=11182&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=cyc_github

数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

  1. 大小顶堆
    • 数据流是一个串，假设排序完成，我将它分为2部分。
    • 这样最半部分取最大值，右半部分取最小值，实现其平均数的结果。
    • 当N为偶数，右半边的数要全大于左边，所以先往左插，再插右。基数相反。
   left.add(val);
   right.add(left.poll());

https://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1?tpId=13&tqId=11216&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=cyc_github

字符流中第一个不重复的字符2022.7.9-3

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符 "go" 时，第一个只出现一次的字符是 "g"。当从该字符流中读出前六个字符“google" 时，第一个只出现一次的字符是 "l"。

  1. 队列，我的第一个数字，一定是只出现一次的，且一定是第一次出现的。之后出现了第二次，就把它出了。
private int[] cnts = new int[128];
private Queue<Character> queue = new LinkedList<>();
public void Insert(char ch) {
    cnts[ch]++;
    queue.add(ch);
    while (!queue.isEmpty() && cnts[queue.peek()] > 1)
        queue.poll();
}
public char FirstAppearingOnce() {
    return queue.isEmpty() '#' : queue.peek();
}

https://www.nowcoder.com/practice/00de97733b8e4f97a3fb5c680ee10720?tpId=13&tqId=11207&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=cyc_github

滑动窗口的最大值2022.7.9-4

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。
例如，如果输入数组 {2, 3, 4, 2, 6, 2, 5, 1} 及滑动窗口的大小 3，那么一共存在 6 个滑动窗口，他们的最大值分别为 {4, 4, 6, 6, 6, 5}。

  1. 堆的维护，直接生成一个结果堆，然后对它进行维护。
    可以直接删除某个数
   heap.remove(num[i]);
   heap.add(num[j]);
   ret.add(heap.peek());

https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788?tpId=13&tqId=11217&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=cyc_github

引用仓库：https://github.com/CyC2018/CS-Notes/blob/master/notes/%E5%89%91%E6%8C%87%20Offer%20%E9%A2%98%E8%A7%A3%20-%20%E7%9B%AE%E5%BD%95.md


https://www.xamrdz.com/backend/3ys1938150.html

相关文章：