广联达笔试
第一题是粒子的题,其实我的思路很简单,用hash表记录下来顺序不对的,碰到就跳过就完事,然后双指针遍历找到两个数组就好了
举个栗子:
5 4 3 2 1(指针1)
1 5 3 4 2(指针2)
首先1是不对的所以把1记录下来,指针2右移,碰到5,是对的,两个指针共同向右移动,接着碰到3,3是不对的,记录下来,指针2右移,碰到4,4是对的,指针1和2同时右移,指针1碰到不对的3直接跳过,碰到2是对的,两个指针一起后移,接着指针1碰到1,1是不对的跳过,至此遍历结束,可以的到逆序的就是指针1和指针2不相等的情况(注意指针1会先跳过记录顺序不对的数)
第二题,我就是正常贪心+hash,过了93,下面是代码
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int m=sc.nextInt(); Map<Integer,Integer> group=new HashMap<>(); Map<Integer,List<Integer>> idxtogroup=new HashMap<>(); for(int i=0;i<m;i++){ int s=sc.nextInt(); int e=sc.nextInt(); group.put(i,sc.nextInt()); for(int j=s;j<=e;j++){ List<Integer> temp=idxtogroup.getOrDefault(j, new ArrayList<>()); temp.add(i); idxtogroup.put(j, temp); } } long res=0; for(int i=1;i<=n;i++){ if(!idxtogroup.containsKey(i)){ res++; } else{ boolean flag=false; List<Integer> list=idxtogroup.get(i); for(int v:list){ if(group.get(v)<=0){ flag=true; break; } } if(flag) continue; for(int v:list){ int ts=group.get(v); group.put(v, ts-1); } res++; } } System.out.println(res); } }