• AcWing 蓝桥杯AB组辅导课 06、双指针、BFS与图论

    文章目录

    前言

    前段时间为了在面试中能够应对一些算法题走上了刷题之路，大多数都是在力扣平台刷，目前是400+，再加上到了新学校之后，了解到学校也有组织蓝桥杯相关的程序竞赛，打算再次尝试一下，就想系统学习一下算法（再此之前是主后端工程为主，算法了解不多刷过一小段时间），前段时间也是第一次访问acwing这个平台，感觉上面课程也是比较系统，平台上题量也很多，就打算跟着acwing的课程来走一段路，大家一起共勉加油！

    • 目前是打算参加Java组，所以所有的题解都是Java。

    所有博客文件目录索引：博客目录索引(持续更新)

    本章节双指针、BFS与图论的习题一览：包含所有题目的Java题解链接

    第六讲完结日期：2023.1.8

    image-20230108201304292

    例题：

    习题：

    一、双指针

    知识点

    例题

    例题1：1238. 日志统计【中等，蓝桥杯】

    题目链接：1238. 日志统计

    标签：双指针、滑动窗口

    分析：

    首先是输入大小范围分析：

    K：赞数  n：日志的长度(输入的数量)    100000
ts：时刻、id：帖子id                100000
D：时间长度                        10000

    • 1
    • 2
    • 3

    数据量是10万，O(n2)平方的话肯定直接超时，基本就是O(n)或者O(nlogn)。

    原本自己的暴力思路就是遍历1-10万的所有的时刻，每一个时刻去比对每个订单，那这个复杂度就是上面所说的O(n2)，这个思路就肯定pass了。

    接着通过看题解，才发现这道题O(nlogn)的巧妙之处，我们转换一下思路，并不是遍历所有时刻，而是遍历所有根据时刻排好序的订单，由于时刻是排好序的，随着从前往后推移，以时间长度作为窗口，虽说每次遍历到的是不同的订单，但是同样窗口之间的时间范围是确定的，这一点是我一开始没有想得到的。

    巧妙点：多订单根据点赞的时刻先来进行排序，接着以两个订单之间的时刻作为窗口大小来进行不断滑动，达到遍历所有订单时仅有O(n)的时间复杂度。

    题解：

    复杂度分析：时间复杂度O(n.logn)【sort的时间的复杂度，下面的for循环O(n)】；空间复杂度O(n)

    //K：赞数  n：日志的长度(输入的数量)    100000
//ts：时刻、id：帖子id                  100000
//D：时间长度                           10000

//条件为[T, T + D)中满足 >= K个赞 即表示是热帖，该ID就需要被记录
//输出所有的帖子ID

//遍历所有的帖子数，每个帖子的时刻
//尝试：90000 x 100000

import java.io.*;
import java.util.*;

//帖子
class Log implements Comparable<Log>{
    int ts;
    int id;
    public Log(int ts, int id) {
        this.ts = ts;
        this.id = id;
    }
    
    @Override
    public int compareTo(Log l) {
        return this.ts - l.ts;
    }
}

class Main {
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    static int N = 100010;
    static int K, n, D;
    //记录所有的日志（时刻、帖子）
    static Log[] logs = new Log[N];
    //记录指定帖子的点赞数
    static int[] cnt = new int[N];
    //记录帖子是否是热帖（使用数组，直接就是排序效果）
    static int[] hotPosts = new int[N];
    
