网易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);
}
}
} 第二题：0AC！ 第三题：基因求逆序数
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;
}
} 