算法编程（三）

一、请使用栈，设计一个数据结构，它具有栈的“先进后出”的特性，同时还可以获取栈中的最小值，要求此数据结构的pop、push、min方法的复杂度均为O(1)

    这个题，最大的问题就在min方法上，如果不使用其他的辅助数据结构，是无法满足min方法的设计要求，即使使用一个临时变量保存当前的最小值（这种情况下，如果最小是被pop，就断片了。。）。所以我们的注意力就集中在：怎们能让一个栈是有序的？其实让栈内数据有序，使用排序的思路肯定是不行的，但是我们能够维持“最小值”的连续性就可以。看看如下的设计思路：

使用2个栈来设计这个数据结构，分别为数据栈和辅助栈
数据栈用来保存push的数据
辅助栈用来保存“最小值”的连续性：

栈底<--------->栈顶
1）添加3
数据栈：3
辅助栈：3，3为最小值
2）添加4
数据栈： 3 4
辅助栈： 3 3
因为4 > 3，为了保持“最小值”连续性，我们在4对应的辅助栈的位置上仍然添加3。
3）添加2
数据栈： 3 4 2
辅助栈： 3 3 2
因为3 > 2，最小值变了，所以讲新的最小值入栈。

如上所述，那么min方法，只需要从辅助栈中peek栈顶的元素值就行了。
当数据栈中pop元素时，也将辅助栈中对应位置的元素移除。

 

    代码样例如下：

static class MinStack {
    Stack<Integer> data = new Stack<>();
    Stack<Integer> helper = new Stack<>();

    synchronized void push(Integer value) {
        data.push(value);
        int min = value;
        if(!helper.isEmpty()) {
            int current = helper.peek();
            if(current <= value) {
                min = current;
            }
        }
        helper.push(min);
    }

    Integer min() {
        if(helper.isEmpty()) {
            return null;
        }
        return helper.peek();
    }

    synchronized void pop() {
        if(data.isEmpty()) {
            return;
        }
        data.pop();
        helper.pop();
    }
}

    

二、请编写一个算法用于判定：序列B为序列A作为栈时可能的弹出顺序（A中的数字不会重复）

    听到题目，第一感觉就是：听不懂！

    先描述一下：假如有序列A为[1,2,3,4,5]，它作为栈时由1开始依次入栈，序列B为[5,4,3,2,1]是A作为栈时的一个弹出顺序。但是序列A在没有完全入栈时也可以弹出，比如[1,2,3,4]先入栈，然后弹出4，然后再将5入栈，那么其弹出序列就是[4,5,3,2,1]。因为A入栈和出栈的时机可以任意，所以它的出栈序列可能会有多种，请你判定一个给定的序列是否为A的一个出栈顺序。

    实话说，看到这个题，我也没有思路...如下为分析过程，突破口就是要用一个辅助栈来保存A。

将A保存在数据栈，B使用一个辅助栈
A：1 2 3 4 5
B：4 5 3 2 1 （假设序列）

1）
遍历A和B，以B作为判断基准
2）
在B中第一个元素为4，因为A中1、2、3均不等于4，直到遇到4
则将它们都添加到数据栈
数据栈： 1 2 3 
3）此时A与B都遇到4，我们认为是一次弹出（或者同时入栈，然后弹出）
4）B继续遍历，此时为5
判断，5是否与数据栈的栈顶一样，如果不一样，则遍历A的下一个元素。
5）此时A与B都遇到5，我们认为是一次弹出。
6）A序列遍历结束，只能根据数据栈作为判定。
7）B继续遍历，此时为3，从数据栈中弹出栈顶，比较是否也为3，如果是继续
8）重复7，直到不相等（返回false）或者数据栈全部弹出（返回true）。

 

    解题思路总结：从B中确定弹出元素，比如a，如果辅助栈的栈顶刚还是a，则弹出，否则遍历A序列找到a，在a之前的元素全部添加到辅助栈中；如果所有的元素都查找完仍没有找到a，则认为判读失败。

 

    代码样例：

public static void main(String[] args) {
    int[] source = {1,2,3,4,5};
    int[] target = {3,5,4,2,1};
    System.out.println(check(source,target));
}

public static boolean check(int[] source,int[] target) {
    if(source.length == 0 || target.length == 0) {
        return false;
    }
    if(source.length != target.length) {
        return false;
    }
    int length = source.length;
    Stack<Integer> data = new Stack<>();
    int di = 0;//数据序列的索引位置
    for(int i = 0; i < length; i ++) {
        int item = target[i];
        //入栈完毕
        if(di == length) {
            if(data.isEmpty()) {
                return false;
            }
            int top = data.pop();
            if(top == item) {
                continue;
            }else {
                return false;
            }
        }
        while (di < length) {
            int current = source[di];
            if(item == current) {
                di++;
                break;
            } else if(data.isEmpty()){
                data.push(current);
                di++;
            } else {
                int top = data.peek();
                if(top == item) {
                    data.pop();
                    break;
                }else {
                    data.push(current);
                    di++;
                }
            }
        }
    }
    return true;
}

 

