字节跳动豆油瓶题

  • 无心学习逛v2的时候看到有人分享2020算法题。觉得十分有趣，遂记录下

题目和解法

题目描述：
抖音上每天都有几亿用户，如果用户 A 和 B 互动不少于 3 次，
我们就认为 A 和 B 属于“豆油”，
如果 A 和 B 是“豆油”，B 和 C 也是“豆油”， 那么 A 和 C 也互为“豆油”，
我们定义“豆油瓶”就是由直系和间接朋友所组成的群体。

给定个 N×N 的矩阵 M，代表抖音上所有用户的互动次数，
如果M[i][j]= 5，那么第i个和第j个用户就互动过5次，
为 0 的话代表没有互动，
对于i = j，即同个用户， 
互动次数我们计为0。请你计算并输出发现的抖音上所有“豆油瓶”的个数。

输入描述:
输入第1行：二维数组的行数(列数一样)N
接下来的N行每行N个数字，空格分割

输出描述:
输出发现的“豆油瓶”数量 k

个人心得

  • 题目构建没有测试数据的方法，
  • 用np写了一个，

  • 构建矩阵，取上部，转置减去2倍的对角线，获取到题目所需的测试数据。

    def samples(num):
    net = np.random.randint(0,4,num**2).reshape(num,num)
    net = np.triu(net)
    net+=net.T - np.diag(net.diagonal())*2
    return net

  • 解法思路基本一致

  • 开一个list存瓶子数量，从第一个循环往下判断，遍历到了记录，以当前的用户继续遍历，完成一遍。计数器+1

  • 修改了一下，把哪些用户存在哪一个瓶里面，最后也输出来看看。

    def solution(num,net):
    vis = [0]*num
    res = 1
    while min(vis) == 0:
        t = [i for i in range(num) if vis[i] == 0]
        vis[t[0]] = res
        q = []
        q.append(t[0])
        while q:
            h = q.pop(0)
            for j in range(num):
                if net[h][j] >=3 and vis[j] == 0:
                    q.append(j)
                    vis[j] = res
        res += 1
    print(vis)
    return res-1

非常有意思的点

  • 题干中说$n$<200,发现$n$=200的话,瓶子数量肯定是1。
  • 刚开始以为自己的程序有问题，试了下$\sum_3^{200}{n}$的散点图，才发现程序是对。

1

  • 可能就是六格理论的另外一种体现。一个人和一定数量人互动超过3次之后，就会找到想通的兴趣点，可以归到一个瓶子里面。理论早就知道，如此的一个量化指标还是很有趣，结果也更加有趣。
  • 有趣。