394. Decode String
class Solution {
public String decodeString(String s) {
String ans = "";
Stack<Integer> countStack = new Stack<>();
Stack<String> ansStack = new Stack<>();
for (int i = 0; i < s.length(); i++){
char c = s.charAt(i);
if (Character.isDigit(c)){
int sum = c - '0';
while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))){
sum = sum * 10 + (s.charAt(i + 1) - '0');
i++;
}
countStack.push(sum);
}
else if (c == '['){
ansStack.push(ans);
ans = "";
}
else if (c == ']'){
StringBuilder temp = new StringBuilder(ansStack.pop());
int repeated = countStack.pop();
for (int j = 0; j < repeated; j++){
temp.append(ans);
}
ans = temp.toString();
}
else{
ans += c;
}
System.out.println("i: " + i + " ans: " + ans);
}
return ans;
}
}
224. Basic Calculator
public class Solution {
public int calculate(String s) {
if (s == null || s.length() == 0) return 0;
s = s.trim().replaceAll("\\s", "");
Stack<Integer> stack = new Stack<>();
int sign = 1, ans = 0, n = s.length(), pre = 0;
for (int i = 0; i < n; i++){
if (s.charAt(i) - '0' >= 0 && s.charAt(i) - '0' <= 9){
int cur = s.charAt(i) - '0';
while (i + 1 < n && s.charAt(i + 1) - '0' >= 0 && s.charAt(i + 1) - '0' <= 9){
cur = cur * 10 + s.charAt(i + 1) - '0';
i++;
}
ans += cur * sign;
}
else if (s.charAt(i) == '+'){
sign = 1;
}
else if (s.charAt(i) == '-'){
sign = -1;
}
else if (s.charAt(i) == '('){
stack.push(ans);
stack.push(sign);
ans = 0;
sign = 1;
}
else if (s.charAt(i) == ')'){
ans = ans * stack.pop() + stack.pop();
}
}
return ans;
}
}
Basic Calculator II
no stack, but similar thoughts
public class Solution {
public int calculate(String s) {
if (s == null || s.length() == 0) return 0;
s = s.trim().replaceAll("\\s", "");
int preVal = 0, ans = 0, n = s.length(), i = 0;
char sign = '+';
while (i < n){
int curVal = 0;
while (i < n && s.charAt(i) - '0' >= 0 && s.charAt(i) - '0' <= 9){
curVal = curVal * 10 + s.charAt(i) - '0';
i++;
}
if (sign == '+'){
ans += preVal;
preVal = curVal;
}
if (sign == '-'){
ans += preVal;
preVal = -curVal;
}
if (sign == '*'){
preVal = preVal * curVal;
}
if (sign == '/'){
preVal = preVal / curVal;
}
if (i < n){
sign = s.charAt(i);
i++;
}
}
ans += preVal;
return ans;
}
}
682 Baseball Game
class Solution {
public int calPoints(String[] ops) {
if (ops == null || ops.length == 0) return 0;
Stack<Integer> stack = new Stack<>();
int ans = 0;
for (int i = 0; i < ops.length; i++){
String cur = ops[i];
if (cur.equals("C")){
int val = stack.pop();
ans -= val;
}
else if (cur.equals("D")){
int val = stack.peek();
ans += val * 2;
stack.push(val * 2);
}
else if (cur.equals("+")){
int num2 = stack.pop();
int num1 = stack.pop();
int num3 = num1 + num2;
ans += num3;
stack.push(num1);
stack.push(num2);
stack.push(num3);
}
else{
int val = Integer.parseInt(cur);
ans += val;
stack.push(val);
}
}
return ans;
}
}
726 Number of Atoms
class Solution {
public String countOfAtoms(String formula) {
Stack<Map<String, Integer>> stack = new Stack<>();
int n = formula.length();
stack.add(new TreeMap<>());
for (int i = 0; i < n;){
if (formula.charAt(i) == '('){
stack.add(new TreeMap<>());
i++;
}
else if (formula.charAt(i) == ')'){
Map<String, Integer> top = stack.pop();
int iStart = ++i, multi = 1;
while (i < n && Character.isDigit(formula.charAt(i))) i++;
if (i > iStart) multi = Integer.parseInt(formula.substring(iStart, i));
for (String name : top.keySet()){
int v = top.get(name);
stack.peek().put(name, stack.peek().getOrDefault(name, 0) + v * multi);
}
}
else{
int iStart = i++;
while (i < n && Character.isLowerCase(formula.charAt(i))) i++;
String name = formula.substring(iStart, i);
iStart = i;
while (i < n && Character.isDigit(formula.charAt(i))) i++;
int multi = i > iStart ? Integer.parseInt(formula.substring(iStart, i)) : 1;
stack.peek().put(name, stack.peek().getOrDefault(name, 0) + multi);
}
}
StringBuilder ans = new StringBuilder();
for (String name : stack.peek().keySet()){
int multi = stack.peek().get(name);
ans.append(name);
if (multi > 1) ans.append("" + multi);
}
return new String(ans);
}
}
503 Next Greater Element II
class Solution {
public int[] nextGreaterElements(int[] nums) {
Stack<Integer> stack = new Stack<>();
for (int i = nums.length - 1; i >= 0; i--){
stack.push(nums[i]);
}
int[] ans = new int[nums.length];
for (int i = nums.length - 1; i >= 0; i--){
ans[i] = -1;
while (!stack.isEmpty() && stack.peek() <= nums[i]){
stack.pop();
}
if (!stack.isEmpty()){
ans[i] = stack.peek();
}
stack.push(nums[i]);
}
return ans;
}
}
402 Remove K Digits
class Solution {
public String removeKdigits(String num, int k) {
if (k == num.length()) return "0";
Stack<Character> stack = new Stack<>();
// if later digit is smaller than previous digit, just discard previous digit, until k = 0
int index = 0;
while (index < num.length()){
while (k > 0 && !stack.isEmpty() && stack.peek() > num.charAt(index)){
stack.pop();
k--;
}
stack.push(num.charAt(index));
index++;
}
// "1111"
while (k > 0){
stack.pop();
k--;
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()){
sb.append(stack.pop());
}
sb.reverse();
while (sb.length() > 1 && sb.charAt(0) == '0') sb.deleteCharAt(0);
return sb.toString();
}
}