Skip to content

Latest commit

 

History

History

0817.Linked List Components

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 
 
 

English Version

题目描述

给定链表头结点 head,该链表上的每个结点都有一个 唯一的整型值

同时给定列表 G,该列表是上述链表中整型值的一个子集。

返回列表 G 中组件的个数,这里对组件的定义为:链表中一段最长连续结点的值(该值必须在列表 G 中)构成的集合。

 

示例 1:

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

示例 2:

输入: 
head: 0->1->2->3->4
G = [0, 3, 1, 4]
输出: 2
解释: 
链表中,0 和 1 是相连接的,3 和 4 是相连接的,所以 [0, 1] 和 [3, 4] 是两个组件,故返回 2。

 

提示:

  • 如果 N 是给定链表 head 的长度,1 <= N <= 10000
  • 链表中每个结点的值所在范围为 [0, N - 1]
  • 1 <= G.length <= 10000
  • G 是链表中所有结点的值的一个子集.

解法

定义 pre 表示是否可加 1,初始为 true。

遍历链表各个结点:

  • 若当前结点值在 nums 中,并且当前为可加 1 的状态,则 res++,并且将 pre 状态置为 false;
  • 若当前结点值不在 nums 中,则将 pre 置为 true,表示可加 1。

最后返回 res 即可。

Python3

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: ListNode, nums: List[int]) -> int:
        s = set(nums)
        res, pre = 0, True
        while head:
            if head.val in s:
                if pre:
                    res += 1
                    pre = False
            else:
                pre = True
            head = head.next
        return res

Java

/**
 * 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> s = new HashSet<>();
        for (int num : nums) {
            s.add(num);
        }
        int res = 0;
        boolean pre = true;
        while (head != null) {
            if (s.contains(head.val)) {
                if (pre) {
                    ++res;
                    pre = false;
                }
            } else {
                pre = true;
            }
            head = head.next;
        }
        return res;
    }
}

...