学习内容:Leecode
学习语言:java
LeeCodeJava并查集

LeeCode

1319.连通网络的操作次数

题目:

用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。
网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。
给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。
题目链接

我的代码

  1. class Solution {
  2.     public int makeConnected(int n, int[][] connections) {
  3.         if(connections.length<n-1){
  4.             return -1;
  5.         }
  6.         int[] computerList=new int[n];
  7.         Arrays.fill(computerList,-1);
  8.         AndCollect andCollect= new AndCollect(computerList,connections);
  9.         return andCollect.union();
  10.     }
  11. }
  13. class AndCollect {
  14.     int[] data;
  15.     int[][] connections;
  17.     public AndCollect(int[] data, int[][] connections) {
  18.         this.data = data;
  19.         this.connections = connections;
  20.     }
  22.     int union(){
  23.         for (int[] connection : connections) {
  24.             merge(connection);
  25.         }
  26.         int count=0;
  27.         for (int datum : this.data) {
  28.             if (datum == -1) {
  29.                 count++;
  30.             }
  31.         }
  32.         return count-1;
  33.     }
  36.     void merge(int[] connect){
  37.         int a=findRoot(connect[0]);
  38.         int b=findRoot(connect[1]);
  39.         if(a!=b){
  40.             data[a]=b;
  41.         }
  42.     }
  45.     int findRoot(int target){
  46.         int temp=target;
  47.         while (data[temp]!=-1){
  48.             temp=data[temp];
  49.         }
  50.         return temp;
  51.     }
  53. }

思路:

通过并查集来解决问题,将每个链接的节点,逐个塞入规划完的集合中,通过判断最后还剩下几个孤立的集合,那么就确定至少需要n-1个操作来操作线,使集合之间相连,否则直接归为false.随后遍历连接线,将连接归于数个集合.计算数据集数量之后就可以得出需要多少线来解决.

并查集

并查集的建立:

建立一个电脑数的数组,统一赋值为-1.代表这些节点的头节点为-1.随后遍历连接集,如果该连接集的两端处在不同一个集合,那么将随意一个元素的根节点的父节点设置为另一个元素的根节点.

判断处于同一个集合

不断获取自己的父节点,直到父节点的值为-1,即那个节点为某个集合的根,如果两个数据的父节点相同,那么他俩就处于同一个集合中.

计算操作数

有n个独立的集合就需要n-1个操作,即最后的数组中有n个-1,就需要操作n-1次

优解代码

  1. class Solution {
  2.     public int makeConnected(int n, int[][] connections) {
  3.         int lines = connections.length;
  4.         if(lines<(n-1)){
  5.             return -1;
  6.         }
  7.         int [] parent = new int[n];
  8.         /*这一步标准的做法是将父节点设置为-1,但是这个人的做法是将父节点设置为自己*/
  9.         for(int i = 0;i<n;i++){
  10.             parent[i]=i;
  11.         } 
  12.         int res = n;
  13.         for(int i = 0;i<lines;i++){
  14.             int p1=find(parent,connections[i][0]);
  15.             int p2=find(parent,connections[i][1]);
  16.             if(p1!=p2){
  17.                 res--;
  18.                 parent[p2]=p1;
  19.             }
  22.         }
  23.         return res-1;
  24.     }
  25.     int find(int[] parent,int key){
  26.         if(parent[key]!=key){
  27.             parent[key]=find(parent,parent[key]);
  28.         }
  29.         return parent[key];
  30.     }
  32. }

优化处:

思路类似,但是他更好地将代码统合到了一个代码块中,且没有new操作,所以会节省不少时间.
他尽量减少了循环的次数,通过让节点总数减去,父节点变更过节点的数量,得到了目标节点数.有利于减少循环的次数,便于减少运算时间.总体上的思路是一样的.

832.翻转图像

题目:

给定一个二进制矩阵 A，我们想先水平翻转图像，然后反转图像并返回结果。
水平翻转图片就是将图片的每一行都进行翻转，即逆序。例如，水平翻转 [1, 1, 0] 的结果是 [0, 1, 1]。
反转图片的意思是图片中的 0 全部被 1 替换， 1 全部被 0 替换。例如，反转 [0, 1, 1] 的结果是 [1, 0, 0]。

我的代码

  1. public class Solution {
  2.     public int[][] flipAndInvertImage(int[][] A) {
  3.         int a=A.length;
  4.         int[][] result=new int[a][a];
  5.         for (int i = 0; i < A.length; i++) {
  6.             for (int i1 = 0; i1 < A[0].length; i1++) {
  7.                 if(A[i][a-1-i1]==0){
  8.                     result[i][i1]=1;
  9.                 }else{
  10.                     result[i][i1]=0;
  11.                 }
  12.             }
  13.         }
  14.         return result;
  15.     }
  16. }

题目总体来说比较简单,但是提升的空间很大:
不再新增内存空间
尽量减少遍历的过程.

优化后的代码

  1. public class Solution {
  2.     public int[][] flipAndInvertImage(int[][] A) {
  3.         int a,b;
  4.         for (int i = 0; i < A.length; i++) {
  5.             for(int i1=0,i2=A.length-1;i1<=i2;i1++,i2--){
  6.                 a=A[i][i1];
  7.                 A[i][i1]=A[i][i2]^1;
  8.                 A[i][i2]=a^1;
  9.             }
  10.         }
  11.         return A;
  12.     }
  13. }

知识:

1.在元素交换的时候,只要第一个元素不变,剩下两个在赋值的时候,可以附加计算
2.多使用双重指针.