朋友圈转发信息

本文主要是介绍朋友圈转发信息，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Sender
1
Relationship
1,2
1,3
1,4
2,5
2,6
3,6
4,6
4,7
5,6
5,8
5,9
6,7
6,8
6,9
7,9
10,7
End

4

这题还算是有点意思吧  主要包含了2个环节   1搞定最短路径  最短路径算法，由于路径长度都是一样的 所以还要简单一点   2 搞定能覆盖下一层的最小点数

这道题我写的时候思路有点不清楚，主要是在Map中 value值设置set对象的时候出了点问题，最后我选择使用了ArrayList代替，这样的话 其实在大数据的时候效率很低，这点需要优化，另外我是明确确定下一层没有重复节点，所以我用了list的containsAll  这点也是需要注意

另外题目有点问题    也就是没说节点的编号问题，所以我这里自己抽取转换了一下，建立了一个映射，这个会影响效率，但是感觉实际应用上会显得很有用

下面放源码

package 消息转发网络;import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;//首先是来一遍最短路径算法  确定每个人距离根的最短路径
//根据最短路径可以获得一个层次树
//在每一层上选在能得到下一层所有点的最小组合
//得到结果public class Main {static int rootIndex; // 存放根指针// 建立顶点到index映射 ,用来消除顶点编号的不连续性static Map<Integer, Integer> vertexMaptoIndex;// 用index的形式保存边static Map<Integer, ArrayList<Integer>> directedEages;// 用来存层次深度static Map<Integer, ArrayList<Integer>> deepMaptoIndexs;static int maxDeep;public static void main(String[] args) {readData();Map<Integer, Integer> indexMaptoDeep = getShortestPathLength();loadDeepMaptoIndex(indexMaptoDeep);// Set<Integer> deeps = deepMaptoIndexs.keySet();// for(int deep : deeps){// ArrayList<Integer> indexs = deepMaptoIndexs.get(deep);// System.out.println("deep: "+deep);// for(int index : indexs){// System.out.print(index + "-");// }// System.out.println();// }// System.out.println(maxLayer);int result = 0;for (int i = 1; i < maxDeep; i++) {result += getMinSizeofCover(i);}System.out.println(result);}// 读入数据// 中间进行数据清理，来消除输入顶点编号的不连续性// 测试通过public static void readData() {Scanner in = new Scanner(System.in);in.next();// 读掉senderSet<Integer> vertexSet = new HashSet<Integer>();int rootVertex = in.nextInt();vertexSet.add(rootVertex);in.next();// 读掉RelationShipString temp = in.next();// 存储读入的边ArrayList<Integer> leftVertexs = new ArrayList<Integer>(20);ArrayList<Integer> rightVertexs = new ArrayList<Integer>(20);while (!temp.equals("End")) {String[] numberArray = temp.split(",");int leftnumber = Integer.parseInt(numberArray[0]);int rightnumber = Integer.parseInt(numberArray[1]);leftVertexs.add(leftnumber);rightVertexs.add(rightnumber);vertexSet.add(leftnumber);vertexSet.add(rightnumber);temp = in.next();}// 创建顶点到边的映射 同时初始化有向图vertexMaptoIndex = new HashMap<Integer, Integer>();directedEages = new HashMap<Integer, ArrayList<Integer>>();int count = 1;for (int vertex : vertexSet) {vertexMaptoIndex.put(vertex, count);directedEages.put(count, new ArrayList<Integer>(10));count++;}rootIndex = vertexMaptoIndex.get(rootVertex);// 生成有向图ArrayList<Integer> tempArrayList;for (int i = 0; i < leftVertexs.size(); i++) {int leftIndex = vertexMaptoIndex.get(leftVertexs.get(i));int rightIndex = vertexMaptoIndex.get(rightVertexs.get(i));tempArrayList = directedEages.get(leftIndex);tempArrayList.add(rightIndex);directedEages.put(leftIndex, tempArrayList);tempArrayList = directedEages.get(rightIndex);tempArrayList.add(leftIndex);directedEages.put(rightIndex, tempArrayList);}}// 得到最短路径// 测试通过public static Map<Integer, Integer> getShortestPathLength() {Map<Integer, Integer> ShortestPathLength = new HashMap<Integer, Integer>();ShortestPathLength.put(rootIndex, 0);Queue<Integer> waitedQueue = new LinkedList<Integer>();waitedQueue.add(rootIndex);while (waitedQueue.size() != 0) {int fromIndex = waitedQueue.remove();List<Integer> availableIndexs = directedEages.get(fromIndex);for (int toIndex : availableIndexs) {if (ShortestPathLength.get(toIndex) == null) {ShortestPathLength.put(toIndex,ShortestPathLength.get(fromIndex) + 1);waitedQueue.add(toIndex);}}}return ShortestPathLength;}private static void loadDeepMaptoIndex(Map<Integer, Integer> indexMaptoDeep) {Set<Integer> keys = indexMaptoDeep.keySet();deepMaptoIndexs = new HashMap<Integer, ArrayList<Integer>>();for (int key : keys) {int deep = indexMaptoDeep.get(key);if (deepMaptoIndexs.get(deep) == null) {deepMaptoIndexs.put(deep, new ArrayList<Integer>(20));maxDeep = maxDeep < deep ? deep : maxDeep;}ArrayList<Integer> indexs = deepMaptoIndexs.get(deep);indexs.add(key);deepMaptoIndexs.put(deep, indexs);}}// 在每一层上选在能得到下一层所有点的最小组合的顶点个数public static int getMinSizeofCover(int deep) {ArrayList<Integer> thisLayerIndexs = deepMaptoIndexs.get(deep);ArrayList<Integer> nextLayerIndexs = deepMaptoIndexs.get(deep + 1);// 包含的顶点Queue<ArrayList<Integer>> includedIndexsQueue = new LinkedList<ArrayList<Integer>>();// 对应的已经覆盖的顶点Queue<ArrayList<Integer>> availableIndexsQueue = new LinkedList<ArrayList<Integer>>();for (int i = 0; i < thisLayerIndexs.size(); i++) {ArrayList<Integer> includedIndexs = new ArrayList<Integer>();includedIndexs.add(i);ArrayList<Integer> availableIndexs = directedEages.get(thisLayerIndexs.get(i));if (availableIndexs.containsAll(nextLayerIndexs)) {return 1;} else {includedIndexsQueue.add(includedIndexs);availableIndexsQueue.add(availableIndexs);}}while (includedIndexsQueue.size() > 0) {//取出当前元组ArrayList<Integer> includedIndexs = includedIndexsQueue.remove();ArrayList<Integer> availableIndexs = availableIndexsQueue.remove();//插入一个新节点观察结果;int start = includedIndexs.get(includedIndexs.size()-1);for(int i = start+1 ; i < thisLayerIndexs.size();i++){ArrayList<Integer> newincludedIndexs= new ArrayList<Integer>(includedIndexs);ArrayList<Integer> newavailableIndexs =new ArrayList<Integer>(availableIndexs);newincludedIndexs.add(i);newavailableIndexs.addAll(directedEages.get(thisLayerIndexs.get(i)));if(newavailableIndexs.containsAll(nextLayerIndexs)){return newincludedIndexs.size();}else{includedIndexsQueue.add(newincludedIndexs);availableIndexsQueue.add(newavailableIndexs);}}}return thisLayerIndexs.size();}
}

这篇关于朋友圈转发信息的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！