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); }