题目一：并查集（算法课第七课）

代码

import java.util.HashMap;
import java.util.List;

public class UnionFind {//头条201808825第一题
    public static class Node {
        // whatever you like
    }

    public static class UnionFindSet {// 小头挂大头
        public HashMap<Node, Node> fatherMap;// KEY:child,VALUE：father . 一路往上找父节点
        public HashMap<Node, Integer> sizeMap;// 某节点所在的集合一共多少节点

        public UnionFindSet(List<Node> nodes) {//一次性把所有样本 传入
            makeSets(nodes);
        }

        private void makeSets(List<Node> nodes) {
            fatherMap = new HashMap<Node, Node>();
            sizeMap = new HashMap<Node, Integer>();
            for (Node node : nodes) {//开始的时候每个节点，自成一个集合
                fatherMap.put(node, node);
                sizeMap.put(node, 1);
            }
        }
        //1. 找到代表节点     2.把集合所有节点 直接链向代表节点 
        private Node findHead(Node node) {//找到 “代表节点”
            Node father = fatherMap.get(node);
            if (father != node) {//直到自己是自己爹（代表节点）
                father = findHead(father);
            }
            fatherMap.put(node, father);
            return father;
        }

        public boolean isSameSet(Node a, Node b) {
            return findHead(a) == findHead(b);//最终找到同一个源头，就是一个集合的
        }

        public void union(Node a, Node b) {
            if (a == null || b == null) {
                return;
            }
            Node aHead = findHead(a);
            Node bHead = findHead(b);
            if (aHead != bHead) { //不在一个集合 ，才需要合并
                int aSetSize = sizeMap.get(aHead);
                int bSetSize = sizeMap.get(bHead);
                if (aSetSize <= bSetSize) {//只用改变 1. 头 2. 集合大小
                    fatherMap.put(aHead, bHead);
                    sizeMap.put(bHead, aSetSize + bSetSize);
                } else {
                    fatherMap.put(bHead, aHead);
                    sizeMap.put(aHead, aSetSize + bSetSize);
                }
            }
        }

    }

    public static void main(String[] args) {
        //……
    }
}

题目二：朋友圈(头条笔试)

数据结构：并查集结构

朋友圈

代码

import java.util.*;
 
public class Main{
    public static class Node {
        public Set<Integer> friends = new HashSet<>();
    }
 
    public static HashMap<Node, Node> fatherMap;
    public static HashMap<Node, Integer> sizeMap;
 
    public static void main(String[] args) {
        //1、输入数据，组织数据结构
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if (n <= 0 || n >= 100000) {
            System.out.println(0);
            return;
        }
        Node[] nodes = new Node[n + 1];
        int tmp;
        fatherMap = new HashMap<Node, Node>();
        sizeMap = new HashMap<Node, Integer>();
        for (int i = 1; i <= n; ++i) {
            nodes[i] = new Node();
            fatherMap.put(nodes[i], nodes[i]);
            sizeMap.put(nodes[i], 1);
            while ((tmp = sc.nextInt()) != 0) {
                nodes[i].friends.add(tmp);
            }
        }
        //2、遍历每个节点，根据合并策略进行合并
        for (int i = 1; i < nodes.length; i++) {
            if (nodes[i].friends.size() == 0) continue;
            for (Iterator<Integer> iterator = nodes[i].friends.iterator(); iterator.hasNext(); ) {
                Integer one = iterator.next();
                if (!isSameSet(nodes[i], nodes[one])) {
                    union(nodes[i], nodes[one]);
                    n--;
                }
            }
        }
        //3、result
        System.out.println(n);
    }
 
    private static Node findHead(Node node) {
        Node father = fatherMap.get(node);
        if (father != node) {
            father = findHead(father);
        }
        fatherMap.put(node, father);
        return father;
    }
 
    public static boolean isSameSet(Node a, Node b) {
        return findHead(a) == findHead(b);
    }
 
    public static void union(Node a, Node b) {
        if (a == null || b == null) {
            return;
        }
        Node aHead = findHead(a);
        Node bHead = findHead(b);
        if (aHead != bHead) {
            int aSetSize = sizeMap.get(aHead);
            int bSetSize = sizeMap.get(bHead);
            if (aSetSize <= bSetSize) {
                fatherMap.put(aHead, bHead);
                sizeMap.put(bHead, aSetSize + bSetSize);
            } else {
                fatherMap.put(bHead, aHead);
                sizeMap.put(aHead, aSetSize + bSetSize);
            }
        }
    }
}

输出：

输出:2

题目三：01岛

代码

public class Islands{
    public static int countIslands(int[][] m) {
        if (m == null || m[0] == null) {
            return 0;
        }
        int N = m.length;
        int M = m[0].length;
        int res = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (m[i][j] == 1) {
                    res++;
                    infect(m, i, j, N, M);
                }
            }
        }
        return res;
    }
      //感染函数
    public static void infect(int[][] m, int i, int j, int N, int M) {
        if (i < 0 || i >= N || j < 0 || j >= M || m[i][j] != 1) {
            return;
        }
        m[i][j] = 2;
        infect(m, i + 1, j, N, M);
        infect(m, i - 1, j, N, M);
        infect(m, i, j + 1, N, M);
        infect(m, i, j - 1, N, M);
    }

    public static void main(String[] args) {
        int[][] m1 = {  { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 
                        { 0, 1, 1, 1, 0, 1, 1, 1, 0 }, 
                        { 0, 1, 1, 1, 0, 0, 0, 1, 0 },
                        { 0, 1, 1, 0, 0, 0, 0, 0, 0 }, 
                        { 0, 0, 0, 0, 0, 1, 1, 0, 0 }, 
                        { 0, 0, 0, 0, 1, 1, 1, 0, 0 },
                        { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, };
        System.out.println(countIslands(m1));
        int[][] m2 = {  { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 
                        { 0, 1, 1, 1, 1, 1, 1, 1, 0 }, 
                        { 0, 1, 1, 1, 0, 0, 0, 1, 0 },
                        { 0, 1, 1, 0, 0, 0, 1, 1, 0 }, 
                        { 0, 0, 0, 0, 0, 1, 1, 0, 0 }, 
                        { 0, 0, 0, 0, 1, 1, 1, 0, 0 },
                        { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, };
        System.out.println(countIslands(m2));
    }
}

输出：

3
1