快捷導(dǎo)航

Java 超詳細講解數(shù)據(jù)結(jié)構(gòu)的應(yīng)用

更新時間：2022年04月08日 10:23:59 作者：撩得Android一次心動

數(shù)據(jù)結(jié)構(gòu)是計算機存儲、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，讓我們一起來了解數(shù)據(jù)結(jié)構(gòu)是如何應(yīng)用的

一.bfs

bfs（廣度優(yōu)先搜索），類似二叉樹的層序遍歷，利用隊列完成。一般用于求最短路。

圖的最短路問題：

給定一個無向圖，每條邊的長度都是1。求1號點到x號點的最短距離。頂點數(shù)n ?邊數(shù)為m

q次詢問 ?輸入x 輸出1到x的最短距離。若1號點到x不連通，則輸出-1

二.雙端隊列

雙端隊列的應(yīng)用（區(qū)間翻轉(zhuǎn)）：

對于長度為n的數(shù)組，給定一個長度為m的區(qū)間，區(qū)間初始位置為a[1]到a[m]。

3種操作：

區(qū)間右移（最右端不會超過a[n]）
區(qū)間左移（最左端不會超過a[n]）
區(qū)間內(nèi)所有數(shù)翻轉(zhuǎn)。

q次操作后請你還原數(shù)組。

三.算法題

1.kotori和迷宮

難度??

知識點：bfs

首先找到k字母，然后從k字母位置開始bfs。bfs過程中即可得到k到每個e的最短路程。（要注意走過的e不可繼續(xù)往下走）

題目描述：

kotori在一個n*m迷宮里，迷宮的最外層被巖漿淹沒，無法涉足，迷宮內(nèi)有k個出口。kotori只能上下左右四個方向移動。她想知道有多少出口是她能到達的，最近的出口離她有多遠？

輸入描述:

第一行為兩個整數(shù)n和m，代表迷宮的行和列數(shù) (1≤n,m≤30)

后面緊跟著n行長度為m的字符串來描述迷宮。'k'代表kotori開始的位置，'.'代表道路，'*'代表墻壁，'e'代表出口。保證輸入合法。

輸出描述:

若有出口可以抵達，則輸出2個整數(shù)，第一個代表kotori可選擇的出口的數(shù)量，第二個代表kotori到最近的出口的步數(shù)。（注意，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];
    //紀錄步數(shù)
    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<>();
    //二維數(shù)組的性質(zhì)，保存了坐標，并且節(jié)省了空間
    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);
  }
}

思考：隊列是怎么實現(xiàn)bfs的？

1.起始點入隊-->2.將起始點四個方向的可達點入隊-->3.起始點出隊。以此循序依次訪問隊列中的元素。

2.小紅找紅點

難度???

知識點：bfs，多源最短路

多源最短路的求法：在bfs開始之前將所有點都扔進隊列，然后開始bfs即可。

題目描述：

小紅拿到了一張無向圖，有 n?個頂點和?m?條邊。每條邊的長度為 1 。?

小紅給一些頂點染成了紅色。她想知道，對于每個頂點，到附近最近的紅色點的距離為多少？

輸入描述:

第一行輸出兩個正整數(shù) n 和 m ，用空格隔開。分別代表頂點數(shù)和邊數(shù)。

第二行輸入一個長度為 n 的字符串，代表每個頂點的染色情況。第?i 個字符為 'R' 代表被染成紅色，為 'W' 代表未被染色。

接下來的?m 行，每行兩個正整數(shù) x 和?y ，代表?x 和?y 有一條無向邊相連。

不保證圖是整體連通的。不保證沒有重邊和自環(huán)。

1<=n,m<=10^5

輸出描述:

輸出一行 n 個整數(shù)，代表從?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]代表當(dāng)前點 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]+" ");
        }
    }
}

對照上一章的案例：小紅點點點結(jié)合理解。? 分別使用的dfs和bfs。

本題思想：先將紅色的所有點都入隊列，然后bfs。

這是一種逆向思維：不是所謂的從編號開始，并且所有走過的都不能在走了。

3.小紅玩數(shù)組?

難度????

知識點：雙端隊列

用一個雙端隊列來模擬過程，用一個變量來標記雙端隊列是否翻轉(zhuǎn)過。

示例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代表沒有翻轉(zhuǎn)！
        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();
 
    }
}

到此這篇關(guān)于Java 超詳細講解數(shù)據(jù)結(jié)構(gòu)的應(yīng)用的文章就介紹到這了,更多相關(guān)Java 數(shù)據(jù)結(jié)構(gòu)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: