从0学习算法-第4天
做人如果没有梦想,那和咸鱼有什么区别。
用栈实现队列
使用栈实现队列的下列操作:
push(x)--将一个元素放入队列的尾部
pop()--从队列首部移除元素
peek()--返回队列首部的元素
empty()--返回队列是否为空
//思路:队列先进先出,栈后进先出,所以一个栈肯定不行,我们需要一个输入栈和一个输出栈 class MyQueue{ Stack<Integer> stackIn;//负责进栈 Stack<Integer> stackOut;//负责出栈 public MyQueue(){ stackIn = new Stack()<>;// stackOut = new Stack()<>; } public void push(int x){ stackIn.push(x); } public int pop(){ dumpstackIn(); return stackOut.pop(); } public int peek(){ dumpstackIn(); return stackOut.peek(); } public boolean empty(){ return stackIn.isEmpty()&&stackOut.isEmpty(); } //如果stackIn不为空,那么将stackIn中的元素放入stackOut中 private void dumpstackIn(){ if(!stackOut.isEmpty()) return; while(!stackIn.isEmpty()){ stackOut.push(stackIn.pop()); } } }
用队列实现栈
使用队列实现栈的下列操作
push(x)--元素x入栈
pop()--移除栈顶元素
top()--获取栈顶元素
empty()--返回栈是否为空
//使用一个队列来模拟栈 class Mystack{ Queue<Integer> queue;//使用队列来实现栈 public Mystack{ queue = new LinkedList<>(); } public void rePosition(){ int size=queue.size();//获取队列的大小 size--;// while(size-->0){ queue.add(queue.poll());//循环将队首元素移动到队尾,直到队首元素变为栈顶元素 } public void push(int x){ queue.add(x);//入栈操作,将元素添加到队尾 } public int pop(){ rePosition();//调整队列顺序,使得队首元素为栈顶元素 int result=queue.poll();//获取队首元素 queue.add(result);//将队首元素再次添加 return result;//返回队首元素 } public boolean empty(){ return queue.isEmpty();//判断栈是否为空 } }
20. 有效的括号
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 注意空字符串可被认为是有效字符串。
class Solution { public boolean isValid(String s) { Deque<Character> deque = new LinkedList<>(); char ch; for (int i = 0; i < s.length(); i++) { ch = s.charAt(i); //碰到左括号,就把相应的右括号入栈 if (ch == '(') { deque.push(')'); }else if (ch == '{') { deque.push('}'); }else if (ch == '[') { deque.push(']'); //当遇到右括号时,会判断栈顶元素是否与当前右括号匹配。如果匹配,则将栈顶元素出栈;如果不匹配,则 返回false } else if (deque.isEmpty() || deque.peek() != ch) { return false; }else {//如果是右括号判断和栈顶元素匹配 deque.pop(); //出栈 } } //最后判断栈是否为空 return deque.isEmpty(); } }
1047. 删除字符串中的所有相邻重复项
给出由小写字母组成的字符串 S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。
在 S 上反复执行重复项删除操作,直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例:
- 输入:"abbaca"
- 输出:"ca"
- 解释:例如,在 "abbaca" 中,我们可以删除 "bb" 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca",其中又只有 "aa" 可以执行重复项删除操作,所以最后的字符串为 "ca"。
class Solution { public String removeDuplicates(String s) { Deque<Character> stack =new LinkedList<>(); for(int i=0;i<s.length();i++){ char ch=s.charAt(i); if(stack.isEmpty()||stack.peek()!=ch){ stack.push(ch); }else{ stack.pop(); } } String str=""; //剩余元素即为不重复元素 while(!stack.isEmpty()){ str=stack.pop()+str; } return str; } }
239. 滑动窗口最大值
给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
class Solution { public int[] maxSlidingWindow(int[] nums, int k) { //利用单调队列 ArrayDeque<Integer> deque=new ArrayDeque<>(); int n=nums.length; int[] res=new int[n-k+1]; int idx=0; for(int i=0;i<n;i++){ //i为nums下标,是要在[i-k+1,i]中选到最大值,只要保证两点 //1.队列头节点需要在[i-k+1,i]范围内,不符合则要弹出 while(!deque.isEmpty()&&deque.peek()<i-k+1){ deque.poll();//头部移除元素 } //2.既然是单调,就要保证每次放进去的数字要比末尾的都大,否则也弹出 while(!deque.isEmpty()&&nums[deque.peekLast()]<nums[i]){//队列尾部元素小于nums[i]时,从队列尾部移除元素 deque.pollLast();//从尾部移除 } deque.offer(i); //因为单调,当i增长到符合第一个k范围的时候,每滑动一步将队列的头节点放入结果就行 if(i>=k-1){ res[idx++]=nums[deque.peek()]; } } return res; } }
347.前 K 个高频元素
给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
示例 1:
- 输入: nums = [1,1,1,2,2,3], k = 2
- 输出: [1,2]
示例 2:
- 输入: nums = [1], k = 1
- 输出: [1]
//思路:1.统计出现频率高的元素 //2.对1步骤排序 //3.按顺序返回k个 //想到优先级队列 class Solution { //解法1:基于大顶堆实现 public int[] topKFrequent1(int[] nums, int k) { Map<Integer,Integer> map = new HashMap<>(); //key为数组元素值,val为对应出现次数 for(int num:nums){ map.put(num,map.getOrDefault(num,0)+1); //将当前元素num的出现次数加1,并将其存储在map中 } PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2)->pair2[1]-pair1[1]); //创建一个优先队列pq,用于存储二元组(num,cnt),其中num表示元素值,cnt表示元素值在数组中的出现次数。优先队列按照二元组的第二个元素(即出现次数)从大到小进行排序,这样队头的元素就是出现次数最多的元素。 for(Map.Entry<Integer,Integer> entry:map.entrySet()){ //遍历map中的每个条目 pq.add(new int[]{entry.getKey(),entry.getValue()}); //将当前条目的键和值封装成一个二元组,并将其添加到优先队列pq中 } int[] ans = new int[k]; //创建一个长度为k的整数数组ans,用于存储结果 for(int i=0;i<k;i++){ //循环k次,从优先队列pq中依次弹出k个元素 ans[i] = pq.poll()[0]; //弹出优先队列pq的队头元素,并将其第一个元素(即元素值)存储在ans数组的第i个位置 } return ans; //返回结果数组ans,其中包含了出现频率最高的k个元素 } }