这两题都是dropbox的哈
924的是把感染的某个节点恢复，928是把感染的某个节点连同他的边删除
leetcode 924 Minimize Malware Spread 解题笔记
13 October 2018
leetcode 924, Minimize Malware Spread
- 给定一个用图表示的网络，如果graph[i][j] = 1, 说明节点i和j之间有连接
- 如果一个节点被病毒感染，所有和这个节点有连接的节点都会被病毒感染，并且会不断扩散
- 输入一个初始节点数组，表示已经感染病毒的节点
问题，假如从初始节点中删除一个节点，选择哪个节点会使得最后已感染病毒的节点最少？
- 这个题目最正规的做法应该是union find， 不过因为之前写了一个错误的bfs版本， 所以这里在原来错误bfs的版本上修正了一下。
- 这里修正的情况是针对有两个initial节点可以互相连接的情况，也就是remove其中一个不会改变最后被感染的机器个数， 所以简单的加了一个set判断了一下
- 很可惜， leetcode的test case没有很好的覆盖这类情况， 原来的错误代码也可以ac， 所以我把这个case提交给leetcode了
比如对下面这个图，
图的矩阵表示： [[1,1,0,0,0],[1,1,1,0,0],[0,1,1,0,0],[0,0,0,1,1],[0,0,0,1,1]]
initial nodes分别是： [0,1,3]
0--1--2
3--4
虽然0和1都可以感染3个节点，但是无论删除0还是1都不会减少被感染的node, 反而remove 3可以减少被感染的node。
所以这个case应该返回3而不是0
public int minMalwareSpread(int[][] graph, int[] initial) {
Map<Integer, Integer> countMap = new HashMap<>();
Set<Integer> set = new HashSet<>();
for(int v: initial) {
set.add(v);
}
for(int v: initial) {
if(!countMap.containsKey(v)) {
countMap.putAll(calcImpacted(graph, v, set));
}
}
int maxCount = -1, retv = 0;
for(Map.Entry<Integer, Integer> entry: countMap.entrySet()) {
if(!set.contains(entry.getKey())) continue;
if(entry.getValue() > maxCount) {
retv = entry.getKey();
maxCount = entry.getValue();
}
else if(entry.getValue() == maxCount && entry.getKey() < retv) {
retv = entry.getKey();
}
}
return retv;
}
public Map<Integer, Integer> calcImpacted(int[][] graph, int initial, Set<Integer> initialSet) {
Queue<Integer> queue = new LinkedList<>();
queue.add(initial);
Set<Integer> set = new HashSet<Integer>();
boolean dup = false;
while(queue.size() > 0) {
int v = queue.poll();
set.add(v);
for(int j = 0; j < graph.length; ++j) {
if(graph[v][j] == 1 && !set.contains(j)) {
queue.add(j);
if(j != initial && initialSet.contains(j)) {
dup = true;
}
}
}
}
Map<Integer, Integer> countMap = new HashMap<Integer,Integer>();
for(int v: set) {
int count = dup ? 0 : set.size();
countMap.put(v, count);
}
return countMap;
}
http://www.noteanddata.com/leetcode-928-Minimize-Malware-Spread-II-java-solution-note-2.html
笔记和数据
Leetcode 928. Minimize Malware Spread II 非brute force版本解题笔记
21 October 2018
leetcode 928. Minimize Malware Spread II
- 这个题目之前写了一个brute force的版本，可以ac，但是复杂度比较高，效率不是很好。
http://www.noteanddata.com/leetcode-928-Minimize-Malware-Spread-II-solution-note.html
现在写了一个非brute force的版本。
- 这里主要的区别是重复的部分， 也就是两个initial会连到一起，然后污染同一批机器
假如有如下图， 然后initial是[1,5]
如果删除1， 就是剩下5，被感染的机器是[2,3,4,5,6]
如果删除5， 就是剩下1，被感染的机器是[1,2,3,4]
1---2---3---4
|
|
5---6
从这个例子可以看出，有一些节点可能会被两个initial都感染到，而有一些节点只能被某一些initial感染到。
如果移除某个initial并且把相关的连接都切断以后， 那么那些只能被这个initial感染的节点就不能被感染， 这实际上就是真正被移除的节点。
- 所以， 可以bfs访问每个initial节点，然后看只能被这个节点感染的节点有哪些。
a. 如果在bfs的过程中遇到其他initial节点就不访问
b. 如果任意某一个节点被一个initial节点访问到过，那就不算是“只能被某个initial节点感染的节点”， 应该从记录中删除
public int minMalwareSpread(int[][] graph, int[] initial) {
Set<Integer> initialSet = new HashSet<>();
for(int node: initial) {
initialSet.add(node);
}
Map<Integer,Integer> uniqueSourceMap = new HashMap<>();
Set<Integer> uniqueSourceSet = new HashSet<>();
for(int node: initial) {
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
queue.add(node);
while(queue.size() > 0) {
int v = queue.poll();
visited.add(v);
if(!uniqueSourceSet.contains(v)) {
uniqueSourceSet.add(v);
uniqueSourceMap.put(v, node);
}
else {
uniqueSourceMap.remove(v);
}
for(int i = 0; i < graph.length; ++i) {
if(graph[v][i] == 1 && !initialSet.contains(i) && !visited.contains(i)) {
queue.add(i);
}
}
}
}
int[] countTable = new int[graph.length];
int maxi = 0;
for(Map.Entry<Integer, Integer> entry: uniqueSourceMap.entrySet()) {
int i = entry.getValue();
countTable[i]++;
if(countTable[i] > countTable[maxi]) maxi = i;
else if(countTable[i] == countTable[maxi] && i < maxi) maxi = i;
}
return maxi;
}
所有操作是O(M+M N N+N)， 也就是O(M N N), 其中M是initial的个数， N是graph的节点数
O(M+N*2+N), 也就是O(N)
写完这个以后， 感觉好像之前的924虽然可以ac但是似乎做错了？，http://www.noteanddata.com/leetcode-924-Minimize-Malware-Spread.html
对于重复情况的判断似乎没有考虑， 那个正确的做法应该是用union find来做， 后面准备验证一下。
或者如果bfs的话还是需要每次把一个节点移除然后再做处理， 直接计数应该不对的。