记录一下少有的全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;
    }