Huahua’s Tech Road

花花酱 LeetCode 743. Network Delay Time

By zxi on December 12, 2017

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

Note:

N will be in the range [1, 100].
K will be in the range [1, N].
The length of times will be in the range [1, 6000].
All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 1 <= w <= 100.

Idea:

Construct the graph and do a shortest path from K to all other nodes.

Solution 2:

C++ / Bellman-Ford

Time complexity: O(ne)

Space complexity: O(n)

// Author: Huahua

// Runtime: 92 ms

class Solution {

public:

int networkDelayTime(vector<vector<int>>& times, int N, int K) {

constexpr int MAX_TIME = 101 * 100;

vector<int> dist(N, MAX_TIME);

dist[K - 1] = 0;

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

for (const auto& time : times) {

int u = time[0] - 1, v = time[1] - 1, w = time[2];

dist[v] = min(dist[v], dist[u] + w);

}

int max_dist = *max_element(dist.begin(), dist.end());

return max_dist == MAX_TIME ? -1 : max_dist;

}

};

Solution3:

C++ / Floyd-Warshall

Time complexity: O(n^3)

Space complexity: O(n^2)

// Author: Huahua

// Runtime: 92 ms

class Solution {

public:

int networkDelayTime(vector<vector<int>>& times, int N, int K) {

vector<vector<int>> d(N, vector<int>(N, -1));

for (auto time : times)

d[time[0] - 1][time[1] - 1] = time[2];

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

d[i][i] = 0;

for (int k = 0; k < N; ++k)

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

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

if (d[i][k] >= 0 && d[k][j] >= 0)

if (d[i][j] < 0 || d[i][j] > d[i][k] + d[k][j])

d[i][j] = d[i][k] + d[k][j];

int ans = INT_MIN;

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

if (d[K - 1][i] < 0) return -1;

ans = max(ans, d[K - 1][i]);

}

return ans;

}

};

// Author: Huahua

// Runtime: 89 ms

class Solution {

public:

int networkDelayTime(vector<vector<int>>& times, int N, int K) {

constexpr int MAX_TIME = 101 * 100;

vector<vector<int>> d(N, vector<int>(N, MAX_TIME));

for (auto time : times)

d[time[0] - 1][time[1] - 1] = time[2];

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

d[i][i] = 0;

for (int k = 0; k < N; ++k)

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

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

d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

int max_time = *max_element(d[K - 1].begin(), d[K - 1].end());

return max_time >= MAX_TIME ? - 1 : max_time;

}

};

花花酱 LeetCode 745. Prefix and Suffix Search

By zxi on December 11, 2017

Link: https://leetcode.com/problems/prefix-and-suffix-search/description/

Problem:

Given many words, words[i] has weight i.

Design a class WordFilter that supports one function, WordFilter.f(String prefix, String suffix). It will return the word with given prefix and suffix with maximum weight. If no word exists, return -1.

Examples:

Input:

WordFilter(["apple"])

WordFilter.f("a", "e") // returns 0

WordFilter.f("b", "") // returns -1

Note:

words has length in range [1, 15000].
For each test case, up to words.length queries WordFilter.f may be made.
words[i] has length in range [1, 10].
prefix, suffix have lengths in range [0, 10].
words[i] and prefix, suffix queries consist of lowercase letters only.

Idea:

Construct all possible filters

Solution1:

C++

Time complexity: O(NL^3 + QL) where N is the number of words, L is the max length of the word, Q is the number of queries.

Space complexity: O(NL^3)

// Author: Huahua

// Runtime: 482 ms

