4.11网易互娱-计算机视觉实习岗笔试

先说情况，四道编程题分别是ac,40%,0,ac 。

第一题：没有什么算法，按照正常思路，先写整数相加函数，如果是小数把小数变成整数，注意补零对齐，再将结果放小数点就可以了。

第二题：先排序，工人和任务从大到小排，对于第i个任务，能够胜任的工人数是j，则可以安排的种树有j-i种，减i是因为前面task已经安排了i个工人，这i个工人肯定是能够胜任第i个任务的。那么遍历一遍任务，按每个任务的安排个数连乘，即为答案。无奈考完才想到这个方法。40%是递归做的。

第三题：这道题有点复杂，做题时先跳过了。现在想想，应该跟数独一样，先确定每一个玩家可以组队的人，然后根据限制条件去得出答案。具体思路还没有，期待大神解答一下。更新：https://www.nowcoder.com/discuss/405871，看到上面的链接，也是数独的思路。不过我看到他直接使用两个库，暴力枚举，由于数据大小是7*7，也ac了，这也行！

第四题：深度优先遍历森林。把小盒子当做根节点，先寻找每个盒子的孩子（即那些长宽高比该盒子大的盒子），最小的盒子是根节点。因为盒子可能不是任何一个盒子的孩子，所以可能有多个根节点，所以是深度遍历森林。

应评论贴下第四题参考python代码：

class Solution:

    def is_bigger(self, box1,box2):
        if box1[0] > box2[0] and box1[1] > box2[1] and box1[2] > box2[2]:
            return True
        return False

    #以box当做节点深度遍历
    def dfs(self,box,cnt):
        if len(self.d[box]) == 0:
            # 更新最大深度
            self.max_cnt = max(self.max_cnt,cnt)
        for box in self.d[box]:
            # 如果box已经被访问了，说明是该box孩子的子孙，肯定深度没有之前大（该节点->孙子 小于 该节点->孩子->孩子）
            # 所以不用访问了
            if self.visit[box] == False:
                self.visit[box] = True
                self.dfs(box,cnt+1)

    def maxBoxes(self, boxes):
        # write code here
        boxes = [(x[0], x[1], x[2]) for x in boxes]
        boxes = sorted(boxes, key=lambda x: x[0] * x[1] * x[2])
        import collections
        # d是记录每个box的孩子
        self.d = collections.defaultdict(list)
        box_cnt = len(boxes)
        # roots记录森林的根节点
        self.roots = [x for x in boxes]
        for i in range(box_cnt):
            for j in range(i + 1, box_cnt):
                if self.is_bigger(boxes[j], boxes[i]):
                    self.d[boxes[i]].append(boxes[j])
                    if boxes[j] in self.roots:
                        self.roots.remove(boxes[j])
        self.max_cnt = 1
        # visit作用见dfs函数
        self.visit = dict()
        for root in self.roots:
            # 每次遍历树，都要把所有节点置为未访问
            for i in range(box_cnt):
                self.visit[boxes[i]] = False
            self.root = root
            self.dfs(root, 1)
        return self.max_cnt

s = Solution()
boxes = [[5,4,3], [5,4,5], [6,6,6]]
print(s.maxBoxes(boxes))

没有论文找算法岗太难了，希望能给个面试机会QAQ

#网易互娱笔试##网易互娱##笔试题目##计算机视觉岗#