@Yano 2019-09-20T02:55:39.000000Z 字数 9567 阅读 5040

# LeetCode之Design题目汇总

LeetCode

# 公众号

coding 笔记、点滴记录，以后的文章也会同步到公众号（Coding Insight）中，希望大家关注^_^

https://github.com/LjyYano/Thinking_in_Java_MindMapping

LeetCode 题目汇总

# Implement Queue using Stacks

Implement the following operations of a queue using stacks.

• push(x) -- Push element x to the back of queue.
• pop() -- Removes the element from in front of queue.
• peek() -- Get the front element.
• empty() -- Return whether the queue is empty.

Notes:

• You must use only standard operations of a stack -- which means only push to toppeek/pop from topsize, and is empty operations are valid.
• Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
• You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

1. push向stack1
2. pop从stack2，如果stack2为空，先将stack1的元素放入stack2
    class MyQueue {        Stack<Integer> stack1 = new Stack<Integer>();        Stack<Integer> stack2 = new Stack<Integer>();        // Push element x to the back of queue.        public void push(int x) {            stack1.push(x);        }        // Removes the element from in front of queue.        public void pop() {            if (stack2.isEmpty()) {                if (stack1.isEmpty()) {                    throw new IllegalStateException();                }                while (!stack1.isEmpty()) {                    stack2.push(stack1.pop());                }            }            stack2.pop();        }        // Get the front element.        public int peek() {            if (stack2.isEmpty()) {                if (stack1.isEmpty()) {                    throw new IllegalStateException();                }                while (!stack1.isEmpty()) {                    stack2.push(stack1.pop());                }            }            return stack2.peek();        }        // Return whether the queue is empty.        public boolean empty() {            if (stack1.isEmpty() && stack2.isEmpty()) {                return true;            }            return false;        }    }

# Implement Stack using Queues

Implement the following operations of a stack using queues.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• empty() -- Return whether the stack is empty.

Notes:

• You must use only standard operations of a queue -- which means only push to backpeek/pop from frontsize, and is empty operations are valid.
• Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
• You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

Update (2015-06-11):
The class name of the Java function had been updated to MyStack instead of Stack.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and all test cases.

1. push就插入到非空的队列中
2. pop就把非空队列元素，依次放到另一个空队列中，只是最后一个元素弹出
    class MyStack {        Queue<Integer> q1 = new LinkedList<Integer>();        Queue<Integer> q2 = new LinkedList<Integer>();        // Push element x onto stack.        public void push(int x) {            if (q1.isEmpty() && q2.isEmpty()) {                q1.add(x);            } else if (!q1.isEmpty()) {                q1.add(x);            } else {                q2.add(x);            }        }        // Removes the element on top of the stack.        public void pop() {            if (empty()) {                throw new IllegalStateException();            }            // q1、q2必有一个为空            if (q2.isEmpty()) {                while (!q1.isEmpty()) {                    int x = q1.remove();                    if (!q1.isEmpty()) {                        q2.add(x);                    }                }            } else if (q1.isEmpty()) {                while (!q2.isEmpty()) {                    int x = q2.remove();                    if (!q2.isEmpty()) {                        q1.add(x);                    }                }            }        }        // Get the top element.        public int top() {            if (empty()) {                throw new IllegalStateException();            }            int x = 0;            // q1、q2必有一个为空            if (q2.isEmpty()) {                while (!q1.isEmpty()) {                    x = q1.remove();                    q2.add(x);                }            } else if (q1.isEmpty()) {                while (!q2.isEmpty()) {                    x = q2.remove();                    q1.add(x);                }            }            return x;        }        // Return whether the stack is empty.        public boolean empty() {            if (q1.isEmpty() && q2.isEmpty()) {                return true;            }            return false;        }    }

# Implement Trie (Prefix Tree)

Implement a trie with insertsearch, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

    class TrieNode {        boolean isLeaf;        char c;        HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();        // Initialize your data structure here.        public TrieNode() {        }        public TrieNode(char c) {            this.c = c;        }    }    public class Trie {        private TrieNode root;        public Trie() {            root = new TrieNode();        }        // Inserts a word into the trie.        public void insert(String word) {            HashMap<Character, TrieNode> children = root.children;            for (int i = 0; i < word.length(); i++) {                char c = word.charAt(i);                TrieNode t;                if (children.containsKey(c)) {                    t = children.get(c);                } else {                    t = new TrieNode(c);                    children.put(c, t);                }                children = t.children;                if (i == word.length() - 1) {                    t.isLeaf = true;                }            }        }        // Returns if the word is in the trie.        public boolean search(String word) {            HashMap<Character, TrieNode> children = root.children;            for (int i = 0; i < word.length(); i++) {                char c = word.charAt(i);                if (!children.containsKey(c)) {                    return false;                }                if (i == word.length() - 1) {                    if (children.get(c).isLeaf == true) {                        return true;                    }                    return false;                }                children = children.get(c).children;            }            // useless            return false;        }        // Returns if there is any word in the trie        // that starts with the given prefix.        public boolean startsWith(String prefix) {            HashMap<Character, TrieNode> children = root.children;            for (int i = 0; i < prefix.length(); i++) {                char c = prefix.charAt(i);                if (!children.containsKey(c)) {                    return false;                }                if (i == prefix.length() - 1) {                    return true;                }                children = children.get(c).children;            }            // useless            return false;        }    }    // Your Trie object will be instantiated and called as such:    // Trie trie = new Trie();    // trie.insert("somestring");    // trie.search("key");

# Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

    class MinStack {        Stack<Integer> stack = new Stack<Integer>();        Stack<Integer> min = new Stack<Integer>();        public void push(int x) {            if (stack.isEmpty()) {                stack.push(x);                min.push(x);            } else {                stack.push(x);                min.push(Math.min(stack.peek(), min.peek()));            }        }        public void pop() {            if (!stack.isEmpty()) {                stack.pop();                min.pop();            }        }        public int top() {            if (!stack.isEmpty()) {                return stack.peek();            }            throw new IllegalStateException();        }        public int getMin() {            if (!min.isEmpty()) {                return min.peek();            }            throw new IllegalStateException();        }    }

# Peeking Iterator

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation -- it essentially peek() at the element that will be returned by the next call to next().

Here is an example. Assume that the iterator is initialized to the beginning of the list: [1, 2, 3].

Call next() gets you 1, the first element in the list.

Now you call peek() and it returns 2, the next element. Calling next() after that still return 2.

You call next() the final time and it returns 3, the last element. Calling hasNext() after that should return false.

Hint:

1. Think of "looking ahead". You want to cache the next element.
2. Is one variable sufficient? Why or why not?
3. Test your design with call order of peek() before next() vs next() before peek().
4. For a clean implementation, check out Google's guava library source code.

Follow up: How would you extend your design to be generic and work with all types, not just integer?

Credits:
Special thanks to @porker2008 for adding this problem and creating all test cases.

peek的含义是，返回顶部元素，但是元素不弹出。但是返回顶部元素的时候，必定要使用next()。定义一个变量“缓存”元素即可。

    private Iterator<Integer> iterator;    private boolean hasPeeked;    private Integer peekedElement;    public L284_Peeking_Iterator(Iterator<Integer> iterator) {        // initialize any member here.        this.iterator = iterator;    }    // Returns the next element in the iteration without advancing the iterator.    public Integer peek() {        if (!hasPeeked) {            peekedElement = iterator.next();            hasPeeked = true;        }        return peekedElement;    }    // hasNext() and next() should behave the same as in the Iterator interface.    // Override them if needed.    public Integer next() {        if (!hasPeeked) {            return iterator.next();        }        Integer result = peekedElement;        hasPeeked = false;        peekedElement = null;        return result;    }    public boolean hasNext() {        return hasPeeked || iterator.hasNext();    }

# Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

    1   / \  2   3     / \    4   5

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

Credits:
Special thanks to @Louis1992 for adding this problem and creating all test cases.

    1   / \  2   3     /     4      /  5
    public String serialize(TreeNode root) {        if (root == null) {            return "";        }        StringBuffer sb = new StringBuffer();        Deque<TreeNode> deque = new LinkedList<TreeNode>();        deque.add(root);        while (!deque.isEmpty()) {            TreeNode p = deque.pop();            if (p == null) {                sb.append(",#");            } else {                sb.append("," + p.val);                deque.add(p.left);                deque.add(p.right);            }        }        // 第一个元素前也有一个逗号，截取        return sb.toString().substring(1);    }    public TreeNode deserialize(String data) {        if (data == null || data.length() == 0) {            return null;        }        String[] s = data.split(",");        TreeNode[] node = new TreeNode[s.length];        // 新建TreeNode，并初始化        for (int i = 0; i < node.length; i++) {            if (!"#".equals(s[i])) {                node[i] = new TreeNode(Integer.valueOf(s[i]));            }        }        int parent = 0;        // 将结点连接起来        for (int i = 0; parent * 2 + 2 < s.length; i++) {            if (node[i] != null) {                node[i].left = node[parent * 2 + 1];                node[i].right = node[parent * 2 + 2];                parent++;            }        }        return node[0];    }

• 私有
• 公开
• 删除