栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下 *** 作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。
/**
* @className SortedStack
* @Author sofia
* @Date 2022/3/14
* @Describe https://leetcode-cn.com/problems/sort-of-stacks-lcci/
**/
public class SortedStack {
/*栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，
但不得将元素复制到别的数据结构（如数组）中。该栈支持如下 *** 作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。*/
private Stack<Integer> A , B;
public SortedStack() {
A = new Stack<>();
B = new Stack<>();
}
public void push(int val) {
//如果栈为空，直接入栈
if(A.isEmpty()) A.push(val);
else {
//将A中小于val的值放入B,val入栈，再将B中元素依次入A
while (val>A.peek()){
B.push(A.pop());
}
A.push(val);
if (!B.isEmpty()){
A.push(B.pop());
}
}
}
public void pop() {
if (A.isEmpty()){
return;
}
A.pop();
}
public int peek() {
if (A.isEmpty()){
return -1;
}
return A.peek();
}
public boolean isEmpty() {
return A.isEmpty();
}
}
给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 ‘/’ 开头），请你将其转化为更加简洁的规范路径。
/**
* @className SimplifyPath
* @Author sofia
* @Date 2022/3/15
* @Describe https://leetcode-cn.com/problems/simplify-path/
**/
public class SimplifyPath {
public static String simplifyPath(String path) {
//将path分割返回字符串数组
String[] strs = path.split("/");
Deque<String> deque = new ArrayDeque<>();
for (String str :strs){
if ("..".equals(str)){
deque.pollLast();
}else if (str.length()>0 && !".".equals(str)){
deque.offerLast(str);
}
}
StringBuilder builder = new StringBuilder();
if (deque.isEmpty()){
builder.append("/");
}else {
while (!deque.isEmpty()){
builder.append("/");
builder.append(deque.pollFirst());
}
}
return builder.toString();
}
}
https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
/**
* @className evalRPN
* @Author sofia
* @Date 2022/3/16
* @Describe https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
**/
public class evalRPN {
public static int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (int i=0;i<tokens.length;i++){
if (isNumber(tokens[i])){
stack.push(Integer.valueOf(tokens[i]));
}else {
Integer num1 = Integer.valueOf(stack.pop());
Integer num2 = Integer.valueOf(stack.pop());
if ("+".equals(tokens[i])){
stack.push(num2+num1);
}else if ("*".equals(tokens[i])){
stack.push(num2*num1);
}else if ("/".equals(tokens[i])){
stack.push(num2/num1);
}else if ("-".equals(tokens[i])){
stack.push(num2-num1);
}
}
}
return stack.pop();
}
public static boolean isNumber(String numStr){
return !("+".equals(numStr) || "-".equals(numStr) || "*".equals(numStr) || "/".equals(numStr));
}
public static void main(String[] args) {
String[] tokens = {"4","3","-"};
System.out.println(evalRPN(tokens));
}
}
给出由小写字母组成的字符串 S，重复项删除 *** 作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除 *** 作，直到无法继续删除。在完成所有重复项删除 *** 作后返回最终的字符串。答案保证唯一。
/**
* @className removeDuplicate
* @Author sofia
* @Date 2022/3/17
* @Describe https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string/
**/
public class removeDuplicate {
public static String removeDuplicates(String s) {
Deque deque = new LinkedList(); //双边队列
char[] charArray = s.toCharArray();
for (int i=0;i<charArray.length;i++){
if (!deque.isEmpty() && deque.getLast().equals(charArray[i])){
deque.pollLast();
}else if (deque.isEmpty() || !deque.getLast().equals(charArray[i])){
deque.offer(charArray[i]);
}
}
StringBuilder stringBuilder = new StringBuilder();
while (!deque.isEmpty()){
stringBuilder.append(deque.pollFirst());
}
return stringBuilder.toString();
}
public static void main(String[] args) {
String s="abbbabaaa";
System.out.println(removeDuplicates(s));
}
}
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
/**
* @className calculate
* @Author sofia
* @Date 2022/3/18
* @Describe https://leetcode-cn.com/problems/basic-calculator/
**/
public class calculate {
public int calculate(String s){
int i = 0;
int result = 0;
Deque<Integer> queue = new LinkedList<>();
int symbol = 1; //用来标记正负号
queue.push(symbol); //左括号进栈，右括号出栈
while (i<s.length()){
if (s.charAt(i)==' '){
i++;
}else if (s.charAt(i)=='+'){
symbol = queue.peek();
i++;
}else if (s.charAt(i)=='-'){
symbol = -queue.peek();
i++;
}else if (s.charAt(i)=='('){
queue.push(symbol);
i++;
}else if (s.charAt(i)==')'){
queue.pop();
i++;
}else {
long count = 0l;
while (i<s.length()&&Character.isDigit(s.charAt(i))){
count = count * 10 + s.charAt(i)-'0';
i++;
}
result += symbol*count;
}
}
return result;
}
}
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种 *** 作（push、top、pop 和 empty）。
**
* @className MyStack
* @Author sofia
* @Date 2022/3/19
* @Describe https://leetcode-cn.com/problems/implement-stack-using-queues/
**/
public class MyStack {
Queue<Integer> A;
public MyStack() {
A = new LinkedList<>();
}
//每次入队时把除当前队列的所有元素先出队再入队
public void push(int x) {
A.offer(x);
for (int i=0;i<A.size()-1;i++){
A.offer(A.poll());
}
}
public int pop() {
return A.poll();
}
public int top() {
return A.peek();
}
public boolean empty() {
return A.isEmpty();
}
}
给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和d出 pop *** 作序列的结果时，返回 true；否则，返回 false 。
https://leetcode-cn.com/problems/validate-stack-sequences/
public boolean validateStackSequences(int[] pushed, int[] popped) {
int N = pushed.length;
Stack<Integer> stack = new Stack();
int j = 0;
for (int x: pushed) {
stack.push(x);
while (!stack.isEmpty() && j < N && stack.peek() == popped[j]) {
stack.pop();
j++;
}
}
return j == N;
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）