首页 > 8.31蔚来Java笔试
头像
waigo
发布于 2021-08-31 23:02
+ 关注

8.31蔚来Java笔试

芜湖,今天又全A了一个笔试。

  • 1.题目一:找数对

      //1.用set记一下已经有过的数
      //2.已经有过数对的开始放入set
      public int get_pair_count (int[] arr) {
          if(arr==null||arr.length<2) return 0;
          HashSet<Integer> found = new HashSet<>();
          HashSet<Integer> collected = new HashSet<>();
          for(int a:arr){
              if(found.contains(a-1)){
                  collected.add(a-1);//有个a-1开始的数对
              }
              if(found.contains(a+1)){
                  collected.add(a);//有个a开始的数对
              }
              found.add(a);
          }
          return collected.size();
      }
  • 2.题目二:链表去重

      //将链表中有的进set
      public ListNode remove_duplicate1(ListNode head) {
          ListNode temp = head;
          ListNode res = new ListNode(0);
          ListNode tail = res;
          HashSet<Integer> set = new HashSet<>();
          while(temp!=null){
              if(!set.contains(temp.val)){
                  tail.next = temp;
                  tail = temp;
                  set.add(temp.val);
              }
              temp = temp.next;
          }
          tail.next = null;
          return res.next;
      }
  • 3.题目三:一个字符串s,一个字符串t,它们各自整个子串s1,t1,如果s1中替换一个字符就能和t1相同则记一次,问这种情况有几个。

      public int countSubstr (String s, String t) {
          if(s==null||t==null||s.length()==0||t.length()==0) return 0;
          int rows = s.length();
          int cols = t.length();
          //先求一个dp,dp[i][j]表示以i,j结尾,相等子串长度
          int[][] eq = getEq(s,t,rows,cols);
          //s做行,t做列
          int[][] dp = new int[rows+1][cols+1];
          int res = 0;
          //第一行
          for(int row = 1;row<=rows;row++){
              for(int col = 1;col<=cols;col++){
                  if(s.charAt(row-1)!=t.charAt(col-1)){
                      //看一下前面相等的长度,一次收集完
                      int frontEq = eq[row-1][col-1];
                      dp[row][col] = 1 + frontEq;
                  }else if(dp[row-1][col-1]>0){//当前相等就看前一位是否相等
                      dp[row][col] = dp[row-1][col-1];
                  }
                  res+=dp[row][col];
              }
          }
          return res;
      }
    
      private int[][] getEq(String s, String t, int rows, int cols) {
          int[][] eq = new int[rows+1][cols+1];
          for(int row = 1;row<=rows;row++){
              for(int col = 1;col<=cols;col++){
                  if(s.charAt(row-1)==t.charAt(col-1)){
                      eq[row][col] = 1 + eq[row-1][col-1];
                  }
              }
          }
          return eq;
      }

全部评论

(3) 回帖
加载中...
话题 回帖

相关热帖

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

热门推荐