最后更新于6年前
每个组件都有末尾,抓住这个即可,i一次遍历,若i在G中且i的后继不在G中,说明i是一个组件的末尾,组件+1;若i的后继为空,说明i仍是一个组件末尾
将G列表转成set才能通过,否则超时
考虑组件头也可以,不过比找末尾复杂。
class Solution: def numComponents(self, head: ListNode, G: List[int]) -> int: res = 0 G_set = set(G) i = head while i: if i.val in G_set and (not i.next or i.next.val not in G_set): res += 1 #找到一个组件末尾 i = i.next return res