Java超詳細精講數據結構之bfs與雙端隊列
一.bfs
bfs（廣度優先搜索），類似二叉樹的層序遍歷，利用隊列完成。一般用於求最短路。
圖的最短路問題：
給定一個無向圖，每條邊的長度都是1。求1號點到x號點的最短距離。 頂點數n 邊數為m
q次詢問 輸入x 輸出1到x的最短距離。 若1號點到x不連通，則輸出-1
二.雙端隊列
雙端隊列的應用（區間翻轉）：
對於長度為n的數組，給定一個長度為m的區間，區間初始位置為a[1]到a[m]。
3種操作：
- 區間右移（最右端不會超過a[n]）
- 區間左移（最左端不會超過a[n]）
- 區間內所有數翻轉。
q次操作後請你還原數組。
三.算法題
1.kotori和迷宮
難度⭐⭐
知識點：bfs
首先找到k字母，然後從k字母位置開始bfs。bfs過程中即可得到k到每個e的最短路程。（要註意走過的e不可繼續往下走）
題目描述：
kotori在一個n*m迷宮裡，迷宮的最外層被巖漿淹沒，無法涉足，迷宮內有k個出口。kotori隻能上下左右四個方向移動。她想知道有多少出口是她能到達的，最近的出口離她有多遠？
輸入描述:
第一行為兩個整數n和m，代表迷宮的行和列數 (1≤n,m≤30)
後面緊跟著n行長度為m的字符串來描述迷宮。'k'代表kotori開始的位置，'.'代表道路，'*'代表墻壁，'e'代表出口。保證輸入合法。
輸出描述:
若有出口可以抵達，則輸出2個整數，第一個代表kotori可選擇的出口的數量，第二個代表kotori到最近的出口的步數。（註意，kotori到達出口一定會離開迷宮）
若沒有出口可以抵達，則輸出-1。
示例1
輸入
6 8
e.*.*e.*
.**.*.*e
..*k**..
***.*.e*
.**.*.**
*……e
輸出
2 7
說明
可供選擇坐標為[4,7]和[6,8]，到kotori的距離分別是8和7步。
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = bf.readLine().split(" ");
int n = Integer.parseInt(s1[0]);
int m = Integer.parseInt(s1[1]);
//建立地圖、標記圖
char[][] maze = new char[n][m];
boolean[][] visited = new boolean[n][m];
//紀錄步數
int[][] dis = new int[n][m];
//紀錄初始的坐標
int ki = 0, kj = 0;
for(int i = 0; i < n; i++){
String s = bf.readLine();
for(int j = 0; j < m; j++){
dis[i][j] = Integer.MAX_VALUE;
char c = s.charAt(j);
maze[i][j] = c;
if(c == 'k'){
ki = i;
kj = j;
}
}
}
int count = 0, min = Integer.MAX_VALUE;
Queue<Integer> queue = new ArrayDeque<>();
//二維數組的性質，保存瞭坐標，並且節省瞭空間
queue.add(ki * m + kj);
visited[ki][kj] = true;
dis[ki][kj]= 0;
while(!queue.isEmpty()){
int temp = queue.poll();
int tempi = temp / m, tempj = temp % m;
//支持八個方向的移動或者不移動（但是因為Math.abs(i - j) == 1限定瞭絕對值為1，所以變成瞭四個方向）
for(int i = -1; i <= 1; i++){
for(int j = -1; j <= 1; j++){
if(Math.abs(i - j) == 1 && tempi + i >= 0 && tempi + i < n && tempj + j >= 0 && tempj + j < m && !visited[tempi + i][tempj + j]){
if(maze[tempi + i][tempj + j] == '.'){
visited[tempi + i][tempj + j] = true;
dis[tempi + i][tempj + j] = dis[tempi][tempj] + 1;
queue.add((tempi + i) * m + (tempj + j));
}
if(maze[tempi + i][tempj + j] == 'e'){
visited[tempi + i][tempj + j] = true;
dis[tempi + i][tempj + j] = dis[tempi][tempj] + 1;
min = Math.min(min, dis[tempi][tempj] + 1);
count++;
}
}
}
}
}
if(count == 0) System.out.print(-1);
else System.out.print(count + " " + min);
}
}
思考：隊列是怎麼實現bfs的？
1.起始點入隊–>2.將起始點四個方向的可達點入隊–>3.起始點出隊。以此循序依次訪問隊列中的元素。
2.小紅找紅點
難度⭐⭐⭐
知識點：bfs，多源最短路
多源最短路的求法：在bfs開始之前將所有點都扔進隊列，然後開始bfs即可。
題目描述：
小紅拿到瞭一張無向圖，有 n個頂點和m條邊。每條邊的長度為 1 。
小紅給一些頂點染成瞭紅色。她想知道，對於每個頂點，到附近最近的紅色點的距離為多少？
輸入描述:
第一行輸出兩個正整數 n 和 m ，用空格隔開。分別代表頂點數和邊數。
第二行輸入一個長度為 n 的字符串，代表每個頂點的染色情況。第i 個字符為 'R' 代表被染成紅色，為 'W' 代表未被染色。
接下來的m 行，每行兩個正整數 x 和y ，代表x 和y 有一條無向邊相連。
不保證圖是整體連通的。不保證沒有重邊和自環。
1<=n,m<=10^5
輸出描述:
輸出一行 n 個整數，代表從1 到 n 每個頂點到最近的紅色頂點的距離。若對於某點而言無論如何都走不到紅色頂點，則輸出 -1 。
示例1:
輸入
5 5
RWWRW
1 2
3 3
1 2
2 5
1 4
輸出
0 1 -1 0 2
說明
樣例的圖如上所示。
import java.util.*;
import java.io.*;
public class Main{
static ArrayList<Integer>[] g;
static String[] strings;
static int[] visited;
static int[] dis;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] firstLine = br.readLine().split(" ");
int n = Integer.parseInt(firstLine[0]);
int m = Integer.parseInt(firstLine[1]);
g = new ArrayList[n+1];
visited = new int[n+1];
dis= new int[n+1];
for (int i=1;i<n+1;i++) {
g[i] = new ArrayList<Integer>();
}
//一個字符一個字符的讀取
strings = br.readLine().split("");
for (int i=0;i<m;i++) {
//描繪雙向圖
String[] temp = br.readLine().split(" ");
int x = Integer.parseInt(temp[0]);
int y = Integer.parseInt(temp[1]);
g[x].add(y);
g[y].add(x);
}
//g[x]代表當前點 g[x].get(i)代表所連的線
Queue<Integer> queue = new ArrayDeque<>();
for(int i=1;i<=n;i++){
if(strings[i-1].equals("R")){
queue.add(i);
visited[i]=1;
}
}
while(!queue.isEmpty()){
int temp=queue.remove();
for(int i=0;i<g[temp].size();i++){
if(visited[g[temp].get(i)]==0){
visited[g[temp].get(i)]=1;
dis[g[temp].get(i)]=dis[temp]+1;
queue.add(g[temp].get(i));
}
}
}
for(int i=1;i<=n;i++){
if(visited[i]==0)System.out.print("-1 ");
else System.out.print(dis[i]+" ");
}
}
}
對照上一章的案例：小紅點點點結合理解。 分別使用的dfs和bfs。
本題思想：先將紅色的所有點都入隊列，然後bfs。
這是一種逆向思維：不是所謂的從編號開始，並且所有走過的都不能在走瞭。
3.小紅玩數組
難度⭐⭐⭐⭐
知識點：雙端隊列
用一個雙端隊列來模擬過程，用一個變量來標記雙端隊列是否翻轉過。
示例1：
輸入
6 4
1 5 4 6 2 8
5
21323
輸出
4 6 2 1 5 8
import java.io.*;
import java.util.*;
public class Main{
static Deque<Integer> workQueue;
public static void main(String[] args)throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw=new PrintWriter(System.out);
String[] firstLine=br.readLine().split(" ");
int total=Integer.parseInt(firstLine[0]);
int size=Integer.parseInt(firstLine[1]);
int[] arr=new int[total];
String[] secondLine=br.readLine().split(" ");
for(int i=0;i<total;i++){
arr[i]=Integer.parseInt(secondLine[i]);
}
int L=0;
int R=size-1;
workQueue=new LinkedList<>();
for(int i=0;i<size;i++){
workQueue.offerLast(arr[i]);
}
int times=Integer.parseInt(br.readLine());
String tries=br.readLine();
int is=0;//0代表沒有翻轉！
for(int i=0;i<times;i++){
if(tries.charAt(i)=='1'){
if(R==arr.length-1)
continue;
R++;
if(is==0){
workQueue.offerLast(arr[R]);
int tmp=workQueue.pollFirst();
arr[L]=tmp;
}else{
workQueue.offerFirst(arr[R]);
int tmp=workQueue.pollLast();
arr[L]=tmp;
}
L++;
}else if(tries.charAt(i)=='2'){
if(L==0)
continue;
L--;
if(is==0){
workQueue.offerFirst(arr[L]);
arr[R]=workQueue.pollLast();
}else{
workQueue.offerLast(arr[L]);
arr[R]=workQueue.pollFirst();
}
R--;
}else{
is=1-is;
}
}
for(int i=0;i<L;i++){
pw.print(arr[i]+" ");
}
if(is==0){
while(!workQueue.isEmpty()) {
pw.print(workQueue.pollFirst() + " ");
}
}else{
while(!workQueue.isEmpty()) {
pw.print(workQueue.pollLast() + " ");
}
}
for(int i=R+1;i<arr.length;i++){
pw.print(arr[i]+" ");
}
pw.flush();
}
}
到此這篇關於Java超詳細精講數據結構之bfs與雙端隊列的文章就介紹到這瞭,更多相關Java bfs與雙端隊列內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！
推薦閱讀：
- Java中BufferedReader與Scanner讀入的區別詳解
- java:無法訪問org.springframework.boot.SpringApplication的解決方法
- java使用IO流對數組排序實例講解
- 關於BufferedReader的讀取效率問題
- 使用BufferedReader讀取TXT文件中數值,並輸出最大值