0817. Linked List Components

817. Linked List Components #

题目 #

We are given head, the head node of a linked list containing unique integer values.

We are also given the list G, a subset of the values in the linked list.

Return the number of connected components in G, where two values are connected if they appear consecutively in the linked list.

Example 1:


Input: 
head: 0->1->2->3
G = [0, 1, 3]
Output: 2
Explanation: 
0 and 1 are connected, so [0, 1] and [3] are the two connected components.

Example 2:


Input: 
head: 0->1->2->3->4
G = [0, 3, 1, 4]
Output: 2
Explanation: 
0 and 1 are connected, 3 and 4 are connected, so [0, 1] and [3, 4] are the two connected components.

Note:

  • If N is the length of the linked list given by head, 1 <= N <= 10000.
  • The value of each node in the linked list will be in the range [0, N - 1].
  • 1 <= G.length <= 10000.
  • G is a subset of all values in the linked list.

题目大意 #

这道题题目的意思描述的不是很明白,我提交了几次 WA 以后才悟懂题意。

这道题的意思是,在 G 中能组成多少组子链表,这些子链表的要求是能在原链表中是有序的。

解题思路 #

这个问题再抽象一下就成为这样:在原链表中去掉 G 中不存在的数,会被切断成几段链表。例如,将原链表中 G 中存在的数标为 0,不存在的数标为 1 。原链表标识为 0-0-0-1-0-1-1-0-0-1-0-1,那么这样原链表被断成了 4 段。只要在链表中找 0-1 组合就可以认为是一段,因为这里必定会有一段生成。

考虑末尾的情况,0-1,1-0,0-0,1-1,这 4 种情况的特征都是,末尾一位只要是 0,都会新产生一段。所以链表末尾再单独判断一次,是 0 就再加一。

代码 #


package leetcode

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func numComponents(head *ListNode, G []int) int {
	if head.Next == nil {
		return 1
	}
	gMap := toMap(G)
	count := 0
	cur := head

	for cur != nil {
		if _, ok := gMap[cur.Val]; ok {
			if cur.Next == nil { // 末尾存在,直接加一
				count++
			} else {
				if _, ok = gMap[cur.Next.Val]; !ok {
					count++
				}
			}
		}
		cur = cur.Next
	}
	return count
}

func toMap(G []int) map[int]int {
	GMap := make(map[int]int, 0)
	for _, value := range G {
		GMap[value] = 0
	}
	return GMap
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者