Java日记2018-06-02

29. 顺时针打印矩阵
    判断比较多，是否能考虑所有边界？

public static ArrayList<Integer> printmatrix(int[][] mat) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        int r = 0;
        int row = mat.length - 1;
        int c = 0;
        int col = mat[0].length - 1;
        while (r <= row && c <= col) {
            for (int i = c; i <= col; i++) {
                System.out.print(mat[r][i] + " ");
                res.add(mat[r][i]);
            }
            for (int i = r + 1; i <= row; i++) {
                System.out.print(mat[i][col] + " ");
                res.add(mat[i][col]);
            }
            //注意这个判断，防止往下打印
            if (r != row) {
                for (int i = col - 1; i >= c; i--) {
                    System.out.print(mat[row][i] + " ");
                    res.add(mat[row][i]);
                }
            }
            //注意这个判断，防止往下打印
            if (c != col) {
                for (int i = row - 1; i > r; i--) {
                    System.out.print(mat[i][c] + " ");
                    res.add(mat[i][c]);
                }
            }
            r++;
            c++;
            row--;
            col--;
        }
        return res;
    }

30. 包含 min 函数的栈
    熟悉stack的用法

//包含 min 函数的栈
    private static Stack<Integer> stack = new Stack<Integer>();
    private static Stack<Integer> minstack = new Stack<Integer>();
    public static void push(int node) {
        stack.push(node);
        minstack.push(minstack.isEmpty()? node:Math.min(node, minstack.peek()));
    
    }
    public static int min(){
        return minstack.peek();
    }

31. 栈的压入、弹出序列
    【思路】借用一个辅助的栈，遍历压栈顺序，先讲第一个放入栈中，这里是1，然后判断栈顶元素是不是出栈顺序的第一个元素，这里是4，很显然1≠4，所以我们继续压栈，直到相等以后开始出栈，出栈一个元素，则将出栈顺序向后移动一位，直到不相等，这样循环等压栈顺序遍历完成，如果辅助栈还不为空，说明弹出序列不是该栈的弹出顺序。

举例：

入栈1,2,3,4,5

出栈4,5,3,2,1

首先1入辅助栈，此时栈顶1≠4，继续入栈2

此时栈顶2≠4，继续入栈3

此时栈顶3≠4，继续入栈4

此时栈顶4＝4，出栈4，弹出序列向后一位，此时为5，,辅助栈里面是1,2,3

此时栈顶3≠5，继续入栈5

此时栈顶5=5，出栈5,弹出序列向后一位，此时为3，,辅助栈里面是1,2,3

….

依次执行，最后辅助栈为空。如果不为空说明弹出序列不是该栈的弹出顺序。

在实现时候要补充一个popindex 索引当标志位，为两个循环指引

public static boolean IsPopOrder(int[] popa, int[] popb) {
        Stack<Integer> st = new Stack<Integer>();
        int popindex = 0;
        for (int i = 0; i < popa.length; i++) {
            st.push(popa[i]);
            while (popindex < popb.length && st.peek() == popb[popindex]) {
                st.pop();
                popindex++;
                
            }
        }
        return st.isEmpty();
    }