    public static void main(String[] args) throws Exception{
        String[] s = cin.readLine().split(" ");
        n = Integer.parseInt(s[0]);//日志数量
        D = Integer.parseInt(s[1]);//时间长度
        K = Integer.parseInt(s[2]);//点赞数
        //记录所有的帖子
        for (int i = 0; i < n; i++) {
            s = cin.readLine().split(" ");
            int ts = Integer.parseInt(s[0]);
            int id = Integer.parseInt(s[1]);
            logs[i] = new Log(ts, id);
        }
        
        //根据时刻来进行排序
        Arrays.sort(logs, 0, n);
        
        //遍历所有的日志，进行双指针滑动窗口操作
        //l指针仅仅只是记录窗口左侧的帖子时刻（l与r主要就是维护一个时间窗口，与帖子几并不相关）
        for (int l = 0, r = 0; r < n; r++) {
            Log cur = logs[r];
            //给当前帖子进行点赞
            cnt[cur.id]++;
            //滑动窗口判断当前帖子时间与l位置的帖子时间区间是否>=D
            while (l < r && cur.ts - logs[l].ts >= D) {
                //满足条件时：窗口向右移动，点赞数-1
                cnt[logs[l].id]--;
                l++;
            }
            //当前是在时间段里 && 满足点赞数
            if (cnt[cur.id] >= K) {
                hotPosts[cur.id] = 1;
            }
        }
        
        //遍历一遍所有的帖子（题目说要从前往后）
        for (int i = 0; i < N; i++) {
            if (hotPosts[i] > 0) System.out.println(i);
        }
        
    }
    
}

    • 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
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82

    image-20221027171207640

    习题

    例题1：1240. 完全二叉树的权值【简单，第十届蓝桥杯】

    题目链接：AcWing 1240. 完全二叉树的权值

    标签：双指针、二叉树

    分析：

    首先看元素数量为10万个，时间复杂度基本就是O(n)或者O(n.logn)，在这道题中两种解法都是O(n)

    思路1：递归版本，我们使用一个动态数组来存储每一层的和，最终来去比较所有层找到最大和的那层。

    思路2：双指针。

    第一个指针d表示的是层数，第二个指针i表示的是每一层的起点位置。

    两层遍历，每次遍历的个数是2层数-1

    直接去找规律然后模拟即可：

    image-20230106001042045

    题解：

    思路1：递归版本

    复杂度分析：时间复杂度O(n)；空间复杂度O(n)

    //10万数据量
import java.util.*;
import java.io.*;

class Main {
    
    static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    //二叉树存数组，左右节点为i * 2 + 1, i * 2 + 2
    static int[] arr = new int[100010];
    static int n;
    //存储每一层的
    static List<Long> paths = new ArrayList<>();
    
    public static void dfs(int[] arr, int pos, int path){
        //越界
        if (pos >= n) return;
        if (paths.size() < (path + 1)) {
            paths.add(0L);
        }
        //计算指定path层的节点值
        paths.set(path, paths.get(path) + arr[pos]);
        //左右节点
        dfs(arr, pos * 2 + 1, path + 1);
        dfs(arr, pos * 2 + 2, path + 1);
    }
    
    public static void main(String[] args)throws Exception {
        n = Integer.parseInt(cin.readLine());
        String[] s = cin.readLine().split(" ");
        for (int i = 0; i < n; i ++) {
            arr[i] = Integer.parseInt(s[i]);
        }
        dfs(arr, 0, 0);
        int ans = 0;
        for (int i = 1; i < paths.size(); i++) {
            if (paths.get(i) > paths.get(ans)) {
                ans = i;
            }
        }
        System.out.println(ans + 1);
    }
}

    • 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

    image-20230106001259649

    思路2：迭代，双指针方式，找规律

    复杂度分析：时间复杂度O(n)；空间复杂度O(1)

    import java.util.*;
import java.io.*;
class Main {
    
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static int[] arr = new int[100010];
    static int n;
    
    public static void main(String[] args)throws Exception {
        n = Integer.parseInt(cin.readLine());
        String[] lines = cin.readLine().split(" ");
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(lines[i - 1]);
        }
        //层、每层第第一个
        int ans = 0;
        long max = Long.MIN_VALUE;
        //d表示层数(每层+1递增)
        //i表示每层的第一个数下标（按照2的平方去递增）
        for (int d = 1, i = 1; i <= n; i *= 2, d++) {
            long res = 0L;
            //定位到指定层的第一个数下标，遍历该层（该层的数量由第d层来决定）
            for (int x = i; x < i + Math.pow(2, d - 1) && x <= n; x++) {
                res += arr[x];
            }
            //计算最大层的数值
            if (res > max) {
                max = res;
                ans = d;
            }
        }
        System.out.println(ans);
    }
}

    • 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

    image-20230106000059552

    二、BFS

    知识点

    例题

    例题1：1101. 献给阿尔吉侬的花束【中等，信息学奥赛一本通】

    题目链接：1101. 献给阿尔吉侬的花束

    分析：

    首先看下数据范围，宽高范围最大是200，每个已访问过的格子只会被访问一次，那么时间复杂度就是O(n2)。

    又题目说是要找最短路径，此时我们就可以使用bfs，那么直接模板套，我们只需要关注一些边界条件。

    广搜-二维矩阵模板：

    class Point {
	private int x;
	private int y;
	public Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

class Solution {
    public static void main (String[] args) {
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(1,2));//出发点
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                //取出Point结点进行操作
                Point point = queue.poll();
                //进行操作
                //放置四个方向的节点
				for (int d = 0; d < dicts.length; d++) {
					int x = point.x + dicts[d][0];
					int y = point.y + dicts[d][1];
					queue.offer(new Point(x, y))
				}
            }
        }
    }
}

    • 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

    思路：

    思路1：BFS，广搜

    复杂度分析：时间复杂度O(n2)；空间复杂度O(n2)

    import java.io.*;
