LeetCode 817. Linked List Compon

问题描述

给定一个链表的头指针 head，其中链表各节点值为互不相同的整数。同时给定一个列表 G，其值为链表所有值的子集。

要求返回 G 中连接组件的个数。如果 G 中两个元素顺序的出现在链表中，即它们是连接的，则认为是它们属于一个连接组件。

栗 1：

输入: 
head: 0->1->2->3
G = [0, 1, 3]

输出：2

解释：[0, 1] 是连接的组件，[3] 是单独的，也算一个组件。

栗 2：

输入：
head: 0->1->2->3->4
G = [0, 3, 1, 4]

输出：2

解释：[0, 1] 是连接的，[3, 4] 也是连接的。

注意：

1. 假设 N 为链表长度，1 <= N <= 10000。
2. 链表每个节点的值在 [0, N - 1] 范围内。
3. 1 <= G.length <= 10000。
4. G 是链表所有节点值的子集。

想看英文描述的戳这里。

解题思路

首先得明确什么是连接组件？其实题目描述的还不完整。

根据测试结果，我的理解如下：

1. 如果有 x 个数，它们能按照给定的链表顺序串起来，即为一个组件，不论这 x 个数的顺序如何。
2. 单个未能串起来的数，也算一个组件。即 G 中任何数与其都没有连接关系。

举个特殊的栗子：

输入：
head: 0->1->2->3->4
G = [0, 3, 1, 4, 2]

输出：1

解释：[0, 1, 2, 3, 4] 是一个连接组件，因为 G 中的值可以按照 [0, 1, 2, 3, 4] 是顺序串起来。

我的解法

我的方法不够简单，也算一种思路。

要想找到 G 中能够串起来的数字，就需要知道每个数是否存在前节点或者后节点能将其串起来，且在 G 中存在。其前后节点根据链表可以得知。

• 如果存在前节点，那么继续寻找是否有点与该前节点相连，即该前节点的前节点是否存在。一直重复该步骤，直至不存在前节点，则视为一个组件。
• 如果存在后节点，那么继续寻找是否有点与该后节点相连，即该后节点的后节点是否存在。一直重复该步骤，直至不存在后节点，则视为一个组件。
• 如果前后节点均不存在，则说明没有可以与其连接的数，此时视为一个组件。

步骤如下：

1. 记录链表中每个节点的前后节点值，注意前/后节点不存在时的处理
2. 遍历 G 中元素
   • 如果当前值在链表中存在前节点 pre，则继续往前找 pre 的 pre
   • 如果当前值在链表中存在后节点 next，则继续往后找 next 的 next
   • 若元素被访问过，则标记为已处理，防止重复处理。因为前后节点在 G 中不是顺序的。

对于栗 3 来说，记录每个节点的前后节点值结果如下。其中，前后节点值以数组存储，第 1 个元素为前节点，第 2 个元素为后节点，若不存在，记为 -1。

{
  0 => [ -1, 1 ],
  1 => [ 0, 2 ],
  2 => [ 1, 3 ],
  3 => [ 2, 4 ],
  4 => [ 3, -1 ] 
}

若遍历 G = [0, 4, 3, 1]，次序如下：

1. 访问 0，其后节点为 1，在 G 中存在，则继续找 1 的后节点。标记 0 已处理。
2. 访问 1，其后节点为 2，在 G 中不存在，则遍历下一个元素 4。这时找到了一个连接组件 [0, 1]。标记 1 已处理。
3. 访问 4，其前节点为 3，在 G 中存在，则继续找 3 的前节点。标记 4 已处理。
4. 访问 3，其前节点为 2，在 G 中不存在。此时找到一个连接组件 [3, 4]。标记 3 已处理。
5. 此时访问 1， 由于 1 前面已经处理过，因此遍历完成。

则总共有 2 个组件。

代码如下：

var numComponents = function(head, G) {
    if (head && G && G.length > 0) {
        let map = new Map()

        // 记录节点前后的值，若无则为 -1
        let pre = -1
        while (head) {
            let next = head.next ? head.next.val : -1
            map.set(head.val, [pre, next])

            pre = head.val
            head = head.next
        }

        let num = 0
        let i = 0
        let flagMap = new Map()
        while (i < G.length) {

            const value = G[i]

            if (!flagMap.get(value)) {
                // 标记已处理
                flagMap.set(value, true)

                // 不是子集
                if (!map.has(value)) {
                    return 0
                }

                num += 1

                const list = map.get(value)
                let pre = list[0]
                let next = list[1]

                // 存在 pre，一直往前找 pre
                while (pre !== -1 && G.includes(pre) && !flagMap.has(pre)) {
                    // 标记已处理
                    flagMap.set(pre, true)

                    // 继续找 pre 的 pre
                    const list = map.get(pre)

                    pre = list[0]
                }

                // 存在 next，一直往后找 next
                while (next !== -1 && G.includes(next) && !flagMap.has(next)) {
                    // 标记已处理
                    flagMap.set(next, true)

                    const list = map.get(next)

                    next = list[1]
                }
            }

            i += 1
        }

        return num
    }

    return 0
};

简单解法

这种方式很简洁，采用逆向思维。上面我们采用的是遍历 G，导致要计算 G 中元素的前后节点是否存在，比较繁琐。

而换个角度来思考，链表本来就是已经连接好的，只需要判断其连接的值在 G 中是否存在即可。

因此顺序遍历链表，如果当前节点值在 G 中存在，且其 next 节点值在 G 中不存在，则认为断开了连接，形成一个组件。

代码如下：

var numComponents = function(head, G) {
    if (head && G && G.length > 0) {
        let nums = 0

        // 放入 set
        const set = new Set()
        G.forEach(element => {
            set.add(element)
        });

        // 遍历链表，若当前节点在 G 中，且下一个节点不在 G 中，则认为断开了链接，算一个 component。
        while (head) {

            if (set.has(head.val) && (head.next == null || !set.has(head.next.val))) {
                nums += 1
            }

            head = head.next
        }

        return nums
    }

    return 0
}