LeetCode算法练习——广度优先搜索 BFS

很久没有进行练习了,手都生疏了不少。前一段时间完成30道DFS题目的练习,现在开始BFS,预计做完BFS分类中的所有中等难度题。
LeetCode中的分类并不是非常的标准,BFS的题目中很多用DFS也可以解答,只要能够解出,不一定绝对要使用LeetCode建议的算法。

给个目录:
LeetCode102 二叉树的层次遍历
LeetCode103 二叉树的锯齿形层次遍历
LeetCode127 单词接龙
LeetCode787 K 站中转内最便宜的航班
LeetCode752 打开转盘锁
LeetCode200 岛屿的个数
LeetCode199 二叉树的右视图
LeetCode210 课程表 II
LeetCode279 完全平方数
LeetCode310 最小高度树
LeetCode863 二叉树中所有距离为 K 的结点
LeetCode133 克隆图

LeetCode102 二叉树的层次遍历

题目

给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

例如:
给定二叉树: [3,9,20,null,null,15,7],

1
2
3
4
5
3
/ \
9 20
/ \
15 7

返回其层次遍历结果:

1
2
3
4
5
[
[3],
[9,20],
[15,7]
]

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
map<int,vector<int>> hash; //新建一个map用于存储结果
vector<vector<int>> levelOrder(TreeNode* root) {
dfs(root,0);//dfs开始
vector<vector<int>> res; //res存储最终结果
for(auto key:hash){
res.push_back(key.second); //将map转换为vector
}
return res;//返回结果
}
void dfs(TreeNode* root, int depth){
if(!root) return;//如果是空节点 直接返回
hash[depth].push_back(root->val); //同一层次的节点放入一个vector中
dfs(root->left,depth+1);//遍历左子树
dfs(root->right,depth+1);//遍历右子树
}
};

体会

DFS+记录深度,非常经典的树的遍历题目,熟悉DFS应该在三分钟内可以A掉,具体内容请看注释。

LeetCode103 二叉树的锯齿形层次遍历

题目

给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

例如:
给定二叉树 [3,9,20,null,null,15,7],

1
2
3
4
5
3
/ \
9 20
/ \
15 7

返回锯齿形层次遍历如下:

1
2
3
4
5
[
[3],
[20,9],
[15,7]
]

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
map<int,vector<int>> hash;
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
dfs(root,0);
vector<vector<int>> res;
for(auto key:hash){
if(key.first%2){ //偶数层反转数组
reverse(key.second.begin(),key.second.end());
res.push_back(key.second);
}
else res.push_back(key.second); //奇数层正常放入
}
return res;
}
void dfs(TreeNode* root, int depth){
if(!root) return;//如果当前节点为空 返回
hash[depth].push_back(root->val); //同一层节点放在一个vector中
dfs(root->left,depth+1); //遍历左子树
dfs(root->right,depth+1); //遍历右子树
}
};

体会

本题与上一题思路完全一致,唯一的区别在于偶数层节点需要反向输出达到最后的效果,奇数层节点正常输出。

LeetCode127 单词接龙

题目

给定两个单词(beginWord 和 endWord)和一个字典,找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则:

每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:

如果不存在这样的转换序列,返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的,且二者不相同。
示例 1:

1
2
3
4
5
6
7
8
9
输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
输出: 5
解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
返回它的长度 5。

示例 2:

1
2
3
4
5
6
7
8
输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
输出: 0
解释: endWord "cog" 不在字典中,所以无法进行转换。

C++代码

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
class Solution {
public:
int min_length = INT_MAX; //记录最短路径
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
queue<pair<string,int>> que;//建立一个队列 记录当前字符串与路径长度
que.push({beginWord,1});//放入起始字符串 路径长度为1
vector<int> visited(wordList.size(),0); //用来记录wordList的访问情况
while(!que.empty()){
auto tmp = que.front(); //取出队首元素
que.pop(); //出队
if(tmp.first==endWord && tmp.second<min_length){ //如果队首元素与最终字符串相同 且 路径长度小于min_length 则修改min_length
min_length = tmp.second;
}
//寻找当前队首字符串的下一个变换字符串
for(int i=0;i<wordList.size();i++){
if(visited[i]) continue; //如果当前字符串被访问过 则跳过
else if (cmp(tmp.first,wordList[i])!=1) continue; //如果当前字符串与队首字符串变换字符数量不为1 则跳过
else { //否则新的字符串入队 并修改当前长度
que.push({wordList[i],tmp.second+1});
visited[i] = 1;
}
}
}
if(min_length==INT_MAX) return 0; //如果当前长度为INT_MAX证明没有找到 返回0
else return min_length; //否则返回当前最小长度
}
//判断src与dst两个字符串不相同字符的个数
int cmp(string src,string dst){
int count = 0;
for(int i=0;i<src.length();i++){
if(src[i]!=dst[i]) count ++;
}
return count;
}
};

