9.25搜狗笔试2.9

    public Interval solve (int n, int k, String str1, String str2) {
        // write code here
        if(str1.equals(str2)){
            return new Interval(k,k);
        }
        int sameCnt = 0;
        for (int i=0;i<n;i++){
            if(str1.charAt(i)==str2.charAt(i)){
                sameCnt++;
            }
        }
        int max = Math.min(sameCnt,k)+n-k;
        //max错了，这是考试时的代码
        int min = k-(n-sameCnt);
        return  new Interval(Math.max(min, 0),max);
    }

    public String rotatePassword(String[] s1, String[] s2) {
        // write code here
        int n = s1.length;
        char[][] paper = new char[n][n];
        char[][] code = new char[n][n];
        for (int i = 0; i < n; i++) {
            paper[i] = s1[i].toCharArray();
            code[i] = s2[i].toCharArray();
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 4; i++) {
            paper = spinPaper(paper, i);
            sb.append(getCode(paper, code));
        }
        return sb.toString();
    }

    private String getCode(char[][] paper, char[][] code) {
        StringBuilder sb = new StringBuilder();
        int n = paper.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(paper[i][j]=='0'){
                    sb.append(code[i][j]);
                }
            }
        }
        return sb.toString();
    }

    private char[][] spinPaper(char[][] paper, int i) {
        if (i == 0) {
            return paper;
        }
        char[][] newPaper = new char[paper.length][paper.length];
        for (int j = 0; j < paper.length; j++) {
            for (int k = 0; k < paper.length; k++) {
                newPaper[k][paper.length - 1 - j] = paper[j][k];
            }
        }
        return newPaper;
    }

 public Interval trim(int n, int m, Interval[] conn) {
        // write code here
        Map<Integer, List<Integer>> opp = new HashMap<>();
        Map<Integer, List<Integer>> neg = new HashMap<>();

        int[] color = new int[n + 1];
        for (int i = 0; i < m; i++) {
            List<Integer> oppList = opp.computeIfAbsent(conn[i].start, k -> new ArrayList<>());
            List<Integer> negList = neg.computeIfAbsent(conn[i].end, k -> new ArrayList<>());
            oppList.add(conn[i].end);
            negList.add(conn[i].start);
        }
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(-1);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            List<Integer> negList = neg.get(cur);
            if (negList != null) {
                for (int next : negList) {
                    if (color[next] == 0) {
                        color[next] = 1;
                        queue.offer(next);
                    }
                }
            }
        }
        queue.offer(0);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            List<Integer> oppList = opp.get(cur);
            if (oppList != null) {
                for (int next : oppList) {
                    if (next != -1 && color[next] == 1) {
                        color[next] = 2;
                        queue.offer(next);
                    }
                }
            }
        }
        int cnt = 0, sum = 0;
        for (int i = 1; i <= n; i++) {
            if (color[i] == 2) {
                cnt++;
                sum += i;
                sum %= 100000007;
            }
        }
        return new Interval(cnt, sum);
    }