Posts tagged as “BFS”

花花酱 LeetCode 863. All Nodes Distance K in Binary Tree

By zxi on June 30, 2018

Problem

题目大意：给你一棵二叉树（根结点root）和一个target节点。返回所有到target的距离为K的节点。

We are given a binary tree (with root node root), a target node, and an integer value K.

Return a list of the values of all nodes that have a distance K from the target node. The answer can be returned in any order.

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2
Output: [7,4,1]
Explanation: 
The nodes that are a distance 2 from the target node (with value 5)
have values 7, 4, and 1.

Note that the inputs "root" and "target" are actually TreeNodes.
The descriptions of the inputs above are just serializations of these objects.

Note:

The given tree is non-empty.
Each node in the tree has unique values 0 <= node.val <= 500.
The target node is a node in the tree.
0 <= K <= 1000.

Solution1: DFS + BFS

Use DFS to build the graph, and use BFS to find all the nodes that are exact K steps from target.

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {

buildGraph(nullptr, root);

vector<int> ans;

unordered_set<TreeNode*> seen;

queue<TreeNode*> q;

seen.insert(target);

q.push(target);

int k = 0;

while (!q.empty() && k <= K) {

int s = q.size();

while (s--) {

TreeNode* node = q.front(); q.pop();

if (k == K) ans.push_back(node->val);

for (TreeNode* child : g[node]) {

if (seen.count(child)) continue;

q.push(child);

seen.insert(child);

}

++k;

}

return ans;

}

private:

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

void buildGraph(TreeNode* parent, TreeNode* child) {

if (parent) {

g[parent].push_back(child);

g[child].push_back(parent);

}

if (child->left) buildGraph(child, child->left);

if (child->right) buildGraph(child, child->right);

}

};

Array version

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {

constexpr int kMaxN = 500 + 1;

g = vector<vector<int>>(kMaxN);

buildGraph(nullptr, root);

vector<int> ans;

vector<int> seen(kMaxN);

queue<int> q;

seen[target->val] = 1;

q.push(target->val);

int k = 0;

while (!q.empty() && k <= K) {

int s = q.size();

while (s--) {

int node = q.front(); q.pop();

if (k == K) ans.push_back(node);

for (int child : g[node]) {

if (seen[child]) continue;

q.push(child);

seen[child] = 1;

}

++k;

}

return ans;

}

private:

vector<vector<int>> g;

void buildGraph(TreeNode* parent, TreeNode* child) {

if (parent) {

g[parent->val].push_back(child->val);

g[child->val].push_back(parent->val);

}

if (child->left) buildGraph(child, child->left);

if (child->right) buildGraph(child, child->right);

}

};

Solution 2: Recursion

Recursively compute the distance from root to target, and collect nodes accordingly.

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 5 ms

class Solution {

public:

vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {

ans.clear();

dis(root, target, K);

return ans;

}

private:

vector<int> ans;

// Returns the distance from root to target.

// Returns -1 if target does not in the tree.

int dis(TreeNode* root, TreeNode* target, int K) {

if (root == nullptr) return -1;

if (root == target) {

collect(target, K);

return 0;

}

int l = dis(root->left, target, K);

int r = dis(root->right, target, K);

// Target in the left subtree

if (l >= 0) {

if (l == K - 1) ans.push_back(root->val);

// Collect nodes in right subtree with depth K - l - 2

collect(root->right, K - l - 2);

return l + 1;

}

// Target in the right subtree

if (r >= 0) {

if (r == K - 1) ans.push_back(root->val);

// Collect nodes in left subtree with depth K - r - 2

collect(root->left, K - r - 2);

return r + 1;

}

return -1;

}

// Collect nodes that are d steps from root.

void collect(TreeNode* root, int d) {

if (root == nullptr || d < 0) return;

if (d == 0) ans.push_back(root->val);

collect(root->left, d - 1);

collect(root->right, d - 1);

}

};