体会

这个题目与POJ上的一道题目非常类似,本题采用BFS算法。首先创建一个队列,队列中需要包括当前的字符串与路径长度,向队列中存入beginWord,之后重复如下过程:遍历wordList寻找与队首字符串仅一个字母不同的字符串,寻找到之后存入队列中,直到寻找到endWord,比较当前的长度与min_length,选小的作为min_length。最后返回min_length。

LeetCode787 K 站中转内最便宜的航班

题目

有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始,以价格 w 抵达 v。
现在给定所有的城市和航班,以及出发城市 src 和目的地 dst,你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。 如果没有这样的路线,则输出 -1。

1
2
3
4
5
示例 1:
输入:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
输出: 200
1
2
3
4
5
示例 2:
输入:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
输出: 500

C++代码

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
class Solution {
public:
int min_value = INT_MAX;
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
queue<vector<int>> que; //建立一个队列 队列存储的是 价值和 与 路径。 数组的第一个元素为当前路径的价值和,后面的元素为当前的路径。
que.push({0,src}); //起点入队
while(!que.empty()){ //如果队列不为空
auto tmp = que.front(); //取出队首元素
que.pop();
if(tmp[tmp.size()-1]==dst){ //如果当前路径已经碰到终点
if(tmp.size()-1<=K+2 && tmp[0]<min_value) min_value = tmp[0]; //且当前路径的长度小于K+2(中转点+起点+终点)且当前路径的价值小于min_value 更新 min_value。
}
if(tmp.size()>K+2 || tmp[0]>min_value) continue;//剪枝 如果当前路径的长度>K+2或者当前路径的价值大于min_value都不在进行搜索
for(auto key:flights){ //遍历flights
if(tmp[tmp.size()-1]==key[0] && find(tmp.begin()+1,tmp.end(),key[1])==tmp.end()){ //find函数用来保证当前路径中没有重复节点
vector<int> new_vec; //创建一个新的临时vec
new_vec.insert(new_vec.end(),tmp.begin(),tmp.end()); //将tmp的内容全部放入new_vec
new_vec[0]+= key[2]; //new_vec的价值 = tmp的价值 + 新节点的价值
new_vec.push_back(key[1]); //将新的节点放入new_vec中
que.push(new_vec);//将new_vec放入que
}
}
}
if(min_value==INT_MAX) return -1; //如果min_value等于INT_MAX证明没有找到 返回-1
else return min_value; //否则返回最小长度
}
};

体会

经典BFS算法,这个题需要考虑一个问题。题目中虽然说了没有环路,但是两个节点间有往返的情况。对于这种情况我们在BFS的过程中需要存储整个路径,用来判断是否会出现重复节点。由于K有的时候会非常大,搜索的深度会非常深,这时候要注意剪枝。如果当前路径的长度>K+2或者当前路径的价值大于min_value都不在进行搜索,这样剪枝可以让效率成倍的提升。

LeetCode752 打开转盘锁

题目

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转:例如把 ‘9’ 变为 ‘0’,’0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 ‘0000’ ,一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字,一旦拨轮的数字和列表里的任何一个元素相同,这个锁将会被永久锁定,无法再被旋转。

字符串 target 代表可以解锁的数字,你需要给出最小的旋转次数,如果无论如何不能解锁,返回 -1。

示例 1:

1
2
3
4
5
6
输入:deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出:6
解释:
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的,
因为当拨动到 "0102" 时这个锁就会被锁定。

示例 2:

1
2
3
4
输入: deadends = ["8888"], target = "0009"
输出:1
解释:
把最后一位反向旋转一次即可 "0000" -> "0009"。

示例 3:

1
2
3
4
输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出:-1
解释:
无法旋转到目标数字且不被锁定。

示例 4:

1
2
输入: deadends = ["0000"], target = "8888"
输出:-1

