leetcode
leetcode 251 ~ 300
搜寻名人

搜寻名人

难度:

标签:

题目描述

代码结果

运行时间: 664 ms, 内存: 16.4 MB


/*
 * 思路:
 * 使用Java Stream简化对每个候选人的检查。
 * 通过过滤和匹配来判断是否有满足名人条件的人。
 */
 
import java.util.stream.IntStream;
 
public class Solution {
    public int findCelebrity(int n) {
        return IntStream.range(0, n)
                .filter(i -> IntStream.range(0, n).allMatch(j -> i == j || !knows(i, j) && knows(j, i)))
                .findFirst()
                .orElse(-1);
    }
 
    private boolean knows(int a, int b) {
        // 这个方法由系统提供,模拟判断a是否认识b
        return false; // 仅为示例,实际应根据系统实现
    }
}

解释

方法:

这个题解使用了两次遍历来找到名人。第一次遍历从候选人0开始,将候选人与之后的每个人进行比较,如果候选人认识当前人,说明候选人不是名人,将当前人设为新的候选人。这样第一次遍历后,我们就能找出潜在的名人候选人。第二次遍历用来验证这个候选人是否真的是名人,即所有其他人都认识候选人,且候选人不认识任何其他人。同时使用了缓存来存储已经调用过的knows API结果,避免重复调用。

时间复杂度:

O(n)

空间复杂度:

O(n^2)

代码细节讲解

🦆
在第一次遍历中,为什么遇到`candidate`认识`i`时,就立刻确定`candidate`不是名人,并将`i`设为新的候选人?是否有可能错过真正的名人?
在第一次遍历中,如果`candidate`认识`i`,则根据名人的定义(名人不认识任何其他人,但所有其他人都认识名人),`candidate`显然不能是名人。因此,我们需要更换候选人。选择`i`作为新的候选人是基于假设如果`candidate`不是名人,而`candidate`认识`i`,那么`i`有可能是名人。这种方法不会错过名人,因为每次更换候选人都是因为当前候选人违反了名人的条件。最终,这个过程将筛选出一个唯一的可能的名人候选人,然后需要通过第二次遍历来验证这个候选人是否真的是名人。
🦆
第二次遍历中,`is_celebrity`函数调用`cache_knows`函数来验证候选人,如果`cache`中没有存储某次调用结果会怎样影响算法的性能和结果?
如果`cache`中没有存储`knows`函数的某次调用结果,那么`is_celebrity`函数将直接调用`knows`函数来获取结果,并将其存储在`cache`中。这将确保每次`knows`调用的结果都被缓存,减少了重复调用的需要。如果没有使用缓存,每次需要验证候选人与其他所有人的关系时都可能需要重新调用`knows`,这会增加API调用次数,导致性能下降。因此,使用缓存可以显著优化性能,尤其是在网络延迟或API调用成本较高的情况下。
🦆
算法中提到使用缓存来存储`knows`API的结果以减少网络延迟,这种策略在哪些情况下最为有效?是否有可能因为缓存过多数据而影响性能?
缓存`knows`API的结果特别有效于减少网络或API调用延迟,以及调用次数较多的情况。例如,在高并发环境或网络延迟高的情况下,缓存可以显著提升性能。然而,如果缓存过多数据,的确有可能影响性能,尤其是在内存有限的系统中。缓存占用过多内存可能导致系统其他部分的性能下降,或者触发更频繁的垃圾收集,从而影响整体性能。因此,合理设计缓存的大小和清理策略是很重要的,以确保缓存机制能够提供最大的性能优势而不引入额外的性能负担。

相关问题

找到小镇的法官

小镇里有 n 个人,按从 1n 的顺序编号。传言称,这些人中有一个暗地里是小镇法官。

如果小镇法官真的存在,那么:

  1. 小镇法官不会信任任何人。
  2. 每个人(除了小镇法官)都信任这位小镇法官。
  3. 只有一个人同时满足属性 1 和属性 2

给你一个数组 trust ,其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人。

如果小镇法官存在并且可以确定他的身份,请返回该法官的编号;否则,返回 -1

 

示例 1:

输入:n = 2, trust = [[1,2]]
输出:2

示例 2:

输入:n = 3, trust = [[1,3],[2,3]]
输出:3

示例 3:

输入:n = 3, trust = [[1,3],[2,3],[3,1]]
输出:-1
 

提示:

  • 1 <= n <= 1000
  • 0 <= trust.length <= 104
  • trust[i].length == 2
  • trust 中的所有trust[i] = [ai, bi] 互不相同
  • ai != bi
  • 1 <= ai, bi <= n