Breadth First Search
Traversal
102. Binary Tree Level Order Traversal
107. Binary Tree Level Order Traversal II
199. Binary Tree Right Side View
BFS 可以解这一题, 但是是 O(N) 的解法, 用 DFS 可以到 O(Log(N))
vector<int> rightSideView(TreeNode* root) {
vector<int> res;
if (!root) return res;
dfs(root, res, 1);
return res;
}
void dfs(TreeNode* root, vector<int>& res, int level) {
if (!root) return;
if (res.size() < level) res.push_back(root->val);
dfs(root->right, res, level + 1);
dfs(root->left, res, level + 1);
}
103. Binary Tree Zigzag Level Order Traversal
133. Clone Graph
Connected Component / Cycle Detction
261. Graph Valid Tree
323. Number of Connected Components in an Undirected Graph
200. Number of Islands
Topological Sort
使用 BFS 进行拓扑排序的关键就是要构造入度图.
207. Course Schedule
实际上就是检测环
using graph_t = vector<unordered_set<int>>;
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
graph_t graph(numCourses);
vector<int> degree(graph.size());
queue<int> zeros;
for (auto course : prerequisites) graph[course.second].insert(course.first);
for (auto v : graph)
for (auto w : v)
degree[w]++;
for (int j = 0; j < numCourses; ++j)
if (degree[j] == 0) zeros.push(j);
while (!zeros.empty()) {
auto cur = zeros.front(); zeros.pop();
numCourses--;
for (auto v : graph[cur]) {
if (--degree[v] == 0) zeros.push(v);
}
}
return numCourses == 0;
}
Multi End BFS
Multi End BFS 的技巧就是同时从多点开始进行遍历.
310. Minimum Height Trees
130. Surrounded Regions
将所有边上的为O的点加入到初始化队列进行 BFS. 没有被 visited 的点就可以直接设为 X
286. Walls and Gates
126. Word Ladder II
这一题既要自己构造 graph, 又要进行 multi end BFS, 还要构造路径. 需要经常看看.
317. Shortest Distance from All Buildings
126. Word Ladder II
305. Number of Islands II
Implicit Graph
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n. For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
解题的关键在于构造 Graph. 要求最小的 squre 数, 那么自身为平方数的自然就是第一层了, 那第二层就可以通过第一层的数亮亮相加来得到, 第三层可以通过第一层和第二层两两相加得到, 以此类推,直到得到所需的数.
int numSquares(int n) {
if (n <= 1) return n;
vector<int> squares;
vector<int> cnt(n+1);
queue<int> q;
for (int i = 1; i*i <= n; ++i) {
squares.push_back(i*i);
cnt[i*i] = 1;
q.push(i*i);
}
if (squares.back() == n) return 1;
int num = 1;
while (!q.empty()) {
num++;
int len = q.size();
while (len--) {
int cur = q.front(); q.pop();
for (auto j : squares) {
if (cur + j == n) {
return num;
} else if (cur + j < n && cnt[cur + j] == 0) {
cnt[cur + j] = num;
q.push(cur+j);
} else if (cur + j > n) break;
}
}
}
return 0;
}
301. Remove Invalid Parentheses
同样也是要隐式的构造树, 当前层就是原字符串, 下一层就是移除一个字符后的所有可能的串.
class Solution {
public:
vector<string> removeInvalidParentheses(string s) {
vector<string> res;
unordered_set<string> visited;
if (isValid(s)) return {s};
queue<string> q;
q.push(s);
visited.insert(s);
bool found = false;
while (!q.empty()) {
auto str = q.front(); q.pop();
if (isValid(str)) {
found = true;
res.push_back(str);
}
if (found) {
continue;
}
for (size_t i = 0; i < str.size(); ++i) {
if (str[i] != ')' && str[i] != '(') continue;
string next = str.substr(0, i) + str.substr(i+1);
if (visited.find(next) == visited.end()) {
q.push(next);
visited.insert(next);
}
}
}
return res;
}
bool isValid(const string& str) {
int cnt = 0;
for (auto ch : str) {
if (ch == '(') cnt++;
else if (ch == ')') {
if (--cnt < 0) return false;
}
}
return cnt == 0;
}
};
对应的 DFS 的解法为
vector<string> removeInvalidParentheses(string s) {
vector<string> res;
vector<string> allres;
int max_len = 0;
std::function<void(string, int, int, int)> dfs = [&](string cur, int pos, int left, int right) {
if (left == right && cur.size() >= max_len) {
allres.push_back(cur);
max_len = cur.size();
}
for (int i= pos; i < s.size(); ++i) {
if (i != pos && s[i] == s[i-1]) continue;
if (s[i] == '(') dfs(cur+s[i], i+1, left+1, right);
else if (s[i] == ')' && left > right) dfs(cur+s[i], i + 1, left, right+1);
else if (s[i] != ')') dfs(cur+s[i], i + 1, left, right);
}
};
dfs("", 0, 0, 0);
for (auto str : allres) {
if (str.size() >= max_len) res.push_back(str);
}
return res;
}