C++代码

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
class Solution {
public:
int openLock(vector<string>& deadends, string target) {
string beginStr = "0000"; //初始字符
set<string> dead(deadends.begin(),deadends.end()); //将deadends转化为set 用来提高检索速度
set<string> visited; //用来记录已经访问过的号码
char flag_1 = '9'+1; //用来处理9->0
char flag_2 = '0'-1; //用来处理0->9
int min_length = INT_MAX;//用来记录最短路径的长度
visited.insert(beginStr); //将初始字符设置为访问
queue<pair<int,string>> que; //建立一个队列 队列中记录当前节点与深度
que.push({0,beginStr});//放入其实节点
if(dead.count("0000")) return -1; //如果dead中有0000 直接返回-1
while(!que.empty()){
auto tmp = que.front(); //取出队列中第一个元素
que.pop();
if(tmp.second == target && tmp.first<min_length){ //如果当前节点就是target 且深度小于当前的min_length,更新min_length。
min_length = tmp.first;
}
if(tmp.first>min_length) continue; //剪枝 如果当前深度大于min_length则不需要再搜索
for(int i=0;i<4;i++){ //对于密码中的每一位做+1 -1 操作
string str_plus = tmp.second;
string str_subs = tmp.second;
str_plus[i]+=1;
str_subs[i]-=1;
if(str_plus[i]==flag_1){ //9->0
str_plus[i] = '0';
}
if(str_subs[i]==flag_2){ //0->9
str_subs[i] = '9';
}
if(!dead.count(str_plus) && !visited.count(str_plus)) { //如果dead与visited中都不存在 str_plus,则将其放入队列。
que.push({tmp.first+1,str_plus});
visited.insert(str_plus);
}
if(!dead.count(str_subs) && !visited.count(str_subs)) { //如果dead与visited中都不存在 str_subs,则将其放入队列。
que.push({tmp.first+1,str_subs});
visited.insert(str_subs);
}
}
}
return min_length == INT_MAX? -1: min_length; //返回最终结果
}
};

体会

经典BFS+剪枝。将问题转化为一个图,每一个节点都与其他8个节点相连接,0000与0001、0009、0010、0090、0100、0900、1000、9000这个八个节点相连,以此类推。使用BFS逐层遍历这个图,找到答案并记录下最小路径。这个题直接BFS肯定会爆时间,因为每一个数字都会产生8种变化,不做剪枝数据量将非常大。使用visited数组记录访问过的数据,防止重复。使用set代替vector,set查询复杂度为O(1),vector查询复杂度为O(n),要快不少。

LeetCode200 岛屿的个数

题目

给定一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

1
2
3
4
5
6
7
8
9
示例 1:
输入:
11110
11010
11000
00000
输出: 1

示例 2:

1
2
3
4
5
6
7
输入:
11000
11000
00100
00011
输出: 3

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int count = 0;
for(int i=0;i<grid.size();i++){
for(int j=0;j<grid[i].size();j++){
if(grid[i][j]=='1') { //如果找到1 将这个点作为种子进行涂色
dfs(grid,i,j);
count++;
}
}
}
return count;
}
void dfs(vector<vector<char>>& grid,int x,int y){
if(x<0||x>grid.size()-1||y<0||y>grid[0].size()-1||grid[x][y]=='0'||grid[x][y]=='2') return; //越界或者碰到0或2 都直接返回
grid[x][y] = '2'; //将当前节点染色
dfs(grid,x+1,y); //对周围四个点做相同操作
dfs(grid,x-1,y);
dfs(grid,x,y+1);
dfs(grid,x,y-1);
}
};

体会

DFS水题。可以把这个题转化为一个涂色问题,找到一个1就将这个区域全涂成2,遍历整个数组,看一功能涂多少个区域。

LeetCode199 二叉树的右视图

题目

给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。

示例:

1
2
3
4
5
6
7
8
9
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1 <---
/ \
2 3 <---
\ \
5 4 <---

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
map<int,int> hash; //key是层 value是最右侧的数
vector<int> rightSideView(TreeNode* root) {
vector<int> res;//用于记录最后的结果
dfs(root,0); //从root开始dfs
for(auto key:hash){
res.push_back(key.second);//将hash中的结果按层
}
return res;
}
void dfs(TreeNode* root,int depth){
if(!root) return;
hash[depth] = root->val; //因为是采用先序遍历,所以每次都更新hash 最后的结果就是最右侧的数据
dfs(root->left,depth+1);//dfs左子树
dfs(root->right,depth+1);//dfs右子树
}
};

