Huahua's Tech Road

花花酱 LeetCode 332. Reconstruct Itinerary

By zxi on September 12, 2017

Problem:

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
All airports are represented by three capital letters (IATA code).
You may assume all tickets form at least one valid itinerary.

Example 1:
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return ["JFK", "MUC", "LHR", "SFO", "SJC"].

Example 2:
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.

Idea:

Convert the graph to a tree and do post-order traversal

Solution:

// Author: Huahua

// Running time: 13 ms

class Solution {

public:

vector<string> findItinerary(vector<pair<string, string>> tickets) {

route_.clear();

trips_.clear();

for(const auto& pair : tickets)

trips_[pair.first].push_back(pair.second);

for(auto& pair : trips_) {

auto& dests = pair.second;

std::sort(dests.begin(), dests.end());

}

const string kStart = "JFK";

visit(kStart);

return vector<string>(route_.crbegin(), route_.crend());

}

private:

// src -> {dst1, dest2, ..., destn}

unordered_map<string, deque<string>> trips_;

// ans (reversed)

vector<string> route_;

void visit(const string& src) {

auto& dests = trips_[src];

while (!dests.empty()) {

// Get the smallest dest

const string dest = dests.front();

// Remove the ticket

dests.pop_front();

// Visit dest

visit(dest);

}

// Add current node to the route

route_.push_back(src);

}

};

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

By zxi on September 12, 2017

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

花花酱 LeetCode 146. LRU Cache O(1)

By zxi on September 10, 2017

Problem:

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);

cache.put(2, 2);

cache.get(1); // returns 1

cache.put(3, 3); // evicts key 2

cache.get(2); // returns -1 (not found)

cache.put(4, 4); // evicts key 1

cache.get(1); // returns -1 (not found)

cache.get(3); // returns 3

cache.get(4); // returns 4

Idea:

Use Hashtable for fast mapping and double linked list for fast manipulation.

Time Complexity:

Put O(1)

Get O(1)

Solution:

// Author: Huahua

class LRUCache {

public:

LRUCache(int capacity) {

capacity_ = capacity;

}

int get(int key) {

const auto it = m_.find(key);

// If key does not exist

if (it == m_.cend()) return -1;

// Move this key to the front of the cache

cache_.splice(cache_.begin(), cache_, it->second);

return it->second->second;

}

void put(int key, int value) {

const auto it = m_.find(key);

// Key already exists

if (it != m_.cend()) {

// Update the value

it->second->second = value;

// Move this entry to the front of the cache

cache_.splice(cache_.begin(), cache_, it->second);

return;

}

// Reached the capacity, remove the oldest entry

if (cache_.size() == capacity_) {

const auto& node = cache_.back();

m_.erase(node.first);

cache_.pop_back();

}

// Insert the entry to the front of the cache and update mapping.

cache_.emplace_front(key, value);

m_[key] = cache_.begin();

}

private:

int capacity_;

list<pair<int,int>> cache_;

unordered_map<int, list<pair<int,int>>::iterator> m_;

};

/**

* Your LRUCache object will be instantiated and called as such:

* LRUCache obj = new LRUCache(capacity);

* int param_1 = obj.get(key);

* obj.put(key,value);

花花酱 LeetCode 676. Implement Magic Dictionary

By zxi on September 10, 2017

Problem:

Implement a magic directory with buildDict, and search methods.

For the method buildDict, you’ll be given a list of non-repetitive words to build a dictionary.

For the method search, you’ll be given a word, and judge whether if you modify exactly one character into another character in this word, the modified word is in the dictionary you just built.

Example 1:

Input: buildDict(["hello", "leetcode"]), Output: Null

Input: search("hello"), Output: False

Input: search("hhllo"), Output: True

Input: search("hell"), Output: False

Input: search("leetcoded"), Output: False

Note:

You may assume that all the inputs are consist of lowercase letters a-z.
For contest purpose, the test data is rather small by now. You could think about highly efficient algorithm after the contest.
Please remember to RESET your class variables declared in class MagicDictionary, as static/class variables are persisted across multiple test cases. Please see here for more details.

Idea:

Fuzzy match

Time Complexity:

buildDict: O(n*m)

n: numbers of words

m: length of word

search: O(m)

m: length of word

Space Complexity:

O(n*m)

Solution:

// Author: Huahua

class MagicDictionary {

public:

/** Initialize your data structure here. */

MagicDictionary() {

dict_.clear();

}

/** Build a dictionary through a list of words */

