链表是否有环-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;
    }

表达式计算

条件：

1. 运算符只包含+-*/()
2. 数字只包含正整数
3. 表达式合法
4. 每步计算结果均在int范围内

提示：

1. 运算符有优先级
2. 同优先级从左至右和从右至左计算结果相同
3. 两个栈

步骤：
从左至右读取字符串，两个栈“数字栈”“运算符栈”

1. 遇到数字，入数栈
2. 遇到+-*/
   2.1 如果符栈空，入符栈
   2.2 如果符栈不空，优先级当前运算符 >= 符栈栈顶，入符栈
   2.3 如果符栈不空，优先级当前运算符 < 符栈栈顶，计算一次（数栈栈顶两个元素，符栈栈顶一个元素，计算结果入数栈），重复步骤2直到当前运算符入符栈
3. 遇到(，入符栈
4. 遇到)，重复计算，直到遇到(

    // 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;
    }

这种方式有精度丢失的问题。

括号匹配

描述：输入字符串只包括()[]{}，判断字符串是否括号匹配
思路：

1. 栈
2. 左括号，入栈
3. 右括号

• 栈空，false
• 栈非空，栈顶元素与当前元素匹配，继续
• 栈非空，栈顶元素与当前元素不匹配，false

4. 遍历结束，栈空，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
思路：这类题目都优先考虑栈，这个题的关键，在于找出匹配子串的起点和终点

1. 栈，用于存(的下标；start，表示当前最后一个非起点字符的下标
2. 左括号，入栈
3. 右括号

• 栈空，更新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;
    }