LeetCode算法练习——深度优先搜索 DFS(3)

LeetCode Everyday!
我们继续LeetCode之旅,这一篇再完成十个题,我们就进入下一个章节。做了一段时间LeetCode。感觉真的挺不错的,以前数据结构课上的很多内容又回以前来了。LeetCode很适合锻炼基础功,题目也很清晰。很不错。建议各位如果有时间,可以从中级算法开始练习。一日一题,都会有很大提升。

给个目录:
LeetCode638 大礼包
LeetCode542 01矩阵
LeetCode529 扫雷游戏
LeetCode547 朋友圈
LeetCode576 出界的路径数
LeetCode721 账户合并
LeetCode743 网络延迟时
LeetCode785 判断二分图
LeetCode841 钥匙和房间
LeetCode207 课程表

LeetCode638 大礼包

题目

在LeetCode商店中, 有许多在售的物品。

然而,也有一些大礼包,每个大礼包以优惠的价格捆绑销售一组物品。

现给定每个物品的价格,每个大礼包包含物品的清单,以及待购物品清单。请输出确切完成待购清单的最低花费。

每个大礼包的由一个数组中的一组数据描述,最后一个数字代表大礼包的价格,其他数字分别表示内含的其他种类物品的数量。

任意大礼包可无限次购买。

示例 1:

1
2
3
4
5
6
7
输入: [2,5], [[3,0,5],[1,2,10]], [3,2]
输出: 14
解释:
有A和B两种物品,价格分别为¥2和¥5。
大礼包1,你可以以¥5的价格购买3A和0B。
大礼包2, 你可以以¥10的价格购买1A和2B。
你需要购买3个A和2个B, 所以你付了¥10购买了1A和2B(大礼包2),以及¥4购买2A。

示例 2:

1
2
3
4
5
6
7
输入: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
输出: 11
解释:
A,B,C的价格分别为¥2,¥3,¥4.
你可以用¥4购买1A和2B,也可以用¥9购买2A,2B和1C。
你需要买1A,2B和1C,所以你付了¥4买了1A和1B(大礼包1),以及¥3购买1B, ¥4购买1C。
你不可以购买超出待购清单的物品,尽管购买大礼包2更加便宜。

说明:

最多6种物品, 100种大礼包。
每种物品,你最多只需要购买6个。
你不可以购买超出待购清单的物品,即使更便宜。

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
class Solution {
public:
//判断是否能够放入当前这个礼包
bool valid(vector<int> special_single, vector<int> needs){
for(int i=0;i<needs.size();i++){
if(special_single[i]>needs[i]) return false;
}
return true;
}
int shoppingOffers(vector<int> &price, vector<vector<int>> &special, vector<int> &needs) {
int min_money = 0; //表示最小值
//如果全部买单独的物品
for(int i=0;i<needs.size();i++){
min_money += price[i] * needs[i];
}
//遍历所有礼包
for(int i=0;i<special.size();i++){
if(valid(special[i],needs)){
//如果礼包可以购买的话
vector<int> new_needs; //新建一个数组 表示新的needs
for(int j=0;j<needs.size();j++)
new_needs.push_back(needs[j]-special[i][j]); //新的needs = 旧的needs - 礼包中物品的个数
int money_tmp = shoppingOffers(price,special,new_needs) + special[i].back(); //将当前礼包的几个加到money_temp上,同时继续遍历
min_money = min(min_money,money_tmp); //最后求出最低价格
}
}
return min_money;//返回最低价格
}
};

体会

这个题不难,但鉴于我抠脚的水平,竟然做了很久。我们采取这样的思路,首先单独买下所有的产品,计算出价格,之后我们遍历礼包进行搜索,在搜索的过程中每次都要更新needs,这样可以实现零售+礼包的方式,每次记录下礼包的价格,搜索结束后,找到最小的价格,返回。

LeetCode542 01矩阵

题目

给定一个由 0 和 1 组成的矩阵,找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1:
输入:

1
2
3
0 0 0
0 1 0
0 0 0

输出:

1
2
3
0 0 0
0 1 0
0 0 0

示例 2:
输入:

1
2
3
0 0 0
0 1 0
1 1 1

输出:

