「栈」专题 3:使用自己编写的模拟系统栈,写出非递归的程序


「栈」专题 3:使用自己编写的模拟系统栈,写出非递归的程序

二叉树的三种非递归遍历

栈和递归密不可分:分别可以解决二叉树的前序遍历、中序遍历、后序遍历

LeetCode 第144 题:前序遍历

LeetCode 第 94 题:中序遍历

LeetCode 第 145 题:后序遍历

LeetCode 第 145 题: 后序遍历二叉树

递归写法

public class Solution2 {

    private List<Integer> result = new ArrayList<>();

    /**
     * 递归的方式后续遍历二叉树
     * @param root
     * @return
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        postorder(root);
        return result;

    }

    private void postorder(TreeNode root) {
        if(root!=null){
            postorder(root.left);
            postorder(root.right);
            result.add(root.val);
        }
    }
}

非递归写法

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

enum UseType {
    RECURSION,
    ADD
}

class Command {
    UseType useType;
    TreeNode treeNode;

    public Command(UseType useType, TreeNode treeNode) {
        this.useType = useType;
        this.treeNode = treeNode;
    }
}


public class Solution {

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result  =new ArrayList<>();
        if(root==null){
            return result;
        }
        Stack<Command> stack = new Stack<>();
        stack.add(new Command(UseType.RECURSION,root));

        while (!stack.isEmpty()){
            Command command = stack.pop();

            if(UseType.ADD == command.useType){
                result.add(command.treeNode.val);
            }else {
                assert UseType.RECURSION == command.useType;
                stack.push(new Command(UseType.ADD,command.treeNode));
                if(command.treeNode.right!=null){
                    stack.push(new Command(UseType.RECURSION,command.treeNode.right));
                }
                if(command.treeNode.left!=null){
                    stack.push(new Command(UseType.RECURSION,command.treeNode.left));
                }
            }
        }
        return result;
    }

}

LeetCode 第 341 题:类的设计问题,挺有意思的

二叉树的层序遍历

LeetCode 第 102 题:层序遍历

LeetCode 第 107 题:自底向上的层序遍历

LeetCode 第 103 题:二叉树的锯齿形层次遍历

LeetCode 第 199 题:二叉树的右视图

分析:二叉树从右边看,得到的一个数组。

(一题多解)LeetCode 第 279 题:求最小的完全平方数之和

思路1:广度优先遍历、层序遍历

思路2:动态规划

(难)LeetCode 第 127 题:

要求:给定两个单词(beginWord 和 endWord)和一个字典,找到从 beginWord 到 endWord 的最短转换序列的长度。

(难,据说经常考,要注意)LeetCode 第 126 题:

LeetCode 第 347 题:前 K 个高频元素

思路:不能用排序,那就用优先队列。

LeetCode 第 23 题:合并 K 个排序链表

典型问题,一定要掌握。(1、优先队列;2、分治归并

LeetCode 第 225 题:用队列实现栈

思想:负负得正。

方法1:干脆就 push 的时候麻烦一点,出栈和查看栈顶元素就很简单了;

from collections import deque


class MyStack(object):

    # 用一个栈实现队列,其实就是找规律
    # push 的时候麻烦
    # top 和 pop 的时候简单

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.queue = deque()

    def push(self, x):
        """
        Push element x onto stack.
        :type x: int
        :rtype: void
        """
        self.queue.append(x)
        l = len(self.queue)
        if l > 0:
            for _ in range(l - 1):
                self.queue.append(self.queue.popleft())

    def pop(self):
        """
        Removes the element on top of the stack and returns that element.
        :rtype: int
        """

        return self.queue.popleft()

    def top(self):
        """
        Get the top element.
        :rtype: int
        """
        return self.queue[0]

    def empty(self):
        """
        Returns whether the stack is empty.
        :rtype: bool
        """
        return not self.queue

# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

方法2:用两个队列实现栈

LeetCode 第 232 题:用两个栈(stack)实现队列(queue)

设计辅助函数,出队列都从 stack2 出,进队列(push)都从 stack1 进。

自己在纸上画一画就很清楚了。只要涉及出队列和 peek 队列的,都执行一次辅助函数的操作。

要特别注意的地方:只有当 stack2 为空的时候,才可以一次性把 stack1 倒到 stack2,然后再从 stack 栈顶拿元素。

class MyQueue(object):

    # 关键:stack1 是主栈
    # stack2 永远是辅助

    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def push(self, x):
        # 永远只向 stack1 加入元素
        self.stack1.append(x)

    def __shift_stacks(self):
        # 这里不要忘记,只有当 stack2 为空的时候,才可以一次性把 stack1 倒到 stack2  
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())

    def pop(self):
        # 只要是 pop 或者 peek 的时候,表示要从队列首拿出元素
        # 此时就要把 stack1 的元素全部倒入 stack2 ,然后拿出 stack2 的栈顶元素
        self.__shift_stacks()
        return self.stack2.pop()

    def peek(self):
        self.__shift_stacks()
        return self.stack2[-1]

    def empty(self):
        # 两个栈没有元素复制,只有二者都空的时候,才表示队列为空
        return not self.stack1 and not self.stack2

# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

LeetCode 第 341 题:Flatten Nested List Iterator

传送门:https://leetcode.com/problems/flatten-nested-list-iterator/description/

参考解答:

http://blog.csdn.net/jmspan/article/details/51285573

http://blog.csdn.net/l294265421/article/details/51203616

思路: 题目要求用迭代器实现, 所以不能预先把值求出来. 可以利用栈来实现, 也就是用两个栈一个保存当前数组的元素指针, 另一个保存这个数组的结束迭代器. 用栈的目的是可以模拟递归, 也就是可以层层嵌套, 最深的总是在最上面, 当遍历完深层的数组还可以回来继续遍历之前的层.

https://segmentfault.com/a/1190000008925686>

https://segmentfault.com/a/1190000008925686

https://segmentfault.com/a/1190000008925686

(这篇文章里面有很多扩展阅读,例如:leetcode 315 Count of Smaller Numbers After Self 以及 BST总结。)

这道题是拉平层层嵌套的链表,题目难度为Medium。

这种嵌套的问题很自然想到要用栈来处理,由于要按照先后次序输出,所以要将链表从尾部开始依次进栈,然后判断栈顶元素是数字还是链表,如果是链表,将该链表出栈之后按同样的方法将它自身的元素从尾部开始进栈,直到栈顶元素是数字即可出栈输出了。这里将主要操作放在了hasNext()函数中,没有在next()函数中处理是为了避免空链表干扰hasNext()函数的判断。具体代码:

解法一:

参考:http://blog.csdn.net/zdavb/article/details/51553476

interface NestedInteger {
    boolean isInteger();
    Integer getInteger();
    List<NestedInteger> getList();
}


class NestedIntegerImpl implements NestedInteger {
    private boolean isInteger = false;
    private Integer intData;
    private List<NestedInteger> nestedList = new ArrayList<>();

    public NestedIntegerImpl(boolean isInteger, Integer intData) {
        this.isInteger = isInteger;
        this.intData = intData;
    }

    public NestedIntegerImpl(boolean isInteger, NestedInteger... nestedIntegers) {
        this.isInteger = false;
        for (NestedInteger nestedInteger : nestedIntegers) {
            this.nestedList.add(nestedInteger);
        }
    }

    @Override
    public boolean isInteger() {
        return isInteger;
    }

    @Override
    public Integer getInteger() {
        return intData;
    }

    @Override
    public List<NestedInteger> getList() {
        return nestedList;
    }
}

public class NestedIterator implements Iterator<Integer> {

    List<NestedInteger> nestedList;
    // 把下一个的值放在这个 data 变量里面
    int data;

    public NestedIterator(List<NestedInteger> nestedList) {
        this.nestedList = nestedList;
    }

    @Override
    public Integer next() {
        return data;
    }

    @Override
    public boolean hasNext() {
        while (nestedList != null && nestedList.size() > 0) {
            NestedInteger tmpInt = nestedList.remove(0);
            if (tmpInt.isInteger()) {
                data = tmpInt.getInteger();
                return true;
            } else {
                nestedList.addAll(0, tmpInt.getList());
            }
        }
        return false;
    }
}

测试用例一:

/**
     * 测试用例 [1,[4,[6,5]]]
     * @param args
     */
public static void main(String[] args) {
    NestedInteger six = new NestedIntegerImpl(true, 6);
    NestedInteger five = new NestedIntegerImpl(true, 5);
    NestedInteger six_1_five = new NestedIntegerImpl(false, six, five);

    NestedInteger four = new NestedIntegerImpl(true, 4);
    NestedInteger four_2_six_1_five = new NestedIntegerImpl(false, four, six_1_five);

    NestedInteger one = new NestedIntegerImpl(true, 1);
    NestedInteger one_3_four_2_six_1_five = new NestedIntegerImpl(false, one, four_2_six_1_five);
    NestedIterator nestedIterator = new NestedIterator(one_3_four_2_six_1_five.getList());
    while (nestedIterator.hasNext()) {
        Integer next = nestedIterator.next();
        System.out.printf("%d \t", next);
    }
}

解法二:自己根据一的思路,使用 Stack 来完成的

心得:

思考?为什么用栈就可以解决这个问题呢?

Java 代码:

NestedInteger 接口:

interface NestedInteger { 
    boolean isInteger(); 
    Integer getInteger(); 
    List<NestedInteger> getList(); 
} 

NestedInteger 接口的实现(LeeCode 此题并不要求,我为了测试添加):

class NestedIntegerImpl implements NestedInteger {
    boolean isInteger;
    int intData;
    List<NestedInteger> nestedList = new ArrayList<>();

