刷题打卡，第 二十九 天
题目一、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; //返回记录的组件数量 } }
提交结果：
⚽求关注⚽ 作者🥇 .29. 🥇 的✔博客主页✔
⚽来刷题⚽ 记录每日LeetCode✔刷题专栏✔
您的点赞，收藏以及关注是对作者最大的鼓励喔 ~~
