924. 尽量减少恶意软件的传播

给出了一个由 n 个节点组成的网络，用 n × n 个邻接矩阵图 graph 表示。在节点网络中，当 graph[i][j] = 1 时，表示节点 i 能够直接连接到另一个节点 j。 

一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。

假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。

如果从 initial 中移除某一节点能够最小化 M(initial)， 返回该节点。如果有多个节点满足条件，就返回索引最小的节点。

请注意，如果某个节点已从受感染节点的列表 initial 中删除，它以后仍有可能因恶意软件传播而受到感染。

示例 1：

输入：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
输出：0

示例 2：

输入：graph = [[1,0,0],[0,1,0],[0,0,1]], initial = [0,2]
输出：0

示例 3：

输入：graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]
输出：1

提示：

• n == graph.length
• n == graph[i].length
• 2 <= n <= 300
• graph[i][j] == 0 或 1.
• graph[i][j] == graph[j][i]
• graph[i][i] == 1
• 1 <= initial.length <= n
• 0 <= initial[i] <= n - 1
• initial 中所有整数均不重复

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimize-malware-spread
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

成功，题目描述不是特别清晰，其实是无向图，题目简单的用连接两个字概括有点不清楚；另外索引其实指的是图中的索引，initial的索引。删除表示初始感染不包含此元素，并不是真的删除掉该元素，也不是该元素不能被传播。

方法：前缀和

想到每个元素之间有相互包含的情况，会比较复杂，不能说全部加起来再减掉一块。那可以采用前缀后缀方法，可以参考这题：剑指 Offer 66. 构建乘积数组

1. 提前算出后缀，再把它和前缀组合起来，就变成除了当前元素之外其他元素的结果长度。

2. 索引尽可能小。给initial 排个序（前面dfs过程实际每加一层都循环一次n，相当于 n 方复杂度，这里 nlogn 无伤大雅），后面只有小于前面的情况才替换即可，这里可以少一点if判断

class Solution {
        Set []spreads;
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
 
        //循环graph n方，排个序肯定比它小
        Arrays.sort(initial);
        int m = initial.length;
        //每个点能传播到多少点
        spreads = new HashSet[m];
        for(int i = 0; i < m; i++){
            spreads[i] = new HashSet<>();
            dfs(spreads[i],initial[i],graph);
        }
 
        //哈希后缀，代表传播了多少人 [i,m-1]
        Set[] lasts = new HashSet[m+1];
        lasts[m] = new HashSet<>();
        for(int i = m-1; i >= 0; i--){
            Set tmp = new HashSet<>(lasts[i+1]);
            tmp.addAll(spreads[i]);
            lasts[i] = tmp;
        }
 
        int ans = initial[0];
        int spread = Integer.MAX_VALUE;
        //哈希前缀，代表传播了多少人
        Set tmp = new HashSet<>();
        for(int i = 0; i < m; i++){
            //前+后=不包括自己的
            Set curr = new HashSet<>(tmp);
            curr.addAll(lasts[i+1]);
            //成功减少恶意软件传播，替换答案
            // （索引问题，由于排序不存在后面比前面小的情况，判断变简单）
            if(curr.size()
                spread = curr.size();
                ans = initial[i];
            }
            tmp.addAll(spreads[i]);
        }
        return ans;
    }
 
        private void dfs(Set spread, int index, int[][] graph) {
            if(spread.contains(index)) return;
            spread.add(index);
            for(int i = 0; i < graph[index].length; i++){
                if(graph[index][i]==1){
                    dfs(spread,i,graph);
                }
            }
 
        }
    }