首页 > 8.31深信服Java笔试
头像
waigo
编辑于 2021-08-31 18:04
+ 关注

8.31深信服Java笔试

记录一下少有的全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) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