前言
身在大 CS 時代，有越來越多人投入刷題的行列，在眼花撩亂的題海中，要想有效率地刷題，就需要掌握題目解法中，可以在許多地方應用的觀念，才能以簡禦繁。 Huli 寫的 程式解題新手入門注意事項 講得很好，寫題目是為了學會解題的思考方法，確保自己掌握重要的資料結構跟演算法。這也是為什麼我想要寫這系列的文章，把多個散落在各處的題目銜接起來，以後看到相似的問題就可以舉一反三，而不是去背各題目的解法。
舉例來說，之前遇過一題電話面試，問到的題目是：
Input: vector<bool> holidays, int pto
holidays 表示平日或假日，例如 0000011 表示前面 5 天是平日，後面 2 天是假日。
pto 表示最多可以放幾天假。
Output: 計算在可以用完 pto 的情況下，最久可以放多長的假。
範例：holidays = {0,0,0,0,0,1,1}, pto = 2, output = 4
因為可以放 {0,0,0,1,1,1,1}
基本上因為之前有寫過 Sliding Window 的 pattern，所以這題很快就寫出來了，也順利進到下一關，所以大家不需要追求把題目都刷完，而是掌握好重要的基礎，接下來就是應用這些基礎就可以面對很多變化題（當然還是會有一些解法很巧妙的題目，但其實大部分公司不會硬出巧妙題）。
放上程式碼給大家參考：
#include <iostream>
#include <vector>
using namespace std;
int longest_holidays(const vector<bool>& holidays, int pto) {
int longestHoliday = -1, windowStart = 0;
for(int windowEnd = 0; windowEnd < holidays.size(); ++windowEnd) {
if(holidays[windowEnd] == 0) {
-- pto;
}
// Shrink window size
while(pto < 0) {
if(holidays[windowStart++] == 0) {
++ pto;
}
}
// Compare valid window size and longestHoliday
longestHoliday = max(longestHoliday, windowEnd - windowStart + 1);
}
return longestHoliday;
}
int main(){
// 000001100000110000111
vector<bool> holidays = {0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,1,1,1};
int longest_holiday = longest_holidays(holidays, 9);
cout << "My longest holiday: " << longest_holiday << ", hooray!\n";
return 0;
}
上面這題還有一個 follow-up 問題，可以看我的 面經分享。
Breadth-First Search 簡介
言歸正傳，今天要來跟大家介紹相當基礎的演算法 pattern - Breadth-First Search，雖然 BFS 是基礎中的基礎，大家多少都會，但你真的確定自己除了在 tree 跟 graph 這些顯而易見的題型以外，都能活用 BFS 嗎？
我們先看一個題目 - Leetcode #279 - Perfect Squares：
如果沒什麼刷題經驗，可能會想要用暴力的枚舉方法來解這個問題；如果有一些刷題經驗，可能會想到用 Dynamic Programming 來解。但其實，這題也可以用 BFS 解！而且實作非常簡單，舉這個例子是想讓大家看看 BFS 也可以應用在沒有明顯 graph 結構的問題上，我們會在第四個範例中解釋怎麼用 BFS 來解這題。
在進到題目之前，先給大家 BFS 實作的模板，這樣只要寫過幾題，之後在實作 BFS 就不容易出錯，因為基本的模板相通，只要將注意力集中在各題目不同的細節上就好。
BFS template 1
BFS 跟 queue 這個資料結構是好夥伴，使用 queue 讓 BFS 的實作變得很簡單，比如說下面這個嘗試計算 root node 跟 target node 距離的 pseudo code：
/**
* Return the length of the shortest path between root and target node.
*/
int BFS(Node root, Node target) {
queue<Node> queue; // store all nodes which are waiting to be processed
step = 0; // number of steps neeeded from root to current node
// initialize
add root to queue;
// BFS
while (queue is not empty) {
step = step + 1;
// iterate the nodes which are already in the queue
int size = q.size();
for (int i = 0; i < size; ++i) {
Node cur = the first node in queue;
return step if cur is target;
for (Node next : the neighbors of cur) {
add next to queue;
}
remove the first node from queue;
}
}
return -1; // there is no path from root to target
}
BFS template 2
有時候，我們必須要避免走到重複的 node（例如在 cyclic graph 中，就可能又走回起點），才不會讓 BFS 無法結束，所以需要紀錄哪些 node 已經走過，模板如下：
/**
* Return the length of the shortest path between root and target node.
*/
int BFS(Node root, Node target) {
queue<Node> queue; // store all nodes which are waiting to be processed
Set<Node> visited; // store all the nodes that we've visited
step = 0; // number of steps neeeded from root to current node
// initialize
add root to queue;
add root to visited;
// BFS
while (queue is not empty) {
step = step + 1;
// iterate the nodes which are already in the queue
int size = queue.size();
for (int i = 0; i < size; ++i) {
Node cur = the first node in queue;
return step if cur is target;
for (Node next : the neighbors of cur) {
if (next is not in visited) {
add next to queue;
add next to visited;
}
}
remove the first node from queue;
}
}
return -1; // there is no path from root to target
}
Breadth-First Search 的第一個範例 - Leetcode #286 - Walls and Gates
題目
這個題目比較明顯有 graph 的樣子，因為每一步都只能走到上/下/左/右的其中一個鄰居，而且是要找 "距離最近" 的門，所以比較直覺會想到可以用 BFS，我們就直接來看看解法。
Breadth-First Search 解法
要做 BFS，我們有兩種選擇，第一種是從每個房間開始，尋找離這個房間最近的門；第二種則是先把每個門都放進 queue 裡面，每次都只走一步，如果遇到的是房間，就更新房間到門口的步數。
雖然這題的想法很簡單，可是如果你對 BFS 的模板還不是很熟，還是會需要花一些時間想一想邏輯要怎麼寫的，所以不用緊張，慢慢地想過一遍，盡力自己寫寫看，寫不出來就看看答案，看完自己想一遍再寫，反覆幾次就會越來越熟悉。提供一份 C++ 版本的實作如下：
class Solution {
public:
void wallsAndGates(vector<vector<int>>& rooms) {
// Check corner cases
int m = rooms.size();
if(m < 1) { return; }
int n = rooms[0].size();
if(n < 1) { return; }
// Prepare for BFS
int GATE = 0, WALL = -1, ROOM = numeric_limits<int>::max();
queue<pair<int,int>> q;
vector<pair<int,int>> dirs{{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
// Put all gates into queue
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
if(rooms[i][j] == GATE) q.push({i,j});
}
}
// Start BFS
int steps = 0;
while(!q.empty()) {
for(int sz = q.size()-1; sz >= 0; --sz) {
pair<int, int> cur = q.front();
q.pop();
if(rooms[cur.first][cur.second] == ROOM) {
rooms[cur.first][cur.second] = steps;
}
if(rooms[cur.first][cur.second] != WALL) {
// Traverse neighbor
for(int i = 0; i < dirs.size(); ++i) {
cur.first += dirs[i].first;
cur.second += dirs[i].second;
if(isValid(cur, m, n) && rooms[cur.first][cur.second] == ROOM) {
q.push(cur);
}
cur.first -= dirs[i].first;
cur.second -= dirs[i].second;
}
}
}
++steps;
}
}
private:
bool isValid(const pair<int, int>& cur, const int& m, const int& n) {
return cur.first >= 0 && cur.first < m && cur.second >= 0 && cur.second < n;
}
};
Breadth-First Search 的第二個範例 - Leetcode #200 - Number of Islands
題目
Depth-First Search 解法
這題應該算是非常經典的問題，目前在面試中出現的頻率也還是很高，以寫程式的簡潔度來說，DFS 是比較容易寫的，概念上就是，每次我們遇到一個島的邊界（也就是 '1' 的地方），我們就呼叫 DFS function 把跟這個 '1' 相鄰的 '1' 都變成 '0'，實作如下：
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m = grid.size(), n = m ? grid[0].size() : 0, islands = 0;
// 走過矩陣的所有 element，只要遇到島，就把島都消滅(即 '1' -> '0')
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
islands++;
dfs(grid, m, n, i, j);
}
}
}
return islands;
}
private:
void dfs(vector<vector<char>>& grid, const int& m, const int& n, const int& i, const int& j) {
if(grid[i][j] == '0') return;
grid[i][j] = '0';
if(i - 1 >= 0) { dfs(grid, m, n, i-1, j); }
if(i + 1 < m) { dfs(grid, m, n, i+1, j); }
if(j - 1 >= 0) { dfs(grid, m, n, i, j-1); }
if(j + 1 < n) { dfs(grid, m, n, i, j+1); }
}
};
Breadth-First Search 解法
DFS 的實作雖然簡潔，可是，如果輸入的矩陣非常大，並且包含著很大的島，那隨著 DFS 的遞迴呼叫層數增加，是有可能產生 stack overflow 的，所以如果能用 BFS 解決，就會是比較安全的解法。
一樣，雖然想法上很簡單，但實作上還是需要多寫幾次才會熟悉，附上一份 BFS 的實作給大家參考：
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m = grid.size(), n = m ? grid[0].size() : 0, islands = 0, offsets[] = {0, 1, 0, -1, 0};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
islands++;
grid[i][j] = '0';
queue<pair<int, int>> todo;
todo.push({i, j});
while (!todo.empty()) {
pair<int, int> p = todo.front();
todo.pop();
for (int k = 0; k < 4; k++) {
int r = p.first + offsets[k], c = p.second + offsets[k + 1];
if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == '1') {
grid[r][c] = '0';
todo.push({r, c});
}
}
}
}
}
}
return islands;
}
};
Breadth-First Search 的第三個範例 - Leetcode #752 - Open the Lock
題目
這一題開始變得比較有趣，因為一看到這個題目的時候，未必會想到要用 BFS，所以接下來，讓我先分享一下思考的方法。
思考方法
這題雖然乍看之下不會直接想到要用 BFS，但其實還是有很多蛛絲馬跡，比如說：
- 我們從 0000 開始，所以有一個起點。
- 希望尋找的是 0000 到 target 之間的 "最短距離"。
看到這兩個提示，腦海中就會開始浮現一個從 0000 為 root，開始探索直到走到 target 的一個搜尋過程：
0000 -> 1000, 9000, 0100, 0900, 0010, 0090, 0001, 0009 -> ... -> ... -> target
所以就開始有可以使用 BFS 的影子出現。換句話說，因為看到有起點、要求最短距離，所以想了 "走一步" 是什麼意思？然後想到就是把其中一個數字 +1 或 -1。接著就可以再延伸，發現這就是一個從 0000 開始，然後假設 deadends 是已經 visit 過所以不能再走，的一個 BFS 問題。
Breadth-First Search 解法
class Solution {
public:
int openLock(vector<string>& deadends, string target) {
// Prepare for BFS
// 因為不能走到 deadends 裡面的排列，所以我們直接放進 visited，這樣做 BFS 時就不會考慮這些路線
unordered_set<string> visited(deadends.begin(), deadends.end());
array<char, 10> digit= {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
queue<string> todo;
// 假設 0000 沒有在 visited(也就是 deadends 裡沒有) 中，我們才需要開始尋找
if(!visited.count("0000")) {
todo.push("0000");
visited.insert("0000");
}
// Start BFS
int steps = -1;
while(!todo.empty()) {
++steps;
for(int sz = todo.size() - 1; sz >= 0; --sz) {
string cur = todo.front();
todo.pop();
// Check if it's target
if(cur == target) {
return steps;
}
// Go through neighbors
// 如何找到對的 neighbor 也是這題比較 tricky 的地方之一
for(int i = 0; i < 4; ++i) {
for(int j = -1; j <= 1; j += 2) {
string neighbor = cur;
// Wrap around index to prevent out-of-bound error
neighbor[i] = digit[(neighbor[i]-'0'+j+10) % 10];
if(!visited.count(neighbor)) {
todo.push(neighbor);
visited.insert(neighbor);
}
}
}
}
}
return -1;
}
};
寫完這題，如果你是 BFS 新手，應該會覺得頗好玩，因為這題的鄰居找法跟之前有明顯 matrix 結構的情況不太一樣，而是變成在另一個抽象的搜索空間中做 BFS。
Breadth-First Search 的第四個範例 - Leetcode #279 - Perfect Squares
題目
暴力解
暴力法很直覺，反正就每種組合都試試看就對了，例如若要看 12 至少要由幾個 perfect suqare number 組成，那就看 "1 至少要幾個 + 11 至少要幾個"、"2 至少要幾個 + 10 至少要幾個" ... 依此類推，直到比較過所有可能的拆分方法，就知道最少要幾個，實作如下：
class Solution {
public:
int numSquares(int n) {
if(isPerfectSquare(n)) {
return 1;
}
int res = n;
for(int i = 1; i <= n / 2; ++i) {
int comb = numSquares(i) + numSquares(n - i);
if(comb < res) {
res = comb;
}
}
return res;
}
private:
bool isPerfectSquare(double x) {
// Find floating point value of square root of x.
double sr = sqrt(x);
// If square root is an integer
return ((sr - floor(sr)) == 0);
}
};
很顯然，這種方法有夠慢，在 leetcode 上面跑也確實會超時。雖然可以用 memoization、Dynamic Programming，不過今天的重點是 BFS，所以我們來探討一下 BFS 解。
Breadth-First Search 解法
如果你有辦法想到 BFS，應該會覺得滿好玩的。這題的思路如下：
- 如果 n 是 perfect square，答案就是 1。
- 如果 n 可以由兩個 perfect square 組成，答案就是 2。
所以我們如果要使用 BFS，起點就是所有的 perfect square！
看一個範例：
n = 12
起點：1, 4, 9
走一步：1+1 = 2, 1+4 = 5, 1 + 9 = 10, 4+4 = 8
走兩步：2+1 = 3, 2+4 = 6, 2+9 = 11...
所以，每次要拜訪的鄰居就是 queue 裡面的數字再加上一個 perfect square！
想懂觀念之後，實作出來就只是時間問題：
class Solution {
public:
int numSquares(int n) {
// Declare data structure for BFS
unordered_set<int> visited;
queue<int> todo;
todo.push(0);
visited.insert(0);
// Start BFS
int steps = 0;
while(!todo.empty()) {
++steps;
for(int sz = todo.size() - 1; sz >= 0; --sz) {
// Retrieve current int
int cur = todo.front();
todo.pop();
for(int j = 1; j < n; ++j) {
int sum = cur + j * j;
if(sum == n) { return steps; }
else if(sum > n) { break; }
else{
if(!visited.count(sum)) {
todo.push(sum);
visited.insert(sum);
}
}
}
}
}
return steps;
}
};
Breadth-First Search 的第五個範例 - Leetcode #1284 - Minimum Number of Flips to Convert Binary Matrix to Zero Matrix
題目
這一題是我在某一週的 Leetcode contest 寫到的，因為當時我正好寫完上面四個 BFS 的範例題，對 BFS 的 pattern 很有感覺，所以這題很快就寫出來了。
Breadth-First Search 解法
因為概念上跟第三個範例有點像，都是在自己想像中的搜索空間中進行 BFS，所以這題的想法我就不贅述了，基本上就是把整個 matrix 的狀態當作 node，每翻一次就是走一步，就可以用 BFS 解決了，附上程式碼：
class Solution {
public:
int minFlips(vector<vector<int>>& mat) {
// Check corner cases
int m = mat.size();
int n = m ? mat[0].size() : 0;
if(m < 1 or n < 1) { return -1; }
// Prepare for BFS
set<vector<vector<int>>> visited;
queue<vector<vector<int>>> q;
q.push(mat);
visited.insert(mat);
int steps = 0;
while(!q.empty()) {
for(int sz = q.size() - 1; sz >= 0; --sz) {
vector<vector<int>> cur = q.front();
q.pop();
// 已經成功翻成全部都是 0
if(allZero(cur)) {
return steps;
}
for(int r = 0; r < m; ++r) {
for(int c = 0; c < n; ++c) {
// 以 (r,c) 為中心翻一次 matrix
flip(cur, m, n, r, c);
// 如果還沒走過這個盤面，放入 queue
if(!visited.count(cur)) {
q.push(cur);
visited.insert(cur);
}
// 把盤面翻回來
flip(cur, m, n, r, c);
}
}
}
++steps;
}
return -1;
}
private:
void flip(vector<vector<int>>& mat, int& m, int& n, int& r, int& c) {
// 翻鄰居
if(r - 1 >= 0) { mat[r-1][c] = (mat[r-1][c] == 1) ? 0 : 1; }
if(r + 1 < m) { mat[r+1][c] = (mat[r+1][c] == 1) ? 0 : 1; }
if(c - 1 >= 0) { mat[r][c-1] = (mat[r][c-1] == 1) ? 0 : 1; }
if(c + 1 < n) { mat[r][c+1] = (mat[r][c+1] == 1) ? 0 : 1; }
// 翻(r,c)
mat[r][c] = (mat[r][c] == 1) ? 0 : 1;
}
bool allZero(const vector<vector<int>>& mat) {
for(int i = 0; i < mat.size(); ++i) {
for(int j = 0; j < mat[0].size(); ++j) {
if(mat[i][j] != 0) {
return false;
}
}
}
return true;
}
};
總結
今天跟大家介紹了一個新的 pattern - Breadth-First Search，上面提供的五題是讓大家體驗一下，BFS 看似簡單的，卻可以應用在很多乍看之下不會聯想到 BFS 的題目。能夠體驗到這一層，就是你可以開始靈活運用 BFS 的起點。刷題不只是為了通過面試，而是加強自己對資結和演算法的洞見和體驗，進而優雅有效率地解決工程問題，共勉之。
