惠阳网站优化,学校英文网站建设,品牌网址,关于网站seo优化文章目录 1.有效的括号1.答案2.思路 2.最小栈1.答案2.思路 3.前 K 个高频元素1.答案2.思路 4.用栈实现队列1.答案2.思路 5.删除字符串中的所有相邻重复项1.答案2.思路 1.有效的括号
1.答案
package com.sunxiansheng.arithmetic.day10;import java.util.Stack;/*** Descripti… 文章目录 1.有效的括号1.答案2.思路 2.最小栈1.答案2.思路 3.前 K 个高频元素1.答案2.思路 4.用栈实现队列1.答案2.思路 5.删除字符串中的所有相邻重复项1.答案2.思路 1.有效的括号
1.答案
package com.sunxiansheng.arithmetic.day10;import java.util.Stack;/*** Description: 20. 有效的括号** Author sun* Create 2025/1/15 09:37* Version 1.0*/
public class t20 {public static boolean isValid(String s) {// 栈StackCharacter stack new Stack();// 遍历for (int i 0; i s.length(); i) {// 如果是左括号就入栈char c s.charAt(i);if (c ( || c { || c [) {stack.push(c);}// 如果是右括号就进行匹配if (c ) || c } || c ]) {// 如果栈为空就返回falseif (stack.isEmpty()) {return false;}// 从栈中获取一个左括号进行匹配Character pop stack.pop();boolean match match(pop, c);if (!match) {return false;}}}return stack.isEmpty();}/*** 匹配** param left* param right* return*/private static boolean match(Character left, Character right) {if (left ( right )) {return true;}if (left { right }) {return true;}if (left [ right ]) {return true;}return false;}
}2.思路
就是左括号入栈右括号匹配但是需要注意的是右括号在匹配左括号之前栈不能为空并且最后所有的右括号都匹配完了栈也不能为空
2.最小栈
1.答案
package com.sunxiansheng.arithmetic.day10;import java.util.Stack;/*** Description: 155. 最小栈** Author sun* Create 2025/1/15 09:51* Version 1.0*/
public class MinStack {/*** 辅助栈*/private StackInteger stack;/*** 最小栈*/private StackInteger minStack;public MinStack() {stack new Stack();minStack new Stack();// 初始化为一个最大的元素minStack.push(Integer.MAX_VALUE);}public void push(int val) {// 压栈压最小stack.push(val);minStack.push(Math.min(val, minStack.peek()));}public void pop() {// pop都出去stack.pop();minStack.pop();}public int top() {return stack.peek();}public int getMin() {return minStack.peek();}
}2.思路
最小栈初始化一个最大值压栈压最小pop都出去这样就能保证最小栈的栈顶是目前的最小元素
3.前 K 个高频元素
1.答案
package com.sunxiansheng.arithmetic.day10;import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;/*** Description: 347. 前 K 个高频元素** Author sun* Create 2025/1/15 10:06* Version 1.0*/
public class t347 {public static int[] topKFrequent(int[] nums, int k) {// 首先统计频率MapInteger, Integer map new HashMap();for (int num : nums) {map.put(num, map.getOrDefault(num, 0) 1);}// 构建大顶堆PriorityQueueMap.EntryInteger, Integer pq new PriorityQueue((a, b) - b.getValue() - a.getValue());// 将map的元素放到大顶堆中for (Map.EntryInteger, Integer entry : map.entrySet()) {pq.offer(entry);}// 从大顶堆中取出前k个元素int[] res new int[k];for (int i 0; i k; i) {res[i] pq.poll().getKey();}return res;}
}2.思路
统计频率之后将其放到大顶堆中然后取出前k个元素即可
4.用栈实现队列
1.答案
package com.sunxiansheng.arithmetic.day10;import java.util.Stack;/*** Description: 232. 用栈实现队列** Author sun* Create 2025/1/15 10:19* Version 1.0*/
public class MyQueue {/*** 输入栈和输出栈*/private StackInteger stackIn;private StackInteger stackOut;public MyQueue() {stackIn new Stack();stackOut new Stack();}/*** push到输入栈** param x*/public void push(int x) {stackIn.push(x);}/*** 如果输出栈是空的就将输入栈的元素全都放到输出栈** return*/public int pop() {if (stackOut.isEmpty()) {while (!stackIn.isEmpty()) {stackOut.push(stackIn.pop());}}return stackOut.pop();}/*** 如果输出栈是空的就将输入栈的元素全都放到输出栈** return*/public int peek() {if (stackOut.isEmpty()) {while (!stackIn.isEmpty()) {stackOut.push(stackIn.pop());}}return stackOut.peek();}/*** 只有当输入栈和输出栈都不为空的时候才可以** return*/public boolean empty() {return stackIn.isEmpty() stackOut.isEmpty();}
}2.思路
两个栈可以实现队列的原理就是一个输入栈输入然后需要输出的时候就将输入栈中的元素放到输出栈中这样负负得正就是顺序的了
5.删除字符串中的所有相邻重复项
1.答案
package com.sunxiansheng.arithmetic.day10;import java.util.Stack;/*** Description: 1047. 删除字符串中的所有相邻重复项** Author sun* Create 2025/1/15 10:29* Version 1.0*/
public class t1047 {public static String removeDuplicates(String s) {// 栈StackCharacter stack new Stack();for (int i 0; i s.length(); i) {// 当前元素char c s.charAt(i);// 如果栈不为空并且匹配成功的才会出栈否则就是栈为空或者是栈不为空但是匹配失败的情况就入栈if (!stack.isEmpty() stack.peek() c) {stack.pop();} else {stack.push(c);}}// 将栈中的元素倒序char[] chars new char[stack.size()];for (int i chars.length - 1; i 0; i--) {chars[i] stack.pop();}return new String(chars);}
}2.思路
如果栈不为空并且匹配成功的才会出栈否则就是栈为空或者是栈不为空但是匹配失败的情况就入栈
