链表是否有环-done
表达式计算-done
括号匹配-done
最长有效括号长度
链表是否有环
提示：快慢指针
private boolean hasRoll(Node node) {
boolean hasRoll = false;
if (node == null || node.next == null) {
return hasRoll;
}
Node fast = node;
Node slow = node;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
hasRoll = true;
break;
}
}
return hasRoll;
}
表达式计算
条件：
- 运算符只包含+-*/()
- 数字只包含正整数
- 表达式合法
- 每步计算结果均在int范围内
提示：
- 运算符有优先级
- 同优先级从左至右和从右至左计算结果相同
- 两个栈
步骤：
从左至右读取字符串，两个栈“数字栈”“运算符栈”
- 遇到数字，入数栈
- 遇到+-*/
2.1 如果符栈空，入符栈
2.2 如果符栈不空，优先级当前运算符 >= 符栈栈顶，入符栈
2.3 如果符栈不空，优先级当前运算符 < 符栈栈顶，计算一次（数栈栈顶两个元素，符栈栈顶一个元素，计算结果入数栈），重复步骤2直到当前运算符入符栈 - 遇到(，入符栈
- 遇到)，重复计算，直到遇到(
// string表达式计算
private static Integer cal(String str) {
Stack<Integer> numStack = new Stack<Integer>();
Stack<Character> opeStack = new Stack<Character>();
int num = 0; // 待入库数
// n1 ope n2
int n1;
int n2;
char ope;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
// 1+23
if (c >= '0' && c <= '9') {
// 数字入栈
do {
num = num * 10 + (c - '0');
i++;
if (i == str.length()) {
break;
}
c = str.charAt(i);
}while (c >= '0' && c <= '9');
i--;
numStack.push(num);
num = 0;
}else if ('(' == c) {
opeStack.push(c);
} else if (')' == c) {
while ('(' != (ope = opeStack.pop())) {
n2 = numStack.pop();
n1 = numStack.pop();
numStack.push(opeNum(n1, ope, n2));
}
}else if (opeStack.empty() || getP(c) >= getP(opeStack.peek())) {
opeStack.push(c);
}else if (getP(c) < getP(opeStack.peek())) {
while(!opeStack.isEmpty() && '(' != opeStack.peek() && getP(c) < getP(opeStack.peek())) {
n2 = numStack.pop();
n1 = numStack.pop();
ope = opeStack.pop();
numStack.push(opeNum(n1, ope, n2));
}
opeStack.push(c);
}
}
// 最后有下面两个可能
// "运算符栈为空"
// "两个栈都不空，运算符栈里的符号优先级相同"
int res = 0;
while (!opeStack.isEmpty()) {
ope = opeStack.pop();
n2 = numStack.pop();
n1 = numStack.pop();
numStack.push(opeNum(n1, ope, n2));
}
res = numStack.peek();
return res;
}
// 转换成数字，用于判断运算符优先级
private static int getP(char c) {
int res = 0;
switch (c) {
case '+' :
case '-' :
res = 1;
break;
case '*' :
case '/' :
res = 2;
break;
}
return res;
}
// 计算n1 ope n2
private static Integer opeNum(int n1, char ope, int n2) {
Integer res = null;
switch (ope) {
case '+' :
res = n1 + n2;
break;
case '-' :
res = n1 - n2;
break;
case '*' :
res = n1 * n2;
break;
case '/' :
res = n1 / n2;
break;
}
return res;
}
这种方式有精度丢失的问题。
括号匹配
描述：输入字符串只包括()[]{}，判断字符串是否括号匹配
思路：
- 栈
- 左括号，入栈
- 右括号
- 栈空，false
- 栈非空，栈顶元素与当前元素匹配，继续
- 栈非空，栈顶元素与当前元素不匹配，false
- 遍历结束，栈空，true；栈非空，false
private static boolean barMapping(String str) {
if (str == null || str.length() <= 1) {
return false;
}
Stack<Character> stack = new Stack<Character>();
String left = "([{";
String right = ")]}";
for (int i = 0; i < str.length(); i++) {
if (left.contains(str.charAt(i)+"")) {
stack.push(str.charAt(i));
}else if (right.contains(str.charAt(i)+"")) {
if (stack.empty()) {
return false;
}else if (left.indexOf(stack.pop()) != right.indexOf(str.charAt(i))) {
return false;
}
}
}
return stack.empty();
}
最长有效括号长度
描述：给定字符串只包含()，找出最长有效括号的长度，例如")()())"输出4
思路：这类题目都优先考虑栈，这个题的关键，在于找出匹配子串的起点和终点
- 栈，用于存(的下标；start，表示当前最后一个非起点字符的下标
- 左括号，入栈
- 右括号
- 栈空，更新start
- 栈非空，弹出栈顶元素，观察栈
-- 栈空，用当前匹配更新max，即i-start更新max
-- 栈非空，用当前匹配更新max，即i-栈顶元素值，更新max
private static int longestBarMapping(String str) {
int max = 0;
if (str == null || str.length() <= 1) {
return max;
}
int start = -1;
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < str.length(); i++) {
if ('(' == str.charAt(i)) { // 左括号
stack.push(i);
}else if (stack.empty()) { // 右括号 & 栈空
start = i;
}else { // 右括号 & 栈非空
stack.pop();
if (stack.empty()) {
max = Math.max(max, i-start);
}else {
max = Math.max(max, i-stack.peek());
}
}
}
return max;
}
