专栏首页Bingo的深度学习杂货店Leetcode【817、876、1019】

Leetcode【817、876、1019】

解题思路:

这道题是给一个链表和数组,数组是链表元素的子集。求数组中联通数量。

直接将数组转化为集合,然后遍历一次链表。令 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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 分类刷题 —— Linked List

    最近有朋友问我怎么没有更新文章了,因为最近有空的时候都在刷 LeetCode,零零星星刷了快 2 个月了,也累积了不少题目了,所以最近打算把做的几百道题归类,总...

    一缕殇流化隐半边冰霜
  • 链表问题(二)-LeetCode 147、876、234、817、92(链表的中点,快慢指针)

    首先判断两个相邻节点的大小,如果head->val > head->next->val,则需要将head->next->val插入到从dummy节点开始遍历第一...

    算法工程师之路
  • 2020-11-03:手写代码:链表如何快速找到中间节点?

    2.输入链表头节点,奇数长度返回中点,偶数长度返回下中点 。这道题是leetcode上的第876道题,叫【链表的中间节点】。

    福大大架构师每日一题
  • Leetcode 817. Linked List Components

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • SUMO学习笔记(1)

    https://sumo.dlr.de/docs/Tutorials/Hello_World.html

    嘘、小点声
  • LeetCode 817. 链表组件

    返回列表 G 中组件的个数,这里对组件的定义为:链表中一段最长连续结点的值(该值必须在列表 G 中)构成的集合。

    Michael阿明
  • 快慢指针巧解链表题目(二)

    输入:[1,2,3,4,5] 输出:此列表中的节点 3思路分析:要找到链表的中间节点,可以定义两个指针,一个是慢指针slow,另一个是快指针fast。初始,慢指...

    五分钟学算法
  • Leetcode 876. Middle of the Linked List

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • Leetcode-Easy 876. Middle of the Linked List

    结题思路主要是通过快慢指针来找到中间节点:快指针的移动速度是慢指针移动速度的2倍,因此当快指针到达链表尾时,慢指针到达中点。

    致Great
  • Golang Leetcode 876. Middle of the Linked List.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/arti...

    anakinsun
  • Leetcode 1019. Next Greater Node In Linked List

    **解析:**Version 1,这个题跟Leetcode 503. Next Greater Element II非常相似,只不过是把数组换成了链表,参考ht...

    Tyan
  • 算法笔记学习-链表

    灵活使用递归。构造递归条件,使用递归可以巧妙的解题。不过需要注意有些题目不能使用递归,因为递归深度太深会导致超时和栈溢出。

    买唯送忧
  • 链表问题、单调栈-LeetCode 430、725、168、1290、215、1019、503(递减型单调栈)

    您将获得一个双向链表,除了下一个和前一个指针之外,它还有一个子指针,可能指向单独的双向链表。这些子列表可能有一个或多个自己的子项,依此类推,生成多级数据结构,如...

    算法工程师之路
  • 常见编程模式之快慢指针

    快慢指针方法,又称为龟兔赛跑算法,其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。这种方法对于处理「环形」链表或数组非常有用。以链表为例,...

    口仆
  • 数据结构笔记(一):数组、链表

    数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。

    free赖权华
  • LeetCode 876. 链表的中间结点(快慢指针)

    Michael阿明
  • 每日两题 T3

    遍历数组的同时,将元素放入数组,然后取出数组中间元素,但是会有内存额外开销,时间复杂度

    合一大师
  • 杭电OJ刷题指南

    说起来刷题,很多大牛都会推荐LeetCode或者牛客网,这两个网站是刷题的好网站。但对新手来说,有一点难度,新手建议先去杭电OJ刷题,这里的题目难度不大,如果你...

    Jasonangel
  • java加密解密

    landv

扫码关注云+社区

领取腾讯云代金券