import java.util.*;

class Point{
    int x;
    int y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class Main {
    
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    static int N = 210;
    static char[][] arr = new char[N][N];
    //四个方向
    static final int[][] dicts = {
        {-1, 0},
        {0, -1},
        {1, 0},
        {0, 1}
    };
    
    public static void main(String[] args)throws Exception {
        int c = Integer.parseInt(cin.readLine());
        while (c -- != 0) {
            String[] s = cin.readLine().split(" ");
            int n = Integer.parseInt(s[0]);
            int m = Integer.parseInt(s[1]);
            //确定S的位置
            int x = 0, y = 0;
            //初始化数组
            for (int i = 0; i < n; i++) {
                String str = cin.readLine();
                for (int j = 0; j < m; j++) {
                    arr[i][j] = str.charAt(j);
                    //找到出发点
                    if (arr[i][j] == 'S') {
                        x = i;
                        y = j;
                    }
                }
            }
            bfs(arr, n, m, x, y);
        }
    }
    
    public static void bfs(char[][] arr, int n, int m, int x, int y) {
        Queue<Point> queue = new LinkedList<>();
        boolean[][] visited = new boolean[n][m];
        queue.offer(new Point(x, y));
        boolean isFind = false;
        int res = -1;
        while (!queue.isEmpty() && !isFind) {
            int size = queue.size();
            res++;
            //遍历当前圈中的所有节点
            for (int i = 0; i < size; i++) {
                Point p = queue.poll();
                x = p.x;
                y = p.y;
                //若是越界停止访问
                if (x < 0 || y < 0 || x >= n || y >= m) continue;
                //若是碰到栏杆或者已访问过就停止继续访问
                if (arr[x][y] == '#' || visited[x][y]) continue;
                //找到目标点
                if (arr[x][y] == 'E') {
                    isFind = true;
                    break;
                }
                visited[x][y] = true;
                //每个节点都有四个方向
                for (int d = 0; d < dicts.length; d++) {
                    queue.offer(new Point(x + dicts[d][0], y + dicts[d][1]));
                }
            }
        }
        if (isFind) {
            System.out.println(res);
        }else {
            System.out.println("oop!");
        }
    }
}

    • 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
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87

    image-20221031181732488

    习题

    习题1：AcWing 1096. 地牢大师【简单，《信息学奥赛一本通》】

    分析：

    数据量N为100，由于是3D，那么就是n3，就是100万，时间复杂度控制在O(n)中即可通过。

    从起点-终点的最小步数可以直接通过BFS宽搜来进行获取，本题主要在于一些初始化操作会比较复杂麻烦些，bfs的宽搜代码就是基本模板。

    其中小细节就是通过在访问地图中‘.’时直接将其设置为’‘#’，即可省去一个访问三维数组，节省了空间。

    思路：宽搜

    复杂度分析：时间复杂度O(n)；空间复杂度O(n)

    import java.util.*;
import java.io.*;

class Pos {
    int z, x, y;
    int dis;
    
    public Pos(int z, int x, int y, int dis) {
        this.z = z;
        this.x = x;
        this.y = y;
        this.dis = dis;
    }
}

class Main {
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 110;
    //六个方向
    static final int[] dz = {0, 0, 0, 0, 1, -1};
    static final int[] dx = {0, 0, 1, -1, 0, 0};
    static final int[] dy = {1, -1, 0, 0, 0, 0};
    
    //每一轮读入地牢层数、行数、列数
    static int L, R, C;
    //构建三维地图
    static char[][][] mg = new char[N][N][N];
    //初始点与终点
    static Pos start, end;
    
