817. Linked List Components

Oct 07, 2020

今天的题目是817. Linked List Components

非常简单的一道题。。。为什么会出现在Medium中呢?

G数组转成一个unordered_set就可以快速的判断某个元素是否在G中了,用一个flag来标识前一个元素是否在G中,初始值为false,然后遍历链表:

  1. 当前元素在G时,flag = true
  2. 当前元素不在G时,如果flag == true,计数就加一,然后flag = false

遍历完链表后,再判断一次flag是否为真,如果是,则计数加一。

代码如下:

int numComponents(ListNode* head, vector<int>& G) {
	unordered_set<int> iset(G.begin(), G.end());
	int c = 0;
	bool flag = false;
	while (head)
	{
		if (iset.count(head->val) != 0) {
			flag = true;
		} else {
			c += flag;
			flag = false;
		}
		    head = head->next;
	}
	c += flag;
	return c;
}
  • 时间复杂度为:O(n+m)
  • 空间复杂度为:O(m)
  • n为链表大小,mG的大小

当然如果不用unordered_set来做也是可以的,因为题目中限制了链表长度和值的范围,而G中元素都是链表中的元素,所以我们可以用一个长度为 10000 的数组来代替unordered_set

代码如下:

int numComponents(ListNode* head, vector<int>& G) {
    // unordered_set<int> iset(G.begin(), G.end());
    vector<bool> iset(10000, false);
    for(int v: G) iset[v] = true;

    int c = 0;
    bool flag = false;
    while (head)
    {
        if (iset[head->val]) {
            flag = true;
        } else {
            c += flag;
            flag = false;
        }
        head = head->next;
    }
    c += flag;
    return c;
}
  • 时间复杂度为:O(n+m)
  • 空间复杂度为:O(1)
  • n为链表大小,mG的大小
LeetCodeLinked ListLeetCode

889. Construct Binary Tree from Preorder and Postorder Traversal

1344. Angle Between Hands of a Clock

comments powered by Disqus