专栏首页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【24、109、328、455、725】

    这道题是给一个链表,相邻结点数值两两进行交换,要求不修改结点值且只能操作链表本身。

    echobingo
  • Leetcode【61、82、83、142、143、1171】

    1、先计算链表长度 size,k = k % size,如果 k % size == 0,则不用移动,直接返回 head; 2、否则,需要将前 size - ...

    echobingo
  • Leetcode【86、92、148、206】

    这道题是给一个链表和整数 x,将小于 x 的数按位置顺序放在链表左侧,大于等于 x 的按位置顺序放在右侧。

    echobingo
  • 根据大小写字母单列拆分

      昨天同事遇到了这个问题,就帮忙看了一下,顺便温习一下好些时候因为LINQ而没用的SQL函数,喜新厌旧,这样不对呀~

    Isaac Zhang
  • CV学习笔记(五):ROI与泛洪填充

    ROI(region of interest),中文翻译过来就是感兴趣区域,在机器视觉、图像处理中,从被处理的图像以方框、圆、椭圆、不规则多边形等方式勾勒出需要...

    云时之间
  • CV学习笔记(五):ROI与泛洪填充

    ROI(region of interest),中文翻译过来就是感兴趣区域,在机器视觉、图像处理中,从被处理的图像以方框、圆、椭圆、不规则多边形等方式勾勒出需要...

    云时之间
  • Windows10 下利用Hyper-V安装CentOS系统

    lin_zone
  • 关于文件的压缩与解压

    1 #coding:utf-8 2 import tarfile 3 import zipfile 4 import rarfile 5 import...

    Gxjun
  • 福利来一枚:虚拟云服务器

    逆天博客所作的服务器还有1天就过期了,发挥点余热,送个没有部署过的同志练练手(本来准备还有7天的时候放出来的,忘记。。。) ? 说来惭愧,博客开了一年了,没怎么...

    逸鹏
  • 聊聊canal-go的SimpleCanalConnector

    canal-go-v1.0.7/client/simple_canal_connector.go

    codecraft

扫码关注云+社区

领取腾讯云代金券