牛牛发现,从这片大陆开始工业化以来,一共发生了m次原始生产力提升。每一次原始生产力提升在一个工厂u发生,它会让工厂u以及和工厂u直接通过管道相连的工厂的生产力加1。
每个工厂最开始的生产力都是0。
现在牛牛知道了m次生产力提升发生的工厂位置。牛牛想知道这m次提升发生之后每个工厂的生产力是多少。
4,2,[1,2,2],[2,3,4],[2,1]
[2,2,1,1]
第一次生产力提升发生在工厂2,工厂1,2,3,4的生产力都提升了1点第二次生产力提升发生在工厂1,工厂1,2的生产力都提升了1点最终工厂1,2的生产力都为2,工厂3,4的生产力都为1
第一个参数代表工厂数量第二个参数代表生产力提升次数第三个参数u和第四个参数vector<int> v各自包含n-1个元素代表管道。第i根管道连接第个工厂和第个工厂。第五个参数q包含m个元素代表生产力提升发生的位置。
class Solution { public: /** * 扩散 * @param n int整型 * @param m int整型 * @param u int整型vector * @param v int整型vector * @param q int整型vector * @return int整型vector */ vector<int> solve(int n, int m, vector<int>& u, vector<int>& v, vector<int>& q) { vector<int> r(n, 0); int a[n]; memset(a, 0, sizeof(a)); for(int i=0;i<m;i++){ if(q[i]>0 && q[i]<=n){ a[q[i]-1]++; r[q[i]-1]++; } } for(int i=0;i<n-1;i++){ r[u[i]-1] += a[v[i]-1]; r[v[i]-1] += a[u[i]-1]; } return r; } };
vector<int> solve(int n, int m, vector<int>& u, vector<int>& v, vector<int>& q) { vector<int> r(n, 0); int *a=(int*)calloc(n,sizeof(int)); // 分配内存空间并赋值为0 for(int i=0;i<m;i++){ if(q[i]>0 && q[i]<=n){ a[q[i]-1]++; r[q[i]-1]++; } } // for(int i=0;i<n-1;i++){ r[u[i]-1] += a[v[i]-1]; r[v[i]-1] += a[u[i]-1]; } free(a); return r; }
import java.util.*; public class Solution { public int[] solve(int n, int m, int[] u, int[] v, int[] q) { // write code here HashMap record = new HashMap(); HashMap res = new HashMap(); for (int i = 0; i < m; i++) { if (record.containsKey(q[i] - 1)) { int tempNum = record.get(q[i] - 1); record.put(q[i] - 1, tempNum + 1); res.put(q[i] - 1, tempNum + 1); } else { record.put(q[i] - 1, 1); res.put(q[i] - 1, 1); } } for (int i = 0; i < n - 1; i++) { if (record.containsKey(v[i] - 1)) { int tempNum = 0; if (res.containsKey(u[i] - 1)) { tempNum = res.get(u[i] - 1); } res.put(u[i] - 1, tempNum + record.get(v[i] - 1)); } if (record.containsKey(u[i] - 1)) { int tempNum = 0; if (res.containsKey(v[i] - 1)) { tempNum = res.get(v[i] - 1); } res.put(v[i] - 1, tempNum + record.get(u[i] - 1)); } } int[] productivity = new int[n]; for (int i = 0; i < n; i++) { if (res.containsKey(i)) { productivity[i] = res.get(i); } } return productivity; } }
vector<int> solve(int n, int m, vector<int>& u, vector<int>& v, vector<int>& q) { //u:n-1:0-n-2,v:n-1:0-n-2,q:m:0-m vector<int> result(n,0); vector<int> pv(n,0); for(int i=0;i<m;i++){ //if(q[i]<=0) return vector<int> (1,-1); //if(q[i]>0 && q[i]<=n){ pv[q[i]-1]++; result[q[i]-1]++; //} } for(int i=0;i<n-1;i++){ result[u[i]-1]+=pv[v[i]-1]; result[v[i]-1]+=pv[u[i]-1]; } return result; }
vector<int> solve(int n, int m, vector<int>& u, vector<int>& v, vector<int>& q) { //u:n-1:0-n-2,v:n-1:0-n-2,q:m:0-m vector<int> result(n,0); vector<int> pv(n,0); for(int i=0;i<m;i++){ if(q[i]<=0) return vector<int> (1,-1); //if(q[i]>0 && q[i]<=n){ pv[q[i]-1]++; result[q[i]-1]++; //} } for(int i=0;i<n-1;i++){ result[u[i]-1]+=pv[v[i]-1]; result[v[i]-1]+=pv[u[i]-1]; } return result; }
vector<int> solve(int n, int m, vector<int>& u, vector<int>& v, vector<int>& q) { //u:n-1:0-n-2,v:n-1:0-n-2,q:m:0-m vector<int> result(n,0); vector<int> pv(n,0); for(int i=0;i<m;i++){ //if(q[i]<=0) return vector<int> (1,-1); if(q[i]>0 && q[i]<=n){ pv[q[i]-1]++; result[q[i]-1]++; } } for(int i=0;i<n-1;i++){ result[u[i]-1]+=pv[v[i]-1]; result[v[i]-1]+=pv[u[i]-1]; } return result; }
# # 扩散 # @param n int整型 # @param m int整型 # @param u int整型一维数组 # @param v int整型一维数组 # @param q int整型一维数组 # @return int整型一维数组 # import collections class Solution: def solve(self , n , m , u , v , q ): graph = collections.defaultdict(list) vals = [0] * (n + 1) for i in range(n - 1): graph[u[i]].append(v[i]) graph[v[i]].append(u[i]) for i in range(m): vals[q[i]] += 1 for j in range(len(graph[q[i]])): vals[graph[q[i]][j]] += 1 return vals[1: ]
# # 扩散 # @param n int整型 # @param m int整型 # @param u int整型一维数组 # @param v int整型一维数组 # @param q int整型一维数组 # @return int整型一维数组 # import collections class Solution: def solve(self , n , m , u , v , q ): add1, add2, res = [0] * (n + 1), [0] * (n + 1), [0] * (n + 1) for i in range(m): add1[q[i]] += 1 for i in range(n - 1): add2[u[i]] += add1[v[i]] add2[v[i]] += add1[u[i]] for i in range(1, n + 1): res[i] = add1[i] + add2[i] return res[1: ]
class Solution { public: vector<int> solve(int n, int m, vector<int>& u, vector<int>& v, vector<int>& q) { // write code here int tmp1[n]; for(int i=0;i<n;i++){ tmp1[i] = 0; } //vector<int> tmp1(n,0); 使用vector会出现 Error in `./a.out': double free&nbs***bsp;corruption (out): 0x0000000000aabcf0 vector<int> tmp2(n,0); vector<int> res(n,0); for(int i=0;i<m;++i){ tmp1[q[i]-1]++; } for(int i=0;i<u.size();++i){ tmp2[u[i]-1]+=tmp1[v[i]-1]; tmp2[v[i]-1]+=tmp1[u[i]-1]; } for(int i=0;i<n;++i){ res[i]=tmp1[i]+tmp2[i]; } return res; } };如代码中,最开始使用vector开辟两个数组,会报错 Error in `./a.out': double free or corruption (out): 0x0000000000aabcf0。然后改为栈上数组,成功。
public int[] solve (int n, int m, int[] u, int[] v, int[] q) { List<Integer>[] neighbor = new ArrayList[n+1]; for(int i=0;i<n+1;++i){ neighbor[i] = new ArrayList<>(); } for(int i=0;i<u.length;++i){ neighbor[u[i]].add(v[i]); neighbor[v[i]].add(u[i]); } int[] num = new int[n+1]; for (int i : q) { ++num[i]; } int[] count = new int[n]; int flag = 0; for(int i=1;i<=n;++i){ if (flag == m) { break; } if (num[i] == 0) { continue; } flag++; count[i-1] = count[i-1] + num[i]; for(int j=0;j<neighbor[i].size();j++){ count[neighbor[i].get(j)-1]=count[neighbor[i].get(j)-1]+num[i]; } } return count; }
vector<int> solve(int n, int m, vector<int>& u, vector<int>& v, vector<int>& q) { //会出现double free&nbs***bsp;corruption (out),不知道是什么原因 //开始以为是内存超了,但发现修改程序之后也会有这个问题 //看了别人的程序之后,该成了在栈上开辟数组的形式 //不知道是什么原因,应该没有数组越界的情况 //vector<int> add(n,0); int add[n]; for(int i=0;i<n;i++){ add[i] = 0; } vector<int> add2(n,0); vector<int> res(n,0); for(int i=0;i<m;i++){ add[q[i]-1]++; } for(int i=0;i<n-1;i++){ add2[u[i]-1] += add[v[i]-1]; add2[v[i]-1] += add[u[i]-1]; } for(int i=0;i<n;i++){ res[i] = add[i] + add2[i]; } return res; }