php网站开发要学什么,郑州免费网络推广,wordpress 文档管理,织梦模板安装目录 开场白
栈与队列
LeetCode232. 用栈实现队列
LeetCode225. 用队列实现栈
LeetCode102. 二叉树的层序遍历
LeetCode103. 二叉树的锯齿形层序遍历
堆#xff08;优先级队列#xff09;
堆排序
LeetCode215. 数组中的第 k 个最大元素
总结 开场白
今天是除夕优先级队列
堆排序
LeetCode215. 数组中的第 k 个最大元素
总结 开场白
今天是除夕在此首先祝各位读者朋友们新年快乐愿你在新的一年里心怀希望勇敢追梦愿每一天都充满温暖与惊喜愿所有的努力都能开花结果所有的期待都能如愿以偿。
从寒假开始为了准备面试我在我的个人CSDN账号陆续发布了Java实现数据结构与算法的相关文章意在从我个人角度深度理解数据结构。将相关文章分享分布后很多读者通过私信方式与我交流讨论每次看到大家的留言无论是鼓励、建议还是探讨问题都让我倍感温暖也让我更加坚定了继续分享知识的决心。各位读者的支持是我持续创作的最大动力。
言归正传我们今天简要分析前几篇文章中涉及到的数据结构在 中的应用。很多数据结构在实际问题中是结合着使用的例如二叉树的层序遍历需要使用到队列作为辅助因为层序遍历实际上是一种广度优先搜索Breadth First SearchBFS二叉树的前中后序遍历的迭代方式的实现需要使用到栈即使在递归实现中我们使用三行代码可以实现需求但是递归函数底层使用了函数调用栈如果使用迭代方式我们就需要使用栈来模拟函数调用栈的行为。
栈与队列
LeetCode232. 用栈实现队列
232. 用栈实现队列 - 力扣LeetCode
本题要求使用两个栈来模拟一个队列此队列应该支持常见的入队、出队、获取队首元素以及判空几个常见操作。
这个题让我的思绪回到了大一考学院实验室的时候当时过了笔试环节面试环节一个学长很突然的问了我这个问题——“如何用两个栈模拟一个队列”当时一紧张说成了两栈共享空间学长说 “不好意思我没太明白你的意思”。
实际上只要了解了队列和栈的特性解决这个问题就很容易了。我们需要定义两个栈分别是输入栈和输出栈前者用于接收入队元素后者用于处理获取队首元素和出队操作。假设我们连续向队列中入队元素我们直接将这些元素按顺序压入输入栈此时输入栈就保存了所有入队元素栈顶元素就是队尾元素如果我们需要执行出队或获取队首元素操作我们需要将输入栈的所有元素按顺序出栈然后重新压入到输出栈那么此时输出栈的栈顶元素就变成了模拟队列的队首元素执行出队操作就是将输出栈的栈顶元素出栈获取队首元素就是获取输出栈的栈顶元素。如果后续还需要入队元素直接将元素压入输入栈如果需要获取队首元素或者出队先判断一下输出栈是否为空如果输出栈为空就需要执行相同的操作将输入栈的元素按顺序入栈到输出栈此时栈顶元素就是队首元素。实现代码如下。
class MyQueue {private final ArrayStackInteger inputStack;private final ArrayStackInteger outputStack;private int size;public MyQueue() {inputStack new ArrayStack(101);outputStack new ArrayStack(101);size 0;}public void push(int x) {inputStack.push(x);size;}public int pop() {if (outputStack.isEmpty())while (!inputStack.isEmpty())outputStack.push(inputStack.pop());size--;return outputStack.pop();}public int peek() {if (outputStack.isEmpty())while (!inputStack.isEmpty())outputStack.push(inputStack.pop());return outputStack.peek();}public boolean empty() {return size 0;}
}
在以上实现中我们在类 中定义了一个用于表示模拟队列存储元素数量的变量 通过此方式在后续实现 方法时就很容易直接判断 是否为 即可我们也可以通过判断两栈是否同时为空得出队列是否为空。
需要提前指出的是我们这里使用了顺序栈在构造顺序栈时需要传入期望规模参数 本题已经说明入队出队操作不会超过 次我们直接规定顺序栈的期望规模为 这样就不需要执行判满判空等操作。再次提醒提交代码时需要将自定义的顺序栈类 同时提交。当然我们也可以使用 类来实现栈。
LeetCode225. 用队列实现栈
225. 用队列实现栈 - 力扣LeetCode
本题需要使用两个队列模拟栈的操作模拟栈需要支持普通栈的入栈、出栈、获取栈顶元素和判空操作。我们知道队列是一种先入先出FIFO数据结构而栈是一种后入先出LIFO数据结构如果按照顺序将元素入队那么队首一定是模拟栈的栈底元素而队尾一定是模拟栈的栈顶元素。所以使用队列模拟栈的时候我们可以直接让元素序列入队到第一个队列在出栈或获取栈顶元素时让队尾之前的所有元素出队并让这些元素按刚才出队的顺序入队到另一个队列这个队列的作用就是暂存模拟栈栈顶元素的所有后继元素如果是出栈操作将第一个队列剩余的最后一个元素出队并用变量接收返回即可然后将第二个队列的所有元素出队让这些元素按照顺序重新入队到第一个队列如果只是单纯获取栈顶元素我们在拿到第一个队列剩余的最后一个元素后第二个队列的所有元素出队让这些元素按照出队顺序重新入队到第一个队列。方便起见我们可以自定义一个用于表示模拟栈中存储元素数量的变量 所以实现判空操作就很简单了直接判断 是否为 即可。代码如下。
class MyStack {private final ArrayQueueInteger queue1;private final ArrayQueueInteger queue2;private int size;public MyStack() {queue1 new ArrayQueue(101);queue2 new ArrayQueue(101);size 0;}public void push(int x) {queue1.offer(x);size;}public int pop() {int temp size;while (temp -- ! 1)queue2.offer(queue1.pull());Integer ans queue1.pull();while (!queue2.isEmpty())queue1.offer(queue2.pull());size--;return ans;}public int top() {int temp size;while (temp -- ! 1)queue2.offer(queue1.pull());Integer ans queue1.pull();while (!queue2.isEmpty())queue1.offer(queue2.pull());queue1.offer(ans);return ans;}public boolean empty() {return size 0;}
}
当然本题的进阶实现是直接使用一个队列模拟栈操作可以优化的地方就是元素转移阶段我们可以不需要定义另一个队列暂存这些元素而是直接让这些元素重新入队即可。整个调整过程就是将队尾之前的所有元素出队每个元素出队后又立刻入队到队尾整个操作结束后队首元素就是模拟栈的栈顶元素。代码如下。
class MyStack {private final ArrayQueueInteger queue;private int size 0;public MyStack() {queue new ArrayQueue(101);size 0;}public void push(int x) {queue.offer(x);size;}public int pop() {int temp size - 1;while (temp -- ! 0)queue.offer(queue.pull());size--;return queue.pull();}public int top() {int temp size - 1;while (temp -- ! 0)queue.offer(queue.pull());Integer ans queue.pull();queue.offer(ans);return ans;}public boolean empty() {return size 0;}
}
我们通过上面两个代码片段不难发现出栈和获取栈顶元素这两个操作有重复代码我们不妨将共有的代码提取到入栈操作处即在入栈时就进行队列中元素的调整让队尾元素来到队首通过这种实现方式在后续的出栈和获取栈顶元素时我们直接对队首元素进行操作即可。代码如下。
class MyStack {private final ArrayQueueInteger queue1;private final ArrayQueueInteger queue2;private int size;public MyStack() {queue1 new ArrayQueue(101);queue2 new ArrayQueue(101);size 0;}public void push(int x) {queue1.offer(x);int temp size;while (temp -- ! 0)queue2.offer(queue1.pull());while (!queue2.isEmpty())queue1.offer(queue2.pull());size;}public int pop() {size--;return queue1.pull();}public int top() {return queue1.peek();}public boolean empty() {return size 0;}
}
class MyStack {private final ArrayQueueInteger queue;private int size 0;public MyStack() {queue new ArrayQueue(101);size 0;}public void push(int x) {queue.offer(x);int temp size;while (temp -- ! 0)queue.offer(queue.pull());size;}public int pop() {size--;return queue.pull();}public int top() {return queue.peek();}public boolean empty() {return size 0;}
}
LeetCode102. 二叉树的层序遍历
102. 二叉树的层序遍历 - 力扣LeetCode
二叉树的层序遍历遵循着广度优先搜索的不断延伸思想。具体来说我们需要使用一个队列用来暂存需要遍历的结点让根节点入队每次取出队列中的队首结点并将其的左右孩子存入队列不断进行此操作就可以让队列中存储着当前层的下一层结点实际上队列的出队顺序就是此二叉树的层序遍历序列。 在具体实现中由于队列只有在遍历到叶子结点后才会为空我们需要专门定义一个变量用来存储当前层的结点数每次取出队列元素都是基于这个变量的否则会取出下一层的结点。 public ListListInteger levelOrder(TreeNode root) {if (root null)return new ArrayList();ListListInteger ans new ArrayList();ArrayQueueTreeNode queue new ArrayQueue(2001);queue.offer(root);int levelNum 1;while (!queue.isEmpty()) {ListInteger list new ArrayList();int cnt 0;for (int i 1; i levelNum; i) {TreeNode node queue.pull();list.add(node.val);if (node.left ! null) {queue.offer(node.left);cnt;}if (node.right ! null) {queue.offer(node.right);cnt;}}levelNum cnt;ans.add(list);}return ans;}
LeetCode103. 二叉树的锯齿形层序遍历
103. 二叉树的锯齿形层序遍历 - 力扣LeetCode
本题与上题类似我们认为根节点所处层为第一层通过题目要求我们不难发现当层序号为奇数时我们需要从左到右遍历反之如果层序号为偶数时我们需要从右到左遍历这样就可以实现锯齿形遍历。我们在每层接收结果的时候需要使用一个双端队列若当前层的层序号为奇数我们将队列的队首结点数据从尾部插入到双端队列否则从头部插入双端队列后续的操作与上一题是一致的不再赘述。
为了方便实现我们使用了 进行实现代码如下。 public ListListInteger zigzagLevelOrder(TreeNode root) {if (root null)return new ArrayList();ListListInteger ans new ArrayList();LinkedListTreeNode queue new LinkedList();queue.offer(root);int levelNum 1;boolean isOdd true;while (!queue.isEmpty()) {int cnt 0;LinkedListInteger level new LinkedList();for (int i 1; i levelNum; i) {TreeNode node queue.poll();if (node ! null) {if (isOdd)level.offerLast(node.val);elselevel.offerFirst(node.val);if (node.left ! null) {queue.offer(node.left);cnt;}if (node.right ! null) {queue.offer(node.right);cnt;}}}levelNum cnt;isOdd !isOdd;ans.add(level);}return ans;}
堆优先级队列
堆排序
堆排序是基于堆的一种排序方法假设我们使用大顶堆进行堆内元素的排序执行建堆操作后堆顶元素是所有元素的最大值我们可以选择将堆顶元素与堆的最后一个元素进行交换然后让堆的 变量减 这样就表示我们不再维护最大值元素此时将交换到堆顶的元素执行一次下潜操作新的堆顶元素就是剩下的 个元素中的最大值。不断执行此操作直到堆中维护的元素数量为 为止。 public static void main(String[] args) {MaxHeap heap new MaxHeap(new int[]{1, 34, 54, 13, 25, 6, 9, 17});System.out.println(Arrays.toString(heap.array));while (heap.size 1) {heap.swap(0, heap.size - 1);heap.size --;heap.down(0);}System.out.println(Arrays.toString(heap.array));}
LeetCode215. 数组中的第 k 个最大元素
215. 数组中的第K个最大元素 - 力扣LeetCode
本题给定一个数组和一个整型变量 届时需要返回数组中第 个最大的元素。初见此题第一想法是直接对数组进行排序然后返回指定位置元素即可但是这种方式并没有考虑到数组中存在重复元素的情况。
我们可以直接使用一个大顶堆来维护所有元素然后执行 次出队操作即可。 public int findKthLargest(int[] nums, int k) {MaxHeap heap new MaxHeap(nums);while (k -- ! 0)heap.pull();return heap.peek();}
实际上我们也并不需要维护所有的元素直接定义一个大小为 的小顶堆先将前 个元素存入堆中然后继续遍历数组若当前遍历的元素大于堆顶元素则执行一次替换堆顶元素操作最终堆顶元素就是第 个最大元素。 public int findKthLargest(int[] nums, int k) {MinHeap heap new MinHeap(k);for (int i 0; i k; i )heap.offer(nums[i]);for (int i k; i nums.length; i ) {if (nums[i] heap.peek())heap.replace(nums[i]);}return heap.peek();}总结
本文写的比较仓促因为我要过年了。
