【刷题篇】回溯算法（广度优先搜索（一））

文章目录

• N 叉树的层序遍历
• 腐烂的橘子
• 单词接龙
• 打开转盘锁

N 叉树的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> allset;
        queue<Node*> curset;
        if(root!=nullptr)
            curset.push(root);
        while(!curset.empty())
        {
            int size=curset.size();
            vector<int> part;
            while(size--)
            {
                Node* cur=curset.front();
                part.push_back(cur->val);
                curset.pop();
                for(Node* e : cur->children)
                {
                    curset.push(e);
                }
            }
            allset.push_back(part);
        }
        return allset;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        queue<pair<int,int>> curset;
        int row=grid.size();
        int col=grid[0].size();
        for(int i=0;i<row;i++)
        {
            for(int j=0;j<col;j++)
            {
                if(grid[i][j]==2)
                {
                    curset.push(make_pair(i,j));
                    //break;
                    //这里并不能找到一个就返回，实例【2，2，2，1，1】，就会出错
                }
            }
        }
        int time=0;
        int next[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
        while(!curset.empty())
        {
            int size=curset.size();
            bool flag=false;//这里的标记是非常有作用的，只有为true之后时间才会增加
            while(size--)
            {
                pair<int,int> cur=curset.front();
                curset.pop();
                //遍历烂橘子的周围
                for(int i=0;i<4;i++)
                {
                    int newrow=cur.first+next[i][0];
                    int newcol=cur.second+next[i][1];
                    if(newrow>=row||newrow<0||newcol>=col||newcol<0)
                        continue;
                    if(grid[newrow][newcol]==1)
                    {
                        grid[newrow][newcol]=2;
                        flag=true;
                        curset.push(make_pair(newrow,newcol));
                    }   
                }
            }
            if(flag)
                time++;  
        }
        //遍历一次是否还有好橘子
        for(int i=0;i<row;i++)
        {
            for(int j=0;j<col;j++)
            {
                if(grid[i][j]==1)
                {
                    return -1;
                }
            }
        }
        return time; 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

单词接龙

在字典（单词列表） wordList 中，从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：
序列中第一个单词是 beginWord 。
序列中最后一个单词是 endWord 。
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典 wordList 中的单词。
给定两个长度相同但内容不同的单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        queue<string> q;
        unordered_set<string> book;
        unordered_set<string> newword;//将wordlist导入更加的方便
        int step=1;//因为开始也是算成一个步骤
        //导入原数据
        for(auto& e : wordList)
            newword.insert(e);
        q.push(beginWord);
        book.insert(beginWord);//开始要记住要把beginWord放入标记数组
        while(!q.empty())
        {
            int size=q.size();
            while(size--)
            {
                string cur=q.front();
                q.pop();
                if(cur==endWord)//相等就直接返回就可以了
                    return step;
                for(int j=0;j<cur.size();j++)
                {   //这里是必须要创建一个新值的，因为下面会改变cur的值，
                    //导致在遍历下一个字母时会出现问题
                    string str=cur;
                    for(char i='a';i<='z';i++)
                    {
                        str[j]=i;
                        //确保不在标记数组当中，也要确保要在词典当中找到
                        if(book.find(str)==book.end()&&newword.find(str)!=newword.end())
                        {
                            q.push(str);
                            book.insert(str);
                        }
                    }
                }
            }
            step++;
        }
        return 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

打开转盘锁

一个密码锁由 4 个环形拨轮组成，每个拨轮都有 10 个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’，‘0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 ‘0000’ ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，请给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> Deadends(deadends.begin(), deadends.end());//使用set更加的方便
        unordered_set<string> book;//作为标记手册
        queue<string> bfs;
        int step=0;
        if (target == "0000") return 0;
        //如果在死亡数组中找到“0000”就直接返回-1
        if(Deadends.find("0000")!=Deadends.end())
        {
            return -1;
        }
        bfs.push("0000");
        book.insert("0000");
        while(!bfs.empty())
        {
            int size=bfs.size();
            while(size--)
            {
                string cur=bfs.front();
                bfs.pop();
                if(cur==target)
                {
                    return step;
                }
                for(int i=0;i<cur.size();i++)
                {
                    //储存两个变量，用于记录是向下滚动还是向上
                    string tmp1=cur;
                    string tmp2=cur;
                    if(tmp1[i]=='9')
                    {
                        tmp1[i]='0';
                    }
                    else
                    {
                        tmp1[i]++;
                    }
                    if(tmp2[i]=='0')
                    {
                        tmp2[i]='9';
                    }
                    else
                    {
                        tmp2[i]--;
                    }
                    //判断标记数组是否有，判断死亡数组是否有
                    if(book.find(tmp1)==book.end()&&Deadends.find(tmp1)==Deadends.end())
                    {
                        book.insert(tmp1);
                        bfs.push(tmp1);
                    }
                    if(book.find(tmp2)==book.end()&&Deadends.find(tmp2)==Deadends.end())
                    {
                        book.insert(tmp2);
                        bfs.push(tmp2);
                    }  
                }
            }
            step++;
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65