[数据结构与算法]LeetCode 0817. 链表组件

【LetMeFly】817.链表组件

力扣题目链接：https://leetcode.cn/problems/linked-list-components/

给定链表头结点?head，该链表上的每个结点都有一个 唯一的整型值 。同时给定列表?nums，该列表是上述链表中整型值的一个子集。

返回列表?nums?中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表?nums?中）构成的集合。

?

示例?1：

输入: head = [0,1,2,3], nums = [0,1,3]
输出: 2
解释: 链表中,0 和 1 是相连接的，且 nums 中不包含 2，所以 [0, 1] 是 nums 的一个组件，同理 [3] 也是一个组件，故返回 2。

示例 2：

?

输入: head = [0,1,2,3,4], nums = [0,3,1,4]
输出: 2
解释: 链表中，0 和 1 是相连接的，3 和 4 是相连接的，所以 [0, 1] 和 [3, 4] 是两个组件，故返回 2。

?

提示：

• 链表中节点数为n
• 1 <= n <= 104
• 0 <= Node.val < n
• Node.val?中所有值 不同
• 1 <= nums.length <= n
• 0 <= nums[i] < n
• nums 中所有值 不同

方法一：哈希

首先遍历一遍$nums$数组，将其中的所有元素都存入哈希表中（例如C++中的unordered_set）。这样判断链表中的某个元素是否存在于$nums$中的时间复杂度就变成了$O(1)$

之后遍历链表，用一个布尔类型的变量lastIsIn来记录链表的上一个节点是否存在于$nums$中

若“上一个节点不在$nums$中且这一个节点在$nums$中”，则“控件”个数+1

• 时间复杂度$O(n)$，其中$n$是$nums$中元素的个数
• 空间复杂度$O(n)$

AC代码

C++

class Solution {
public:
    int numComponents(ListNode* head, vector<int>& nums) {
        unordered_set<int> se;
        for (int& t : nums) {
            se.insert(t);
        }
        int ans = 0;
        bool lastIsIn = false;
        while (head) {
            if (se.count(head->val) && !lastIsIn) {
                ans++;
            }
            lastIsIn = se.count(head->val);
            head = head->next;
        }
        return ans;
    }
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/127278261