    //深搜
    static int bfs() {
        //队列
        Queue<Pos> queue = new LinkedList<>();
        //加入起点
        queue.offer(start);
        while (!queue.isEmpty()) {
            //出队一个点
            Pos cur = queue.poll();
            //此时判断是否已经遇到终点
            if (cur.z == end.z && cur.x == end.x && cur.y == end.y) {
                return cur.dis;
            }
            //遍历六个方向
            for (int d = 0; d < 6; d++) {
                int z = cur.z + dz[d], x = cur.x + dx[d], y = cur.y + dy[d];
                //判断是否越界或者遇墙
                if (z < 1 || z > L || x < 1 || x > R || y < 1 || y > C || mg[z][x][y] == '#') {
                    continue;
                }
                //当前迷宫位置'.'设置为'#'，这样就无需设置一个访问数组
                mg[z][x][y] = '#';
                //进行入队
                queue.offer(new Pos(z, x, y, cur.dis + 1));
            }
        }
        return -1;
    }
    
    public static void main(String[] args) throws Exception{
        while (true) {
            //读取LRC
            String[] ss = cin.readLine().split(" ");
            L = Integer.parseInt(ss[0]);
            R = Integer.parseInt(ss[1]);
            C = Integer.parseInt(ss[2]);
            //若是都读到0，那么结束
            if (L == 0 && R == 0 && C == 0) break;
            //地图初始化
            for (int z = 1; z <= L; z++) {
                for (int x = 1; x <= R; x++) {
                    //读取当前层的地牢
                    String line = cin.readLine();
                    for (int y = 1; y <= C; y++) {
                        mg[z][x][y] = line.charAt(y - 1);
                        //获取地图开始与结束位置
                        if (mg[z][x][y] == 'S') {
                            start = new Pos(z, x, y, 0);
                        }else if (mg[z][x][y] == 'E'){
                            end = new Pos(z, x, y, 0);
                        }
                    }
                }
                //读取多余一行
                cin.readLine();
            }
            //bfs（深搜）
            int dis = bfs();
            if (dis != -1) {
                System.out.printf("Escaped in %d minute(s).\n", dis);
            }else {
                System.out.printf("Trapped!\n");
            }
        }
    }
    
    
}

    • 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
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98

    image-20230106191625292

    三、DFS

    例题

    1113. 红与黑【中等，信息学奥赛一本通】

    题目链接：1113. 红与黑

    分析：

    看看数据范围20，是真的小，并且每个格子只会被访问一次。

    又题目说总共能够到达多少块黑色的瓷砖，也就是最大值，我们这里就可以使用dfs，我直接拿dfs模板套。

    dfs-二维矩阵模板：

