Leetcode【817、876、1019】
Leetcode【817、876、1019】
echobingo
发布于 2019-10-14 18:03:32
发布于 2019-10-14 18:03:32
解题思路：
这道题是给一个链表和数组，数组是链表元素的子集。求数组中联通数量。
直接将数组转化为集合，然后遍历一次链表。令 ans = 0，flag = True：
- 如果 flag = True 并且链表元素在集合中，则 ans 加 1，同时设置标记 flag = False；
- 如果链表元素不在集合中时，设置 flag = True；
- 最后 ans 就是答案。
时间复杂度和空间复杂度均为 O(n)。
Python3 实现：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def numComponents(self, head: ListNode, G: List[int]) -> int:
ans, flag = 0, True
G = set(G)
cur = head
while cur:
if flag and cur.val in G: # 找到一个新的联通量
ans += 1
flag = False
elif cur.val not in G:
flag = True
cur = cur.next
return ans问题描述：【Two Pointers】876. Middle of the Linked List
解题思路：
求链表中间的结点，如果链表长度为偶数，返回中间的第二个结点。
很明显，使用快慢指针（1步和2步），遍历链表一次就可以找到。
Python3 实现：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow问题描述：【Stack】1019. Next Greater Node In Linked List
解题思路：
这道题是给一个链表，返回一个列表，列表的对应位置是链表中当前结点的下一个更大的结点的值。
这道题和 Leetcode 【Stack】739. Daily Temperatures 思路相同。都是维护一个递减栈即可。只不过 Leetcode 739 需要求温度间隔，这道题求下一个更大结点的值。
因为是链表，所以栈中需要保存结点的值和对应索引。时间复杂度和空间复杂度均为 O(n)。
Python3 实现：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def nextLargerNodes(self, head: ListNode) -> List[int]:
ans, stack = [], []
cur = head
size = 0 # 链表元素索引
while cur:
ans.append(0) # 每次增加一个位置，这样只需要一次链表循环
while stack and stack[-1][0] < cur.val:
tmp = stack.pop()
ans[tmp[1]] = cur.val
stack.append([cur.val, size]) # 判断完后入栈
size += 1
cur = cur.next
return ans本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019.10.11 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录