817. 链表组件

817. 链表组件

 
  LeetCode
  ,
  6 分钟 读完 (大约 853 个字)   0次访问

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

方法一：模拟

思路：遍历链表，由于一个组件在链表中对应一段极长的连续节点，因此如果当前的节点在数组nums中，且下一个节点不在数组nums中，则组件数加1。通过Arrays工具类的sort方法对nums数组排序，方便使用Arrays类的binarySearch方法查找遍历的节点在不在数组nums中，从而提高查找效率。

运行数据：执行用时：8 ms，内存消耗：42.2 MB

复杂度分析：

  • 时间复杂度：O(mlogn)， m表示链表head的节点数，n表示nums数组长度。
  • 空间复杂度：O(1)。
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
28
29
30
31
32
33
34
/**
 * 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; }
 * }
 */

// LeetCode指定调用方法 
public int numComponents(ListNode head, int[] nums) {

    int count = 0;
    boolean flag = false;
    Arrays.sort(nums);
    while (head != null) {
        int num = head.val;
        head = head.next;
        if (Arrays.binarySearch(nums, num) >= 0) {
            flag = true;
            continue;
        }
        if (flag) {
            flag = false;
            count++;
        }
    }
    if (flag) {
        count++;
    }
    return count;
}

方法二：hash

思路：由于1 <= n <= 10^4、0 <= nums[i] < n、nums 中所有值 不同，所以可以创建一个boolean组数作为哈希表，以nums元素的值作为哈希值将nums组数转存到哈希表中，从而将方法一中查找链表节点的时间复杂度从O(logn)提高到O(1)。以增加10^4次方的额外空间换取查找节点时间效率的提升，由于10^4是常数，空间复杂度仍为O(1)。

运行数据：执行用时：1 ms，内存消耗：41.3 MB

复杂度分析：

  • 时间复杂度：O(m)， m表示链表head的节点数。
  • 空间复杂度：O(1)。
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
28
29
30
31
32
33
34
35
36
37
/**
 * 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; }
 * }
 */

// LeetCode指定调用方法 
public int numComponents(ListNode head, int[] nums) {

    int count = 0;
    boolean flag = false;
    boolean[] hash = new boolean[10001];
    for (int n : nums) {
        hash[n] = true;
    }
    while (head != null) {
        int num = head.val;
        head = head.next;
        if (hash[num]) {
            flag = true;
            continue;
        }
        if (flag) {
            flag = false;
            count++;
        }
    }
    if (flag) {
        count++;
    }
    return count;
}

学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。

才疏学浅，若有错误或不当之处，可批评指正，还请见谅！

  , 

喜欢这篇文章？打赏一下作者吧

2. 两数相加
1945. 字符串转化后的各位数字之和
关注我
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×