体会

直接按先序遍历DFS,记录一下每一层的节点就好,水题。

LeetCode210 课程表 II

题目

现在你总共有 n 门课需要选,记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件,返回你为了学完所有课程所安排的学习顺序。

可能会有多个正确的顺序,你只要返回一种就可以了。如果不可能完成所有课程,返回一个空数组。

示例 1:

1
2
3
输入: 2, [[1,0]]
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1,你需要先完成课程 0。因此,正确的课程顺序为 [0,1] 。

示例 2:

1
2
3
输入: 4, [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3,你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。因此,一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

说明:

输入的先决条件是由边缘列表表示的图形,而不是邻接矩阵。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。
提示:

这个问题相当于查找一个循环是否存在于有向图中。如果存在循环,则不存在拓扑排序,因此不可能选取所有课程进行学习。
通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程(21分钟),介绍拓扑排序的基本概念。
拓扑排序也可以通过 BFS 完成。

C++代码

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
class Solution {
public:
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<int> in(numCourses,0); //记录入度
map<int,vector<int>> linkGraph; //图的临接表
vector<int> res; //最终结果
queue<int> que; //BFS所用队列
//构建图的邻接表 计算每个节点的入度
for(auto key:prerequisites){
linkGraph[key.second].push_back(key.first);
in[key.first]++;
}
//将所有的起点都放入que中,因为数据中存在图不联通的情况
for(int i=0;i<in.size();i++){
if(in[i]==0) que.push(i);
}
//BFS
while(!que.empty()){
auto tmp = que.front();
if(find(res.begin(),res.end(),tmp)==res.end() && in[tmp]==0)res.push_back(tmp); //如果当前节点没有被添加且入度为0 证明这门课的先修课都完成了,可以将该课添加进res
que.pop();
//遍历邻接表 寻找该节点的邻居
for(auto key:linkGraph[tmp]){
//!!!!!注意顺序
in[key]--; //该节点所有的邻居的入度--
if(in[key]==0) //如果邻居的入度为0 则该邻居可以作为起点放入que中
que.push(key);
}
}
//如果所有节点的入度都为0 证明这个图拓扑可排 输出res 否则输出[]
if(*max_element(in.begin(),in.end())==0) return res;
else return {};
}
};

体会

本题与课程表无太大区别,都是考察图的拓扑排序。本题只是记录课程路径即可,将que中的数据逐个放入res中,即是答案。
几个注意点:
1、图的拓扑排序采用BFS则记录入度,采用DFS则记录出度。
2、图可能不联通,所以要将所有的起点都放入que中
3、去除一点时,先将其邻居点的入度-1,再判断邻居入度是否为0,就是我打了一堆!那里。(卡了我好久T_T)
4、res中可能会有重复,记得去重。
课程表解答请点击

LeetCode279 完全平方数

题目

给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

1
2
3
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.

示例 2:

1
2
3
输入: n = 13
输出: 2
解释: 13 = 4 + 9.

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int numSquares(int n) {
//DP[i]表示 i可以表示为DP[i]个平方数的和
vector<int> dp(n+1,INT_MAX); //初始化一个DP数组 全部初始化为INT_MAX
for(int i=1;i*i<=n;i++)
dp[i*i] = 1; //将所有的平方数都置为1
for(int i=1;i<n;i++){ //i为普通数
for(int j=1;i+j*j<=n;j++){ //j为平方数的根
dp[i+j*j] = min(dp[i]+1,dp[i+j*j]); //状态转移方程
}
}
return dp[n]; //最终结果
}
};

体会

首先使用DFS进行了尝试,但是爆时间了。
DP的思路:一个非平方数可以看成是一个平方数+一个非平方数。DP[i]表示i可以表示为DP[i]个平方数的和,则非平方数都可以看作是i+jj,i表示一个普通数,j表示一个平方数的根。状态转移方程为dp[i+jj] = min(dp[i]+1,dp[i+jj]),求出能够组成i的最小个数。所有的平方数都只需要自己就可以组成自己,所以是1,其他初始化为无穷。
例子:
n=12
dp[2] = dp[1+1
1] = min(dp[1]+1,dp[2]) = 2
dp[8] = dp[4+22] = min(dp[4]+1,dp[8]) = 2
dp[12] = dp[8+2
2] = min(dp[8]+1,dp[12]) = 3
本题参考博客请点击
本题也可以使用四平方定理求解,但个人觉得技巧性太强。

