门户网站流量,html5视频播放器例子,免费app软件下载网站,互联网o2o是什么意思栈与队列
232.用栈实现队列
232. 用栈实现队列
使用栈实现队列的下列操作#xff1a;
push(x) – 将一个元素放入队列的尾部。 pop() – 从队列首部移除元素。 peek() – 返回队列首部的元素。 empty() – 返回队列是否为空。
思路: 定义两个栈: 入队栈, 出队栈, 控制出入…栈与队列
232.用栈实现队列
232. 用栈实现队列
使用栈实现队列的下列操作
push(x) – 将一个元素放入队列的尾部。 pop() – 从队列首部移除元素。 peek() – 返回队列首部的元素。 empty() – 返回队列是否为空。
思路: 定义两个栈: 入队栈, 出队栈, 控制出入栈顺序, 进入的元素倒两次就是原顺序
代码:
class MyQueue {StackInteger in;StackInteger out;public MyQueue() {in new Stack();out new Stack();}public void push(int x) {in.push(x);}public int pop() {inToOut();return out.pop();}public int peek() {inToOut();return out.peek();}private void inToOut() {// out非空时不能往里面倒, 出的时候要先把out里的出完, 再倒入// 否则原来的数据会被覆盖if(!out.isEmpty()) return;while(!in.isEmpty()) {out.push(in.pop());}}public boolean empty() {return in.isEmpty() out.isEmpty();}
}225. 用队列实现栈
225. 用队列实现栈
使用队列实现栈的下列操作
push(x) – 元素 x 入栈pop() – 移除栈顶元素top() – 获取栈顶元素empty() – 返回栈是否为空
思路: 每次pop, peek都要reposition
代码:
class MyStack {QueueInteger queue;public MyStack() {queue new LinkedList();}public void push(int x) {queue.offer(x);}public int pop() {reposition();// 每次pop时将队列前size - 1个放到队列末尾return queue.poll();}public int top() {reposition();// 每次pop时将队列前size - 1个放到队列末尾int n queue.poll();queue.offer(n);return n;}public boolean empty() {return queue.isEmpty();}private void reposition() {int size queue.size();size--;while(size-- 0) {queue.offer(queue.poll());}}
}20. 有效的括号
20. 有效的括号
给定一个只包括 ‘(’‘)’‘{’‘}’‘[’‘]’ 的字符串判断字符串是否有效。
有效字符串需满足
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。
思路:
一共有三种情况: 字符串里左方向的括号多余了 所以不匹配。 括号没有多余但是 括号的类型没有匹配上。 字符串里右方向的括号多余了所以不匹配。 每一个左括号, 压入对应的右括号, 当开始遍历右括号时, 按照如下方式和栈中元素进行对比
代码:
class Solution {public boolean isValid(String s) {// 0. 剪枝int len s.length();if(len % 2 ! 0) return false;// 长度为奇数, 则一定不能匹配// 1. 初始化栈StackCharacter stack new Stack();// 2. 遍历每一个字符for(int i 0;i len;i) {// 2.1 每一个左括号, 压入对应的右括号if(s.charAt(i) () {stack.push());}else if(s.charAt(i) [) {stack.push(]);}else if(s.charAt(i) {) {stack.push(});// 2.2 每一个右括号, 查看栈中对应的右括号是否相等}else if(stack.isEmpty() || s.charAt(i) ! stack.peek()) {// 不能是s.pop,否则在判断时就会将元素弹出return false;}else {// 右括号匹配, 出栈stack.pop();}}// 3. 遍历完后, 查看栈中是否还有右括号(左括号多余)return stack.isEmpty();}
}1047. 删除字符串中的所有相邻重复项
1047. 删除字符串中的所有相邻重复项
给出由小写字母组成的字符串 S重复项删除操作会选择两个相邻且相同的字母并删除它们。
在 S 上反复执行重复项删除操作直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例
输入“abbaca”输出“ca”解释例如在 “abbaca” 中我们可以删除 “bb” 由于两字母相邻且相同这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”其中又只有 “aa” 可以执行重复项删除操作所以最后的字符串为 “ca”。
法一: 栈
思路: 用字符串模拟栈(也可以直接用栈, 需要再转为字符串)进行消消乐, 留下的就是最终的字符串
代码:
class Solution {public String removeDuplicates(String s) {// 1. 定义字符串模拟栈StringBuilder sb new StringBuilder();// 2. 遍历s的每一位, 与栈进行消除int top -1;for(int i 0;i s.length();i) {if(top 0 s.charAt(i) sb.charAt(top)) {sb.deleteCharAt(top--);}else {sb.append(s.charAt(i));top;}}// 3. 返回return sb.toString();}
}法二:双指针
思路: 快指针指向原字符串要处理的字符, 慢指针指向新的字符串, 当新字符串出现相邻相等的情况, 则将两个同时排除, 回退到第一次出现该字符的位置, 继续遍历原字符串的下一个字符, 否则, 快慢指针同时往前走.
代码:
class Solution {public String removeDuplicates(String s) {// 1. 初始化char[] str s.toCharArray();int fast 0,slow 0;// 2. 遍历原字符串while(fast str.length) {str[slow] str[fast];// 2.1 新的字符串出现成对可消除, 走到第一次出现的位置, 覆盖(同时消除)if(slow 0 str[slow] str[slow - 1]) {slow--;}else{// 2.2 没有可消除的字符, fast slow都往后走slow;}}// 3. 返回return new String(str,0,slow);}
}150. 逆波兰表达式求值
150. 逆波兰表达式求值
根据 逆波兰表示法求表达式的值。
有效的运算符包括 , - , * , / 。每个运算对象可以是整数也可以是另一个逆波兰表达式。
说明
整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1
输入: [“2”, “1”, “”, “3”, * ]输出: 9解释: 该算式转化为常见的中缀算术表达式为((2 1) * 3) 9
思路: 栈, 每遇到一个操作符, 就对栈中的两个数组进行计算, 注意: 栈中的顺序与原来后缀表达式计算顺序相反, 因此弹出来的两个数字运算时交换顺序注意: 栈中的顺序与原来后缀表达式计算顺序相反, 因此弹出来的两个数字运算时交换顺序.
代码:
class Solution {public int evalRPN(String[] tokens) {// 0. 剪枝if(tokens.length 1) return Integer.valueOf(tokens[0]);// 1. 定义栈StackInteger sk new Stack();// 2. 逐个处理for(String s : tokens) {// 2.1 处理运算符if(.equals(s) || -.equals(s) || *.equals(s) || /.equals(s)) {// 注意: 栈中的顺序与原来后缀表达式计算顺序相反, 因此弹出来的两个数字运算时交换顺序int n sk.pop();int m sk.pop();if(.equals(s)) {sk.push(m n);}else if(-.equals(s)) {sk.push(m - n);}else if(*.equals(s)) {sk.push(m * n);}else if(/.equals(s)) {sk.push(m / n);}}else {// 2.2 处理数字sk.push(Integer.valueOf(s));}}// 3. 返回return sk.pop();}
}239. 滑动窗口最大值
239. 滑动窗口最大值
给定一个数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
进阶
你能在线性时间复杂度内解决此题吗 提示
1 nums.length 10^5-10^4 nums[i] 10^41 k nums.length
思路: 单调队列, 保证队头为窗口内最大值, 保证每次队列内有不多于k个元素
代码:
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {// 1. 定义容器ArrayDequeInteger q new ArrayDeque();int n nums.length,index 0;int[] ans new int[n - k 1];// 2. 循环遍历for(int i 0;i n;i) {// 2.1 出: 将不符合窗口范围的移出while(!q.isEmpty() q.peek() (i - k 1)) q.poll();// 2.2 入: 先将比该数值小的从后往前依次移出(保证单调), 再放入while(!q.isEmpty() nums[q.peekLast()] nums[i]) q.pollLast();q.offer(i);// 2.3 收集: 当窗口中走够k个元素时, 开始收集if(i k - 1) ans[index] nums[q.peek()];}// 3. 返回return ans;}
}347.前 K 个高频元素
347. 前 K 个高频元素
给定一个非空的整数数组返回其中出现频率前 k 高的元素。
示例 1:
输入: nums [1,1,1,2,2,3], k 2输出: [1,2]
示例 2:
输入: nums [1], k 1输出: [1]
思路: map统计num及其出现次数, PriorityQueue用作小顶堆, 维护前k个出现次数最多的entry
代码:
class Solution {public int[] topKFrequent(int[] nums, int k) {// 1. 定义容器int[] ans new int[k];MapInteger,Integer map new HashMap();PriorityQueueint[] pq new PriorityQueue((o1,o2) - o1[1] - o2[1]);// 2. 填充mapfor(int num : nums) {map.put(num,map.getOrDefault(num,0) 1);}// 3. 填充pqSetMap.EntryInteger,Integer entries map.entrySet();for(Map.EntryInteger,Integer e : entries) {int[] t new int[2];t[0] e.getKey();t[1] e.getValue();pq.offer(t);// 维持小顶堆中3个出现次数最多元素if(pq.size() k) pq.poll();}// 4. 返回for(int i 0;i k;i) {ans[i] pq.poll()[0];}return ans;}
}
