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;
    }