刷题打卡，第 二十九 天
- 题目一、817. 链表组件
题目一、817. 链表组件
原题链接：817. 链表组件
题目描述：
给定链表头结点 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中找到符合题目要求的组件，并返回组件数量。
根据题目知道组件就是链表中某一段最长连续结点的值（该值必须在列表 nums 中）构成的集合。
我们可以遍历链表节点，如果链表节点是子集nums中的组件开头，我们就记录下组件的数量。
判断当前节点是组件开头的两个依据：
①链表节点存在于子集nums中，且当前节点是链表头节点，组件数 1
②链表节点存在于子集nums中，且前一个节点不存在与自己中，组件数 1，为了确定前一个节点是否在子集中，我们需要使用一个布尔类型来记录。
遍历完之后返回记录下的组件数即可。
提交代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public int numComponents(ListNode head, int[] nums) {
Set<Integer> set = new HashSet<>(); //创建不可重复集合Set
int total = 0; //total记录组件数量
for(int num : nums){ //遍历子串数组
set.add(num); //元素存入集合中
}
boolean flag = false; //设置标记，判定头节点以及前一个结点是否不在子串中
while(head != null){ //遍历链表
if(set.contains(head.val)){ //节点在子串中存在
if(flag == false){ //为头节点或前一个结点不在子串中
flag = true; //flag设置为true
total; //组件 1
}
}
else{ //不为组件开头元素
flag = false; //设置flag为false
}
head = head.next; //继续i向后遍历数组
}
return total; //返回记录的组件数量
}
}提交结果：
⚽
求关注⚽ 作者
