8.17 饿了么笔试 AK(难得的一次AK)

T1:判断外卖是否超时 100%

public static void main(String[] args)  {
         Scanner sc=new Scanner(System.in);
         String t1=sc.next();
         String t2=sc.next();
         String t3=sc.next();
         String[] arr1=t1.split(":");
         String[] arr2=t1.split(":");
         int h1=Integer.parseInt(arr1[0]);
         int m1=Integer.parseInt(arr1[1]);
        int h2=Integer.parseInt(arr2[0]);
        int m2=Integer.parseInt(arr2[1]);
        int a=(h1-1)*60+m1;
        int b=(h2-1)*60+m2;
        if((a<=b&&b-a<=120)||(a>b&&a-b>120)){
            System.out.println("No");
        }else {
            System.out.println("Yes");
        }
    }

T2:是否可以重构字符串 100%

public static void main(String[] args)  {
         Scanner sc=new Scanner(System.in);
         String s=sc.next();
         int n=s.length();
         int[] cnt=new int[26];
         boolean[] vis=new boolean[26];
         StringBuilder sb=new StringBuilder();
         int types=0;
         for(int i=0;i<n;i++){
             char c=s.charAt(i);
             cnt[c-'a']++;
             if(cnt[c-'a']==1){
                 types++;
             }
         }
         boolean flag=false;
         int type2=0;
         for(int i=0;i<n;i++){
             char c=s.charAt(i);
             for(int j=0;j<26;j++){
                 if(j!=c-'a'&&(!vis[j]||flag)){
                     sb.append(j+'a');
                     vis[j]=true;
                     type2++;
                     if(type2==types){
                         flag=true;
                     }
                     break;
                 }
             }
         }
         String ans=sb.toString();
         if(ans.length()==n){
             System.out.println(ans);
         }else {
             System.out.println(-1);
         }
    }

# T3:小美送外卖 100%

Dijkstar算法即可,最后根据目的地遍历disTo数组,累加求和即可,最后需要乘以2,因为一来一回

public static void main(String[] args)  {
         Scanner sc=new Scanner(System.in);
         int n=sc.nextInt();
         int m=sc.nextInt();
         int q=sc.nextInt();
         ArrayList<long[]> []G=new ArrayList[n+1];
         for(int i=0;i<n;i++){
             int u=sc.nextInt();
             int v=sc.nextInt();
             int w=sc.nextInt();
             if(G[u]==null){
                 G[u]=new ArrayList<>();
             }
             if(G[v]==null){
                 G[v]=new ArrayList<>();
             }
             G[u].add(new long[]{v,w});
             G[v].add(new long[]{u,w});
         }
         int[] arr=new int[q];
         for(int i=0;i<q;i++){
             arr[i]=sc.nextInt();
         }
         PriorityQueue<long[]> pq=new PriorityQueue<>((x,y)->Long.compare(x[1],y[1]));
         boolean[] vis=new boolean[n+1];
         long[] disTo=new long[n+1];
         Arrays.fill(disTo,Long.MAX_VALUE);
         pq.offer(new long[]{1,0});
         disTo[0]=0;
         while (!pq.isEmpty()){
             long[] e=pq.poll();
             int u=(int)e[0];
             long dis=e[1];
             if(vis[u]){
                 continue;
             }
             vis[u]=true;
             for(long[] next:G[u]){
                 int v=(int)next[0];
                 long w=next[1];
                 if(!vis[v]&&disTo[v]>dis+w){
                     disTo[v]=dis+w;
                     pq.offer(new long[]{v,disTo[v]});
                 }
             }
         }
         long ans=0;
         for(int v:arr){
             ans+=disTo[v];
         }
        System.out.println(ans*2);

    }

全部评论
请问下第三题vis数组为什么可以剪枝呀?
点赞 回复 分享
发布于 2023-08-18 09:01 加拿大

相关推荐

03-25 16:22
南华大学 Java
不敢追175女神:你是打了上千个招呼吧?😂
点赞 评论 收藏
分享
评论
3
30
分享

创作者周榜

更多
牛客网
牛客企业服务