字节机试面经

No.1

579万平方公里土地，分给岛上的魔法师，魔法师存在师徒关系，1 是2的师傅，1和2就是一个部落，可以循环1 2, 2 3, 3 1。

最终判断岛上有多少个部落，每个部落占多少土地（按魔法师数量分）

import java.lang.reflect.Array;
import java.util.*;

public class Main {
    static int[] parent;
    static int[] dep;
    static int[] nums;
    public static int find(int a) {
        while(parent[a] != a) a = parent[a];
        return a;
    }
    public static void union(int a, int b) {
        int p_a = find(a);
        int p_b = find(b);
        if(p_a != p_b) {
            if (dep[p_a] > dep[p_b]) {
                parent[p_b] = p_a;
                nums[p_a] += nums[p_b];
            } else {
                parent[p_a] = p_b;
                dep[p_b]++;
                nums[p_b] += nums[p_a];
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        parent = new int[n + 1];
        dep = new int[n + 1];
        nums = new int[n + 1];
        Arrays.fill(dep, 1);
        Arrays.fill(nums, 1);
        for(int i = 0; i < n + 1; i++) {
            parent[i] = i;
        }
        int m =sc.nextInt();
        for(int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            union(a, b);
        }
        int cnt = 0;
        List<Integer> list = new ArrayList<>();
        for(int i = 1; i <= n; i++) {
            if(parent[i] == i) {
                list.add(579 * nums[i] / n);
                cnt++;
            }
        }
        System.out.println(cnt);
        list.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for(int t: list)
            System.out.print(t + " ");
        System.out.println();
    }
}

No.2力扣题，A了75

https://leetcode.cn/problems/last-stone-weight-ii/

No.3 n个老鼠有坐标，两个洞口A，B，k个老鼠可以进A洞，n-k个老鼠可以进B洞，求最小的进洞总距离。

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        double[] pa = new double[2];
        pa[0] = sc.nextDouble();
        pa[1] = sc.nextDouble();
        double[] pb = new double[2];
        pb[0] = sc.nextDouble();
        pb[1] = sc.nextDouble();
        double[][] dis = new double[n][3];
        for(int i = 0; i < n; i++) {
            double x = sc.nextDouble();
            double y = sc.nextDouble();
            dis[i][0] = getDis(x, y, pa[0], pa[1]);
            dis[i][1] = getDis(x, y, pb[0], pb[1]);
            dis[i][2] = Math.abs(dis[i][0] - dis[i][1]);
        }
        Arrays.sort(dis, new Comparator<double[]>() {
            @Override
            public int compare(double[] o1, double[] o2) {
                return o1[2] - o2[2] < 0? 1: -1;
            }
        });
        double sum = 0;
        int cnt_a = 0;
        int cnt_b = 0;
        for(int i = 0; i < n; i++) {
            if(cnt_a == k) {
                sum += dis[i][1];
                continue;
            }
            if(cnt_b == n - k) {
                sum += dis[i][0];
                continue;
            }
            if(dis[i][0] > dis[i][1]) {
                cnt_b++;
                sum += dis[i][1];
            } else {
                cnt_a++;
                sum += dis[i][0];
            }
        }
        System.out.println(sum);
    }

    private static double getDis(double x, double y, double v, double v1) {
        double lev = Math.abs(x - v);
        double vet = Math.abs(y - v1);
        return Math.sqrt(lev * lev + vet * vet);
    }

}

No.4真不会了，题都忘了。。。