首页 > 试题广场 >

扩散

[编程题]扩散

热度指数：2920 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛客大陆一共有n个工厂，有n-1对工厂之间有管道相连，因为工厂之间需要合作，所以这n-1个管道保证任意两个工厂都可以通过管道互相抵达。

牛牛发现，从这片大陆开始工业化以来，一共发生了m次原始生产力提升。每一次原始生产力提升在一个工厂u发生，它会让工厂u以及和工厂u直接通过管道相连的工厂的生产力加1。

每个工厂最开始的生产力都是0。

现在牛牛知道了m次生产力提升发生的工厂位置。牛牛想知道这m次提升发生之后每个工厂的生产力是多少。

示例1

输入

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个元素代表生产力提升发生的位置。

算法知识视频讲解

C/C++

nbgao

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;
    }
};

发表于 2020-07-15 22:32:32 回复(3)

卖萌小伙张三

出这题目的人脑子是不是装着屎？这是面试题又不是你们狗屁的ACM竞赛题，***卡老子vector干嘛？脑袋有包？***玩意出的***题目，浪费老子一上午时间

发表于 2020-06-12 09:07:25 回复(1)

牛客690429953号

python3 72%是怎么做到的我咋就54%。。。

发表于 2020-06-10 00:56:46 回复(0)

Python

spongebob7

class Solution:
def solve(self , n , m , u , v , q ):
# write code here
res = [0]*n
detail =[[0]*n]*n
for i in range(0,n):
tmp=[0]*n
tmp[i]=1
for j in range(0,n-1):
if u[j]-1==i:
tmp[v[j]-1]=1
elif v[j]-1==i:
tmp[u[j]-1]=1
detail[i]=tmp
for i in range(0,m):
for j in range(0,n):
if detail[q[i]-1][j]==1:
res[j]+=1
return res

发表于 2021-03-27 11:32:27 回复(0)

Python

up_zhang

python3 77%感觉顶天了：构造树，然后遍历。

class Node(object):
def __init__(self, key=None, value=0, pre=None, childs=None):
if childs is None:
childs = []
self.key = key
self.pre = pre
self.childs = childs

class Solution:
def solve(self, n, m, u, v, q):
values = [0] * n
u_v = zip(u, v)
node_dict = {}
for i in u_v:
u = i[0]
v = i[1]

u_node = Node(key=u, pre=None, childs=[v])
if u in node_dict.keys():
node_dict[u].childs.append(v)
else:
node_dict[u] = u_node
if v in node_dict.keys():
node_dict[v].pre = u
else:
v_node = Node(key=v, pre=u_node, childs=[])
node_dict[v] = v_node
for j in q:
values[j-1] += 1
pre_node = node_dict[j].pre
if pre_node:
values[pre_node.key-1] += 1
child_node_keys = node_dict[j].childs
for child_node_key in child_node_keys:
values[child_node_key-1] += 1
return values

发表于 2020-09-07 22:55:55 回复(0)

丶寻光

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;
}

发表于 2020-08-19 07:20:03 回复(0)

侥幸而已

java怎么写怎么超时，通过率68.18。优化半天，还是超时，怕不是要空间换时间

发表于 2020-08-07 11:23:43 回复(0)

吃瓜群众9102

来一个java用hashmap的代码

之前用列表做卡在95%，而且不是边界或特殊情况的问题

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;
    }
}

编辑于 2020-07-24 18:49:26 回复(0)

C/C++

钢琴手1720

数组必须在栈上，vector和new管理的内存在堆上，都越界。

实话是不理解，那头资源到底是怎么分配的也不敢瞎猜。

发表于 2020-07-24 15:38:29 回复(0)

牛客174867978号

#
# 扩散
# @param n int整型
# @param m int整型
# @param u int整型一维数组
# @param v int整型一维数组
# @param q int整型一维数组
# @return int整型一维数组
#
class Solution:
def solve(self, n, m, u, v, q):
# write code here
res = [0] * n
U,V = len(u),len(v)

# 找到谁的生成力得到提升
for i in q:
# 给自己的厂生产力 +1
if i in range(1,n+1):
res[i-1] += 1

# 给相近的厂的生产力 +1
# 自己连别人
for x in range(0,U):
if u[x] == i:
if v[x] in range(1,n+1):
res[v[x]-1] += 1
# 别人连自己
for y in range(0, V):
if v[y] == i:
if u[y] in range(1, n + 1):
res[u[y]-1] += 1

return res

s = Solution()
re = s.solve(2,2,[1],[2],[1,1])
print(re)

发表于 2020-07-14 15:09:10 回复(0)

C/C++

听君

服气，卡在95.45%以及那个数组越界以及访问非法内存！没有考虑非法输入是我的错，但是我看上面给的代码也没见进行非法输入判断。

报错代码:

 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;
        
    }

报了错，虽然因为数组太大，没有完整显示，但是已经知道了问题，最后的代码其实也没完整，不知道u和v里面的输入需不需要验证……但算了，有点累了，下次多思考一下。

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;
        
    }

发表于 2020-07-09 15:42:51 回复(0)

Python

watle自动机

此题有毒，好奇Python3的时间限制是多少，以下两种写法都t了。。

法一：

#
# 扩散
# @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: ]

发表于 2020-07-05 10:08:24 回复(0)

恍恍惚惚2018

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。然后改为栈上数组，成功。

发表于 2020-06-17 16:58:50 回复(0)

没事。201811082359397

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;
    }

1200 -1300ms java实现，希望还能改进

发表于 2020-06-11 20:41:23 回复(1)

繁星似尘

    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;
    }

发表于 2020-06-07 15:23:23 回复(0)

Python