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 <= 1040 <= Node.val < nNode.val中所有值 不同1 <= nums.length <= n0 <= nums[i] < nnums中所有值 不同
方法一：哈希
首先遍历一遍
n
u
m
s
nums
nums数组，将其中的所有元素都存入哈希表中（例如C++中的unordered_set）。这样判断链表中的某个元素是否存在于
n
u
m
s
nums
nums中的时间复杂度就变成了
O
(
1
)
O(1)
O(1)
之后遍历链表，用一个布尔类型的变量lastIsIn来记录链表的上一个节点是否存在于
n
u
m
s
nums
nums中
若“上一个节点不在 n u m s nums nums中且这一个节点在 n u m s nums nums中”，则“控件”个数+1
- 时间复杂度 O ( n ) O(n) O(n)，其中 n n n是 n u m s nums nums中元素的个数
- 空间复杂度 O ( n ) O(n) 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