北京网站制作的公司哪家好,加盟网网站建设,wordpress相关文章推荐,东莞网络营销平台今天解决队列和栈的题#xff0c;期待后面狠狠搞二叉树#xff08;之前面试被刺了TT)
1047. 删除字符串中的所有相邻重复项
这个题目跟前面的匹配括号思路一模一样#xff0c;入栈后消消乐即可
代码实现的时候发现容器类使用toString后就是包含[]的数组#xff0c;所以需…今天解决队列和栈的题期待后面狠狠搞二叉树之前面试被刺了TT)
1047. 删除字符串中的所有相邻重复项
这个题目跟前面的匹配括号思路一模一样入栈后消消乐即可
代码实现的时候发现容器类使用toString后就是包含[]的数组所以需要额外的StringBuilder来满足返回值的需求
class Solution {public String removeDuplicates(String s) {DequeCharacter stack new LinkedList();for (int i 0 ; i s.length(); i) {if (!stack.isEmpty() s.charAt(i)stack.peek()) stack.pop();else stack.push(s.charAt(i));}StringBuilder sb new StringBuilder();while (!stack.isEmpty()) {sb.append(stack.pop());}return sb.reverse().toString();}
}
150. 逆波兰表达式求值
就是给后缀表达式求值跟数据结构学的一样如果是数字就压栈是操作符就取出两个数出来计算把结果压栈。
字符串转数字Integer.valueOf()
class Solution {public int evalRPN(String[] tokens) {DequeInteger stacknew LinkedList();for(String s:tokens){if(s.equals()){stack.push(stack.pop()stack.pop());}else if(s.equals(-)){ stack.push(-stack.pop()stack.pop());}else if(s.equals(*)){ stack.push(stack.pop()*stack.pop());}else if(s.equals(/)){int in1stack.pop();int in2stack.pop();stack.push(in2/in1);}else{stack.push(Integer.valueOf(s));}}return stack.pop();}
}
239. 滑动窗口最大值
经典滑动窗口模型这里直接用deque
在单调队列中存储数组索引来方便判断是否在滑动窗口里面而单调队列在扫描时首先检查队头是否在窗口内再保证之前的老元素大于新加入的元素不然他们就没有利用价值了全部弹出
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {DequeInteger q new LinkedList();int[] res new int[nums.length-k1];int count 0;for(int i 0 ; i nums.length;i){while(!q.isEmpty() q.peek() i-k) q.pollFirst();while(!q.isEmpty() nums[q.peekLast()]nums[i]) q.pollLast();q.offerLast(i);if (i k-1) res[count] nums[q.peek()]}return res;}
}
347.前 K 个高频元素
第一反应是用哈希表map直接存储元素和对应的出现次数再对map按值排序但此时时间复杂度需要nlogn不满足进阶要求
由于没必要对所有元素进行排序一直维护前k个高频即可在java中堆定义为优先级队列本题使用的大顶堆代码如下
class Solution {public int[] topKFrequent(int[] nums, int k) {MapInteger, Integer map new HashMapInteger, Integer();for(int i: nums) map.put(i,map.getOrDefault(i,0)1);PriorityQueueInteger pq new PriorityQueue((x,y)-map.get(y)-map.get(x));for(int key : map.keySet()) pq.offer(key);int[] result new int[k];while(k 0){result[k - 1] pq.poll();k--;}return result;}
}
