深度优先搜索和广度优先搜索
遍历搜索
在树(图/状态集)中寻找特定结点
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x): val(x),letf(NULL),right(NULL){}
}搜索-遍历
- 每个节点都要访问一次
- 每个结点仅仅要访问一次
- 对于结点的访问顺序不限
- 深度优先: depth first search
- 广度优先：breadth frist search
def dfs(node): if node in visited: # already visited return visited.add(node) # process current node #...#logic here dfs(node.left) dfs(node.right)深度优先搜索 Depth-First-Search
DFS代码-递归写法
visited=set() def dfs(node,visited): if node in visited:# terminator #already visited return visited.add(node) #process current node here. ... for next_node in node.children(): if not next_node in visited: dfs(next node,visited)遍历顺序
DFS代码-非递归写法
def DFS(self,tree):
if tree.root is None:
return []
visited,stack = [],[tree.root]
while stack:
node = stack.pop()
visited.add(node)
process(node)
nodes = generate_related_nodes(node)
stack.push(nodes)
# other processing work
...广度优先搜索 Breadth-First-Search
遍历顺序
BFS代码
def BFS(graph,start,end):
queue=[]
queue.append([start])
visited.add(start)
while queue:
node = queue.pop()
visited.add(node)
process(node)
nodes=generate_related_nodes(node)
queue.push(node)
# other processing work
visited = set()
def dfs(node,visited):
visited.add(node)
# process current node here.
...
for next_node in node.children():
if not next_node in visited:
dfs(next node,visited)
def BFS(graphs,start,end):
queue=[]
queue.append([start])
visited.add(start)
while queue:
node = queue.pop()
visited.add(node)
process(node)
nodes=generate_related_nodes(node)
queue.push(nodes)
LeetCode实战题目
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if(!root){
return res;
}
queue<TreeNode*> Q;
TreeNode* p;
Q.push(root);
while(Q.empty()==0){
vector<int> a;
int width=Q.size();
for(int i=0;i<width;i++){
p=Q.front();
a.push_back(p->val);
Q.pop();
if(p->left) Q.push(p->left);
if(p->right) Q.push(p->right);
}
res.push_back(a);
}
return res;
}
};
class Solution {
public:
int minMutation(string start, string end, vector<string>& bank) {
//记录所有需要访问的节点
unordered_set<string> candidate(bank.begin(), bank.end());
//记录基因和step
queue<pair<string ,int>> q;
q.push({start, 0});
string gene;
int step;
while( ! q.empty()) {
//终止条件
if (q.front().first == end){
return q.front().second;
}
gene = q.front().first;
step = q.front().second;
q.pop();
for (int i = 0; i < gene.length(); i++){
char tmp = gene[i]; //记录原状态
for (char base : "ATCG"){
if (gene[i] == base) continue; //相同就不变化
gene[i] = base; //修改碱基
if( candidate.find(gene) != candidate.end()){
q.push({gene, step+1});
candidate.erase(gene);
}
}
gene[i] = tmp;
}
}
return -1;
}
};
class Solution {
public:
const int M1 = 0xCCCCCCCC; // 1100110011001100...
const int M2 = 0x33333333; // 0011001100110011...
const int INF = 1e8;
unordered_map<char, int> m{{'A', 0}, {'T', 1}, {'C', 2}, {'G', 3}};
int toInt(const string& s) {
int n = 0;
for (auto c : s) {
n <<= 2;
n |= m[c];
}
return n;
}
bool valid(int x, int y) {
int t = x ^ y;
// 突变不能跨越点
if ((t & M1) && (t & M2)) return false;
long b = t & (-t);
// 突变的点不能超过2个
return (b << 2) > t;
}
void dfs(unordered_map<int, vector<int> >& g, int x, unordered_map<int, int>& dfn) {
for (auto y : g[x]) {
if (dfn[x] + 1 < dfn[y]) {
dfn[y] = dfn[x] + 1;
dfs(g, y, dfn);
}
}
}
int minMutation(string start, string end, vector<string>& bank) {
int ns = toInt(start);
int ne = toInt(end);
vector<int> nbs;
for (auto& s : bank) {
nbs.push_back(toInt(s));
}
unordered_map<int, vector<int> > g;
int N = nbs.size();
for (int i = 0; i < N; ++i) {
if (valid(ns, nbs[i])) {
g[ns].push_back(nbs[i]);
}
for (int j = 0; j < i; ++j) {
if (valid(nbs[i], nbs[j])) {
g[nbs[i]].push_back(nbs[j]);
g[nbs[j]].push_back(nbs[i]);
}
}
}
unordered_map<int, int> dfn;
for (auto x : nbs) dfn[x] = INF;
dfn[ne] = INF;
dfn[ns] = 0;
dfs(g, ns, dfn);
return dfn[ne] == INF ? -1 : dfn[ne];
}
};class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> res;
if(n==0)
return res;
if(n==1)
{
res.push_back("()");
return res;
}
string s = "";
for(int i = 0 ;i < n;++i)
s+="()";
sort(s.begin(),s.end());
do{
if(IsLegal(s))
res.push_back(s);
}while(next_permutation(s.begin()+1,s.end()));
return res;
}
bool IsLegal(string& s)
{
int count = 0;
for(int i = 0;i < s.size();++i)
{
if(s[i]=='(')
count++;
else
count--;
if(count<0)
return false;
}
return true;
}
};//dfs
class Solution {
public:
vector<int> res;
void dfs(TreeNode* curNode, int level) {
if(res.size() == level) res.push_back(INT_MIN);
res[level] = max(res[level], curNode->val);
if(curNode->left) dfs(curNode->left, level+1);
if(curNode->right) dfs(curNode->right, level+1);
}
vector<int> largestValues(TreeNode* root) {
if(root == NULL) return res;
dfs(root, 0);
return res;
}
};//bfs
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
vector<int> res;
if(root == NULL) return res;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
int levelSize = q.size();
int levelMax = INT_MIN;
for(int i = 0; i < levelSize; i++) {
TreeNode* curNode = q.front();
q.pop();
levelMax = max(curNode->val, levelMax);
if(curNode->left) q.push(curNode->left);
if(curNode->right) q.push(curNode->right);
}
res.push_back(levelMax);
}
return res;
}
};
class Solution{
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList){
//加入所有节点，访问过一次，删除一个。
unordered_set<string> s;
for (auto &i : wordList) s.insert(i);
queue<pair<string, int>> q;
//加入beginword
q.push({beginWord, 1});
string tmp; //每个节点的字符
int step; //抵达该节点的step
while ( !q.empty() ){
if ( q.front().first == endWord){
return (q.front().second);
}
tmp = q.front().first;
step = q.front().second;
q.pop();
//寻找下一个单词了
char ch;
for (int i = 0; i < tmp.length(); i++){
ch = tmp[i];
for (char c = 'a'; c <= 'z'; c++){
//从'a'-'z'尝试一次
if ( ch == c) continue;
tmp[i] = c ;
//如果找到的到
if ( s.find(tmp) != s.end() ){
q.push({tmp, step+1});
s.erase(tmp) ; //删除该节点
}
tmp[i] = ch; //复原
}
}
}
return 0;
}
};class Solution {
public:
bool sim(const string& s1, const string& s2) {
int diff = 0;
for (int i = 0; i < s1.size(); ++i) {
diff += s1[i] != s2[i];
}
return diff <= 1;
}
void dfs(const vector<vector<int> >& g, const vector<int>& dfn, const vector<string>& wordList,
int i, vector<string>& path, vector<vector<string> >& paths) {
if (dfn[i] == 0) {
vector<string> v(path);
reverse(v.begin(), v.end());
paths.push_back(v);
return;
}
for (auto j : g[i]) {
if (dfn[j] == dfn[i] - 1) {
path.push_back(wordList[j]);
dfs(g, dfn, wordList, j, path, paths);
path.pop_back();
}
}
}
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
wordList.push_back(beginWord);
int N = wordList.size();
vector<vector<int> > g(N);
int endi = -1;
// 构图
for (int i = 0; i < N; ++i) {
if (wordList[i] == endWord) endi = i;
for (int j = i + 1; j < N; ++j) {
if (sim(wordList[i], wordList[j])) {
g[i].push_back(j);
g[j].push_back(i);
}
}
}
if (endi == -1) return {};
// 层级编号
vector<int> dfn(N, -1);
queue<int> q;
q.push(N - 1);
dfn[N - 1] = 0;
while (!q.empty()) {
auto i = q.front();
q.pop();
for (auto j : g[i]) {
if (dfn[j] == -1) {
dfn[j] = dfn[i] + 1;
q.push(j);
}
}
}
if (dfn[endi] == -1) return {};
// 回溯路径
vector<string> path{endWord};
vector<vector<string> > paths;
dfs(g, dfn, wordList, endi, path, paths);
return paths;
}
};class Solution {
private:
void dfs(vector<vector<char>>& grid, int r, int c) {
int nr = grid.size();
int nc = grid[0].size();
grid[r][c] = '0';
if (r - 1 >= 0 && grid[r-1][c] == '1') dfs(grid, r - 1, c);
if (r + 1 < nr && grid[r+1][c] == '1') dfs(grid, r + 1, c);
if (c - 1 >= 0 && grid[r][c-1] == '1') dfs(grid, r, c - 1);
if (c + 1 < nc && grid[r][c+1] == '1') dfs(grid, r, c + 1);
}
public:
int numIslands(vector<vector<char>>& grid) {
int nr = grid.size();
if (!nr) return 0;
int nc = grid[0].size();
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
dfs(grid, r, c);
}
}
}
return num_islands;
}
};class Solution {
public:
int dirs[8][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1},
{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
bool valid(int x, int y, int R, int C) {
return x >= 0 && x < R && y >= 0 && y < C;
}
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
if (board[click[0]][click[1]] == 'M') {
board[click[0]][click[1]] = 'X';
return board;
}
int R = board.size();
int C = board[0].size();
vector<vector<int> > ADJ(R, vector<int>(C, 0));
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) {
if (board[i][j] == 'M' || board[i][j] == 'X') {
for (int k = 0; k < 8; ++k) {
int x = i + dirs[k][0];
int y = j + dirs[k][1];
if (valid(x, y, R, C)) {
++ADJ[x][y];
}
}
}
}
}
if (ADJ[click[0]][click[1]] > 0) {
board[click[0]][click[1]] = '0' + ADJ[click[0]][click[1]];
return board;
}
queue<pair<int, int> > q;
board[click[0]][click[1]] = 'B';
q.push({click[0], click[1]});
while (!q.empty()) {
auto p = q.front();
q.pop();
int x = p.first;
int y = p.second;
for (int i = 0; i < 8; ++i) {
int r = x + dirs[i][0];
int c = y + dirs[i][1];
if (valid(r, c, R, C)) {
if (ADJ[r][c] > 0) {
board[r][c] = '0' + ADJ[r][c];
} else if (board[r][c] == 'E') {
board[r][c] = 'B';
q.push({r, c});
}
}
}
}
return board;
}
};