1
2
3
0 0 0
0 1 0
1 2 1

注意:

给定矩阵的元素个数不超过 10000。
给定矩阵中至少有一个元素是 0。
矩阵中的元素只在四个方向上相邻: 上、下、左、右。

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
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
queue<pair<int,int>> que;
//将矩阵中所有的0 坐标入列, 将所有的1设置为INT_MAX
for(int i=0;i<matrix.size();i++){
for(int j=0;j<matrix[0].size();j++)
if(matrix[i][j]==0) que.push(make_pair(i,j));
else if(matrix[i][j]==1) matrix[i][j] = INT_MAX;
}
//循环直到队列为空
while(!que.empty()){
auto q = que.front(); //将队列的首元素取出来
que.pop(); //队首出列
vector<pair<int,int>> dirs ={{0,1},{0,-1},{1,0},{-1,0}}; //四个方向的坐标
//对四个方向进行尝试
for(auto dir : dirs){
//计算新的坐标
int x = q.first + dir.first;
int y = q.second + dir.second;
//如果x,y超过边界 或者 x y的数值比当前小 则不用更新
if(x<0 || x>matrix.size()-1 || y<0 || y>matrix[0].size()-1 || matrix[x][y]<= matrix[q.first][q.second]) continue;
//更新当前位置的 数据 。可以理解为深度
matrix[x][y] = matrix[q.first][q.second] + 1;
//将更新后的点存入队列
que.push({x,y});
}
}
return matrix;
}
};

体会

这个题,开始我尝试用dfs去解答,如果使用dfs,需要遍历每一个为1的点,非常耗时间,最终超时了。这个中周围距离的题目,使用bfs是更好的方式。
bfs的思路是逐层更新,首先我们将所有的1都改为无穷大。从一个0开始,逐层向外更新,每次只考虑周围的四个节点,如果目标节点的值大于源节点的值,就证明我们给目标节点找到了一条更短的路,我们更新目标节点,否则目标节点保持不变。bfs需要使用队列进行存储,先将所有的0入列,作为起点,之后每次更新过的节点都要入列,用来实现祝层向外的效果。

给一个DFS超时的代码 T.T

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
void dfs(vector<vector<int>> &matrix,vector<vector<bool>> visited,int depth,int x,int y,int src_x,int src_y){
if(x>matrix.size()-1 || x<0 || y>matrix[0].size()-1 ||y<0 || visited[x][y]) return;
if(matrix[x][y]==0) {
if(depth<matrix[src_x][src_y]) matrix[src_x][src_y] = depth;
visited[x][y]= false;
return;
}
visited[x][y]= true;
dfs(matrix,visited,depth+1,x,y+1,src_x,src_y);
dfs(matrix,visited,depth+1,x,y-1,src_x,src_y);
dfs(matrix,visited,depth+1,x+1,y,src_x,src_y);
dfs(matrix,visited,depth+1,x-1,y,src_x,src_y);
}
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
vector<vector<bool>> visited(matrix.size(),vector<bool>(matrix[0].size(),false));
for(int i=0;i<matrix.size();i++)
for(int j=0;j<matrix[0].size();j++)
if(matrix[i][j]==1) matrix[i][j]=INT_MAX;
for(int i=0;i<matrix.size();i++)
for(int j=0;j<matrix[0].size();j++) {
dfs(matrix, visited, 0, i, j, i, j);
}
return matrix;
}

LeetCode529 扫雷游戏

题目

让我们一起来玩扫雷游戏!

给定一个代表游戏板的二维字符矩阵。 ‘M’ 代表一个未挖出的地雷,’E’ 代表一个未挖出的空方块,’B’ 代表没有相邻(上,下,左,右,和所有4个对角线)地雷的已挖出的空白方块,数字(’1’ 到 ‘8’)表示有多少地雷与这块已挖出的方块相邻,’X’ 则表示一个已挖出的地雷。

现在给出在所有未挖出的方块中(’M’或者’E’)的下一个点击位置(行和列索引),根据以下规则,返回相应位置被点击后对应的面板:

