leetcode 295. Find Median from Data Stream

leetcode
九章

题目描述

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

leetcode
九章

题目描述

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)

难度:Middle

leetcode
九章

题目描述

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

难度:Hard

leetcode
九章

题目描述

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)

难度:Middle

leetcode
九章

题目描述

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 [2].
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

难度:Middle

leetcode
九章

题目描述

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,[6]]]
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 一言句子获取中...