LeetCode_哈希表_中等_817.链表组件

川长思鸟来 2023-10-07 20:14 8阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

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

**示例 1：**

![在这里插入图片描述][4daf45f2958f47e9b65973a41e347433.png]

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

**示例 2：**

![在这里插入图片描述][6203643df88d4137b9b6a79dd80e3abd.png]

输入: 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 中所有值 不同

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/linked-list-components

## 2.思路 ##

（1）哈希表  
本题要计算数组 nums 中组件的个数，并且由组件的定义可知，我们只需计算每个组件的起始位置的个数即可，具体步骤如下：  
① 用变量 cnt 记录数组 nums 中组件的个数，其初始值为 0；用 hashMap 保存数组 nums 中的整数（此处也可以使用 hashSet）；

② 用布尔类型的变量 flag 标记是否发现一个新组件，其初始值为 false；

③ 遍历链表，对于每一个结点值，做出以下判断：  
1）当前结点值在数组 nums 中：  
如果 flag = fasle，则表明当前还未发现一个新组件，故**将当前结点作为新组件的第一个结点**，同时置 flag = false，cnt++；  
如果 flag = true，则表明当前结点已经处于之前发现的一个组件中，无需其它操作；  
2）当前结点值不在数组 nums 中，此时没有发现新组件，置 flag = false；

④ 遍历结束后，返回 cnt 即可。

## 3.代码实现（Java） ##

//思路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) {
        
            if (head.next == null) {
        
                return 1;
            }
            // cnt 记录数组 nums 中组件的个数
            int cnt = 0;
            Map<Integer, Integer> hashMap = new HashMap<>();
            for (int num : nums) {
        
                hashMap.put(num, 1);
            }
            // flag 标记是否发现一个新组件
            boolean flag = false;
            while (head != null) {
        
                if (hashMap.containsKey(head.val)) {
        
                    /*
                        当前结点值在数组 nums 中
                        flag = fasle 表明还未发现一个新组件，故将当前结点作为新组件的第一个结点
                        flag = true 表明当前结点处于之前发现的一个组件中，无需其它操作
                    */
                    if (!flag) {
        
                        flag = true;
                        //组件数加一
                        cnt++;
                    }
                } else {
        
                    //当前结点值不在数组 nums 中，此时没有发现新组件
                    flag = false;
                }
                head = head.next;
            }
            return cnt;
        }
    }

[4daf45f2958f47e9b65973a41e347433.png]: https://img-blog.csdnimg.cn/4daf45f2958f47e9b65973a41e347433.png
[6203643df88d4137b9b6a79dd80e3abd.png]: https://img-blog.csdnimg.cn/6203643df88d4137b9b6a79dd80e3abd.png