@[toc]

前言

除了去年11月份以及今年近几月的算法刷题之外，只有在当时20年蓝桥杯准备的时候才刷过一些题，在当时就有接触到一些动归、递归回溯、贪心等等，不过那会也还是一知半解，做的题目也特别少，因为考虑到之后面试有算法题以及数据结构算法对于一个程序员十分重要，我也开始了刷题之路。

我目前的学习数据结构与算法及刷题路径：

1、学习数据结构的原理以及一些常见算法。

2、代码随想录：跟着这个github算法刷题项目进行分类刷，在刷题前可以学习一下对应类别的知识点，而且这里面每道题都讲的很详细。

3、牛客网高频面试101题：牛客网—面试必刷101题，在刷的过程中可以在leetcode同步刷一下。

4、接下来就是力扣上的专栏《剑指offer II》、《程序员面试金典（第 6 版）》…有对应的精选题单来对着刷即可。

5、大部分的高频面试、算法题刷完后，就可以指定力扣分类专栏进行一下刷题了。

刚开始刷的时候真的是很痛苦的，想到去年一道题可能就需要好几小时，真的就很难受的，不过熬过来一切都会好起来，随着题量的增多，很多题目你看到就会知道使用什么数据结构或者算法来去求解，并且思考对应的时间空间复杂度，并寻求最优解，我们一起加油！

我的刷题历程

截止2022.8.18：

1、牛客网101题(其中1题是平台案例有问题)：

2、剑指offerII：

力扣总记录数：

加油加油！

基础知识点

并查集（Union-find Data Structure）是一种树型的数据结构。它的特点是由子结点找到父亲结点，用于处理一些不交集（Disjoint Sets）的合并及查询问题。

• Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
• Union：将两个子集合并成同一个集合。

剑指offer

剑指 Offer II 116. 省份数量【中等】

学习：leetcode/并查集/深度优先搜索/朋友圈问题/岛屿问题

题目链接：剑指 Offer II 116. 省份数量

题目内容：

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

思路：

1、并查集

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

class Solution {
    public int findCircleNum(int[][] isConnected) {
        UnionFind uf = new UnionFind(isConnected);
        int len1 = isConnected.length;
        int len2 = isConnected[0].length;
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                if (isConnected[i][j] == 0) continue;
                uf.merge(i, j);
            }
        }
        return uf.size;
    }
}

class UnionFind {
    public int size;
    private int[] parent;
    private int[] weight;

    public UnionFind(int[][] isConnected) {
        int n = isConnected.length;
        this.size = n;
        this.parent = new int[n];
        this.weight = new int[n];
        for (int i = 0; i < n; i++) {
            this.parent[i] = i;
            this.weight[i] = 1;
        }
    }

    public int find(int x) {
        if (x == parent[x]) {
            return x;
        }else {
            parent[x] = find(parent[x]);
            return parent[x];
        }
    }

    public void merge(int x, int y) {
        int _x = find(x);
        int _y = find(y);
        if (_x == _y) return;
        if (weight[_x] < weight[_y]) {
            int temp = _x;
            _x = _y;
            _y = temp;
        }
        parent[_y] = parent[_x];
        weight[_x] += weight[_y];
        --size;
    }

}

leetcode

剑指 Offer II 105. 岛屿的最大面积【中等】

题目链接：剑指 Offer II 105. 岛屿的最大面积

题目内容；

思路：

1、dfs深搜

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

class Solution {

    private int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private int max = 0;

    public int maxAreaOfIsland(int[][] grid) {
        //遍历一遍，若是为1进行dfs，然后res+1
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    max = Math.max(dfs(grid, i, j, 1), max);
                }
            }
        }
        return max;
    }

    public int dfs(int[][] grid, int i, int j, int area) {
        //边界
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length) {
            return 0;
        }
        //若是为1的进行标注并继续往下执行
        if (grid[i][j] == 0) {
            return 0;
        }

        //地图位置进行标注
        grid[i][j] = 0;

        //四个方向进行执行
        int res = 1;
        for (int[] direction: directions) {
            res += dfs(grid, i + direction[0], j + direction[1], area + 1);
        }
        return res;
    }
}

2、并查集

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

class Solution {


    public int maxAreaOfIsland(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        //初始化并查集
        UnionFind unionFind = new UnionFind(grid);
        int iLen = grid.length;
        int jLen = grid[0].length;
        //遍历一遍，若是为1进行dfs，然后res+1
        for (int i = 0; i < iLen; i++) {
            for (int j = 0; j < jLen; j++) {
                if (grid[i][j] == 0) continue;
                //四个方向
                if (i - 1 >= 0 && grid[i - 1][j] == 1) 
                    unionFind.merge(i * jLen + j, (i - 1) * jLen + j);
                if (i + 1 < iLen && grid[i + 1][j] == 1) 
                    unionFind.merge(i * jLen + j, (i + 1) * jLen + j);
                if (j - 1 >= 0 && grid[i][j - 1] == 1) 
                    unionFind.merge(i * jLen + j, i * jLen + j - 1);
                if (j + 1 < jLen && grid[i][j + 1] == 1) 
                    unionFind.merge(i * jLen + j, i * jLen + j + 1);
            }
        }
        int max = 0;
        for (int i = 0; i < iLen; i++) {
            for (int j = 0; j < jLen; j++) {
                max = Math.max(max, unionFind.weight[i * jLen + j]);
            }
        }
        return max;
    }
}

class UnionFind {
    public int size;
    public int[] parent;
    public int[] weight;

    public UnionFind(int[][] grid) {
        int len1 = grid.length;
        int len2 = grid[0].length;
        this.size = len1 * len2;
        this.parent = new int[size];
        this.weight = new int[size];
        //初始化
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                parent[i * len2 + j] = i * len2 + j;
                //根据岛屿是否为1来设置权重是否为1
                if (grid[i][j] == 1) {
                    weight[i * len2 + j] = 1;
                }else {
                    weight[i * len2 + j] = 0;
                }
            }
        }
    }

    public int find(int x) {
        if (x == parent[x]) {
            return x;
        }else {
            parent[x] = find(parent[x]);
            return parent[x];
        }
    }

    public void merge(int x, int y) {
        int _x = find(x);
        int _y = find(y);
        if (_x == _y) return;
        if (weight[_x] < weight[_y]) {
            int temp = _x;
            _x = _y;
            _y = temp;
        }
        //连通结点
        parent[_y] = _x;
        weight[_x] += weight[_y];
        --size;
    }
}