hard Archives - Page 48 of 48 - Huahua's Tech Road

Problem:

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.

Examples:

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

For example:

addNum(1)

addNum(2)

findMedian() = 1.5

addNum(3)

findMedian() = 2

Idea:

Min/Max heap
Balanced binary search tree

Time Complexity:

add(num): O(logn)

findMedian(): O(logn)

Solution1:

// Author: Huahua

// Running Time: 152 ms

class MedianFinder {

public:

/** initialize your data structure here. */

MedianFinder() {}

// l_.size() >= r_.size()

void addNum(int num) {

if (l_.empty() || num <= l_.top()) {

l_.push(num);

} else {

r_.push(num);

}

// Step 2: Balence left/right

if (l_.size() < r_.size()) {

l_.push(r_.top());

r_.pop();

} else if (l_.size() - r_.size() == 2) {

r_.push(l_.top());

l_.pop();

}

double findMedian() {

if (l_.size() > r_.size()) {

return static_cast<double>(l_.top());

} else {

return (static_cast<double>(l_.top()) + r_.top()) / 2;

}

private:

priority_queue<int, vector<int>, less<int>> l_; // max-heap

priority_queue<int, vector<int>, greater<int>> r_; // min-heap

};

Solution 2:

// Author: Huahua

// Running time: 172 ms

class MedianFinder {

public:

/** initialize your data structure here. */

MedianFinder(): l_(m_.cend()), r_(m_.cend()) {}

// O(logn)

void addNum(int num) {

if (m_.empty()) {

l_ = r_ = m_.insert(num);

return;

}

m_.insert(num);

const size_t n = m_.size();

if (n & 1) {

// odd number

if (num >= *r_) {

l_ = r_;

} else {

// num < *r_, l_ could be invalidated

l_ = --r_;

}

} else {

if (num >= *r_)

++r_;

else

--l_;

}

// O(1)

double findMedian() {

return (static_cast<double>(*l_) + *r_) / 2;

}

private:

multiset<int> m_;

multiset<int>::const_iterator l_; // current left median

multiset<int>::const_iterator r_; // current right median

};

Related Problems

Problem

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

Solution

Time complexity: O(2^n)

Space complexity: O(2^n)

C++

// Author: Huahua

class Solution {

public:

vector<string> wordBreak(string s, vector<string>& wordDict) {

unordered_set<string> dict(wordDict.cbegin(), wordDict.cend());

return wordBreak(s, dict);

}

private:

// >> append({"cats and", "cat sand"}, "dog");

// {"cats and dog", "cat sand dog"}

vector<string> append(const vector<string>& prefixes, const string& word) {

vector<string> results;

for(const auto& prefix : prefixes)

results.push_back(prefix + " " + word);

return results;

}

const vector<string>& wordBreak(string s, unordered_set<string>& dict) {

// Already in memory, return directly

if(mem_.count(s)) return mem_[s];

// Answer for s

vector<string> ans;

// s in dict, add it to the answer array

if(dict.count(s))

ans.push_back(s);

for(int j=1;j<s.length();++j) {

// Check whether right part is a word

const string& right = s.substr(j);

if (!dict.count(right)) continue;

// Get the ans for left part

const string& left = s.substr(0, j);

const vector<string> left_ans =

append(wordBreak(left, dict), right);

// Notice, can not use mem_ here,

// since we haven't got the ans for s yet.

ans.insert(ans.end(), left_ans.begin(), left_ans.end());

}

// memorize and return

mem_[s].swap(ans);

return mem_[s];

}

private:

unordered_map<string, vector<string>> mem_;

};

Python3

"""

Author: Huahua

Running time: 56 ms

"""

class Solution:

def wordBreak(self, s, wordDict):

words = set(wordDict)

mem = {}

def wordBreak(s):

if s in mem: return mem[s]

ans = []

if s in words: ans.append(s)

for i in range(1, len(s)):

right = s[i:]

if right not in words: continue

ans += [w + " " + right for w in wordBreak(s[0:i])]

mem[s] = ans

return mem[s]

return wordBreak(s)

Posts tagged as “hard”

花花酱 LeetCode 295. Find Median from Data Stream O(logn) + O(1)

花花酱 Leetcode 140. Word Break II

Problem

Solution

Related Problems