花花酱 LeetCode 847. Shortest Path Visiting All Nodes

By zxi on June 3, 2018

Problem

题目大意：求顶点覆盖的最短路径。

https://leetcode.com/problems/shortest-path-visiting-all-nodes/description/

An undirected, connected graph of N nodes (labeled 0, 1, 2, ..., N-1) is given as graph.

graph.length = N, and j != i is in the list graph[i] exactly once, if and only if nodes i and j are connected.

Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.

Example 1:

Input: [[1,2,3],[0],[0],[0]]
Output: 4
Explanation: One possible path is [1,0,2,0,3]

Example 2:

Input: [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]

Solution: BFS

Time complexity: O(n*2^n)

Space complexity: O(n*2^n)

C++

// Author: Huahua

// Running time: 34 ms

class Solution {

public:

int shortestPathLength(vector<vector<int>>& graph) {

const int kAns = (1 << (graph.size())) - 1;

queue<pair<int, int>> q;

unordered_set<int> visited; // (cur_node << 16) | state

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

q.push({i, 1 << i});

int steps = 0;

while (!q.empty()) {

int s = q.size();

while (s--) {

auto p = q.front();

q.pop();

int n = p.first;

int state = p.second;

if (state == kAns) return steps;

int key = (n << 16) | state;

if (visited.count(key)) continue;

visited.insert(key);

for (int next : graph[n])

q.push({next, state | (1 << next)});

}

++steps;

}

return -1;

}

};

C++ / vector

// Author: Huahua

// Running time: 10 ms

class Solution {

public:

int shortestPathLength(vector<vector<int>>& graph) {

const int n = graph.size();

const int kAns = (1 << n) - 1;

queue<pair<int, int>> q;

vector<vector<int>> visited(n, vector<int>(1 << n));

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

q.push({i, 1 << i});

int steps = 0;

while (!q.empty()) {

int s = q.size();

while (s--) {

auto p = q.front();

q.pop();

int node = p.first;

int state = p.second;

if (state == kAns) return steps;

if (visited[node][state]) continue;

visited[node][state] = 1;

for (int next : graph[node])

q.push({next, state | (1 << next)});

}

++steps;

}

return -1;

}

};

Problem

题目大意：给你每辆公交车的环形路线，问最少需要坐多少辆公交车才能送S到达T。

https://leetcode.com/problems/bus-routes/description/

We have a list of bus routes. Each routes[i] is a bus route that the i-th bus repeats forever. For example if routes[0] = [1, 5, 7], this means that the first bus (0-th indexed) travels in the sequence 1->5->7->1->5->7->1->… forever.

We start at bus stop S (initially not on a bus), and we want to go to bus stop T. Travelling by buses only, what is the least number of buses we must take to reach our destination? Return -1 if it is not possible.

Example:
Input: 
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 6
Output: 2
Explanation: 
The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

Note:

1 <= routes.length <= 500.
1 <= routes[i].length <= 500.
0 <= routes[i][j] < 10 ^ 6.

Solution: BFS

Time Complexity: O(m*n) m: # of buses, n: # of routes

Space complexity: O(m*n + m)

C++

// Author: Huahua

// Running time: 89 ms

