力扣-817.链表组件

题目描述

思路及实现

看到题目给的组件定义，链表中最长连续节点，该节点的值在所给数组中。那么我们可以利用一个flag来判断这个值是否在数组中，在的话就把flag设置成1，不在的话，再判断此时flag的值是否为1，如果为1说明此处是一个组件的结束处，让组件数量加一即可。
当然如果这么写，还需要在循环结束后再检查一次flag的值，确保没有落下最后一个组件。如果不想最后再检查值，可以把判断条件改为值不在数组中。
由于在数组中找某个值是否存在的时间复杂度是O(n)，所以我们可以使用set来替代数组，这样可以使搜索值的时间复杂度降到O(1)。

class Solution:
    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:
        count = 0
        flag = 0
        a_set = set(nums)
        while head is not None:
            if head.val in a_set:  # or: if head.val not in a_set:
                flag = 1
            elif flag == 1:
                flag = 0
                count += 1
            head = head.next
        return count if flag == 0 else count + 1

---

希望本文章能够帮到您~