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

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

做题结果

成功，题目描述不是特别清晰，其实是无向图，题目简单的用连接两个字概括有点不清楚；另外索引其实指的是图中的索引，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, 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); } } } }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。