    int f[4][2]={{0,1},{0,-1},{1,0},{-1,0}};    //用于判断下一步怎么走向几个方向走就是几个数据
void dfs(int x,int y){        //进入点的坐标
    if(/*跳出循环的条件*/){
        /*作出相应操作*/
        return;        //不要忘了return
    }
    for(int i=0;i</*f的长度*/;i++){
        int x0=x+f[i][0];    
        /*此处是更新点的坐标，注意是直接让原来的点加上这个数据，不是直接等于*/
        int y0=y+f[i][1];
        if(/*用新坐标x0,y0判断是否符合条件*/){
            dfs(x0,y0);    //用新的坐标进行递归
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    题解：

    复杂度分析：时间复杂度O(n2)；空间复杂度O(n2)

    import java.io.*;
import java.util.*;

class Main {
    
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static int N = 30;
    static char[][] arr = new char[N][N];
    static int[][] dicts = {
        {-1, 0},
        {0, -1},
        {1, 0},
        {0, 1}
    };
    
    public static void main(String[] args)throws Exception {
        while (true) {
            String[] s = cin.readLine().split(" ");
            int m = Integer.parseInt(s[0]);
            int n = Integer.parseInt(s[1]);
            //停止读入
            if (n == 0 && m == 0) break;
            //初始化空间
            int x = 0, y = 0;
            for (int i = 0; i < n; i++) {
                String str = cin.readLine();
                for (int j = 0; j < m; j++) {
                    arr[i][j] = str.charAt(j);
                    if (arr[i][j] == '@') {
                        x = i;
                        y = j;
                    }
                }
            }
            System.out.println(dfs(n, m, x, y, new boolean[n][m]));   
        }
    }
    
    public static int dfs(int n, int m, int i, int j, boolean[][] visited) {
        //越界情况
        if (i < 0 || j < 0 || i >= n || j >= m) {
            return 0;
        }
        //遇到红色瓷砖停止
        if (arr[i][j] == '#' || visited[i][j]) return 0; 
        int res = 1;
        visited[i][j] = true;
        //四个方向
        for (int d = 0; d < dicts.length; d++) {
            int x = i + dicts[d][0];
            int y = j + dicts[d][1];
            res += dfs(n, m, x, y, visited);
        }
        return res;
    }
}

    • 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
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56

    image-20221031192729985

    习题

    习题1：AcWing 1233. 全球变暖【简单，蓝桥杯】

    分析：

    N为1000，无论是dfs还是bfs我们实际上时间复杂度O(n2)，也就是100万，不会超时。

    需要注意题目问的是地图中岛屿全部被淹没的数量！！！我一开始以为的是统计的没有淹没的数量。

    我们可以通过使用dfs或者bfs来进行一个岛屿的搜索，在搜索的过程中使用visit数组来进行临时保存访问过的岛屿，并且判断是否该岛屿能够被全部淹没，仅仅只需要去判断该元素位置的上下左右是否都是‘#’，若是那么该岛屿就不会被淹没，对于一座岛屿是否被淹没通过使用一个临时变量flag来进行表示，true表示会被淹没，false表示不会。

    思路：深搜

    复杂度分析：时间复杂度O(n2)；空间复杂度O(n2)

    import java.io.*;
import java.util.*;

class Main {
    
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 1010;
    static char[][] islands = new char[N][N];
    static boolean[][] visited = new boolean[N][N];
    //四个方向
    static int[][] dics = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    
    static int n;
    //标记岛屿是否被淹没
    static boolean flag = true;
    
    public static void dfs(int i, int j) {
        if (i < 1 || i > n || j < 1 || j > n) return;
        //标记访问过
        visited[i][j] = true;
        //判断该点是否会被淹没
        if (islands[i + 1][j] == '#' && islands[i - 1][j] == '#' && islands[i][j - 1] == '#' && islands[i][j + 1] == '#') {
            flag = false;
        } 
        //四个方向
        for (int d = 0; d < dics.length; d++) {
            int x = i + dics[d][0], y = j + dics[d][1];
            //必须是陆地并且没有访问过
            if (!visited[x][y] && islands[x][y] == '#') {
                dfs(x, y);   
            }
        }
    }
    
    
    public static void main(String[] args) throws Exception{
        n = Integer.parseInt(cin.readLine());
        //岛屿初始化
        for (int i = 1; i <= n; i++) {
            String line = cin.readLine();
            for (int j = 1; j <= n; j++) {
                islands[i][j] = line.charAt(j - 1);
            }
        }
        
        //对所有岛屿来进行遍历
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (islands[i][j] == '#' && !visited[i][j]) {
                    flag = true;
                    dfs(i, j);
                    if (flag) {
                        ans++;
                    }
                }
            }
        }
        System.out.println(ans);
    }
}

    • 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
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61

    image-20230106203607966

    四、图论

    知识点

    例题

    例题1：1224. 交换瓶子（中等，蓝桥杯）

    题目链接：1224. 交换瓶子

    分析：

    首先看下数据量的范围，长度为10000，符合1s的时间复杂度有O(n2)，O(nlogn)，O(n)，其中O(n2)时间特别紧，若是代码量比较少是刚好能够卡过的。本道题的话可以使用暴力解法（选择排序）以及一个图论解法。

    ①暴力解法：选择排序

    选择排序的过程我不再过多阐述，就是每一轮找到[i + 1, n]部分 < arr[i]的元素，若是有的话满足了符合交换的条件，那么对于符合条件的进行计数+1，最后排序下来之后，我们也就可以得到结果了。

    ②图论解法：

    本道题实际上与前面树状数组的1215. 小朋友排队比较类似，不过还是有一些区别，小朋友排队是求逆序对，并且交换的必须是临近的两个数，在这道题中实际上并没有临近的数才能够进行交换的限制，所以这里可以借助图论来进行解决。

    举例：5个数为2 3 1 5 4

    初始位置：1  2  3  4  5
实际位置：2  3  1  5  4

    • 1
    • 2

    从实际位置这行来看，2应当是在3这个位置上，3应该是在1位置上，1应该是在2位置上；5应该是在4位置上，4应该是在5位置上。

    image-20221031211342643

    对于单个环中的两个元素去交换与两个环中的单个元素去交换会产生两种情况：

    情况①：单个环中的两个元素去交换，例如我们去交换第一个环里的2与3

    此时位置为：

    初始位置：1  2  3  4  5
实际位置：3  2  1  5  4

    • 1
    • 2

    image-20221031211617567

    结论：单个环内两个元素交换，此时一个环就会变为两个环。

    情况2：两个环中的单个元素去交换，例如我们去交换第一个环中的2与第二个环中的5

    此时位置为：

    初始位置：1  2  3  4  5
实际位置：5  3  1  2  4

    • 1
    • 2

    image-20221031211937302

    结论：两个环中的单个元素去交换，此时两个环会变为1个环。

    知道了这两个结论后，我们对于解这道题有什么帮助？我们本道题实际上最终的效果想要达到的效果如下：

    image-20221031212221378

    实际上只需要运用结论1即可，若是我们5个数，形成了两个环，那么如何将两个环拆为五个环内，那么就是使用结论1我们交换1次环内两个元素，一个环就会变为两个环，实际上交换的次数就是 = 数字数量 - 环数

    那么由此我们只需要得到构成环数的数量也就知道需要交换的次数了，我们可以借助一个boolean辅助数组来进行标识环的数量，看代码推一遍即可！

    拿arr数组[2 3 1 5 4]来举例，visited = [false, false, false, false, false]，下标从1开始

cnt = 0; //表示成环的数量
i = 1  
  visited[1] false成立，表示以1作为成环的开始，cnt++
  	 以visited[1]开始  条件为!visited[j]  j = arr[j]，这个过程就是成环的过程，一旦回到1时，此时visited[1]=true结束
     最终：visited = [true, true, true, false, false]
i = 2 x
i = 3 x
i = 4 
  visited[4] false成立，表示4作为环的开始：cnt++
     同样以visted[4]开始 同上过程，回到4即可截止
     最终：visited = [true, true, true, true, true]
i = 5 x
    
//可以看到该例子上面进行了两次成环，cnt加了两次，最终就是表示2个环
交换的次数 = 5 - 2 = 3

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    思路有了，直接可以code了！

    代码：

    思路1：暴力（选择排序）

    复杂度分析：

    复杂度分析：时间复杂度O(n2)；空间复杂度O(n)

    import java.io.*;
import java.util.*;

class Main {
    
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static int N = 10010;
    static int[] arr = new int[N];
    
    public static void main(String[] args) throws Exception{
        int n = Integer.parseInt(cin.readLine());
        String[] s = cin.readLine().split(" ");
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(s[i - 1]);
        }
        //选择排序
        int cnt = 0;
        for (int i = 1; i < n; i++) {
            //找到[i + 1, n]中比arr[i]小的数
            int min = i;
            for (int j = i + 1; j <= n; j++) {
                if (arr[j] < arr[min]) {
                    min = j;    
                }
            }
            //若是索引不同，说明有需要交换的数，那么次数就+1，并且两个数字进行交换
            if (min != i) {
                cnt++;
                int tmp = arr[i];
                arr[i] = arr[min];
                arr[min] = tmp;
            }
        }
        System.out.println(cnt);
    }
    
}