三、使用广度优先的方式遍历二叉树，并逐层打印节点值

    广度优先，就是按照二叉树的level，逐级遍历。如果你有过此方面的算法经验，其实这个题非常简单。如果你喜欢钻牛角尖，估计这题不好办！钻牛角尖的思路就是：递归、遍历、数组等等。

    推演思路：

假如输入二叉树，树的结构如下：
           8
          /\
      6        10
     /\        /\
    5  7      9  11

当前节点          队列
8               6，10
6               10，5，7
10              5，7，9，11
5               7，9，11
7               9，11
9               11
11              空

要求打印结果：8 6 10 5 7 9 11

 

    突破口已经有了，就是使用一个队列来保存即将参与打印的节点。太有才了，此后大家需要记住，广度遍历二叉树时要使用队列！！代码样例如下：

static class BinaryTree {
    BinaryTreeNode root;
}
static class BinaryTreeNode {
    BinaryTreeNode left;
    BinaryTreeNode right;
    int value;
}

public static void print(BinaryTree tree) {
    if(tree == null) {
        return;
    }
    BinaryTreeNode root = tree.root;
    if(root == null) {
        return;
    }
    Queue<BinaryTreeNode> data = new LinkedList<>();
    data.add(root);
    while (!data.isEmpty()) {
        BinaryTreeNode current = data.poll();
        System.out.print(current.value + ",");
        BinaryTreeNode left = current.left;
        if(left != null) {
            data.add(left);
        }
        BinaryTreeNode right = current.right;
        if(right != null) {
            data.add(right);
        }
    }
}

 

    我们还需要简单考虑一下，如果打印结果的要求是“逐层”？

比如上述二叉树，打印结果为：
8
6 10
5 7 9 11

 

    此时我们发现一个队列其实无法满足设计需要，我们需要用两个队列：

1）
队列1     队列二
8            空
空           6 10

2）
队列1      队列二
空           6 10
5 7          10
5 7 9 11   空

基本思路就是，在将其中一个队列出队的时候，将其
子节点添加到另一个队列的尾部，且每次都将当前队列
完全出队，此后再以同样的方式操作另一个队列。

 

    代码样例：

public static void print(BinaryTree tree) {
    if(tree == null) {
        return;
    }
    BinaryTreeNode root = tree.root;
    if(root == null) {
        return;
    }
    Queue<BinaryTreeNode> first = new LinkedList<>();
    Queue<BinaryTreeNode> second = new LinkedList<>();
    first.add(root);
    while (true) {
        if(first.isEmpty() && second.isEmpty()) {
            break;
        }
        if(first.isEmpty()) {
            inner(first,second);
        }else {
            inner(second,first);
        }
    }

}
private static void inner(Queue<BinaryTreeNode> first,Queue<BinaryTreeNode> second) {
    while (!second.isEmpty()) {
        BinaryTreeNode current = second.poll();
        System.out.print(current.value + ",");
        BinaryTreeNode left = current.left;
        if(left != null) {
            first.add(left);
        }
        BinaryTreeNode right = current.right;
        if(right != null) {
            first.add(right);
        }
    }
    System.out.println();
}

 

四、输入一个整数数组，判断该数组是否为某二叉搜索树的后序遍历结果

    我们首先分析一下二叉树后序遍历结果的特点，比如{5,7,6,9,11,10,8}是一个正常的二叉树后序遍历结果；最后一个元素一定是root节点，即为8；从数组的一个元素开始，首次遇到的比8大的元素之前的元素列表都是8的左子树，其他的为右子树，比如{5,7,6}为左子树，{9,11,10}为右子树。当然每个子树也是“后序遍历”的结果，比如对于左子树，6就是其根节点，5是其左节点，7是有节点。这种比较的合法性是可传递的，即任何节点的左子树元素都应该小于它的值，右子树的元素都大于它的值。（无重复元素）

 

    比如输入{7,4,6,5}，判断这个序列是否为后序遍历结果；由此得知：5是跟节点，{7,4,6}是它的右子树，但是其中4小于5，不符合判定规则，因此判断结果为false。

 

    代码样例：

public static boolean check(int[] source,int start,int end) {
    if(start == end) {
        return true;
    }
    int root = source[end];
    int i = start;
    //判断左子树的位置
    for(;i < end; i++) {
        if(source[i] > root) {
            break;
        }
    }
    int j = i;
    for(;j < end - 1;j++) {
        if(source[j] < root ) {
            return false;
        }
    }
    boolean left = true;
    if(i > 0) {
        left = check(source, start, i - 1);
    }

    if(!left) {
       return false;
    }
    boolean right = true;
    if (i < end - 1) {
        right = check(source, i, end - 1);
    }
    return left && right;
}