腾讯研发部分编程题汇总做题笔记---Java

朋友圈(后端开发卷)
现在有 105 个用户,编号为 1- 105,现在已知有 m 对关系,每一对关系给你两个数 x 和 y ,代表编号为 x 的用户和编号为 y 的用户是在一个圈子中,例如: A 和 B 在一个圈子中, B 和 C 在一个圈子中,那么 A , B , C 就在一个圈子中。现在想知道最多的一个圈子内有多少个用户。

数据范围:
在这里插入图片描述

1≤m≤2×10
6

进阶:空间复杂度 O(n) ,时间复杂度 O(nlogn)
时间限制:C/C++ 2秒,其他语言4秒
空间限制:C/C++ 256M,其他语言512M
输入描述:
第一行输入一个整数T,接下来有T组测试数据。
对于每一组测试数据:第一行输入1个整数n,代表有n对关系。
接下来n行,每一行输入两个数x和y,代表编号为x和编号为y的用户在同一个圈子里。
1 ≤ T ≤ 10
1 ≤ n ≤ 2*106
1 ≤ x, y ≤ 105
输出描述:
对于每组数据,输出一个答案代表一个圈子内的最多人数
示例1
输入例子:
2
4
1 2
3 4
5 6
1 6
4
1 2
3 4
5 6
7 8
输出例子:
4
2

ac代码
// package tencent.tel.sum;

import java.util.Scanner;
class UnionFind {
    private int[] parent;
    private int[] size;
    private int count;

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

    public int find(int p) {
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) {
            return;
        }
        if (size[rootP] > size[rootQ]) {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        } else {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        }
        count--;
    }

    public int getMaxUnion(){
        int max = 1;
        for (int x:size)
            max = Math.max(max,x);
        return max;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        while(T-->0){
            int n = in.nextInt();
            UnionFind u = new UnionFind(100005);
            for (int i=0;i<n;i++)
                u.union(in.nextInt(), in.nextInt());
            System.out.println(u.getMaxUnion());
        }

    }
}

在这里插入图片描述
在这里插入图片描述

ac代码



import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int T = in.nextInt();
    while(T-->0){
        double A = in.nextDouble();
        double B = in.nextDouble();
        double C = in.nextDouble();
        if (A-2*B*C<=0) {
            System.out.println(0);
        continue;
        }
        double result = calculate(A,B,C);
        System.out.println(result);
        }
    }
    public static double calculate(double a,double b,double c){
        double y1 = a/b+Math.pow((a*a)/(b*b)-(2*a*c)/b,1.0/2);
        double y2 = a/b-Math.pow((a*a)/(b*b)-(2*a*c)/b,1.0/2);
        double result_1 = jifen(a,b,c,y1);
        double result_2 = jifen(a,b,c,y2);
        return result_1-result_2;
    }
    public static double jifen(double a,double b,double c,double y){
        return Math.pow(y,2)/(2*b)-(c*y)/b-Math.pow(y,3)/(6*a);
    }
}

上一篇:leetcode.209.长度最小的子数组-题目


下一篇:MFC标签设计工具 图片控件上,移动鼠标显示图片控件内的鼠标xy的水平和垂直辅助线要在标签模板上加上文字、条型码、二维码 找准坐标和字体大小 源码