class Solution {

public:

int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {

if (S == T) return 0;

unordered_map<int, vector<int>> m;

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

for (const int stop : routes[i])

m[stop].push_back(i);

vector<int> visited(routes.size(), 0);

queue<int> q;

q.push(S);

int buses = 0;

while (!q.empty()) {

int size = q.size();

++buses;

while (size--) {

int curr = q.front(); q.pop();

for (const int bus : m[curr]) {

if (visited[bus]) continue;

visited[bus] = 1;

for (int stop : routes[bus]) {

if (stop == T) return buses;

q.push(stop);

}

return -1;

}

};

花花酱 LeetCode 433. Minimum Genetic Mutation

By zxi on March 24, 2018

Problem

题目大意：给你一个基因库，问一个基因最少需要变异多少次才能变为另外一个基因。每次变异只能修改一个字符，并且必须在基因库里。

https://leetcode.com/problems/minimum-genetic-mutation/description/

A gene string can be represented by an 8-character long string, with choices from "A", "C", "G", "T".

Suppose we need to investigate about a mutation (mutation from “start” to “end”), where ONE mutation is defined as ONE single character changed in the gene string.

For example, "AACCGGTT" -> "AACCGGTA" is 1 mutation.

Also, there is a given gene “bank”, which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string.

Now, given 3 things – start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from “start” to “end”. If there is no such a mutation, return -1.

Note:

Starting point is assumed to be valid, so it might not be included in the bank.
If multiple mutations are needed, all mutations during in the sequence must be valid.
You may assume start and end string is not the same.

Example 1:

start: "AACCGGTT"
end:   "AACCGGTA"
bank: ["AACCGGTA"]

return: 1

Example 2:

start: "AACCGGTT"
end:   "AAACGGTA"
bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]

return: 2

Example 3:

start: "AAAAACCC"
end:   "AACCCCCC"
bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]

return: 3

Solution: BFS Shortest Path

Time complexity: O(n^2)

Space complexity: O(n)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int minMutation(string start, string end, vector<string>& bank) {

queue<string> q;

q.push(start);

unordered_set<string> visited;

visited.insert(start);

int mutations = 0;

while (!q.empty()) {

size_t size = q.size();

while (size--) {

string curr = std::move(q.front()); q.pop();

if (curr == end) return mutations;

for (const string& gene : bank) {

if (visited.count(gene) || !validMutation(curr, gene)) continue;

visited.insert(gene);

q.push(gene);

}

++mutations;

}

return -1;

}

private:

bool validMutation(const string& s1, const string& s2) {

int count = 0;

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

if (s1[i] != s2[i] && count++) return false;

return true;

}

};

花花酱 LeetCode 787. Cheapest Flights Within K Stops

By zxi on February 22, 2018

题目大意：给你一些城市之间的机票价格，问从src到dst的最少需要花多少钱，最多可以中转k个机场。

There are n cities connected by m flights. Each fight starts from city u and arrives at v with a price w.

Now given all the cities and fights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1.

Example 1:

Input:

n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]

src = 0, dst = 2, k = 1

Output: 200

Explanation:

The graph looks like this:

The cheapest price from city <code>0</code> to city <code>2</code> with at most 1 stop costs 200, as marked red in the picture.

Example 2:

Input:

n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]

src = 0, dst = 2, k = 0

Output: 500

Explanation:

The graph looks like this:

The cheapest price from city <code>0</code> to city <code>2</code> with at most 0 stop costs 500, as marked blue in the picture.

Note:

The number of nodes n will be in range [1, 100], with nodes labeled from 0 to n - 1.
The size of flights will be in range [0, n * (n - 1) / 2].
The format of each flight will be (src, dst, price).
The price of each flight will be in the range [1, 10000].
k is in the range of [0, n - 1].
There will not be any duplicated flights or self cycles.

Solution 1: DFS

w/o prunning TLE

w/ prunning Accepted

C++

// Author: Huahua

// Running time: 36 ms

