# leetcode 295. Find Median from Data Stream

## 题目描述

Median is the middle value in an ordered integer list. If the size of the list
is even, there is no middle value. So the median is the mean of the two middle
value.

For example,

`[2,3,4]`, the median is `3`

`[2,3]`, the median is `(2 + 3) / 2 = 2.5`

Design a data structure that supports the following two operations:

• void addNum(int num) - Add a integer number from the data stream to the data structure.
• double findMedian() - Return the median of all elements so far.

Example:

``````addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2``````

Follow up:

1. If all integer numbers from the stream are between 0 and 100, how would you optimize it?
2. If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?

Tags: Heap, Design

Difficulty: Hard



# leetcode 155. 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.

Example:

``````MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.``````

Tags: Stack, Design

Difficulty: Easy



# leetcode 208. Implement Trie (Prefix Tree)

## 题目描述

Implement a trie with `insert`, `search`, and `startsWith` methods.

Example:

``````Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app");     // returns true``````

Note:

• You may assume that all inputs are consist of lowercase letters `a-z`.
• All inputs are guaranteed to be non-empty strings.

Tags: Design, Trie

Difficulty: Medium

# leetcode 297. 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.

*Example: *

``````You may serialize the following tree:

1
/ \
2   3
/ \
4   5

as "[1,2,3,null,null,4,5]"``````

Clarification: The above format is the same as how LeetCode 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.

Tags: Tree, Design

Difficulty: Hard

# leetcode 380. Insert Delete GetRandom O(1)

## 题目描述

Design a data structure that supports all following operations in average
O(1) time.

1. `insert(val)`: Inserts an item val to the set if not already present.
2. `remove(val)`: Removes an item val from the set if present.
3. `getRandom`: Returns a random element from current set of elements. Each element must have the same probability of being returned.

Example:

``````// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains .
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();``````

Tags: Array, Hash Table, Design

Difficulty: Medium

# leetcode 341. Flatten Nested List Iterator

## 题目描述

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list – whose elements may also be
integers or other lists.

Example 1:

``````Input: [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling _next_ repeatedly until _hasNext_ returns false,
the order of elements returned by _next_ should be: [1,1,2,1,1].``````

Example 2:

``````Input: [1,[4,]]
Output: [1,4,6]
Explanation: By calling _next_ repeatedly until _hasNext_ returns false,
the order of elements returned by _next_ should be: [1,4,6].``````

Tags: Stack, Design

Difficulty: Medium

:D 一言句子获取中...