<习题集><LeetCode><队列><225/232/387/622/641>

2023-12-11 17:36

本文主要是介绍<习题集><LeetCode><队列><225/232/387/622/641>,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

225. 用队列实现栈

232. 用栈实现队列

387. 字符串中的第一个唯一字符

622. 设计循环队列

641. 设计循环双端队列


225. 用队列实现栈

https://leetcode.cn/problems/implement-stack-using-queues/

class MyStack{private Queue<Integer> queue1;private Queue<Integer> queue2;//构造方法;public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}//压栈;public void push(int x){//两个队列为空,则选一个先入队列,这里选queue2;//之后哪个队列非空,则入哪个队列;if (!queue1.isEmpty()){queue1.offer(x);}else{queue2.offer(x);}}//出栈;public int pop(){//哪个队列非空,就将这个队列的元素转移到另一个队列;//转移过程中,记录每一个出队列的元素;//直到出元素的队列为空,不将该元素入队列,而是返回;if(!queue1.isEmpty()){int temp = queue1.poll();while (!queue1.isEmpty()){queue2.offer(temp);temp = queue1.poll();}return temp;}else if(!queue2.isEmpty()){int temp = queue2.poll();while (!queue2.isEmpty()){queue1.offer(temp);temp = queue2.poll();}return temp;}return -1;}//查看栈顶元素;public int top(){//哪个队列非空,就将这个队列的元素转移到另一个队列;//转移过程中,记录每一个出队列的元素,直到出元素的队列为空,返回记录的元素;int temp = -1;if(!queue1.isEmpty()){while(!queue1.isEmpty()){temp = queue1.poll();queue2.offer(temp);}}else if(!queue2.isEmpty()){while(!queue2.isEmpty()){temp = queue2.poll();queue1.offer(temp);}}return temp;}//判断栈是否为空;public boolean empty(){if(queue1.isEmpty() && queue2.isEmpty()){return true;}else {return false;}}
}

232. 用栈实现队列

https://leetcode.cn/problems/implement-queue-using-stacks/

class MyQueue{//两个栈;private Stack<Integer> stack1 = null;private Stack<Integer> stack2 = null;//构造方法,初始化两个栈;public MyQueue() {stack1 = new Stack<>();stack2 = new Stack<>();}//压栈,stack1负责元素入队列;public void push(int x){stack1.push(x);}//stack2负责元素出队列;public int pop(){//如果stack2不为空,直接出;if(!stack2.isEmpty()){return stack2.pop();}else {//如果stack2为空,看看stack1是否为空;//不为空将stack1元素转移到stack2,再将stack2栈顶元素出栈;if(!stack1.isEmpty()){while (!stack1.isEmpty()){stack2.push(stack1.pop());}return stack2.pop();}}return -1;}//stack2的栈顶元素就是队列的队首元素;public int peek(){//如果stack2不为空,返回栈顶元素;if(!stack2.isEmpty()){return stack2.peek();}else {//如果stack2为空,看看stack1是否为空;//不为空将stack1元素转移到stack2,再将stack2栈顶元素peek;if(!stack1.isEmpty()){while (!stack1.isEmpty()){stack2.push(stack1.pop());}return stack2.peek();}}return -1;}public boolean empty(){return stack1.isEmpty() && stack2.isEmpty();}
}

387. 字符串中的第一个唯一字符

