第一道题
最短距离，直线上选一点使得到给出的N个直线上的点的距离之和最短。
先Arrays.sort()对数组排序，取中位下标（N-1）/2，所有的点到该点距离求和。
最大的坑是要用long，题目本身小学奥数难度，十五年前做过。
用了十分钟，五分钟写完，5分钟确定自己用了long+加调试复制粘贴。
第一题代码
package leecode;
import java.util.Arrays;
import java.util.Scanner;
public class Ali001 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()){
int N=in.nextInt();
long trees[]=new long[(int) N];
for(int i=0;i<N;i++){
trees[i]=in.nextLong();
}
Arrays.sort(trees);
int midindex=(N-1)/2;
long toa=trees[midindex];
long ans=0L;
for(int i=0;i<=midindex;i++){
ans+=toa-trees[i];
}
for(int i=midindex;i<N;i++){
ans+=trees[i]-toa;
}
System.out.println(ans);
}
}
} 第二道题是二叉树谁所在的节点深度更小。
一开始觉得头大，觉得ac一道挺不错，所以没抱啥希望
准备写二叉树，写起来觉得好复杂。决定改用哈希表（动态规划？）输入的时候把深度写道哈希表里。十几分钟写完发现一直报错，改的头大，纠结了十分钟。以为自己记错HashMap函数用法了，想起来还不如用数组。五分钟改完发现本地测试用例迟迟不出结果，重新看了遍题目发现是看错题目了数组长度和循环长度多写了1，改完提交就100了，哈希表写法应该也没错，是我眼神出问题的锅。
感觉这道题想清楚了很简单，想不清楚……构建二叉树然后一堆操作，能写出来真的是大佬把。
复杂度应该是O(n),看了很多朋友们的写法，再回来看自己的想法觉得还是自己的比较好，大家想的太复杂了。
每次添加的时候都记录该节点的深度，比较的时候直接比较小明小强的节点深度就好了，一目了然，应该算是用了动态规划。
写完还有十几分钟，室友也在写，最后a了第一道的80.
代码
package leecode;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Ali003 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()){
int N=in.nextInt();
int M=in.nextInt();
int [] map=new int [N+1];
map[1]=1;
for(int i=2;i<=N;i++){
int now=in.nextInt();
map[i]=map[now]+1;
}
boolean []ans=new boolean[M];
for(int i=0;i<M;i++){
int xq=in.nextInt();
int xm=in.nextInt();
int deepxq=map[xq]; //小强深度
int deepxm=map[xm]; //小明深度
if(deepxq<=deepxm){
ans[i]=true;
}else{
ans[i]=false;
}
}
for(int i=0;i<M;i++){
if(ans[i])
System.out.println("A");
else
System.out.println("B");
}
}
}
}
全部评论
(2) 回帖