@Yano
2015-12-30T11:26:12.000000Z
字数 9527
阅读 7351
LeetCode
我的博客:http://blog.csdn.net/yano_nankai
LeetCode题解:https://github.com/LjyYano/LeetCode
LeetCode之Array题目汇总
LeetCode之Hash Table题目汇总
LeetCode之Linked List题目汇总
LeetCode之Math题目汇总
LeetCode之String题目汇总
LeetCode之Binary Search题目汇总
LeetCode之Divide and Conquer题目汇总
LeetCode之Dynamic Programming题目汇总
LeetCode之Backtracing题目汇总
LeetCode之Stack题目汇总
LeetCode之Sort题目汇总
LeetCode之Bit Manipulation题目汇总
LeetCode之Tree题目汇总
LeetCode之Depth-first Search题目汇总
LeetCode之Breadth-first Search题目汇总
LeetCode之Graph题目汇总
LeetCode之Trie题目汇总
LeetCode之Design题目汇总
文章目录:
Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open (
and closing parentheses )
, the plus +
or minus sign -
, non-negative integers and empty spaces .
You may assume that the given expression is always valid.
Some examples:
"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23
Note: Do not use the eval
built-in library function.
题目中只有+ - ( )。遍历字符串,对于每个字符c:
public int calculate(String s) {
if (s == null || s.length() == 0) {
return 0;
}
Stack<Integer> stack = new Stack<Integer>();
int sign = 1;// 符号位,1表示+,-1表示-
int rt = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
int val = c - '0';
// 将数字取出
while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
val = val * 10 + s.charAt(++i) - '0';
}
rt += sign * val;
} else if (c == '-') {
sign = -1;
} else if (c == '+') {
sign = 1;
} else if (c == '(') {
// 按照数字、符号的顺序,压入栈
stack.push(rt);
stack.push(sign);
rt = 0;
sign = 1;
} else if (c == ')') {
rt = rt * stack.pop() + stack.pop();
sign = 1;
}
}
return rt;
}
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +
, -
, *
, /
operators and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid.
Some examples:
"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5
Note: Do not use the eval
built-in library function.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.
分两次遍历,第一次遍历时,遇到乘除符号就计算;第二次遍历,计算加减符号。
public int calculate(String s) {
if (s == null || s.length() == 0) {
return 0;
}
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
int val = c - '0';
// 将数字取出
while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
val = val * 10 + s.charAt(++i) - '0';
}
// 栈顶是 * / 运算符,计算
if (!stack.isEmpty()
&& (stack.peek() == 2 || stack.peek() == 3)) {
int sign = stack.pop();
int op = stack.pop();
int rt = 0;
if (sign == 2) {
rt = op * val;
} else {
rt = op / val;
}
stack.push(rt);
} else {
stack.push(val);
}
} else if (c == ' ') {
continue;
} else {
switch (c) {
case '+':
stack.push(0);
break;
case '-':
stack.push(1);
break;
case '*':
stack.push(2);
break;
case '/':
stack.push(3);
break;
}
}
}
if (stack.isEmpty()) {
return 0;
}
// 因为要从左向右计算,所以要reverse
Collections.reverse(stack);
// 计算+-
int rt = stack.pop();
while (!stack.isEmpty()) {
int sign = stack.pop();
int op = stack.pop();
if (sign == 0) {
rt += op;
} else {
rt -= op;
}
}
return rt;
}
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +
, -
, *
, /
. Each operand may be an integer or another expression.
Some examples:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
这道题是给定了合法的逆波兰表达式,要求根据给定的逆波兰表达式,求出最终结果。
只需要定义一个stack,如果是+, -, *, /四个运算符,就取出栈顶的两个数,进行相应操作。之后将计算得到的结果压入栈中。如果是数字,就直接入栈。
最终stack只剩下一个元素,这个元素就是逆波兰表达式的值。
逆波兰表达式
逆波兰表达式又叫做后缀表达式。下面是一些例子:
正常的表达式 逆波兰表达式
a+b —> a,b,+
a+(b-c) —> a,b,c,-,+
a+(b-c)_d —> a,b,c,-,d,_,+
a+d*(b-c)—>a,d,b,c,-,*,+
a=1+3 —> a=1,3 +
优势
它的优势在于只用两种简单操作,入栈和出栈就可以搞定任何普通表达式的运算。其运算方式如下:
如果当前字符为变量或者为数字,则压栈,如果是运算符,则将栈顶两个元素弹出作相应运算,结果再入栈,最后当表达式扫描完后,栈里的就是结果。
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<Integer>();
for (String s : tokens) {
if ("*".equals(s)) {
int n2 = stack.pop();
int n1 = stack.pop();
stack.push(n1 * n2);
} else if ("/".equals(s)) {
int n2 = stack.pop();
int n1 = stack.pop();
stack.push(n1 / n2);
} else if ("+".equals(s)) {
int n2 = stack.pop();
int n1 = stack.pop();
stack.push(n1 + n2);
} else if ("-".equals(s)) {
int n2 = stack.pop();
int n1 = stack.pop();
stack.push(n1 - n2);
} else {
stack.push(Integer.valueOf(s));
}
}
return stack.pop();
}
Implement the following operations of a queue using stacks.
Notes:
push to top
, peek/pop from top
, size
, and is empty
operations are valid.非常经典的题目,定义两个栈模拟队列。
class MyQueue {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
// Push element x to the back of queue.
public void push(int x) {
stack1.push(x);
}
// Removes the element from in front of queue.
public void pop() {
if (stack2.isEmpty()) {
if (stack1.isEmpty()) {
throw new IllegalStateException();
}
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
stack2.pop();
}
// Get the front element.
public int peek() {
if (stack2.isEmpty()) {
if (stack1.isEmpty()) {
throw new IllegalStateException();
}
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.peek();
}
// Return whether the queue is empty.
public boolean empty() {
if (stack1.isEmpty() && stack2.isEmpty()) {
return true;
}
return false;
}
}
Implement the following operations of a stack using queues.
Notes:
push to back
, peek/pop from front
, size
, and is empty
operations are valid.Update (2015-06-11):
The class name of the Java function had been updated to MyStack instead of Stack.
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and all test cases.
非常经典的题目,定义两个队列模拟栈的操作。总保持一个队列为空:
class MyStack {
Queue<Integer> q1 = new LinkedList<Integer>();
Queue<Integer> q2 = new LinkedList<Integer>();
// Push element x onto stack.
public void push(int x) {
if (q1.isEmpty() && q2.isEmpty()) {
q1.add(x);
} else if (!q1.isEmpty()) {
q1.add(x);
} else {
q2.add(x);
}
}
// Removes the element on top of the stack.
public void pop() {
if (empty()) {
throw new IllegalStateException();
}
// q1、q2必有一个为空
if (q2.isEmpty()) {
while (!q1.isEmpty()) {
int x = q1.remove();
if (!q1.isEmpty()) {
q2.add(x);
}
}
} else if (q1.isEmpty()) {
while (!q2.isEmpty()) {
int x = q2.remove();
if (!q2.isEmpty()) {
q1.add(x);
}
}
}
}
// Get the top element.
public int top() {
if (empty()) {
throw new IllegalStateException();
}
int x = 0;
// q1、q2必有一个为空
if (q2.isEmpty()) {
while (!q1.isEmpty()) {
x = q1.remove();
q2.add(x);
}
} else if (q1.isEmpty()) {
while (!q2.isEmpty()) {
x = q2.remove();
q1.add(x);
}
}
return x;
}
// Return whether the stack is empty.
public boolean empty() {
if (q1.isEmpty() && q2.isEmpty()) {
return true;
}
return false;
}
}
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
本题是一个栈的操作,但是要求getMin()在O(1)的时间复杂度。
考虑使用另一个辅助栈,用来存储[0..i]的最小值。
class MinStack {
Stack<Integer> stack = new Stack<Integer>();
Stack<Integer> min = new Stack<Integer>();
public void push(int x) {
if (stack.isEmpty()) {
stack.push(x);
min.push(x);
} else {
stack.push(x);
min.push(Math.min(stack.peek(), min.peek()));
}
}
public void pop() {
if (!stack.isEmpty()) {
stack.pop();
min.pop();
}
}
public int top() {
if (!stack.isEmpty()) {
return stack.peek();
}
throw new IllegalStateException();
}
public int getMin() {
if (!min.isEmpty()) {
return min.peek();
}
throw new IllegalStateException();
}
}
Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/"
, => "/home"
path = "/a/./b/../../c/"
, => "/c"
Corner Cases:
"/../"
? "/"
.'/'
together, such as "/home//foo/"
. "/home/foo"
.
public String simplifyPath(String path) {
if (path == null) {
return null;
}
String[] names = path.split("/");
int eat = 0;
LinkedList<String> stack = new LinkedList<String>();
for (int i = names.length - 1; i >= 0; i--) {
String token = names[i];
// token是"..", 表示上级路径,前一个路径不打印
// token是".", 表示当前路径,自身不打印
// token是"", 表示为两个"/"相连,不做操作
// eat>0,表示左边不打印
// 否则,将token入栈
if (token.equals("..")) {
eat++;
} else if (token.equals(".")) {
// do nothing
} else if (token.equals("")) {
// do nothing
} else {
if (eat > 0) {
eat--;
} else {
stack.push(token);
}
}
}
StringBuilder s = new StringBuilder();
s.append("/");
// 最后一个不加"/",所以while判断条件是>1
while (stack.size() > 1) {
s.append(stack.pop());
s.append("/");
}
// 最后一个不加"/"
if (!stack.isEmpty()) {
s.append(stack.pop());
}
return s.toString();
}
Given a string containing just the characters '('
, ')'
, '{'
, '}'
, '['
and ']'
, determine if the input string is valid.
The brackets must close in the correct order, "()"
and "()[]{}"
are all valid but "(]"
and "([)]"
are not.
public boolean isValid(String s) {
if (s == null || s.length() % 2 == 1) {
return false;
}
HashMap<Character, Character> map = new HashMap<Character, Character>();
map.put('(', ')');
map.put('[', ']');
map.put('{', '}');
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (map.keySet().contains(c)) {
stack.push(c);
} else if (map.values().contains(c)) {
if (!stack.empty() && map.get(stack.peek()) == c) {
stack.pop();
} else {
return false;
}
}
}
return stack.empty();
}