817. 链表组件:哈希表+flag

简介: 这是 力扣上的 817. 链表组件,难度为 中等。

题目描述

这是 力扣上的 817. 链表组件,难度为 中等

image.png

题目分析

做本题需要擦亮眼睛,题目给出了一个链表,里面的每一个节点对应的数字都是唯一的,还给出了一个 nums 数组,内容是链表的子集,那么也说明 nums 中的数据每一个数字也是唯一的

要求我们找到能在链表中连续的数字,且在 nums 数组中出现的数字,有几段?

思考:

如果不仔细看题,看到示例,我们是否会认为本题是要求我们找到符合要求的升序序列呢?不知道 xdm 第一次做这个题的时候,是否会被自己的潜意识给误导呢?

image.png

这也是心理学上大脑会对看到内容预测事情发展的走向,然后播放给我们看,最终导致我们还去处理数据排序的问题,其实完全没有必要哦


再次仔细看题,我们知道,题目没有对我们有排序的要求,最终问题我们可以简化到在链表中找到连续的数字,且出现在 nums 中的数字,总共有几段

那么对于这种题,我们第一时间应该要想到使用哈希表就能很好的应对了,

使用哈希表记录 nums 中已经存在的数字,然后去遍历链表,我们如何来记录是一个连续的段(并不一定是升序哦)呢?

image.png

我们可以引入一个标识,flag(初始化为 false),表示当前是否处于连续段中,且数字是存在与 nums 中

简单来说,就是

  1. flag 从 false 跳变到 true 的时候,那么这就是一个新段的开始,
  2. 如果 flag 是从 true 变成了 false ,那么这是一个段的结束,

如果 flag 从 true 到 true,那么仍然在段中,同理,flag 从 false 到 false 那就是在符合要求的段之外

  • 遍历链表过程中,如果发现节点的数字是在 nums 中,且 flag 为 false 的时候,那么我们在结果处 +1,并将 flag 置为 true
  • 如果当前遍历的节点数字不在 nums 中,那就将 flag 置为 false 即可

遍历完毕链表之后,直接返回结果

接下来,咱们就可以来实现编码了,咱们这次使用 golang 的方式来进行实现

Golang 的实现方式:

  • Golang 中 hash 表可以使用 map,咱们的键可以是 int,值可以任意定义
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func numComponents(head *ListNode, nums []int) (ans int) {
    help := make(map[int]struct{}, len(nums))
    for _, v := range nums {
        help[v] = struct{}{}
    }
    flag := false
    res := 0
    for head != nil{
    // 数据存在与 nums 中, 且 flag 为 false
        if _,ok := help[head.Val]; ok {
            if !flag {
                res++
                flag = true
            }
        }else{
            flag = false
        }
        head = head.Next
    }
    return res
}

这种实现方式,咱们的时间复杂度是 O(n),n 是链表的节点个数,咱们遍历了一遍

空间复杂度是 O(m),m 是 nums 数组的长度,咱们开辟了一个哈希表来存储 nums 中的数据

今天就到这里,若有偏差,还请斧正

欢迎点赞,关注,收藏

朋友们,你的支持和鼓励,是我坚持分享,提高质量的动力

image.png

好了,本次就到这里

技术是开放的,我们的心态,更应是开放的。拥抱变化,向阳而生,努力向前行。

我是阿兵云原生,欢迎点赞关注收藏,下次见~


相关文章
|
2月前
|
存储 缓存
【每日一题Day336】LC146最近最少使用缓存 | 哈希表+链表
【每日一题Day336】LC146最近最少使用缓存 | 哈希表+链表
22 0
|
4月前
【Leetcode -817.链表组件 -1019.链表中的下一个更大节点】
【Leetcode -817.链表组件 -1019.链表中的下一个更大节点】
21 0
|
2月前
|
索引
【每日一题Day281】LC142链表 Ⅱ| 快慢指针 哈希表
【每日一题Day281】LC142链表 Ⅱ| 快慢指针 哈希表
10 0
|
2月前
|
存储 索引
【每日一题Day280】LC141环形链表 | 快慢指针 哈希表
【每日一题Day280】LC141环形链表 | 快慢指针 哈希表
14 0
|
2月前
【每日一题Day234】LC1171从链表中删去总和值为零的连续节点 | 链表模拟 哈希表+前缀和
【每日一题Day234】LC1171从链表中删去总和值为零的连续节点 | 链表模拟 哈希表+前缀和
14 0
|
9月前
LeetCode剑指 Offer 35—复杂链表的复制(哈希表/递归)
LeetCode剑指 Offer 35—复杂链表的复制(哈希表/递归)
复杂链表的复制(剑指offer35 力扣138)java哈希表/原地拼接
请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。
|
索引
力扣142 - 环形链表||【二重双指针+哈希表】
灵活运用双指针,带您一探环形链表的奥秘
72 0
力扣142 - 环形链表||【二重双指针+哈希表】
|
存储 算法 C++
STL设计之链表设计,分块分组件分析,迭代器设计思路
STL设计之链表设计,分块分组件分析,迭代器设计思路
STL设计之链表设计,分块分组件分析,迭代器设计思路
|
存储 算法 Java
「日更刷题」第一周,链表和哈希表(三)
「日更刷题」第一周,链表和哈希表
49 0