标签:
难度: Medium
标签:
难度: Medium
运行时间: 137 ms
内存: 24.9 MB
class Solution: def adventureCamp(self, expeditions: List[str]) -> int: seen = set(expeditions[0].split('->')) mx = 0 ans = -1 for i in range(1, len(expeditions)): if not expeditions[i]: continue cnt = 0 for camp in expeditions[i].split('->'): if camp not in seen: cnt += 1 seen.add(camp) if cnt > mx: mx = cnt ans = i return ans
这个题解的思路是首先将第一个探险记录中的所有营地名存储到一个集合中,表示这些营地已经被发现。然后,从第二个记录开始遍历每一次探险的记录。对于每条记录,将其中的营地名与已知的集合进行比较,如果发现新的营地(即不在集合中的营地),则将这个新营地添加到集合中,并计数新发现的营地数量。如果某次探险发现的新营地数量超过之前的最大值,则更新最大值并记录当前的探险索引。最后,返回发现新营地最多的探险索引,如果没有发现新营地则返回-1。
时间复杂度: O(n * m)
空间复杂度: O(n * m)
class Solution: def adventureCamp(self, expeditions: List[str]) -> int: seen = set(expeditions[0].split('->')) # 初始化已知营地集合 mx = 0 # 记录发现的最大新营地数量 ans = -1 # 记录发现最多新营地的探险索引 for i in range(1, len(expeditions)): if not expeditions[i]: continue # 跳过空的探险记录 cnt = 0 # 当前探险的新发现营地数量 for camp in expeditions[i].split('->'): if camp not in seen: cnt += 1 # 新发现一个营地 seen.add(camp) # 将新营地添加到集合中 if cnt > mx: mx = cnt # 更新最大新发现营地数量 ans = i # 更新记录索引 return ans # 返回发现新营地最多的探险索引,或-1如果没有新发现
题解中没有明确指出如何处理大小写不同的营地名称。在实际应用中,如果考虑到大小写不同的营地名称应当被视为同一个营地,应该在处理名称前将所有的营地名称统一转化为小写或大写。这可以通过在添加到集合之前使用 Python 的 str.lower() 或 str.upper() 方法来实现。
集合(set)在 Python 中是一个无序的、不重复的元素集,它提供了高效的成员检查功能,时间复杂度为 O(1)。这使得在每次探险中检查新营地是否已被发现变得非常高效。相比之下,列表的成员检查时间复杂度为 O(n),字典虽然也支持 O(1) 时间复杂度的成员检查,但对于本题的需求来说,集合的功能已足够,并且使用集合可以使代码更为简洁,因为它直接表示了一个不重复的元素集合。
在题解中,空的探险记录可能被定义为不包含任何营地名称的记录,即一个空字符串。题解中的代码通过检查字符串是否为空来跳过空记录。关于只有 '->' 符号而无实际营地名称的记录,题解中没有明确说明如何处理这种情况。理论上,这种记录应当也视为无效记录,因为它不包含实际的营地名称。在实操中,应该增加处理逻辑来识别并跳过这类记录,例如检查分割后的列表中是否存在非空字符串。