LeetCode310 最小高度树

对于一个具有树特征的无向图,我们可选择任何一个节点作为根。图因此可以成为树,在所有可能的树中,具有最小高度的树被称为最小高度树。给出这样的一个图,写出一个函数找到所有的最小高度树并返回他们的根节点。

格式

该图包含 n 个节点,标记为 0 到 n - 1。给定数字 n 和一个无向边 edges 列表(每一个边都是一对标签)。

你可以假设没有重复的边会出现在 edges 中。由于所有的边都是无向边, [0, 1]和 [1, 0] 是相同的,因此不会同时出现在 edges 里。

示例 1:

1
2
3
4
5
6
7
8
9
输入: n = 4, edges = [[1, 0], [1, 2], [1, 3]]
0
|
1
/ \
2 3
输出: [1]

示例 2:

1
2
3
4
5
6
7
8
9
10
11
输入: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2
\ | /
3
|
4
|
5
输出: [3, 4]

说明:

根据树的定义,树是一个无向图,其中任何两个顶点只通过一条路径连接。 换句话说,一个任何没有简单环路的连通图都是一棵树。
树的高度是指根节点和叶子节点之间最长向下路径上边的数量。

C++代码

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
class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
if(n==1) return{0}; //如果n=1 直接返回[0]
map<int,vector<int>> hash; //hash用于存储图
vector<int> degree(n,0); //degree存储每一个节点的度
for(auto key:edges){ //将edges的内容存储在hash中
hash[key.first].push_back(key.second);
hash[key.second].push_back(key.first);
}
for(auto key:hash){ //计算每个节点的度
degree[key.first] = key.second.size();
}
while (hash.size()>2){ //如果剩余节点个数大于2
vector<int> leaves; //leaves表示叶节点,即 度数为1 的节点
for(int i=0;i<degree.size();i++){
if(degree[i]==1) leaves.push_back(i); //将所有度数为1的节点存入leaves
}
for(auto leaf:leaves){ //删除leaf,并将leaf的邻居节点的度数-1
degree[leaf]=0;
for(auto key:hash[leaf])
degree[key]--;
hash.erase(leaf);
}
}
vector<int> res; //将hash中剩下的1个或2个节点转存到vector中
for(auto key:hash)
res.push_back(key.first);
return res;
}
};

体会

蛮有技巧的一个题目。
首先拿到这个题目,第一个想法就是BFS,将每个节点都做为树的根节点,最后找到树高度最小的根节点,思路很清晰。但是无奈超时了,最后5个数据怎么优化都过不去,无奈换了思路。
本题思路:一个图肯定存在一个最小高度树,所有度为1的节点必为叶节点。我们从叶节点向内搜索,每次都将叶节点删去,并将其邻居节点的度数-1,直到最后仅有一个或两个节点即可,这一个或两个节点就是最小高度树的根节点。
若一个图的最大路径为奇数个节点,则最小高度树的根节点只有1个。
若一个图的最大路径为偶数个节点,则最小高度树的根节点只有2个。
算法流程:
1.以某种方式储存图,同时记录每个节点的度
2.删除度为1的节点,并把与之相连的节点度数减1
3.重复步骤2直到剩下1或2个节点

BFS代码 求大佬优化

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
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
map<int,vector<int>> hash;
for(auto key:edges){ //存储图
hash[key.first].push_back(key.second);
hash[key.second].push_back(key.first);
}
map<int,vector<int>> res; //key表示深度 value表示能达到当前深度的根节点
int min_length = INT_MAX;
for(auto key:hash){
queue<pair<int,int>> que; //初始化一个队列
vector<int> visited(n,0); //初始化visited防止循环访问
que.push({key.first,0}); //放入第一个节点
visited[key.first]=1; //将第一个节点设置为被访问
while(!que.empty()){
auto tmp = que.front(); //取出队列中的第一个节点
que.pop();
visited[tmp.first]=1; //当前节点设置为访问
if(tmp.second>min_length) break; //如果当前的长度已经大于最小长度 直接弹出
if(find(visited.begin(),visited.end(),0)==visited.end()&&tmp.second<=min_length){ //如果所有的节点都被访问 切当长度小于min_length 修改min_length
min_length = tmp.second;
res[tmp.second].push_back(key.first);
}
for(auto neighbor:hash[tmp.first]){ //将当前节点的neighbor依次入队
if(!visited[neighbor]) {
que.push({neighbor,tmp.second+1});
}
}
}
}
return res[min_length];
}

