class Solution {
public String simplifyPath(String path) {
String[] paths = path.split("/");
Deque<String> deque = new LinkedList<>();
for (String p:paths) {
if (p == null || ".".equals(p) || "".equals(p)) continue;
if ("..".equals(p)) {
if (!deque.isEmpty()) {
deque.pollLast();
}
} else {
deque.offerLast(p);
}
}
if (deque.isEmpty()) {
return "/";
}
StringBuilder stringBuilder = new StringBuilder();
while (!deque.isEmpty()) {
stringBuilder.append("/");
stringBuilder.append(deque.pollFirst());
}
return stringBuilder.toString();
}
}
class MinStack {
private Stack<Integer> stack;
private Stack<Integer> min;
public MinStack() {
stack = new Stack<>();
min = new Stack<>();
}
public void push(int val) {
if (min.isEmpty()) {
min.push(val);
} else {
if (val <= min.peek()) {
min.push(val);
}
}
stack.push(val);
}
public void pop() {
int val = stack.pop();
if (val == min.peek()) {
min.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return min.isEmpty() ? 0 : min.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
class MinStack {
public class ListNode {
int val;
int minVal;
ListNode next;
public ListNode(int val, int minVal, ListNode next) {
this.val = val;
this.minVal = minVal;
this.next = next;
}
}
private ListNode head;
public MinStack() {
}
public void push(int val) {
if (head == null) {
head = new ListNode(val, val, null);
} else {
head = new ListNode(val, Math.min(val, head.minVal), head);
}
}
public void pop() {
if (head != null) {
head = head.next;
}
}
public int top() {
if (head != null) {
return head.val;
}
return -1;
}
public int getMin() {
if (head != null) return head.minVal;
return -1;
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
int j = 0;
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < pushed.length; i++) {
stack.push(pushed[i]);
while (!stack.isEmpty() && stack.peek() == popped[j]) {
stack.pop();
j++;
}
}
return stack.isEmpty();
}
}
class Solution {
public int calculate(String s) {
if (s == null || s.length() == 0) return -1;
int len = s.length();
int result = 0;
int sign = 1;
Stack<Integer> stack = new Stack<>();
stack.push(sign);
int i = 0;
while (i < len) {
char c = s.charAt(i);
if (' ' == c) {
i++;
} else if ('+' == c) {
sign = stack.peek();
i++;
} else if ('-' == c) {
sign = -stack.peek();
i++;
} else if ('(' == c) {
stack.push(sign);
i++;
} else if (')' == c) {
stack.pop();
i++;
} else {
long num = 0;
while (i < len && Character.isDigit(s.charAt(i))) {
num = num * 10 + (s.charAt(i) - '0');
i++;
}
result += sign * num;
}
}
return result;
}
}
class Solution {
public int calculate(String s) {
int num = 0;
if (s == null || s.length() == 0) return -1;
char preSign = '+';
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
//是数字
if (c != ' ' && Character.isDigit(c)) {
num = num * 10 + (c - '0');
}
//不是数字 或者是最后一个
if ((c != ' ' && !Character.isDigit(c)) || (i == s.length() - 1)) {
if (preSign == '+') {
stack.push(num);
} else if (preSign == '-') {
stack.push(-num);
} else if (preSign == '*') {
stack.push(stack.pop() * num);
} else if (preSign == '/') {
stack.push(stack.pop() / num);
}
preSign = c;
num = 0;
}
}
int result = 0;
while (!stack.isEmpty()) {
result += stack.pop();
}
return result;
}
}
class Solution {
public int longestValidParentheses(String s) {
if (s == null || s.length() == 0) return 0;
Stack<Integer> stack = new Stack<>();
stack.push(-1);
int result = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.isEmpty()) {
stack.push(i);
} else {
result = Math.max(result, i - stack.peek());
}
}
}
return result;
}
}
class Solution {
int i = 0;
int n = 0;
public String countOfAtoms(String formula) {
if (formula == null || formula.length() == 0) return "";
n = formula.length();
Stack<HashMap<String, Integer>> stack = new Stack<>();
stack.push(new HashMap<>());
while (i < n) {
char c = formula.charAt(i);
if (c == '(') {
i++;
stack.push(new HashMap<String, Integer>());
} else if (c == ')') {
i++;
int v = parseNum(formula);
HashMap<String, Integer> popMap = stack.pop();
HashMap<String, Integer> topMap = stack.peek();
for (Map.Entry<String, Integer> entry:popMap.entrySet()) {
String atom = entry.getKey();
int num = entry.getValue();
topMap.put(atom, topMap.getOrDefault(atom, 0) + v * num);
}
} else {
String atom = parseAtom(formula);
int num = parseNum(formula);
Map<String, Integer> topMap = stack.peek();
topMap.put(atom, topMap.getOrDefault(atom, 0) + num);
}
}
TreeMap<String, Integer> treeMap = new TreeMap<>(stack.pop());
StringBuilder result = new StringBuilder();
for (Map.Entry<String, Integer> entry:treeMap.entrySet()) {
String atom = entry.getKey();
int num = entry.getValue();
result.append(atom);
if (num > 1) {
result.append(num);
}
}
return result.toString();
}
private int parseNum(String formula) {
//没有了 或者不是数字
if (i == n || !Character.isDigit(formula.charAt(i))) {
return 1;
}
int num = 0;
while (i < n && Character.isDigit(formula.charAt(i))) {
num = num * 10 + (formula.charAt(i++) - '0');
}
return num;
}
private String parseAtom(String formula) {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append(formula.charAt(i++));
while (i < n && Character.isLowerCase(formula.charAt(i))) {
stringBuilder.append(formula.charAt(i++));
}
return stringBuilder.toString();
}
}
class Solution {
public String removeKdigits(String num, int k) {
int length = num.length();
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < length; i++) {
int val = num.charAt(i) - '0';
while (!deque.isEmpty() && k > 0 && deque.peekLast() > val) {
deque.pollLast();
k--;
}
deque.offerLast(val);
}
while (k > 0 && !deque.isEmpty()) {
deque.pollLast();
k--;
}
StringBuilder result = new StringBuilder();
boolean isFirst = true;
while (!deque.isEmpty()) {
int val = deque.pollFirst();
if (isFirst && val == 0) continue;
isFirst = false;
result.append(val);
}
return result.length() == 0 ? "0" : result.toString();
}
}
class Solution {
public boolean checkValidString(String s) {
if (s == null) return true;
Stack<Integer> leftStack = new Stack<>();
Stack<Integer> starStack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
leftStack.push(i);
} else if (c == '*') {
starStack.push(i);
} else {
if (!leftStack.isEmpty()) {
leftStack.pop();
} else if (!starStack.isEmpty()) {
starStack.pop();
} else return false;
}
}
while (!leftStack.isEmpty() && !starStack.isEmpty()) {
int left = leftStack.pop();
int star = starStack.pop();
if (left > star) return false;
}
return leftStack.isEmpty();
}
}
class Solution {
public String decodeString(String s) {
if (s == null) return null;
int len = s.length();
int i = 0;
Deque<Integer> digitDeque = new LinkedList<>();
Deque<String> letterDeque = new LinkedList<>();
while (i < len) {
char c = s.charAt(i);
//是数字
if (Character.isDigit(c)) {
int num = 0;
while (i < len && Character.isDigit(s.charAt(i))) {
num = num * 10 + (s.charAt(i) - '0');
i++;
}
digitDeque.offerLast(num);
System.out.println(num);
} else {
//是字母或者括号
if (c == ']') {
//弹出数字栈
int num = digitDeque.pollLast();
String letter = "";
while(!letterDeque.isEmpty() && !"[".equals(letterDeque.peekLast())) {
letter = letterDeque.pollLast() + letter;
}
//弹出最后一个[括号
letterDeque.pollLast();
StringBuilder letterBuilder = new StringBuilder();
while (num-- > 0) {
letterBuilder.append(letter);
}
//入栈
letterDeque.offerLast(letterBuilder.toString());
i++;
} else {
letterDeque.offerLast(new String(new char[]{c}));
i++;
}
}
}
//字母
StringBuilder result = new StringBuilder();
while (!letterDeque.isEmpty()) {
result.append(letterDeque.pollFirst());
}
return result.toString();
}
}
网友评论