class WordFilter {

public:

WordFilter(const vector<string>& words) {

int index = 0;

for (const string& word : words) {

int n = word.length();

string prefix;

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

if (i > 0) prefix += word[i - 1];

string suffix;

for (int j = n; j >= 0; --j) {

if (j != n) suffix = word[j] + suffix;

const string key = prefix + "_" + suffix;

filters_[key] = index;

}

++index;

}

int f(string prefix, string suffix) {

const string key = prefix + "_" + suffix;

auto it = filters_.find(key);

if (it != filters_.end()) return it->second;

return -1;

}

private:

unordered_map<string, int> filters_;

};

Version #2

// Author: Huahua

// Runtime: 499 ms

class WordFilter {

public:

WordFilter(const vector<string>& words) {

int index = 0;

for (const string& word : words) {

int n = word.length();

vector<string> prefixes(n + 1, "");

vector<string> suffixes(n + 1, "");

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

prefixes[i + 1] = prefixes[i] + word[i];

suffixes[i + 1] = word[n - i - 1] + suffixes[i];

}

for (const string& prefix : prefixes)

for (const string& suffix : suffixes)

filters_[prefix + "_" + suffix] = index;

++index;

}

int f(string prefix, string suffix) {

const string key = prefix + "_" + suffix;

auto it = filters_.find(key);

if (it != filters_.end()) return it->second;

return -1;

}

private:

unordered_map<string, int> filters_;

};

Solution 2:

C++ / Trie

Time complexity: O(NL^2 + QL) where N is the number of words, L is the max length of the word, Q is the number of queries.

Space complexity: O(NL^2)

// Author: Huahua

// Runtime: 572 ms

class Trie {

public:

/** Initialize your data structure here. */

Trie(): root_(new TrieNode()) {}

/** Inserts a word into the trie. */

void insert(const string& word, int index) {

TrieNode* p = root_.get();

for (const char c : word) {

if (!p->children[c - 'a'])

p->children[c - 'a'] = new TrieNode();

p = p->children[c - 'a'];

// Update index

p->index = index;

}

p->is_word = true;

}

/** Returns the index of word that has the prefix. */

int startsWith(const string& prefix) const {

auto node = find(prefix);

if (!node) return -1;

return node->index;

}

private:

struct TrieNode {

TrieNode():index(-1), is_word(false), children(27, nullptr){}

~TrieNode() {

for (TrieNode* child : children)

if (child) delete child;

}

int index;

int is_word;

vector<TrieNode*> children;

};

const TrieNode* find(const string& prefix) const {

const TrieNode* p = root_.get();

for (const char c : prefix) {

p = p->children[c - 'a'];

if (p == nullptr) break;

}

return p;

}

std::unique_ptr<TrieNode> root_;

};

class WordFilter {

public:

WordFilter(vector<string> words) {

for (int i = 0; i < words.size(); ++i) {

const string& w = words[i];

string key = "{" + w;

trie_.insert(key, i);

for (int j = 0; j < w.size(); ++j) {

key = w[w.size() - j - 1] + key;

trie_.insert(key, i);

}

int f(string prefix, string suffix) {

return trie_.startsWith(suffix + "{" + prefix);

}

private:

Trie trie_;

};

Related Problems:

花花酱 LeetCode 744. Find Smallest Letter Greater Than Target

By zxi on December 11, 2017

Problem:

Given a list of sorted characters letters containing only lowercase letters, and given a target letter target, find the smallest element in the list that is larger than the given target.

Letters also wrap around. For example, if the target is target = 'z' and letters = ['a', 'b'], the answer is 'a'.

Examples:

Input:

letters = ["c", "f", "j"]

target = "a"

Output: "c"

Input:

letters = ["c", "f", "j"]

target = "c"

Output: "f"

Input:

letters = ["c", "f", "j"]

target = "d"

Output: "f"

Input:

letters = ["c", "f", "j"]

target = "g"

Output: "j"

Input:

letters = ["c", "f", "j"]

target = "j"

Output: "c"

Input:

letters = ["c", "f", "j"]

target = "k"

Output: "c"

Note:

letters has a length in range [2, 10000].
letters consists of lowercase letters, and contains at least 2 unique letters.
target is a lowercase letter.

Link: https://leetcode.com/problems/find-smallest-letter-greater-than-target/description/

Idea:

Scan the array Time complexity: O(n)
Binary search Time complexity: O(logn)

Solution 1:

C++ / Scan

// Author: Huahua

// Runtime: 16 ms

class Solution {

public:

char nextGreatestLetter(vector<char>& letters, char target) {

for (const char c : letters)

if (c > target) return c;

return letters.front();

}

};

C++ / Set

// Author: Huahua

// Runtime: 16 ms

class Solution {

public:

char nextGreatestLetter(vector<char>& letters, char target) {

vector<int> seen(26, 0);

for (const char c : letters)

seen[c - 'a'] = 1;

while (true) {

if (++target > 'z') target = 'a';

if (seen[target - 'a']) return target;

}

return ' ';

}

};

C++ / Binary Search

// Author: Huahua

// Runtime: 15 ms

class Solution {

public:

char nextGreatestLetter(vector<char>& letters, char target) {

int l = 0;

int r = letters.size();

while (l < r) {

const int m = l + (r - l) / 2;

if (letters[m] <= target)

l = m + 1;

else

r = m;

}

return letters[l % letters.size()];

}

};

花花酱 LeetCode 164. Maximum Gap

By zxi on December 10, 2017

https://leetcode.com/problems/maximum-gap/description/

Problem:

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

题目大意:

给你一个没有排序的正整数数组。输出排序后，相邻元素的差的最大值(Max Gap)。需要在线性时间内解决。

Example:

Input: [5, 0, 4, 2, 12, 10]

Output: 5

Explanation:

Sorted: [0, 2, 4, 5, 10, 12]

max gap is 10 – 5 = 5

Idea:

Bucket sort. Use n buckets to store all the numbers. For each bucket, only track the min / max value.

桶排序。用n个桶来存放数字。对于每个桶，只跟踪存储最大值和最小值。

max gap must come from two “adjacent” buckets, b[i], b[j], j > i, b[i+1] … b[j – 1] must be empty.

max gap 只可能来自”相邻”的两个桶 b[i] 和 b[j], j > i, b[i] 和 b[j] 之间的桶（如果有）必须为空。

max gap = b[j].min – b[i].min

Time complexity: O(n)

时间复杂度: O(n)

Space complexity: O(n)

空间复杂度: O(n)

Solution:

C++

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

int maximumGap(vector<int>& nums) {

const int n = nums.size();

if (n <= 1) return 0;

const auto mm = minmax_element(nums.begin(), nums.end());

const int range = *mm.second - *mm.first;

const int bin_size = range / n + 1;

vector<int> min_vals(n, INT_MAX);

vector<int> max_vals(n, INT_MIN);

for (const int num : nums) {

const int index = (num - *mm.first) / bin_size;

min_vals[index] = min(min_vals[index], num);

max_vals[index] = max(max_vals[index], num);

}

int max_gap = 0;

int prev_max = max_vals[0];

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

if (min_vals[i] != INT_MAX) {

max_gap = max(max_gap, min_vals[i] - prev_max);

prev_max = max_vals[i];

}

return max_gap;

}

};

花花酱 LeetCode 530. Minimum Absolute Difference in BST

By zxi on December 9, 2017

Link

Problem:

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Example:

Input:

Output:

Explanation:

The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).

Note: There are at least two nodes in this BST.

Idea:

Sorting via inorder traversal gives us sorted values, compare current one with previous one to reduce space complexity from O(n) to O(h).

Solution:

C++ O(n) space

// Author: Huahua

// Runtime: 19 ms

class Solution {

public:

int getMinimumDifference(TreeNode* root) {

std::vector<int> sorted;

inorder(root, sorted);

int min_diff = sorted.back();

for (int i = 1; i < sorted.size(); ++i)

min_diff = min(min_diff, sorted[i] - sorted[i - 1]);

return min_diff;

}

private:

void inorder(TreeNode* root, std::vector<int>& sorted) {

if (!root) return;

inorder(root->left, sorted);

sorted.push_back(root->val);

inorder(root->right, sorted);

}

};

C++ O(h) space

// Author: Huahua

// Runtime: 16 ms

class Solution {

public:

int getMinimumDifference(TreeNode* root) {

min_diff_ = INT_MAX;

prev_ = nullptr;

inorder(root);

return min_diff_;

}

private:

void inorder(TreeNode* root) {

if (!root) return;

inorder(root->left);

if (prev_) min_diff_ = min(min_diff_, root->val - *prev_);

prev_ = &root->val;

inorder(root->right);

}

int* prev_;

int min_diff_;

};

Java

// Author: Huahua

// Runtime: 16 ms

class Solution {

public int getMinimumDifference(TreeNode root) {

prev_ = null;

min_diff_ = Integer.MAX_VALUE;

inorder(root);

return min_diff_;

}

private void inorder(TreeNode root) {

if (root == null) return;

inorder(root.left);

if (prev_ != null) min_diff_ = Math.min(min_diff_, root.val - prev_);

prev_ = root.val;

inorder(root.right);

}

private Integer prev_;

private int min_diff_;

}

Python

"""

Author: Huahua

Runtime: 92 ms

"""

class Solution(object):

def getMinimumDifference(self, root):

def inorder(root):

if not root: return

inorder(root.left)

if self.prev is not None: self.min_diff = min(self.min_diff, root.val - self.prev)

self.prev = root.val

inorder(root.right)

self.prev = None

self.min_diff = float('inf')

inorder(root)

return self.min_diff

Related Problems:

[解题报告] LeetCode 98. Validate Binary Search Tree

Huahua's Tech Road

花花酱 LeetCode 743. Network Delay Time

花花酱 LeetCode 745. Prefix and Suffix Search

花花酱 LeetCode 744. Find Smallest Letter Greater Than Target

花花酱 LeetCode 164. Maximum Gap

花花酱 LeetCode 530. Minimum Absolute Difference in BST