void buildDict(vector<string> dict) {

for(string& word: dict) {

for(int i = 0; i < word.length(); ++i) {

char c = word[i];

word[i] = '*';

dict_[word].insert(c);

word[i] = c;

}

/** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */

bool search(string word) {

for(int i = 0; i < word.length(); ++i) {

char c = word[i];

word[i] = '*';

if (dict_.count(word)) {

const auto& char_set = dict_[word];

if (!char_set.count(c) || char_set.size() > 1)

return true;

}

word[i] = c;

}

return false;

}

private:

unordered_map<string, unordered_set<char>> dict_;

};

/**

* Your MagicDictionary object will be instantiated and called as such:

* MagicDictionary obj = new MagicDictionary();

* obj.buildDict(dict);

* bool param_2 = obj.search(word);

Java / Trie

class MagicDictionary {

private Trie root;

public MagicDictionary() {

root = new Trie();

}

public void buildDict(String[] dict) {

for (String word : dict) {

Trie curr = root;

for (char c : word.toCharArray()) {

int index = c - 'a';

if (curr.children[index] == null)

curr.children[index] = new Trie();

curr = curr.children[index];

}

curr.ends = true;

}

public boolean search(String word) {

char[] s = word.toCharArray();

for(int i = 0; i < s.length; i++) {

for (char c = 'a'; c <= 'z'; ++c) {

if (s[i] == c) continue;

char tmp = s[i];

s[i] = c;

if (contains(s)) return true;

s[i] = tmp;

}

return false;

}

private boolean contains(char[] word) {

Trie curr = root;

for (int i = 0; i < word.length; ++i) {

curr = curr.children[word[i] - 'a'];

if (curr == null) return false;

}

return curr.ends;

}

class Trie {

private boolean ends;

private Trie[] children;

public Trie() {

children = new Trie[26];

ends = false;

}

Java / Trie v2

class MagicDictionary {

private Trie root;

public MagicDictionary() {

root = new Trie();

}

public void buildDict(String[] dict) {

for (String word : dict) {

Trie curr = root;

for (char c : word.toCharArray()) {

int index = c - 'a';

if (curr.children[index] == null)

curr.children[index] = new Trie();

curr = curr.children[index];

}

curr.ends = true;

}

public boolean search(String word) {

char[] s = word.toCharArray();

Trie prefix = root;

for(int i = 0; i < s.length; i++) {

for (char c = 'a'; c <= 'z'; ++c) {

if (s[i] == c) continue;

char tmp = s[i];

s[i] = c;

if (contains(s, prefix, i)) return true;

s[i] = tmp;

}

prefix = prefix.children[s[i] - 'a'];

if (prefix == null) return false;

}

return false;

}

private boolean contains(char[] word, Trie prefix, int s) {

Trie curr = prefix;

for (int i = s; i < word.length; ++i) {

curr = curr.children[word[i] - 'a'];

if (curr == null) return false;

}

return curr.ends;

}

class Trie {

private boolean ends;

private Trie[] children;

public Trie() {

children = new Trie[26];

ends = false;

}

花花酱 LeetCode 300. Longest Increasing Subsequence

By zxi on September 10, 2017

Problem:

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n²) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Idea:

Dynamic Programming

Time Complexity:

O(n^2)

Solution 1:

// Author: Huahua

// Running time: 29 ms

class Solution {

public:

int lengthOfLIS(vector<int>& nums) {

if (nums.empty()) return 0;

int n = nums.size();

auto f = vector<int>(n, 1);

for (int i = 1; i < n; ++i)

for (int j = 0; j < i; ++j)

if (nums[i] > nums[j])

f[i] = max(f[i], f[j] + 1);

return *max_element(f.begin(), f.end());

}

};

Solution 2: DP + Binary Search / Patience Sort

dp[i] := smallest tailing number of a increasing subsequence of length i + 1.

dp is an increasing array, we can use binary search to find the index to insert/update the array.

ans = len(dp)

Time complexity: O(nlogn)
Space complexity: O(n)

C++

class Solution {

public:

int lengthOfLIS(vector<int>& nums) {

const int n = nums.size();

if (n == 0) return 0;

vector<int> dp;

for (int i = 0; i < n; ++i) {

auto it = lower_bound(begin(dp), end(dp), nums[i]);

if (it == end(dp))

dp.push_back(nums[i]);

else

*it = nums[i];

}

return dp.size();

}

};

Python3

class Solution:

def lengthOfLIS(self, nums: List[int]) -> int:

d = []

for x in nums:

i = bisect_left(d, x)

if i == len(d):

d.append(x)

else:

d[i] = x

return len(d)

Related Problems: