记录一下少有的全A笔试
题目一:给个数组，计算每个位置右边最近比它大，左边最近比它小的差值。
//i是下标 nums[i]>0 //对i找到其最近的两个位置x,y，满足x<i且nums[x]<nums[i],y>i且nums[y]>nums[i] //单调栈的概念题 //输出结果是nums[y]-nums[x]右-左,找不到x,y则认为nums[x]=0,nums[y]=0 //注意元素可能重复[9,3,3,6] public int[] nearestDiff (int[] nums) { if(nums==null||nums.length==0) return new int[]{}; //lMXRB --> left Min and right Big int[][] lMXRB = new int[nums.length][2];//lMXRB[i][0]：左边小，lMXRB[i][1]：右边大 //栈中存的都是下标 Stack<List<Integer>> stack = new Stack<>(); //栈是一个从下到上递减的单调栈，栈中压的是同值list //1.找出每个i位置右边最近比自己大的 //每个数出现的时候从栈中弹出比当前小的，此时当前数就是弹出数右边最近最大的 int N = nums.length; int cur; for(int i = 0;i<N;i++){ cur = nums[i]; while(!stack.isEmpty()&&nums[stack.peek().get(0)]<cur){ List<Integer> top = stack.pop(); for(int idx:top){ lMXRB[idx][1] = cur; } } if(stack.isEmpty()||nums[stack.peek().get(0)]!=cur){ stack.push(new ArrayList<>()); } stack.peek().add(i); } //栈中都清空，已经没有右边比自己大的了，所以都是0 stack.clear(); //栈是一个从下到上递增的单调栈，栈中压的是同值list //2.找出每个i位置左边最近比自己小的 //每个数出现的时候从栈中弹出比当前大的，此时压着的就是比自己小的 for(int i = 0;i<N;i++){ cur = nums[i]; while(!stack.isEmpty()&&nums[stack.peek().get(0)]>cur){ List<Integer> top = stack.pop(); for(int idx:top){ lMXRB[idx][0] = stack.isEmpty()?0:nums[stack.peek().get(0)]; } } if(stack.isEmpty()||nums[stack.peek().get(0)]!=cur){ stack.push(new ArrayList<>()); } stack.peek().add(i); } //清出来，此时和上面不同，可能还有压着有答案的 while(!stack.isEmpty()){ List<Integer> top = stack.pop(); for(int idx:top){ lMXRB[idx][0] = stack.isEmpty()?0:nums[stack.peek().get(0)]; } } //计算结果 int[] res = new int[N]; for(int i = 0;i<N;i++){ res[i] = lMXRB[i][1] - lMXRB[i][0]; } return res; }题目二:IP地址合并
private static final int SEGMENT = 4;//地址四段 //1.解法类似天际线问题，就是先将IP地址进行一个排序，然后开始遍历，全程维护start,end //一旦出现断层就收集一个答案。 //具体实现 //1.先将IP地址给分装成对象 //2.确定对象的比较策略，就是IP地址如何比较谁在前，谁在后的问题 //很明显，从前到后，进行比较IP地址的四个部分，出现小了，那小的那个在前面 //将每部分都以数字的方式存储，简单化比较的复杂度 public static class IPv4Address implements Comparable<IPv4Address>{ int[] address = new int[SEGMENT]; public IPv4Address(String ip){ String[] split = ip.split("\\."); for(int i = 0;i<4;i++){ address[i] = Integer.valueOf(split[i]); } } @Override public int compareTo(IPv4Address o) { for(int i = 0;i<SEGMENT-1;i++){ if(this.address[i]<o.address[i]){ return -2;//o1在前 }else if(this.address[i]>o.address[i]){ return 2;//o2在前 } } //前三位都相同，则返回最后一位的差值,根据最后一位返回-1可以判断是否连续 return this.address[SEGMENT-1]-o.address[SEGMENT-1]; } @Override public String toString() { StringBuilder builder = new StringBuilder(); for(int i = 0;i<SEGMENT;i++){ builder.append(address[i]).append("."); } builder.deleteCharAt(builder.length()-1); return builder.toString(); } } public static class AddressZone{ IPv4Address start; IPv4Address end; public AddressZone(String ipZone){ if(ipZone.contains("-")){ String[] split = ipZone.split("-"); start = new IPv4Address(split[0]); end = new IPv4Address(split[1]); }else{ start = new IPv4Address(ipZone); end = start; } } public AddressZone(IPv4Address start, IPv4Address end) { this.start = start; this.end = end; } @Override public String toString() { if(start==end||start.compareTo(end)==0){ return start.toString(); } return start.toString()+"-"+end.toString(); } } public static class ZoneComparator implements Comparator<AddressZone>{ @Override public int compare(AddressZone o1, AddressZone o2) { return o1.start.compareTo(o2.start); } } public ArrayList<String> merge(ArrayList<String> input) { if(input==null||input.size()==0) return new ArrayList<>(); int size = input.size(); AddressZone[] zones = new AddressZone[size]; for(int i = 0; i< size; i++){ zones[i] = new AddressZone(input.get(i)); } //排序 Arrays.sort(zones,new ZoneComparator()); ArrayList<String> res = new ArrayList<>(); IPv4Address start = zones[0].start; IPv4Address end = zones[0].end; for(int i = 1;i<size;i++){ AddressZone curZone = zones[i]; int gap = end.compareTo(curZone.start); if(Math.abs(gap)!=2){ //最后一位判断 if(gap==-1){ //连续 end = curZone.end; }else if(gap<0){ //收集 res.add(new AddressZone(start,end).toString()); //修改start,end start = curZone.start; end = curZone.end; }else{ //改end,只有新end要大才改 int endGap = end.compareTo(curZone.end); end = endGap<0?curZone.end:end; } }else{ //前三位就能够确定了，不存在连续的情况 if(gap<0){ //收集 res.add(new AddressZone(start,end).toString()); //修改start,end start = curZone.start; end = curZone.end; }else{ //改end,只有新end要大才改 int endGap = end.compareTo(curZone.end); end = endGap<0?curZone.end:end; } } } //最后没有触发收集了，手动收集一下最后一次 res.add(new AddressZone(start,end).toString()); return res; }
全部评论
(5) 回帖