    • 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

    image-20221031210316855

    思路2：图论解法

    复杂度分析：时间复杂度O(n)；空间复杂度O(n)

    import java.io.*;
import java.util.*;

class Main {
    
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static int N = 10010;
    static int[] arr = new int[N];
    static boolean[] visited = new boolean[N];
    
    public static void main(String[] args) throws Exception{
        int n = Integer.parseInt(cin.readLine());
        String[] s = cin.readLine().split(" ");
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(s[i - 1]);
        }
        //取出有多少能够进行成环的
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                //成环的数量+1
                cnt++;
                //给当前能够进行成环的visited数组进行下标设置true
                for (int j = i; !visited[j]; j = arr[j]) {
                    visited[j] = true;
                }
            }
        }
        //最后交换的次数就是所有小朋友的数量 - 环数
        System.out.println(n - cnt);
    }
    
}

    • 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

    image-20221031205518961

    习题

    习题1：AcWing 1207. 大臣的旅费【中等，树的直径，蓝桥杯A组】

    分析：

    节点数量最大有10万个，那么时间复杂度应当要控制在O(n)、O(n.logn)中。

    抓住题目中的关键点：【从首都到达每个大城市的方案都是唯一的】，从这么一点来看本道题是不成环的，那么就是一棵树。

    我们来拿题目给的一个样例来进行举例说明：

    输入样例：
