首页 > 阿里笔试8.10(人生第一次全ac)
头像
长的黑漆漆
编辑于 2020-08-11 09:45
+ 关注

阿里笔试8.10(人生第一次全ac)


第一道题
最短距离,直线上选一点使得到给出的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) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