https://leetcode.cn/problems/first-unique-character-in-a-string/

    public int firstUniqChar1(String s) {//创建一个代表26个英文字母的数组;int[] arr = new int[26];//将字符串s转换为字符数组;(也可以不转,使用String的方法即可)char[] chs = s.toCharArray();//将每个字符转换成整数,这个整数代表下标,放入arr数组中;for(int i=0;i<chs.length;i++){int n = chs[i] - 'a';arr[n]++;}//遍历字符数组,查arr数组元素,找到第一个元素为1的,就返回这个字符;for(int i=0;i<chs.length;i++){int n = chs[i] - 'a';if(arr[n] == 1){return i;}}//找不到返回-1;return -1;}

622. 设计循环队列

https://leetcode.cn/problems/design-circular-queue/

class MyCircularQueue {//用于存放元素的数组elem,队首下标front,队尾下标rear,队列有效元素size;private int[] elem;private int front;private int rear;private int size;//构造方法,构造容量为k的数组;public MyCircularQueue(int k) {elem = new int[k];}//入队列方法;public boolean enQueue(int value) {if(this.isFull()){return false;}//赋值给队尾元素,rear++;elem[rear] = value;rear++;//超过最大容量,下标回到0;if(rear >= elem.length){rear = 0;}//有效元素++;size++;return true;}//出队列方法;public boolean deQueue() {if(this.isEmpty()){return false;}//队首下标直接向后移动;front++;//超过最大容量,下标回到0;if(front >= elem.length){front = 0;}//有效元素--;size--;return true;}//查看队首元素;public int Front() {if(this.isEmpty()){return -1;}return elem[front];}//查看队尾元素;public int Rear() {if(this.isEmpty()){return -1;}//应注意队尾在每一次入队列后都会向后移动;//因此想得到队尾元素需要查看队尾下标的前一个元素;int temp = rear-1;//处理循环队列中0下标的转换问题;if(rear == 0){temp = elem.length-1;}return elem[temp];}//有效元素为0,则队列为空;public boolean isEmpty() {return size == 0;}//有效元素等于数组容量,则队列满;public boolean isFull() {return size == elem.length;}
}

641. 设计循环双端队列

https://leetcode.cn/problems/design-circular-deque/

class MyCircularDeque {//用于存放元素的数组,队首元素下标,队尾元素下标,有效元素个数;private int[] elems;private int front;private int rear;private int size;//构造方法;public MyCircularDeque(int k) {elems = new int[k];}//头插法;public boolean insertFront(int value) {//判断是否已满;if(this.isFull()){return false;}//队首指针前移,注意转换最大下标和0下标;if(front == 0){front = elems.length-1;}else{front--;}//赋值和有效元素++;elems[front] = value;size++;return true;}//尾插法;public boolean insertLast(int value) {//判断是否已满;if(this.isFull()){return false;}//赋值和有效元素++;elems[rear] = value;size++;//队尾指针后移,注意转换最大下标和0下标;if(rear == elems.length-1){rear = 0;}else{rear++;}return true;}//头删法;public boolean deleteFront() {//判断是否为空;if(this.isEmpty()){return false;}//队首指针后移,注意转换最大下标和0下标;if(front == elems.length-1){front = 0;}else{front++;}//有效元素--;size--;return true;}//尾删法;public boolean deleteLast() {//判断是否为空;if(this.isEmpty()){return false;}//队尾指针前移,注意转换最大下标和0下标;if(rear == 0){rear = elems.length-1;}else{rear--;}//有效元素--;size--;return true;}//查看队首元素;public int getFront() {if(this.isEmpty()){return -1;}return elems[front];}//查看队尾元素;public int getRear() {if(this.isEmpty()){return -1;}//注意队尾元素应该是队尾指针的前一个,注意转换最大下标和0下标;int temp = rear-1;if(rear == 0){temp = elems.length-1;}return elems[temp];}//判断是否为空;public boolean isEmpty() {return size == 0;}//判断是否已满;public boolean isFull() {return size == elems.length;}
}

这篇关于<习题集><LeetCode><队列><225/232/387/622/641>的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/481510

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 2431 poj 3253 优先队列的运用

poj 2431: 题意: 一条路起点为0, 终点为l。 卡车初始时在0点,并且有p升油,假设油箱无限大。 给n个加油站,每个加油站距离终点 l 距离为 x[i],可以加的油量为fuel[i]。 问最少加几次油可以到达终点,若不能到达,输出-1。 解析: 《挑战程序设计竞赛》: “在卡车开往终点的途中,只有在加油站才可以加油。但是,如果认为“在到达加油站i时,就获得了一

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

poj3750约瑟夫环,循环队列

Description 有N个小孩围成一圈,给他们从1开始依次编号,现指定从第W个开始报数,报到第S个时,该小孩出列,然后从下一个小孩开始报数,仍是报到S个出列,如此重复下去,直到所有的小孩都出列(总人数不足S个时将循环报数),求小孩出列的顺序。 Input 第一行输入小孩的人数N(N<=64) 接下来每行输入一个小孩的名字(人名不超过15个字符) 最后一行输入W,S (W < N),用

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

POJ2010 贪心优先队列

c头牛,需要选n头(奇数);学校总共有f的资金, 每头牛分数score和学费cost,问合法招生方案中,中间分数(即排名第(n+1)/2)最高的是多少。 n头牛按照先score后cost从小到大排序; 枚举中间score的牛,  预处理左边与右边的最小花费和。 预处理直接优先队列贪心 public class Main {public static voi

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点