leetcode之dfs+bfs+dsu刷题总结1
1-所有可能的路径
题目链接：题目链接戳这里！！！
思路：dfs搜索所有路径，并用栈记录搜索轨迹。
class Solution {
Stack<Integer> stack = new Stack<>() ;
List<List<Integer>> list = new ArrayList<>() ;
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
dfs(0,graph) ;
return list ;
}
public void dfs(int x, int [][] graph){
stack.push(x) ;
if(x==graph.length-1){
list.add(new ArrayList<>(stack)) ;
}
for(int y : graph[x]){
dfs(y,graph) ;
}
stack.pop() ;
}
}
2-判断二分图
题目链接：题目链接戳这里！！！
思路：dfs+染色法。
我们使用图搜索算法从各个连通域的任一顶点开始遍历整个连通域，遍历的过程中用两种不同的颜色对顶点进行染色，相邻顶点染成相反的颜色。这个过程中倘若发现相邻的顶点被染成了相同的颜色，说明它不是二分图；反之，如果所有的连通域都染色成功，说明它是二分图。
class Solution {
public boolean isBipartite(int[][] graph) {
int [] vis = new int [graph.length] ;
for(int i=0; i<graph.length; i++){
if(vis[i]==0 && !dfs(graph,i,1,vis)){
return false ;
}
}
return true ;
}
public boolean dfs(int [][] graph, int x, int color, int [] vis){
if(vis[x]!=0){
return vis[x] == color ;
}
vis[x] = color ;
for(int y : graph[x]){
if(!dfs(graph,y,-color,vis)){
return false ;
}
}
return true ;
}
}
思路2：bfs+染色法
对于每个顶点，如果未被访问过，则入队，对于该顶点的所有邻接顶点，如果已经被染色，且颜色与当前颜色相同，则不是二分图，如果未被染色，则应染成和相邻顶点相同的颜色。
class Solution {
public boolean isBipartite(int[][] graph) {
int [] vis = new int [graph.length] ;
Queue<Integer> queue = new LinkedList<>() ;
for(int i=0; i<graph.length; i++){
if(vis[i]!=0){
continue ;
}
queue.add(i) ;
vis[i] = 1 ;
while(!queue.isEmpty()){
int x = queue.poll() ;
for(int y : graph[x]){
if(vis[y]==vis[x]){
return false ;
}
if(vis[y]==0){
vis[y] = -vis[x] ;
queue.add(y) ;
}
}
}
}
return true ;
}
}
3-地图中的最高点
题目链接：题目链接戳这里！！！
思路：多源bfs
题目要求让矩阵中的最高高度最大，我们可以通过最大化每个格子的高度来做到这一点。由于任意相邻的格子高度差至多为 1，这意味着对于每个格子，其高度至多比其相邻格子中的最小高度多 1。
题目要求水域的高度必须为 0，因此水域的高度是已经确定的值，我们可以从水域出发，推导出其余格子的高度：
首先，计算与水域相邻的格子的高度。对于这些格子来说，其相邻格子中的最小高度即为水域的高度 0，因此这些格子的高度为 1。
然后，计算与高度为 1 的格子相邻的、尚未被计算过的格子的高度。对于这些格子来说，其相邻格子中的最小高度为 1，因此这些格子的高度为 2。
以此类推，计算出所有格子的高度。
记录下所有水域的位置，然后执行广度优先搜索，计算出所有陆地格子的高度，即为答案。
class Solution {
int [] dx = {-1,1,0,0} ;
int [] dy = {0,0,-1,1} ;
public int[][] highestPeak(int[][] isWater) {
int [][] ans = new int [isWater.length][isWater[0].length] ;
for(int i=0; i<ans.length; i++){
Arrays.fill(ans[i], -1) ; //初始化所有顶点未被访问
}
Queue<int[]> queue = new ArrayDeque<int[]>() ;
for(int i=0; i<isWater.length; i++){
for(int j=0; j<isWater[0].length; j++){
if(isWater[i][j]==1){
ans[i][j] = 0 ;
queue.add(new int []{i,j}) ;
}
}
}
while(!queue.isEmpty()){
int [] p = queue.poll() ;
for(int i=0; i<4; i++){
int tx = p[0] + dx[i] ;
int ty = p[1] + dy[i] ;
if(tx>=0 && ty>=0 && tx<isWater.length && ty<isWater[0].length && ans[tx][ty]==-1){
ans[tx][ty] = ans[p[0]][p[1]] + 1 ;
queue.add(new int []{tx,ty}) ;
}
}
}
return ans ;
}
}
4-所有路径
题目链接：题目链接戳这里！！！
思路：dfs+栈记录
从0号顶点出发，依次搜索相邻顶点，并用栈记录搜索轨迹。
class Solution {
List<List<Integer>> list = new ArrayList<>() ;
Stack<Integer> stack = new Stack<>() ;
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
dfs(graph,0) ;
return list ;
}
public void dfs(int [][] graph, int x){
stack.push(x) ;
if(x==graph.length-1){
list.add(new ArrayList<>(stack)) ;
}
for(int y : graph[x]){
dfs(graph,y) ;
}
stack.pop() ;
}
}
5-多余的边
题目链接：题目链接戳这里！！！
思路:并查集
在一棵树中，边的数量比节点的数量少 1。如果一棵树有 n 个节点，则这棵树有 n?1 条边。这道题中的图在树的基础上多了一条边，因此边的数量也是 n。
树是一个连通且无环的无向图，在树中多了一条边之后就会出现环，因此多余的边即为导致环出现的边。
可以通过并查集寻找多余的边。初始时，每个节点都属于不同的连通分量。遍历每一条边，判断这条边连接的两个顶点是否属于相同的连通分量。
如果两个顶点属于不同的连通分量，则说明在遍历到当前的边之前，这两个顶点之间不连通，因此当前的边不会导致环出现，合并这两个顶点的连通分量。
如果两个顶点属于相同的连通分量，则说明在遍历到当前的边之前，这两个顶点之间已经连通，因此当前的边导致环出现，为多余的边，将当前的边作为答案返回。
class Solution {
public int[] findRedundantConnection(int[][] edges) {
int n = edges.length ;
int [] parent = new int [n+1] ;
for(int i=1; i<=n; i++){
parent[i] = i ;
}
for(int i=0; i<n; i++){
int [] edge = edges[i] ;
int node0 = edge[0], node1 = edge[1] ;
if(find(parent,node0)!=find(parent,node1)){
union(parent,node0,node1) ;
}else{
return edge ;
}
}
return new int []{} ;
}
public int find(int [] parent, int node){
if(node!=parent[node]){
parent[node] = find(parent,parent[node]) ;
}
return parent[node] ;
}
public void union(int [] parent, int node1, int node0){
parent[parent[node1]] = find(parent,parent[node0]) ;
}
}
6-矩阵中的距离
题目链接：题目链接戳这里！！！
思路：bfs
首先将所有的0入队，然后多元广度优先搜索，如果其它相邻点未搜索过，则为当前点加1.
class Solution {
int [] dx = {-1,1,0,0} ;
int [] dy = {0,0,-1,1} ;
public int[][] updateMatrix(int[][] mat) {
//广度优先搜索
int m = mat.length ;
int n = mat[0].length ;
Queue<int[]> queue = new LinkedList<int[]>() ;
int [][] ans = new int [m][n] ;
boolean [][] vis = new boolean [m][n] ;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(mat[i][j] == 0){
queue.add(new int [] {i,j}) ;
vis[i][j] = true ;
}
}
}
while(!queue.isEmpty()){
int [] edge = queue.poll() ;
for(int i=0; i<4; i++){
int tx = edge[0] + dx[i] ;
int ty = edge[1] + dy[i] ;
if(tx>=0 && ty>=0 && tx<m && ty<n && !vis[tx][ty]){
ans[tx][ty] = ans[edge[0]][edge[1]] + 1 ;
queue.add(new int []{tx,ty}) ;
vis[tx][ty] = true ;
}
}
}
return ans ;
}
}
7-最小基因变化
题目链接：题目链接戳这里！！！
思路：bfs+剪枝
题目给定一个起始字符串start和一个目标字符串end, 其中start只能通过以下步骤变化为新的字符串。
每一次变化，都只能用"A", “C”, “G”, "T"里的任意一个字母替换当前字符串里的某一个字母。
替换后得到的新的字符串必须在给定的bank里。
明确这两点之后，我们很容易地想到这个题建模为树(具体来说，无权树)，可知只不过这个树的子树会比较多，可以剪枝。
class Solution {
public int minMutation(String start, String end, String[] bank) {
Set<String> bankSet = new HashSet<>() ;
for(String str : bank){
bankSet.add(str) ;
}
String [] gene = {"A","C","G","T"} ;
Set<String> vis = new HashSet<>() ;
Queue<String> queue = new LinkedList<>() ;
vis.add(start) ;
queue.add(start) ;
int step = 0 ;
while(!queue.isEmpty()){
int size = queue.size() ;
for(int k=0; k<size; k++){
String s = queue.poll() ;
if(s.equals(end)){
return step ;
}
for(int i=0; i<s.length(); i++){
StringBuilder cur = new StringBuilder(s) ;
for(int j=0; j<gene.length; j++){
String ans = cur.replace(i,i+1,gene[j]).toString() ;
if(!vis.contains(ans) && bankSet.contains(ans)){
queue.add(ans) ;
vis.add(ans) ;
}
}
}
}
step ++ ;
}
return -1 ;
}
}
8-打开转盘锁
题目链接：题目链接戳这里！！！
思路：bfs+剪支
我们可以使用广度优先搜索，找出从初始数字 0000 到解锁数字target 的最小旋转次数。
具体地，我们在一开始将 0000 加入队列，并使用该队列进行广度优先搜索。在搜索的过程中，设当前搜索到的数字为 status，旋转的次数为 step，我们可以枚举 status 通过一次旋转得到的数字。设其中的某个数字为 next，如果其没有被搜索过，我们就将 next加入队列。如果搜索到了target，我们就返回其对应的旋转次数。
为了避免搜索到死亡数字，我们可以使用哈希表存储 deadends 中的所有元素，这样在搜索的过程中，我们可以均摊 O(1)地判断一个数字是否为死亡数字。同时，我们还需要一个哈希表存储所有搜索到的状态，避免重复搜索。
如果搜索完成后，我们仍没有搜索到 target，说明我们无法解锁，返回 -1。
class Solution {
public int openLock(String[] deadends, String target) {
if("0000".equals(target)){
return 0 ;
}
Set<String> deadSet = new HashSet<>() ;
for(String str : deadends){
deadSet.add(str) ;
}
Set<String> vis = new HashSet<>() ;
Queue<String> queue = new LinkedList<>() ;
vis.add("0000") ;
queue.add("0000") ;
if(deadSet.contains("0000")){
return -1 ;
}
int step=0;
while(!queue.isEmpty()){
step ++ ;
int size = queue.size() ;
for(int i=0; i<size; i++){
String status = queue.poll() ;
for(String next : get(status)){
if(!vis.contains(next) && !deadSet.contains(next)){
if(next.equals(target)){
return step ;
}
queue.add(next) ;
vis.add(next) ;
}
}
}
}
return -1 ;
}
public char f1(char ch){
return ch=='9' ? '0' : (char)(ch+1) ;
}
public char f2(char ch){
return ch=='0' ? '9' : (char)(ch-1) ;
}
public List<String> get(String s){
List<String> res = new ArrayList<>() ;
char [] c = s.toCharArray() ;
for(int i=0; i<c.length;i++){
char num = c[i] ;
c[i] = f1(c[i]) ;
res.add(new String(c)) ;
c[i] = f2(num) ;
res.add(new String(c)) ;
c[i] = num ;
}
return res ;
}
}
9-连通网络的操作次数
题目链接：题目链接戳这里！！！
思路1：并查集
我们可以使用并查集来得到图中的连通分量数。
并查集本身就是用来维护连通性的数据结构。如果其包含 n 个节点，那么初始时连通分量数为 n，每成功进行一次合并操作，连通分量数就会减少 1。
将所有已经联通的合并为一个集合，每次访问每个元素的根节点，如果不是它本身，联通分量就累加1，联通分量数减1就是答案。
class Solution {
public int makeConnected(int n, int[][] connections) {
if(n-1>connections.length){
return -1 ;
}
//并查集
int [] parent = new int [n+1] ;
for(int i=1; i<=n; i++){
parent[i] = i ;
}
for(int [] connection : connections){
union(parent,connection[0]+1,connection[1]+1) ;
}
int cnt = 0 ;
for(int i=1; i<=n; i++){
if(i==parent[i]){
cnt ++ ;
}
}
return cnt - 1 ;
}
public int find(int [] parent, int x){
if(x!=parent[x]){
parent[x] = find(parent,parent[x]) ;
}
return parent[x] ;
}
public void union(int [] parent, int x, int y){
int root1 = find(parent,x) ;
int root2 = find(parent,y) ;
if(root1==root2){
return ;
}
parent[root1] = root2 ;
}
}
思路2：dfs
建立双向邻接表，然后深度优先搜索，统计联通分量个数，联通分量个数减去1就是答案。然而深搜的效率比并查集低很多。
class Solution {
public int makeConnected(int n, int[][] connections) {
if(n-1>connections.length){
return -1 ;
}
List<List<Integer>> edges = new ArrayList<>() ;
for(int i=0; i<n; i++){
edges.add(new ArrayList<>()) ;
}
for(int [] connection : connections){
edges.get(connection[0]).add(connection[1]) ;
edges.get(connection[1]).add(connection[0]) ;
}
int ans = 0 ;
boolean [] vis = new boolean[n] ;
for(int i=0; i<n; i++){
if(!vis[i]){
dfs(edges,i,vis) ;
ans ++ ;
}
}
return ans - 1 ;
}
public void dfs(List<List<Integer>> edges, int x, boolean [] vis){
vis[x] = true ;
for(int y : edges.get(x)){
if(!vis[y]){
dfs(edges,y,vis) ;
}
}
}
}
10-开锁密码
题目链接：题目链接戳这里！！！
思路：bfs+剪支
我们可以使用广度优先搜索，找出从初始数字 0000 到解锁数字target 的最小旋转次数。
具体地，我们在一开始将 0000 加入队列，并使用该队列进行广度优先搜索。在搜索的过程中，设当前搜索到的数字为 str，旋转的次数为 step，我们可以枚举 str 通过一次旋转得到的数字。设其中的某个数字为 next，如果其没有被搜索过，我们就将 next加入队列。如果搜索到了target，我们就返回其对应的旋转次数。
为了避免搜索到死亡数字，我们可以使用哈希表存储 deadends 中的所有元素，这样在搜索的过程中，我们可以均摊 O(1)地判断一个数字是否为死亡数字。同时，我们还需要一个哈希表存储所有搜索到的状态，避免重复搜索。
如果搜索完成后，我们仍没有搜索到 target，说明我们无法解锁，返回 -1。
class Solution {
public int openLock(String[] deadends, String target) {
//广度优先搜索
if("0000".equals(target)){
return 0 ;
}
Set<String> deadSet = new HashSet<>() ;
for(int i=0; i<deadends.length; i++){
deadSet.add(deadends[i]) ;
}
Set<String> vis = new HashSet<>() ;
Queue<String> queue = new LinkedList<>() ;
vis.add("0000") ;
queue.add("0000") ;
if(deadSet.contains("0000")){
return -1 ;
}
int step = 0 ;
while(!queue.isEmpty()){
step ++ ;
int size = queue.size() ;
for(int i=0; i<size; i++){
String str = queue.poll() ;
for(String next : get(str)){
if(!vis.contains(next) && !deadSet.contains(next)){
if(next.equals(target)){
return step ;
}
queue.add(next) ;
vis.add(next) ;
}
}
}
}
return -1 ;
}
public List<String> get(String s){
char [] c = s.toCharArray() ;
List<String> ans = new ArrayList<>() ;
for(int i=0; i<c.length; i++){
char num = c[i] ;
c[i] = f1(c[i]) ;
ans.add(new String(c)) ;
c[i] = f2(num) ;
ans.add(new String(c)) ;
c[i] = num ;
}
return ans ;
}
public char f1(char ch){
return ch=='9' ? '0' : (char)(ch+1) ;
}
public char f2(char ch){
return ch=='0' ? '9' : (char)(ch-1) ;
}
}
11-颜色填充
题目链接：题目链接戳这里！！！
思路1：dfs+标记
如果四个方向满足条件，就沿着四个方向搜索，并涂色。
class Solution {
int [] dx = {-1,1,0,0} ;
int [] dy = {0,0,-1,1} ;
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
dfs(image,sr,sc,newColor,image[sr][sc]) ;
return image ;
}
public void dfs(int [][] image, int x, int y, int newColor, int n){
image[x][y] = newColor ;
for(int i=0; i<4; i++){
int tx = x + dx[i] ;
int ty = y + dy[i] ;
if(tx>=0 && ty>=0 && tx<image.length && ty<image[0].length && image[tx][ty]==n && image[tx][ty]!=newColor){
dfs(image,tx,ty,newColor,n) ;
}
}
}
}
思路2：bfs
将第一个坐标位置涂色，并将坐标入队，每次沿着四个方向涂色即可。
class Solution {
int [] dx = {-1,1,0,0} ;
int [] dy = {0,0,-1,1} ;
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
Queue<int[]> queue = new LinkedList<int[]>() ;
int n = image[sr][sc] ;
image[sr][sc] = newColor ;
queue.add(new int []{sr,sc}) ;
while(!queue.isEmpty()){
int [] a = queue.poll() ;
for(int i=0; i<4; i++){
int tx = a[0] + dx[i] ;
int ty = a[1] + dy[i] ;
if(tx>=0 && ty>=0 && tx<image.length && ty<image[0].length && image[tx][ty] != newColor && image[tx][ty]==n){
image[tx][ty] = newColor ;
queue.add(new int []{tx,ty}) ;
}
}
}
return image ;
}
}