如果一个地雷(’M’)被挖出,游戏就结束了- 把它改为 ‘X’。
如果一个没有相邻地雷的空方块(’E’)被挖出,修改它为(’B’),并且所有和其相邻的方块都应该被递归地揭露。
如果一个至少与一个地雷相邻的空方块(’E’)被挖出,修改它为数字(’1’到’8’),表示相邻地雷的数量。
如果在此次点击中,若无更多方块可被揭露,则返回面板。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入:
[['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'M', 'E', 'E'],
['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'E', 'E', 'E']]
Click : [3,0]
输出:
[['B', '1', 'E', '1', 'B'],
['B', '1', 'M', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]

示例 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入:
[['B', '1', 'E', '1', 'B'],
['B', '1', 'M', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]
Click : [1,2]
输出:
[['B', '1', 'E', '1', 'B'],
['B', '1', 'X', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]

注意:

输入矩阵的宽和高的范围为 [1,50]。
点击的位置只能是未被挖出的方块 (‘M’ 或者 ‘E’),这也意味着面板至少包含一个可点击的方块。
输入面板不会是游戏结束的状态(即有地雷已被挖出)。
简单起见,未提及的规则在这个问题中可被忽略。例如,当游戏结束时你不需要挖出所有地雷,考虑所有你可能赢得游戏或标记方块的情况。

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
class Solution {
public:
void dfs(vector<vector<char>>& board,vector<int> click){
int x = click[0];
int y = click[1];
int width = board[0].size();
int height = board.size();
//周围八个格子的坐标
vector<pair<int,int>> dirs ={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
if(x<0 || x>height-1 || y<0 || y>width-1) return;
int mine_count = 0;
遍历周围八个格子同时记录雷的个数
for( auto dir : dirs){
int x_new = x+dir.first;
int y_new = y+dir.second;
if(x_new<0 || x_new>height-1 || y_new<0 || y_new>width-1) continue;
if(board[x_new][y_new] == 'M' || board[x_new][y_new] == 'X' ) mine_count++;
}
//如果雷的个数不为0 这个位置填上雷的个数
if(mine_count!=0) board[x][y] = mine_count +'0';
else { //否则这个位置填上 B 并继续dfs
board[x][y] = 'B';
for(auto dir :dirs){
int new_x = x + dir.first;
int new_y = y +dir.second;
if(new_x>=0 && new_x<height && new_y>=0 && new_y<width && board[new_x][new_y]=='E') //如果即将遍历的点是 E 才遍历,如果是B证明遍历过了,防止死循环
dfs(board,{x+dir.first,y+dir.second});
}
}
}
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
if(board[click[0]][click[1]]=='M') board[click[0]][click[1]]='X';
else dfs(board,click);
return board;
}
};

体会

比较经典的体会,dfs算法完成扫雷。从给定的点开始dfs遍历,每到打一个新点,检查周围八个位置的雷的个数,如果雷的个数不为0,这个点设置为数字,否则这个点就是B。如果这个点是B则继续dfs周围的八个点,搜索的时候要注意 下一个点是E才搜索,不然会陷入死循环。

LeetCode547 朋友圈

题目

班上有 N 名学生。其中有些人是朋友,有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友,B 是 C 的朋友,那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈,是指所有朋友的集合。

给定一个 N * N 的矩阵 M,表示班级中学生之间的朋友关系。如果M[i][j] = 1,表示已知第 i 个和 j 个学生互为朋友关系,否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

示例 1:

1
2
3
4
5
6
7
输入:
[[1,1,0],
[1,1,0],
[0,0,1]]
输出: 2
说明:已知学生0和学生1互为朋友,他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。

示例 2:

1
2
3
4
5
6
输入:
[[1,1,0],
[1,1,1],
[0,1,1]]
输出: 1
说明:已知学生0和学生1互为朋友,学生1和学生2互为朋友,所以学生0和学生2也是朋友,所以他们三个在一个朋友圈,返回1。

注意:

N 在[1,200]的范围内。
对于所有学生,有M[i][i] = 1。
如果有M[i][j] = 1,则有M[j][i] = 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
class Solution {
public:
int dfs(vector<vector<int>> M, vector<bool> &visited, int p) {
if(visited[p]) return 0; //如果当前节点被访问过 直接结束
else {
visited[p] = true; //将当前节点标记为访问过
int count =1;
for (int i = 0; i < M.size(); i++) {//遍历 找到当前这个人的朋友
if (M[p][i] == 1 && !visited[i] && i != p) { //如果M数组值为1 且这个人不是自己 就是朋友
count += dfs(M, visited, i); //接着找朋友
}
}
return count; //最后返回一共找了几次朋友 虽然并不需要这个值 只要有朋友就可以了
}
}
int findCircleNum(vector<vector<int>>& M) {
int py = 0; //朋友圈的个数
vector<bool> visited(M.size(), false);//初始化一个visited数组 用于记录访问的情况
for(int i=0;i<M.size();i++)
if(dfs(M,visited,i)) py++;//如果dfs的结果不是0,证明存在朋友圈。
return py;
}
};

体会

题目挺经典的,一道dfs无回溯题目。将这个题目仔细解读一下,就可以发现我们需要求朋友关系图中的连通分量。采用dfs算法,对每一个人都进行搜索,如果找到了朋友,就把朋友作为起点继续搜索。使用visited数组记录每个人被访问的状态。dfs返回值为int,只要存在朋友圈,返回值就不为0,否则返回0,证明没有找到朋友圈。

LeetCode576 出界的路径数

题目

给定一个 m × n 的网格和一个球。球的起始坐标为 (i,j) ,你可以将球移到相邻的单元格内,或者往上、下、左、右四个方向上移动使球穿过网格边界。但是,你最多可以移动 N 次。找出可以将球移出边界的路径数量。答案可能非常大,返回 结果 mod 109 + 7 的值。

示例 1:

1
2
输入: m = 2, n = 2, N = 2, i = 0, j = 0
输出: 6

示例 2:

1
2
输入: m = 1, n = 3, N = 3, i = 0, j = 1
输出: 12

说明:

球一旦出界,就不能再被移动回网格内。
网格的长度和高度在 [1,50] 的范围内。
N 在 [0,50] 的范围内。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int findPaths(int m, int n, int N, int i, int j) {
vector<vector<vector<int>>> dp(N+1,vector<vector<int>>(m,vector<int>(n,0))); //新建一个dp数组
//dp[k][i][j]表示剩余k步时,起点在[i,j]时的出度数
for(int k=1;k<=N;k++){
for(int x=0;x<m;x++){
for(int y=0;y<n;y++){
long long v1,v2,v3,v4;
if(x==0) v1=1;else v1 = dp[k-1][x-1][y]; //没有到达最顶 就向上移动一位
if(x==m-1) v2=1;else v2 = dp[k-1][x+1][y]; //没有到达最底 就向下移动一位
if(y==0) v3=1;else v3 = dp[k-1][x][y-1]; //没有到达最左 就向左移动一位
if(y==n-1) v4=1;else v4 = dp[k-1][x][y+1]; //没有到达最右 就向右移动一位
dp[k][x][y] = (v1+v2+v3+v4)%1000000007;//dp[k][i][j] 讲就是将四个方向的出度进行求和
}
}
}
return dp[N][i][j];
}
};

体会

这个题其实不是搜索题,是一道DP题。我也写了一份暴搜的代码,运行没问题,但是肯定会超时。底下有这份代码。
DP的思路就是将大问题划分为小问题,列出状态转移方程。这道题 问题[k][i][j]:表示剩余k步时,起点在[i,j]的出届数,这个问题可以转化为 剩余k-1步,起点[i,j]四个方向各点出届数的和。所以状态转移方程 dp[k][i][j] = dp[k-1][i-1][j] + dp[k-1][i+1][j] + dp[k-1][i][j-1] + dp[k-1][i][j+1],编程实现即可。

附:暴搜代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int res = 0;
int findPaths(int m, int n, int N, int i, int j) {
dfs(m,n,N,i,j,0);
return res;
}
void dfs(int m,int n,int N,int i, int j,int now){
if(i<0 || i>m-1 || j<0 || j>n-1){
res ++;
return;
}
if(now == N) return;
dfs(m,n,N,i+1,j,now+1);
dfs(m,n,N,i-1,j,now+1);
dfs(m,n,N,i,j+1,now+1);
dfs(m,n,N,i,j-1,now+1);
}

LeetCode721 账户合并

题目

给定一个列表 accounts,每个元素 accounts[i] 是一个字符串列表,其中第一个元素 accounts[i][0] 是 名称 (name),其余元素是 emails 表示该帐户的邮箱地址。

现在,我们想合并这些帐户。如果两个帐户都有一些共同的邮件地址,则两个帐户必定属于同一个人。请注意,即使两个帐户具有相同的名称,它们也可能属于不同的人,因为人们可能具有相同的名称。一个人最初可以拥有任意数量的帐户,但其所有帐户都具有相同的名称。

合并帐户后,按以下格式返回帐户:每个帐户的第一个元素是名称,其余元素是按顺序排列的邮箱地址。accounts 本身可以以任意顺序返回。

例子 1:

1
2
3
4
5
6
7
8
Input:
accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
Output: [["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'], ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]
Explanation:
第一个和第三个 John 是同一个人,因为他们有共同的电子邮件 "johnsmith@mail.com"。
第二个 John 和 Mary 是不同的人,因为他们的电子邮件地址没有被其他帐户使用。
我们可以以任何顺序返回这些列表,例如答案[['Mary','mary@mail.com'],['John','johnnybravo@mail.com'],
['John','john00@mail.com','john_newyork@mail.com','johnsmith@mail.com']]仍然会被接受。

注意:

accounts的长度将在[1,1000]的范围内。
accounts[i]的长度将在[1,10]的范围内。
accounts[i][j]的长度将在[1,30]的范围内。

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:
vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
map<string,string> root;
map<string,string> owner;
map<string,set<string>> m;
vector<vector<string>> res;
//初始化root 与 owner,开始时 每一个元素都是自己的根节点
for(int i=0;i<accounts.size();i++){
for(int j=0;j<accounts[i].size();j++){
root[accounts[i][j]] = accounts[i][j];
owner[accounts[i][j]] =accounts[i][0];
}
}
//连接同源节点
for(int i=0;i<accounts.size();i++){
string tmp = find(accounts[i][1],root);
for(int j=2;j<accounts[i].size();j++){
root[find(accounts[i][j],root)] = tmp;
}
}
//根据root制作m,m中的每一个元是一个独立树
for(int i=0;i<accounts.size();i++){
for(int j=1;j<accounts[i].size();j++)
m[find(accounts[i][j],root)].insert(accounts[i][j]);
}
//通过m得到最后res
for(auto key : m){
vector<string> one(key.second.begin(), key.second.end());
one.insert(one.begin(),owner[key.first]);
res.push_back(one);
}
return res;
}
//递归查询根节点
string find(string str,map<string,string>&root){
if(str == root[str])
return str;
else return find(root[str],root);
}
};

体会

这个题还是值得一讲的。这是一道运用并查集的题型。最小生成树、亲戚关系的判定、确定无向图的连通子图个数、最小公共祖先问题等,都要用到并查集。我们将题目给的样例简化成如下,进行讲解。

1
2
3
4
J:A B
J:C
J:B D
M:E

首先,初始化root owner。初始化的root中 每一个节点都是自己的根节点.

1
2
3
4
5
6
root: owner: m:
A:A A:J
B:B B:J
C:C C:J
D:D D:J
E:E E:M

根据account连接同源节点得到

1
2
3
4
5
6
root: owner: m:
A:A A:J
B:A B:J
C:C C:J
D:A D:J
E:E E:M

可以看到,现在的root中,非源节点的节点已经连接到了其源节点。这个效果来自于find的递归查询。
通过root建立m

1
2
3
4
5
6
root: owner: m:
A:A A:J A:ABD
B:A B:J C:C
C:C C:J E:E
D:A D:J
E:E E:M

源节点相同的节点已经形成了一棵树。
通过m与owner便可构建出最后的答案。

LeetCode743 网络延迟时

题目

有 N 个网络节点,标记为 1 到 N。

给定一个列表 times,表示信号经过有向边的传递时间。 times[i] = (u, v, w),其中 u 是源节点,v 是目标节点, w 是一个信号从源节点传递到目标节点的时间。

现在,我们向当前的节点 K 发送了一个信号。需要多久才能使所有节点都收到信号?如果不能使所有节点收到信号,返回 -1。

注意:

N 的范围在 [1, 100] 之间。
K 的范围在 [1, N] 之间。
times 的长度在 [1, 6000] 之间。
所有的边 times[i] = (u, v, w) 都有 1 <= u, v <= N 且 1 <= w <= 100。

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
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int N, int K) {
queue<int> q;
vector<int> each_time(N+1,INT_MAX); //each_time表示从K到每个节点的最短距离,初始化为INT_MAX
each_time[K] = 0; //到自己的距离为0
each_time[0] = 0; //0不存在 置为0
//队列模拟bfs算法
q.push(K);
while(!q.empty()){
int curr = q.front();
for(auto i:times){
//如果 目标节点的值 大于 当前节点+当前节点到目标节点的路径 就更新目标节点,并把目标节点放入队列
if(curr == i[0] && each_time[i[1]]>each_time[i[0]]+i[2])
{
q.push(i[1]);
each_time[i[1]] = each_time[i[0]] + i[2];
}
}
q.pop();
}
int ans=0;
//从所有的最短路径中 找出最大的
for(auto a: each_time){
ans = max(a,ans);
}
return (ans == INT_MAX) ? -1 : ans; //输出-1还是输出最大值
}
};

体会

本题题目可以化简为求单源最短路径中的最大值。我们可以使用Dijkstra算法求出单源最短路径,再求最大值,但是这样速度比较慢。这个题我采用BFS算法,速度要快一些。思路很简单,初始节点入队列,在 times 中查找初始节点的目标节点,并对目标节点进行更新。//如果目标节点的值大于当前节点+路径长度就更新目标节点,并把目标节点放入队列。这个思路跟Dijkstra是一样的。最后输出所有最短路径中的最大值就可以,输出时注意判断是否有解。

LeetCode785 判断二分图

题目

给定一个无向图graph,当这个图为二分图时返回true。

如果我们能将一个图的节点集合分割成两个独立的子集A和B,并使图中的每一条边的两个节点一个来自A集合,一个来自B集合,我们就将这个图称为二分图。

graph将会以邻接表方式给出,graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边: graph[i] 中不存在i,并且graph[i]中没有重复的值。

示例 1:

1
2
3
4
5
6
7
8
9
输入: [[1,3], [0,2], [1,3], [0,2]]
输出: true
解释:
无向图如下:
0----1
| |
| |
3----2
我们可以将节点分成两组: {0, 2} 和 {1, 3}。

示例 2:

1
2
3
4
5
6
7
8
9
输入: [[1,2,3], [0,2], [0,1,3], [0,2]]
输出: false
解释:
无向图如下:
0----1
| \ |
| \ |
3----2
我们不能将节点分割成两个独立的子集。

注意:

graph 的长度范围为 [1, 100]。
graph[i] 中的元素的范围为 [0, graph.length - 1]。
graph[i] 不会包含 i 或者有重复的值。
图是无向的: 如果j 在 graph[i]里边, 那么 i 也会在 graph[j]里边。

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
class Solution {
public:
bool dfs(vector<vector<int>>& graph,vector<int> &color,int pos,int c){
color [pos] =c;//将当前点的颜色标记为 c
for(int i=0;i<graph[pos].size();i++){ //寻找当前点的邻居
if(color[graph[pos][i]] == c) return false; //如果当前点的邻居的颜色也是c 则证明重复 返回
if(color[graph[pos][i]] == 0 && !dfs(graph,color,graph[pos][i],-c)) return false; //如果该邻居的还没上色 则给他上-c色,dfs下去,如果全部上色成功,则返回true
}
return true;
}
bool isBipartite(vector<vector<int>>& graph) {
vector<int> color(graph.size(),0);
//遍历所有节点 防止出现图不连通的情况
for(int i=0;i<graph.size();i++){
if(color[i] == 0){
//如果当前点没有上色,则从该点开始上色 初始颜色为1
if(!dfs(graph,color,i,1)){
return false;
}
}
}
return true;
}
};

体会

判断二分图,我们利用染色的方式来解决。使用dfs,对每一个节点先染上C色,判断他的邻居节点,如果颜色也是C,证明冲突,返回false;如果邻居节点没有染色,则尝试给邻居染上-c色,逐层dfs,如果全部染色成功,返回true。
注意,这个题需要对所有的节点都尝试dfs,因为不是每一组输入的图都是连通的。

LeetCode841 钥匙和房间

题目

有 N 个房间,开始时你位于 0 号房间。每个房间有不同的号码:0,1,2,…,N-1,并且房间里可能有一些钥匙能使你进入下一个房间。

在形式上,对于每个房间 i 都有一个钥匙列表 rooms[i],每个钥匙 rooms[i][j] 由 [0,1,…,N-1] 中的一个整数表示,其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。

最初,除 0 号房间外的其余所有房间都被锁住。

你可以自由地在房间之间来回走动。

如果能进入每个房间返回 true,否则返回 false。

示例 1:

1
2
3
4
5
6
7
8
输入: [[1],[2],[3],[]]
输出: true
解释:
我们从 0 号房间开始,拿到钥匙 1。
之后我们去 1 号房间,拿到钥匙 2。
然后我们去 2 号房间,拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间,我们返回 true。

示例 2:

1
2
3
输入:[[1,3],[3,0,1],[2],[0]]
输出:false
解释:我们不能进入 2 号房间。

提示:

1 <= rooms.length <= 1000
0 <= rooms[i].length <= 1000
所有房间中的钥匙数量总计不超过 3000。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
void dfs(vector<vector<int>> &rooms,vector<int> &visited,int room){
if(visited[room]) return; //如果当前节点被访问 就返回
visited[room] = 1; //将当前节点设置为访问
for(int i=0;i<rooms[room].size();i++){ //遍历当前节点的邻居
dfs(rooms,visited,rooms[room][i]);
}
}
bool canVisitAllRooms(vector<vector<int>>& rooms) {
vector<int> visited(rooms.size(),0); //建立一个visited数组
dfs(rooms,visited,0); //从0点开始查询
if(find(visited.begin(),visited.end(),0)==visited.end()) return true; //如果所有的节点都被访问了 就返回true 反之false
else return false;
}
};

体会

经典dfs无回溯题目,直接按思路写就可以,没有难度。具体内容请看注释。当我看到通过率时46.6%时,我就感觉可以1A了。哈哈哈哈哈

LeetCode207 课程表

题目

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

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

给定课程总量以及它们的先决条件,判断是否可能完成所有课程的学习?

示例 1:

1
2
3
输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前,你需要完成课程 0。所以这是可能的。

示例 2:

1
2
3
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前,你需要先完成​课程 0;并且学习课程 0 之前,你还应先完成课程 1。这是不可能的。

说明:

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

这个问题相当于查找一个循环是否存在于有向图中。如果存在循环,则不存在拓扑排序,因此不可能选取所有课程进行学习。
通过 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
class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
map<int,vector<int>> linkGraph;
vector<int> in(numCourses,0);
vector<int> out(numCourses,0);
vector<int> visited(numCourses,0);
//构造图的邻接表
for(auto p:prerequisites){
linkGraph[p.first].push_back(p.second);
in[p.second]++;
out[p.first]++;
}
queue<int> que;
//将所有入度为0的点 放入队列中
for(int i=0;i<in.size();i++)
if(in[i]==0) que.push(i);
while(!que.empty()){
int tmp = que.front(); // 去除队列首元素
que.pop();
for(auto i : linkGraph[tmp]){ //删除该节点 要将与其连接的节点的入度都-1
in[i]--;
if(in[i]==0){ //如果入度为0 添加进队列
que.push(i);
}
}
}
if(*max_element(in.begin(),in.end())==0) return true; //入度全为0 证明 环
else return false;
}
};

体会

这一份应该是网上本题最清晰简单的解法了。考察拓扑排序,第一次坐到这个问题。去一个图是否是拓扑可排的方法就两种,DFS每次删去出度为0的节点,BFS每次删去入度为0的节点,最终判断是否所有的出度/入度都为0,如果都为0,证明无环,拓扑可排。
思路:将边缘列表转换为临接表,同是记录下每一个节点的入度。
将所有入度为0的节点,入队。
每次取出队首元素,删除它,将其连接节点的入度-1,如果入度为0的话,放入队列中,重复此过程。
最后判断所有的入度是否都是0,都是则无环,输出。