网易ME计划笔试7.21

import java.util.*;


public class Solution {
    /**
     *
     * @param node_data_list int整型二维数组 
     * @return int整型二维数组
     */
    private static int[][] result = null;
    private static int visitIndex = 0;
    private static Map<Integer,Deque<Integer>> map = null;
    public int[][] invert_tree (int[][] node_data_list) {
        // write code here
        map = new HashMap<>();
        result = new int[node_data_list.length][2];
        visitIndex = 0;

        for(int i=0;i<node_data_list.length;i++){
            if(!map.containsKey(node_data_list[i][1])){
                map.put(node_data_list[i][1],new LinkedList());
            }
            map.get(node_data_list[i][1]).addLast(node_data_list[i][0]);
        }
        PreVisit( map.get(0).removeLast(),0);
        return result;
    }
    public void PreVisit(int son,int par){
        result[visitIndex][0] = son;
        result[visitIndex++][1] = par;
        while(map.containsKey(son)&&!map.get(son).isEmpty()){
            PreVisit(map.get(son).removeLast(),son);
        }
    }
}

package org.example;

public class Solution {
    private static int inverseCount = 0;
    public static void main(String[] args) {
        int[] input = {1,2,3,4,5,6,7,0};
        new Solution().InversePairs(input);
    }
    public int InversePairs(int[] array) {
        inverseCount = 0;
        Divide(array, 0, array.length-1);
        return inverseCount;
    }
    public void Divide(int[] arr, int begin, int end) {
        if (begin >= end) {
            return;
        }
        int mid = (begin + end) / 2;
        Divide(arr, begin, mid);
        Divide(arr, mid + 1, end);
        Merge(arr, begin, end);
    }
    public void Merge(int[] arr, int begin, int end) {
        int mid = (begin + end) / 2;
        int curr = 0, curr1 = begin, curr2 = mid + 1;
        int[] temp = new int[end - begin + 1];
        while (curr1 <= mid && curr2 <= end) {
            if (arr[curr1] <= arr[curr2]) {
                temp[curr++] = arr[curr1++];
            } else {
                temp[curr++] = arr[curr2++];
                inverseCount += (mid - curr1 + 1);
                inverseCount%=1000000007;
            }
        }
        while (curr1 <= mid) {
            temp[curr++] = arr[curr1++];
        }
        while (curr2 <= end) {
            temp[curr++] = arr[curr2++];
        }
        for (int i = begin; i <= end; i++) {
            arr[i] = temp[i - begin];
        }
    }
}

import java.util.*;

public class Solution {
    /**
     * @param filenames string字符串一维数组 所有文件名
     * @param relations string字符串二维数组 文件依赖关系
     * @return int整型
     */
    public int split_package(String[] filenames, String[][] relations) {
        // write code here
        Map<String, Boolean> isVisit = new HashMap<>();
        for (String s : filenames) {
            isVisit.put(s, false);
        }
        Map<String, Set<String>> relyMap = new HashMap<>();
        for (int i = 0; i < relations.length; i++) {
            if (!relyMap.containsKey(relations[i][0])) {
                relyMap.put(relations[i][0], new HashSet<>());
            }
            relyMap.get(relations[i][0]).add(relations[i][1]);
            if (!relyMap.containsKey(relations[i][1])) {
                relyMap.put(relations[i][1], new HashSet<>());
            }
            relyMap.get(relations[i][1]).add(relations[i][0]);
        }
        int visitCount = 0;
        Queue<String> visitQueue = new LinkedList<>();
        for (String s : filenames) {
            if (!isVisit.get(s)) {
                visitCount++;

                visitQueue.clear();
                visitQueue.add(s);
                while (!visitQueue.isEmpty()) {
                    String currStr = visitQueue.poll();
                    isVisit.put(currStr, true);
                    if(relyMap.containsKey(currStr)) {
                        for(String innerS : relyMap.get(currStr)) {
                            if(!isVisit.get(innerS))
                                visitQueue.add(innerS);
                        }
                    }
                }
            }

        }
        return visitCount;

    }
}