    public NestedIntegerImpl(boolean isInteger, int intData) {
        this.isInteger = isInteger;
        this.intData = intData;
    }

    public NestedIntegerImpl(boolean isInteger, NestedInteger... nestedIntegers) {
        this.isInteger = isInteger;
        for (NestedInteger nestedInteger : nestedIntegers) {
            nestedList.add(nestedInteger);
        }
    }


    @Override
    public boolean isInteger() {
        return isInteger;
    }

    @Override
    public Integer getInteger() {
        return intData;
    }

    @Override
    public List<NestedInteger> getList() {
        return nestedList;
    }
}

NestedIterator 接口的实现(这是 LeetCode 要求我们做的事情):

public class NestedIterator implements Iterator<Integer> {

    private Stack<NestedInteger> stack = new Stack<>();
    private int data;


    public NestedIterator(List<NestedInteger> nestedList) {
        for (int i = nestedList.size() - 1; i >= 0; i--) {
            stack.push(nestedList.get(i));
        }
    }

    @Override
    public boolean hasNext() {
        while (!stack.isEmpty()) {
            NestedInteger top = stack.pop();
            if (top.isInteger()) {
                data = top.getInteger();
                return true;
            } else {
                List<NestedInteger> nestedList = top.getList();
                for (int i = nestedList.size() - 1; i >= 0; i--) {
                    stack.push(nestedList.get(i));
                }
            }
        }
        return false;
    }

