小鲸鱼的梦境
0%

『LeetCode』817 链表组件

发表于 分类于 Valine：
本文字数： 3.9k 阅读时长 ≈ 4 分钟

题目

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 <= 10^{4}
  • 0 <= Node.val < n
  • Node.val 中所有值 不同
  • 1 <= nums.length <= n
  • 0 <= nums[i] < n
  • nums 中所有值 不同

标签

数组, 哈希表, 链表

题解

【链表组件】简单模拟

模拟

题目要求找出值在 nums 数组中的连续结点的段数，为了方便快速查询，将 nums 放到哈希表中，然后遍历链表查询即可

1
2
3
4
5
6
7
8
9
10
11
12
13
# Code language: Python
class Solution:
    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:
        s = set(nums)
        cur, cnt = 0, 0
        while head:
            if head.val in s:
                cur += 1
            else:
                cnt += cur != 0
                cur = 0
            head = head.next
        return cnt + (cur != 0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Code language: Java
class Solution {
    public int numComponents(ListNode head, int[] nums) {
        Set<Integer> s = new HashSet<>();
        for (int a: nums) s.add(a);
        int ans = 0, cnt = 0;
        for (ListNode p = head; p != null; p = p.next) {
            if (s.contains(p.val)) {
                ++cnt;
            } else {
                ans += cnt > 0 ? 1 : 0;
                cnt = 0;
            }
        }
        return ans + (cnt > 0 ? 1 : 0);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Code language: C++
class Solution {
public:
    int numComponents(ListNode* head, vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end());
        int ans = 0, cnt = 0;
        for (auto p = head; p != nullptr; p = p->next) {
            if (s.find(p->val) == s.end()) {
                ans += cnt > 0 ? 1 : 0;
                cnt = 0;
            } else {
                ++cnt;
            }
        }
        return ans + (cnt > 0 ? 1 : 0);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* Code language: JavaScript */
/**
 * @param {ListNode} head
 * @param {number[]} nums
 * @return {number}
 */
var numComponents = function(head, nums) {
    const s = new Set(nums);
    let ans = 0, cnt = 0;
    while (head) {
        if (s.has(head.val)) {
            ++cnt;
        } else {
            ans += cnt > 0 ? 1 : 0;
            cnt = 0;
        }
        head = head.next;
    }
    return ans + (cnt > 0 ? 1 : 0);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* Code language: Golang */
func numComponents(head *ListNode, nums []int) (ans int) {
    s := make(map[int]bool)
    for _, a := range nums {
        s[a] = true
    }
    for cnt := 0; head != nil; head = head.Next {
        if _, e := s[head.Val] ;e {
            if cnt == 0 {
                ans++
            }
            cnt++
        } else {
            cnt = 0
        }
    }
    return
}
  • 时间复杂度: \(O(n)\)
  • 空间复杂度: \(O(n)\)

其他方法

提交记录里面还有几份去年写的方法，都不是最优解

二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Code language: C++
class Solution {
public:
    int numComponents(ListNode* head, vector<int>& nums) {
        ListNode* p = head;
        int ans = 0;
        sort(nums.begin(), nums.end());
        bool cont = false;
        while (p != nullptr) {
            bool tag = binary_search(nums.begin(), nums.end(), p->val);
            if (cont && !tag) {
                ++ans;
                cont = false;
            }
            else if (!cont && tag)
                cont = true;
            p = p->next;
        }
        if (cont) ++ans;
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Code language: Python
class Solution:
    def numComponents(self, head: ListNode, nums: List[int]) -> int:
        ans = 0
        cont = False
        nums.sort()
        n = len(nums)
        while head:
            tag = False
            s = bisect.bisect_left(nums, head.val)
            if s != n and nums[s] == head.val:
                tag = True
            if cont and not tag:
                ans += 1
                cont = False
            elif not cont and tag:
                cont = True
            head = head.next
        if cont:
            ans += 1
        return ans
  • 时间复杂度: \(O(n \log n)\)
  • 空间复杂度: \(O(\log n)\)

直接搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// Code language: C++
class Solution {
public:
    int numComponents(ListNode* head, vector<int>& nums) {
        ListNode* p = head;
        int ans = 0;
        bool cont = false;
        while (p != nullptr) {
            bool tag = false;
            for (auto num : nums) {
                if (num == p->val) {
                    tag = true;
                    break;
                }
            }
            if (cont && !tag) {
                ++ans;
                cont = false;
            }
            else if (!cont && tag)
                cont = true;
            p = p->next;
        }
        if (cont) ++ans;
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Code language: Python
class Solution:
    def numComponents(self, head: ListNode, nums: List[int]) -> int:
        ans = 0
        cont = False
        while head:
            tag = False
            for num in nums:
                if num == head.val:
                    tag = True
                    break
            if cont and not tag:
                ans += 1
                cont = False
            elif not cont and tag:
                cont = True
            head = head.next
        if cont:
            ans += 1
        return ans
  • 时间复杂度: \(O(n^2)\)
  • 空间复杂度: \(O(1)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往 我的博客 或 Algorithm - Github 查看更多题解

--- ♥ end ♥ ---

欢迎关注我呀~