class Solution {

public:

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {

g_.clear();

for (const auto& e : flights)

g_[e[0]].emplace_back(e[1], e[2]);

vector<int> visited(n, 0);

visited[src] = 1;

int ans = INT_MAX;

dfs(src, dst, K + 1, 0, visited, ans);

return ans == INT_MAX ? - 1 : ans;

}

private:

unordered_map<int, vector<pair<int,int>>> g_;

void dfs(int src, int dst, int k, int cost, vector<int>& visited, int& ans) {

if (src == dst) {

ans = cost;

return;

}

if (k == 0) return;

for (const auto& p : g_[src]) {

if (visited[p.first]) continue; // do not visit the same city twice.

if (cost + p.second > ans) continue; // IMPORTANT!!! prunning

visited[p.first] = 1;

dfs(p.first, dst, k - 1, cost + p.second, visited, ans);

visited[p.first] = 0;

}

};

Solution 2: BFS

C++

// Author: Huahua

// Running time: 20 ms

class Solution {

public:

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {

unordered_map<int, vector<pair<int,int>>> g;

for (const auto& e : flights)

g[e[0]].emplace_back(e[1], e[2]);

int ans = INT_MAX;

queue<pair<int,int>> q;

q.push({src, 0});

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

int curr = q.front().first;

int cost = q.front().second;

q.pop();

if (curr == dst)

ans = min(ans, cost);

for (const auto& p : g[curr]) {

if (cost + p.second > ans) continue; // Important: prunning

q.push({p.first, cost + p.second});

}

if (steps++ > K) break;

}

return ans == INT_MAX ? - 1 : ans;

}

};

Solution 3: Bellman-Ford algorithm

dp[k][i]: min cost from src to i taken up to k flights (k-1 stops)

init: dp[0:k+2][src] = 0

transition: dp[k][i] = min(dp[k-1][j] + price[j][i])

ans: dp[K+1][dst]

Time complexity: O(k * |flights|) / O(k*n^2)

Space complexity: O(k*n) -> O(n)

w/o space compression O(k*n)

C++ O(k*n)

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {

constexpr int kInfCost = 1e9;

vector<vector<int>> dp(K + 2, vector<int>(n, kInfCost));

dp[0][src] = 0;

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

dp[i][src] = 0;

for (const auto& p : flights)

dp[i][p[1]] = min(dp[i][p[1]], dp[i-1][p[0]] + p[2]);

}

return dp[K + 1][dst] >= kInfCost ? -1 : dp[K + 1][dst];

}

};

C++ O(n)

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {

constexpr int kInfCost = 1e9;

vector<int> cost(n, kInfCost);

cost[src] = 0;

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

vector<int> tmp(cost);

for (const auto& p : flights)

tmp[p[1]] = min(tmp[p[1]], cost[p[0]] + p[2]);

cost.swap(tmp);

}

return cost[dst] >= kInfCost ? -1 : cost[dst];

}

};

Java

// Author: Huahua

// Running time: 11 ms

class Solution {

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {

final int kInfCost = 1<<30;

int[] cost = new int[n];

Arrays.fill(cost, kInfCost);

cost[src] = 0;

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

int[] tmp = cost.clone();

for(int[] p: flights)

tmp[p[1]] = Math.min(tmp[p[1]], cost[p[0]] + p[2]);

cost = tmp;

}

return cost[dst] >= kInfCost ? -1 : cost[dst];

}

Python3

"""

Author: Huahua

Running time: 132 ms

"""

class Solution:

def findCheapestPrice(self, n, flights, src, dst, K):

kInfCost = 1e9

cost = [kInfCost for _ in range(n)]

cost[src] = 0

for i in range(K + 1):

tmp = list(cost)

for p in flights:

tmp[p[1]] = min(tmp[p[1]], cost[p[0]] + p[2])

cost = tmp

return -1 if cost[dst] >= 1e9 else cost[dst]

Posts tagged as “BFS”

花花酱 LeetCode 863. All Nodes Distance K in Binary Tree

Problem

Solution1: DFS + BFS

Solution 2: Recursion

花花酱 LeetCode 847. Shortest Path Visiting All Nodes

Problem

Solution: BFS

Related Problems

花花酱 LeetCode 815. Bus Routes

Problem

Solution: BFS

花花酱 LeetCode 433. Minimum Genetic Mutation

Problem

Solution: BFS Shortest Path

花花酱 LeetCode 787. Cheapest Flights Within K Stops

Solution 1: DFS

C++

Solution 2: BFS

C++

Solution 3: Bellman-Ford algorithm

C++ O(k*n)

C++ O(n)

Java

Python3