淘天笔试简单题解
第一题：我猜是贪心，分别统计每个数字的最大值，然后统计每个频次出现的数字数目，然后分别从最大值开始贪心，最后写的，没时间了
当前值的频次a
小于等于频次a的所有的数字总数为 m
频次大于a的数字个数（不是总数）为b
如果 a + m + b*a >=k ，那么当前数就是最大的众数
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();in.nextLine();
int[] res = new int[t];
for(int i = 0;i<t;i++){
int n = in.nextInt(),k = in.nextInt();in.nextLine();
int[] a = new int[n];
Map<Integer,Integer> map = new HashMap<>();
for(int j=0;j<n;j++){
a[j] = in.nextInt();
map.put(a[j],map.getOrDefault(a[j],0)+1);
}
Map<Integer,Integer> map2 = new HashMap<>();
for(Map.Entry<Integer,Integer> e:map.entrySet()){
map2.put(e.getKey(),map2.getOrDefault(e.getKey(),0)+1);
}
Arrays.sort(a);
int cnt = 0;
int mx;
for(int j=n-1;j>=0;j--){
int times = map.get(a[j]);
int c = times;
for(int z=1;z<=times;z++){
if(map2.get(z)!=null){
c+=map2.get(z);
if(c>=k){
res[i]=a[j];
break;
}
}
}
if(res[i]!=0){
break;
}
j-=times-1;
}
}
for(int i=0;i<t;i++){
System.out.println(res[i]);
}
}
}
第二题：数论？（菜鸟不懂是哪个类别的）
就是如果当前的x>n ，那么在n位置就是x%n的值，所以需要一次取余
在[x+1,... ]位置就是 x 的值，因为x对于一个大于x的值取余为x，这里右界看一下就好了，不好写，因为n的值不定（所以有一个特判）
在[1,x] 的左侧就是0，因为x一旦到了x的位置取余之后一直是0
但是这题需要看一下边界，就是 k<=x+1（被边界卡了不少时间）
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();in.nextLine();
int[] res = new int[t];
for(int i = 0;i<t;i++){
int n = in.nextInt(),x = in.nextInt(),k = in.nextInt();
if(k==n+1){
// System.out.println("special");
res[i] = x; // 特判
}
else{
x = x%n; // 第 n 项
if(k<=x+1){
// System.out.println("left");
res[i] = 0; // 如果查询在 x 的左侧，取余结果为0
}
else{
// System.out.println("right");
res[i] = x; // 如果查询在 x 右侧，得到 x
}
}
}
for(int i=0;i<t;i++){
System.out.println(res[i]);
}
}
}
这题没看懂，应该是并查集，如果两个端点祖先相同，输出yes，否则no
然后看了示例感觉好像可以构成多个那个不知道什么名字的玩意儿
那么需要确定之前出现的边有没有构成环，我就用一个map记录每次构成环的时候的祖先节点，
如果一个无环的域和成环的域连接了，需要将无环域的原本祖先也记录进去，否则无环域的非祖先节点没有当前域已经承欢的信息
但是最后也不行
这题调了快半个小时，绝望了
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
class Union{
int[] fa;
public Union(int n){
fa = new int[n+1];
for(int i = 0;i<n+1;i++){
fa[i] = i;
}
}
public int find(int u){
if(fa[u] == u){
return u;
}
int f = find(fa[u]);
fa[u] = f; // 变胖
return f;
}
public boolean isU(int u,int v){
if(find(u)==find(v)){
return true;
}
return false;
}
public void u(int u,int v){
int uu = find(u),vv = find(v);
fa[uu] =vv;
}
public void print(){
for(int i=0;i<fa.length+1;i++){
System.out.println(i+ " de fa is "+ fa[i]);
}
}
}
Scanner in = new Scanner(System.in);
int n = in.nextInt(), m = in.nextInt();in.nextLine();
boolean sign = true;
Union union = new Union(n);
boolean[] res = new boolean[n];
Map<Integer,Boolean> map = new HashMap<>();
for(int i = 0;i<n+1;i++){
map.put(i,false);
}
// union.print();
for(int i=0;i<m;i++){
int u=in.nextInt(),v = in.nextInt();in.nextLine();
int uf = union.find(u);
int uv = union.find(v);
if(map.get(uf) || map.get(uv) ){
res[i] = false;
if(!map.get(uf)){ // 顺序不能错
union.u(u,v);
map.put(uf,true);
}else if (!map.get(uv)){
union.u(v,u);
map.put(uv,true);
}
continue;
}
if(union.isU(u,v)){
// System.out.println(i+ " "+" true");
map.put(union.find(u),true);
res[i] = true;
}
else{
// System.out.println(i+ " "+" false ");
res[i] = false;
union.u(u,v);
}
}
// union.print();
for(int i = 0;i<n;i++){
System.out.println(res[i]?"Yes":"No");
}
}
}
总得分0+1+0.03，哎😔
一开始忘记了笔试，中途开始写，太慌了，而且不给用IDEA，好难调代码啊
#淘天##淘天笔试##笔试##实习##实习笔试#
百威成长空间 50人发布