LeetCode863 二叉树中所有距离为 K 的结点

题目

给定一个二叉树(具有根结点 root), 一个目标结点 target ,和一个整数值 K 。返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。

示例 1:

1
2
3
输入:root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2
输出:[7,4,1]

解释:
所求结点为与目标结点(值为 5)距离为 2 的结点,
值分别为 7,4,以及 1

提示:
给定的树是非空的,且最多有 K 个结点。
树上的每个结点都具有唯一的值 0 <= node.val <= 500 。
目标结点 target 是树上的结点。
0 <= K <= 1000.

C++代码

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
class Solution {
public:
map<int,vector<int>> graph;
int graph_size=0;
vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
dfs(root);
//BFS寻找第K近的节点
queue<pair<int,int>> que; //BFS所用队列
vector<int> res; //res用于存储最终结果
vector<int> visited(graph_size+1,0);
que.push({target->val,0}); //将第一个节点放入队列
visited[target->val]=1; //将第一个节点设置为被访问
while(!que.empty()){
auto tmp = que.front(); //取出队列中的第一个节点
que.pop();
if(tmp.second==K) { //如果当前节点的深度已经达到K 将该节点放入res
res.push_back(tmp.first);
continue;
}
for(auto key:graph[tmp.first]){ //将该节点的邻居节点依次放入队列中 并将visited设置为被访问
if(!visited[key]){
que.push({key,tmp.second+1});
visited[key]=1;
}
}
}
cout<<graph_size;
return res;
}
void dfs(TreeNode* root){ //dfs将树转化为图
if(!root)return;
//建立根节点与左子节点 右节点的双向连接 写得有点蠢 见谅
if(root->val>graph_size) graph_size = root->val;
if(root->left) graph[root->val].push_back(root->left->val);
if(root->right) graph[root->val].push_back(root->right->val);
if(root->left) graph[root->left->val].push_back(root->val);
if(root->right) graph[root->right->val].push_back(root->val);
dfs(root->left);
dfs(root->right);
}
};

体会

DFS+BFS,没想到没有爆时间。
使用DFS将树转化为图,之后使用BFS算法从target开始,寻找距离target为K的节点。两个搜索组合即可。

LeetCode133 克隆图

题目

克隆一张无向图,图中的每个节点包含一个 label (标签)和一个 neighbors (邻接点)列表 。

OJ的无向图序列化:

节点被唯一标记。

我们用 # 作为每个节点的分隔符,用 , 作为节点标签和邻接点的分隔符。

例如,序列化无向图 {0,1,2#1,2#2,2}。

该图总共有三个节点, 被两个分隔符 # 分为三部分。

第一个节点的标签为 0,存在从节点 0 到节点 1 和节点 2 的两条边。
第二个节点的标签为 1,存在从节点 1 到节点 2 的一条边。
第三个节点的标签为 2,存在从节点 2 到节点 2 (本身) 的一条边,从而形成自环。
我们将图形可视化如下:

1
2
3
4
5
6
7
1
/ \
/ \
0 --- 2
/ \
\_/

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
map<int,UndirectedGraphNode*> hash;
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
return dfs(node);
}
UndirectedGraphNode* dfs(UndirectedGraphNode* node) {
if(!node) return node; //如果当前节点为NULL 返回NULL
if(hash.count(node->label)) return hash[node->label]; //如果当前节点被拷贝 返回
UndirectedGraphNode* new_node = new UndirectedGraphNode(node->label); //创建一个新的节点
hash[node->label] = new_node; //将当前节点存在hash中
for(auto tmp:node->neighbors){ //遍历当前节点的邻居节点 对每一个邻居节点dfs
new_node->neighbors.push_back(dfs(tmp));
}
return new_node;
}
};

体会

开始拿到这个题真的愣了一下,其实就是一个无向图的遍历问题,使用DFS算法遍历,每次遍历到一个新的节点,进行深拷贝。