顺序遍历，哈希集合，求解《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 中所有值 不同
答案
哈希集合
b 找到不在集合（包括初始位置）设为1
b 的下一个在集合的位置，可以作为新组件的开始位置
var numComponents = function(head, nums) {
const s = new Set(nums)
let b = 1, r = 0
while (head) {
if (s.has(head.val) === false) b = 1
else if (b === 1) {
r++
b = 0
}
head = head.next
}
return r
};function numComponents(head: ListNode | null, nums: number[]): number {
const s = new Set(nums)
let b = 1, r = 0
while (head) {
if (s.has(head.val) === false) b = 1
else if (b === 1) {
b = 0
r++
}
head = head.next
}
return r
};class Solution {
function numComponents($head, $nums) {
$b = 1;
$r = 0;
while ($head) {
if (in_array($head->val, $nums) === false) $b = 1;
elseif ($b === 1) {
$b = 0;
$r++;
}
$head = $head->next;
}
return $r;
}
}func numComponents(head *ListNode, nums []int) int {
s := map[int]struct{}{}
for _, num := range nums {
s[num] = struct{}{}
}
b, r := 1, 0
for head != nil {
if _, ok := s[head.Val]; ok == false {
b = 1
} else if b == 1 {
b, r = 0, r + 1
}
head = head.Next
}
return r
}func numComponents(head *ListNode, nums []int) int {
s, r := map[int]struct{}{}, 0
for _, num := range nums {
s[num] = struct{}{}
}
for b := 1; head != nil; head = head.Next {
if _, ok := s[head.Val]; ok == false {
b = 1
} else if b == 1 {
b, r = 0, r + 1
}
}
return r
}class Solution {
public int numComponents(ListNode head, int[] nums) {
Set<Integer> s = new HashSet<Integer>();
for (int num : nums) s.add(num);
int b = 1, r = 0;
while (head != null) {
if (s.contains(head.val) == false) b = 1;
else if (b == 1) {
b = 0;
r++;
}
head = head.next;
}
return r;
}
}public class Solution {
public int NumComponents(ListNode head, int[] nums) {
ISet<int> s = new HashSet<int>();
foreach (int num in nums) s.Add(num);
int b = 1, r = 0;
while (head != null) {
if (s.Contains(head.val) == false) b = 1;
else if (b == 1) {
b = 0;
r++;
}
head = head.next;
}
return r;
}
}typedef struct {
int key;
UT_hash_handle hh;
} HashItem;
int numComponents(struct ListNode* head, int* nums, int numsSize){
HashItem* h = NULL;
for (int i = 0; i < numsSize; i++) {
HashItem* pEntry = malloc(sizeof(HashItem));
pEntry->key = nums[i];
HASH_ADD_INT(h, key, pEntry);
}
int b = 1, r = 0;
while (head) {
HashItem* pEntry = NULL;
HASH_FIND_INT(h, &head->val, pEntry);
if (pEntry == NULL) b = 1;
else if (b == 1) {
b = 0;
r++;
}
head = head->next;
}
HashItem* cur, *tmp;
HASH_ITER(hh, h, cur, tmp) {
HASH_DEL(h, cur);
free(cur);
}
return r;
}class Solution {
public:
int numComponents(ListNode* head, vector<int>& nums) {
unordered_set<int> s;
for (int num : nums) s.emplace(num);
int b = 1, r = 0;
while (head) {
if (s.find(head->val) == s.end()) b = 1;
else if (b == 1) {
b = 0;
r++;
}
head = head->next;
}
return r;
}
};class Solution:
def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:
s, b, r = set(nums), 1, 0
while head:
if head.val not in s: b = 1
elif b == 1: b, r = 0, r + 1
head = head.next
return r