花花酱 LeetCode 210. Course Schedule II

By zxi on December 13, 2017

Problem

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

1	2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

1	4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

Note:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.

题目大意：

给你一些课程和它的先修课程，让你输出修课顺序。如果无法修完所有课程，返回空数组。

Idea

Topological sorting

拓扑排序

Solution 1: Topological Sorting

Time complexity: O(V+E)

Space complexity: O(V+E)

C++

// Author: Huahua

// Runtime: 16 ms

class Solution {

public:

vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {

vector<vector<int>> graph(numCourses);

for(const auto& p : prerequisites)

graph[p.second].push_back(p.first);

// states: 0 = unkonwn, 1 == visiting, 2 = visited

vector<int> v(numCourses, 0);

vector<int> ans;

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

if (dfs(i, graph, v, ans)) return {};

std::reverse(ans.begin(), ans.end());

return ans;

}

private:

bool dfs(int cur, vector<vector<int>>& graph, vector<int>& v, vector<int>& ans) {

if (v[cur] == 1) return true;

if (v[cur] == 2) return false;

v[cur] = 1;

for (const int t : graph[cur])

if (dfs(t, graph, v, ans)) return true;

v[cur] = 2;

ans.push_back(cur);

return false;

}

};

Java

// Author: Huahua

// Runtime: 83 ms

class Solution {

public int[] findOrder(int numCourses, int[][] prerequisites) {

ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

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

graph.add(new ArrayList<Integer>());

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

int course = prerequisites[i][0];

int prerequisite = prerequisites[i][1];

graph.get(course).add(prerequisite);

}

int[] visited = new int[numCourses];

List<Integer> ans = new ArrayList<Integer>();

Integer index = numCourses;

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

if (dfs(i, graph, visited, ans)) return new int[0];

return ans.stream().mapToInt(i->i).toArray();

}

private boolean dfs(int curr, ArrayList<ArrayList<Integer>> graph, int[] visited, List<Integer> ans) {

if (visited[curr] == 1) return true;

if (visited[curr] == 2) return false;

visited[curr] = 1;

for (int next : graph.get(curr))

if (dfs(next, graph, visited, ans)) return true;

visited[curr] = 2;

ans.add(curr);

return false;

}

Related Problems:

花花酱 LeetCode 742. Closest Leaf in a Binary Tree

By zxi on December 12, 2017

Problem:

Given a binary tree where every node has a unique value, and a target key k, find the value of the closest leaf node to target k in the tree.

Here, closest to a leaf means the least number of edges travelled on the binary tree to reach any leaf of the tree. Also, a node is called a leaf if it has no children.

In the following examples, the input tree is represented in flattened form row by row. The actual root tree given will be a TreeNode object.

Example 1:

Input:

root = [1, 3, 2], k = 1

Diagram of binary tree:

/ \

3 2

Output: 2 (or 3)

Explanation: Either 2 or 3 is the closest leaf node to the target of 1.

Example 2:

Input:

root = [1], k = 1

Output: 1

Explanation: The closest leaf node is the root node itself.

Example 3:

Input:

root = [1,2,3,4,null,null,null,5,null,6], k = 2

Diagram of binary tree:

/ \

2 3

Output: 3

Explanation: The leaf node with value 3 (and not the leaf node with value 6) is closest to the node with value 2.

Note:

root represents a binary tree with at least 1 node and at most 1000 nodes.
Every node has a unique node.val in range [1, 1000].
There exists some node in the given binary tree for which node.val == k.

题目大意:

给你一棵树，每个节点的值都不相同。

给定一个节点值，让你找到离这个节点距离最近的叶子节点的值。

Idea:

Shortest path from source to any leaf nodes in a undirected unweighted graph.

问题转换为在无向/等权重的图中找一条从起始节点到任意叶子节点最短路径。

Solution:

C++ / DFS + BFS

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Runtime: 16 ms

class Solution {

public:

int findClosestLeaf(TreeNode* root, int k) {

graph_.clear();

start_ = nullptr;

buildGraph(root, nullptr, k);

queue<TreeNode*> q;

q.push(start_);

unordered_set<TreeNode*> seen;

while (!q.empty()) {

int size = q.size();

while (size-->0) {

TreeNode* curr = q.front();

q.pop();

seen.insert(curr);

if (!curr->left && !curr->right) return curr->val;

for (TreeNode* node : graph_[curr])

if (!seen.count(node)) q.push(node);

}

return 0;

}

private:

void buildGraph(TreeNode* node, TreeNode* parent, int k) {

if (!node) return;

if (node->val == k) start_ = node;

if (parent) {

graph_[node].push_back(parent);

graph_[parent].push_back(node);

}

buildGraph(node->left, node, k);

buildGraph(node->right, node, k);

}

unordered_map<TreeNode*, vector<TreeNode*>> graph_;

TreeNode* start_;

};

花花酱 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()];

}

};

Huahua's Tech Road

花花酱 LeetCode 210. Course Schedule II

Problem

Idea

Solution 1: Topological Sorting

C++

Java

Related Problems:

花花酱 LeetCode 742. Closest Leaf in a Binary Tree

花花酱 LeetCode 743. Network Delay Time

花花酱 LeetCode 745. Prefix and Suffix Search

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