深度优先搜索和广度优先搜索

遍历搜索

在树(图/状态集)中寻找特定结点

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;
    }
};

单词接龙 II

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;
    }
};