5 
1  2  2 
1  3  1 
2  4  5 
2  5  4 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    image-20230108193508700

    可以看出构成并没有成环，它实际上是一棵树，按照题目的要求我们要找到距离最大的两个城市并求出最多花费的路费，如果说我们用自己的眼睛去看简单计算下就可以发现节点4与节点5的距离是最大的，其范围值为9。那么怎么让计算机去求得最大的范围呢？

    • 最粗暴的方法就是首先构建一个邻接表，然后使用dfs来去找到每个节点到其他节点的最大路径，然后依次比较得到最大距离，但是这个绝对是会超时的！

    接着我们的思路可以从树的特点来进行出发，我们可以首先从任意一点出发进行dfs，找到该点的最大距离节点，接着再从这个最大距离节点出发同样进行一遍dfs操作，此时我们就能够找到最大距离，那么时间复杂度就是两次的O(n)，可直接ac该题！

    第一次dfs过程如下：从节点1找到节点4位置

    image-20230108194125346

    第二次dfs：接着从节点4出发，找到最大距离的点，就是4->5

    image-20230108194303357

    此时我们是否已经可以看出第一次dfs是找到树的一个最边界点，第二次dfs则是找到该边界点的一个最大距离边界点！这个过程实际上就是在求【树的直径】。

    ok此时找到最大距离的两个点后我们即可得到最大距离的长度n，接着我们就可以来计算本道题所让我们求的最多旅费：

    走1千米时，当前第1千米路费为a1 = (1 + 10)，总路费s1=a1=(1+10)

    走2千米时，当前第2千米路费为a2 = (2 + 10)，总路费为s2 = a1 + a2 = (1 + 10) + (2 + 10)

    走3千米时，当前第3千米路费为a3 = (3 + 10)，总路费为s3 = a1 + a2 + a3 = (1 + 10) + (2 + 10) + (3 + 10)

    ······

    走第n千米时，当前第n千米路费为an = n + 10，总路费为sn = a1 + a2 + a3 + … an = (1 + 10) + (2 + 10)+ ⋯ + (n + 10)

    此时等差数列求和：sn = (1 + 10) + (2 + 10)+ ⋯ + (n + 10) = (1+n) * n /2+10 * n

    最终把n代入到式子即可求得了，接着就是ac这道题！

    思路：树的直径（dfs）

    复杂度分析：时间复杂度O(n)；空间复杂度O(n)

    import java.util.*;
import java.io.*;

class Main {
    
    //输入数据量特别大使用BufferedReader
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    
    //图节点
    static class Node { 
        public int v, w;
        public Node(int v, int w) {
            this.v = v;
            this.w = w;
        }
    } 
    
    static int N = 100010;
    //定义邻接表
    static ArrayList<Node>[] u = new ArrayList[N];
    //定义距离数组
    static int[] dist = new int[N];//距离数组
    static int n;
    
    //使用dfs来进行构建对应的idx节点对应各个点的最大距离dist数组
    public static void dfs(int cur, int pre, int dis) {
        //遍历每个节点
        for (Node e: u[cur]) {
            //若是遍历到重复节点直接结束
            if (e.v == pre) continue;
            //连接上一次距离
            dist[e.v] = dis + e.w;
            //递归到下一个节点
            dfs(e.v, cur, dist[e.v]);
        }
    }
    