    @Override
    public Integer next() {
        return data;
    }

}

测试用例:

/**
 * 测试用例 [[6,4,5],8,[1,2]]
 *
 * @param args
 */
public static void main(String[] args) {
    NestedInteger six = new NestedIntegerImpl(true, 6);
    NestedInteger four = new NestedIntegerImpl(true, 4);
    NestedInteger five = new NestedIntegerImpl(true, 5);
    NestedInteger six_four_five = new NestedIntegerImpl(false, six, four, five);

    NestedInteger eight = new NestedIntegerImpl(true, 8);

    NestedInteger one = new NestedIntegerImpl(true, 1);
    NestedInteger two = new NestedIntegerImpl(true, 2);
    NestedInteger one_two = new NestedIntegerImpl(false, one,two);


    NestedInteger six_four_five__eight__one_two = new NestedIntegerImpl(false, six_four_five, eight,one_two);


    NestedIterator nestedIterator = new NestedIterator(six_four_five__eight__one_two.getList());
    while (nestedIterator.hasNext()) {
        Integer next = nestedIterator.next();
        System.out.printf("%d \t", next);
    }
}

解法三:(同解法二,只不过使用的是双端队列)

public class NestedIterator implements Iterator<Integer> {

    private int data;
    private Deque<NestedInteger> deque = new ArrayDeque<>();

    public NestedIterator(List<NestedInteger> nestedList) {
        for (NestedInteger nestedInteger : nestedList) {
            deque.addLast(nestedInteger);
        }
    }

    @Override
    public boolean hasNext() {
        while (!deque.isEmpty()) {
            NestedInteger top = deque.pollFirst();
            if (top.isInteger()) {
                this.data = top.getInteger();
                return true;
            } else {
                List<NestedInteger> nestedList = top.getList();
                for (int i = nestedList.size() - 1; i >= 0; i--) {
                    deque.addFirst(nestedList.get(i));
                }
            }
        }
        return false;
    }

    @Override
    public Integer next() {
        return data;
    }
}

(本节完)


文章作者: liweiwei1419
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !
评论
 上一篇
「力扣」第 20 题:有效的括号(简单) 「力扣」第 20 题:有效的括号(简单)
「力扣」第 20 题:有效的括号(简单) 中文网址:20. 有效的括号 ; 英文网址:20. Valid Parentheses , 给定一个只包括 '(',')','{','}&
2017-09-04
下一篇 
「栈」专题 2:二叉树的三种非递归实现 「栈」专题 2:二叉树的三种非递归实现
「栈」专题 2:二叉树的三种非递归实现对于递归而言,简单来说就是自己调用自己,但是再一次调用自己,又有不一样的地方,具体表现就是参数不同。 通常我们写递归程序的时候,是不会直接使用栈的。因为操作系统在执行递归程序的时候,就帮助我们使用了栈。
2017-09-02
  目录