algorithm001 / algorithm

119 stars 152 forks source link

【053-week3】学习总结_补交 #831

Open 361028096 opened 5 years ago

361028096 commented 5 years ago

本周学习了 图 和 堆 相关的内容,需要更多的练习

【解题思路】 703.Kth Largest Element in a Stream 这道题的数组是不断在变大的,所以每次第K大的数字都在不停的变化。那么我们其实只关心前K大个数字就可以了,所以我们可以使用一个最小堆来保存前K个数字,当再加入新数字后,最小堆会自动排序,然后把排序后的最小的那个数字去除,则堆中还是K个数字,返回的时候只需返回堆顶元素即可。

997.Find the Town Judge 这个问题,我们可以建立一个defaultdict(set),然后遍历trust中的每个元素it(将it[0]作为key,将it[1]作为value)添加到dict中,这样我们就建立了一个信任关系的映射。我们知道每个人(除了小镇法官外)都信任小镇的法官,那么我们只需要查找dict中是不是有一个value的长度等于N-1,如果存在的话,那么对应的key就是法官。此时还有一个问题,就是小镇的法官不相信任何人,我们只需要新建一个set,将it的key添加到set中,如果我们返回的数在set中存在的话,那么说明存在法官相信他人的情况。这里还有一个边界条件没有考虑,就是小镇只有一个人的时候,那么这个人一定是法官。