    public static void main(String[] args) throws Exception{
        n = Integer.parseInt(cin.readLine().trim());
        for (int i = 1; i < n; i++) {
            //由于所有测试用例中空格包含有"  "和" "，两个空格或者一个空格情况需要进行区别对待
            String line = cin.readLine();
            String spiltStr = " ";
            if (line.contains("  ")) spiltStr = "  ";
            String[] nums = line.split(spiltStr);
            int p = Integer.parseInt(nums[0].trim());
            int q = Integer.parseInt(nums[1].trim());
            int d = Integer.parseInt(nums[2].trim());
            //开辟一个动态数组
            if (u[p] == null) u[p] = new ArrayList<>();
            if (u[q] == null) u[q] = new ArrayList<>();
            //构建邻接表
            u[p].add(new Node(q, d));
            u[q].add(new Node(p, d));
        }
        
        //从节点1开始进行找最长距离的点
        int idx = 1;
        //找寻节点1对应的所有点的最长距离
        dfs(idx, -1, 0);
        //确定最长距离点
        idx = getMaxNode();
        
        //初始化距离数组
        Arrays.fill(dist, 0);
        //找寻节点idx的最长距离
        dfs(idx, -1, 0);
        //找到对应idx节点的最大距离节点
        int maxv = getMaxNode();
        //得到【树的直径】最长距离
        int maxDistance = dist[maxv];
        //计算最大距离
        System.out.println((maxDistance + 1L) * maxDistance / 2 + 10L * maxDistance);
    }
    
    //从dist数组中找到最大距离的节点
    public static int getMaxNode() {
        int maxv = 1;
        for (int i = 2; i <= n; i++) {
            if (dist[i] > dist[maxv]) {
                maxv = i;
            }
        }
        return maxv;
    }
    
}

    • 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
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87

    image-20230108192341047

    习题—单链表（模板题，数组实现）

    分析

    使用e数组来存储链表中每个节点的值。

    使用ne数组来存储链表中每个节点的的next节点的索引。

    两个数组的索引都是指向的同一个节点，一个是节点的值，一个是该节点的下一个索引节点下标。

    思路：数组实现单链表

    复杂度分析：insert、add方法时间复杂度都是O(1)

    import java.io.*;
import java.util.*;

class Main {
    
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static int N = 100010;
    static int n;
    //存放第idx位数据
    static int[] e = new int[N];
    //存放第idk位数据的下一个结点索引
    static int[] ne = new int[N];
    static int head = -1;//头节点，存的是数据的索引
    static int idx;//最新的下标
    
    public static void addToHead(int x) {
        e[idx] = x;//赋值
        ne[idx] = head;//更新当前的新添加的结点next的索引
        head = idx;//更新头节点
        idx++;//索引更新
    }
    
    public static void insert(int k, int x) {
        e[idx] = x;//赋值
        ne[idx] = ne[k];//当前next索引更新为第k个位置的next索引
        ne[k] = idx;//更新第k个next索引为当前值索引
        idx++;//索引更新
    }
    
    public static void remove(int k) {
        ne[k] = ne[ne[k]];//获取当前第k个next索引值的next索引，即可表示删除
    }
    
    public static void print() {
        for (int i = head; i != -1; i = ne[i]) {
            System.out.printf("%d ", e[i]);
        }
    }
    
    public static void main (String[] args)throws Exception {
        n = Integer.parseInt(cin.readLine());
        //初始化链表
        LinkedList list = new LinkedList();
        while (n -- != 0) {
            String[] s = cin.readLine().split(" ");
            String oper = s[0];
            int k = 0, x = 0;
            //插入数
            switch(oper) {
                case "I":
                    k = Integer.parseInt(s[1]);
                    x = Integer.parseInt(s[2]);
                    insert(k - 1, x);
                    break;
                case "D":
                    k = Integer.parseInt(s[1]);
                    //若是k=0，直接更新头节点位置
                    if (k == 0) {
                        head = ne[head];
                    }else {
                        remove(k - 1);
                    }
                    break;
                case "H":
                    x = Integer.parseInt(s[1]);
                    addToHead(x);
                    break;
            }
        }
        //遍历所有值
        print();
    }
}

    • 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
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73

    image-20221103111447495

    参考文章

    [1]. AcWing 1207. 大臣的旅费（Java 树的直径）

  • 相关阅读:
    054协同过滤算法的电影推荐系统
    基于DBC Signal Group生成Autosar SR接口（2）
    【Shell 系列教程】shell介绍（一）
    魔众短链接系统 v3.9.0
    支持向量机分类算法
    DeFi 巨头进军 NFT 领域 用户怎么看？
    Pycharm中出现ImportError:DLL load failed:找不到指定模块的解决方法
    OSI体系结构和TCP/IP体系结构
    Spring Framework 6中的新功能和增强功能
    【负荷预测】基于蚂蚁优化算法的BP神经网络在负荷预测中的应用研究（Matlab完整代码实现）
  • 原文地址：https://blog.csdn.net/cl939974883/article/details/127760980