Java C++题解leetcode817链表组件示例

下面是Java C++题解leetcode817链表组件的完整攻略:

题目描述

给定链表头结点 head,该链表上的每个结点都有一个唯一的整型值。

同时给定列表 G,该列表是上述链表中整型值的一个子集。

返回列表 G 中组件的个数,这里的组件定义为:链表中一段最长连续节点的值(即链表的子段)在列表 G 中出现次数与该段中节点数目相同。(例如,如果组件中的节点数目为 2,且其中的值恰好为 G 中的两个值,这样的组件是合法的)

示例 1:

输入: 
head: 0->1->2->3
G = [0, 1, 3]
输出: 2
解释: 
链表中,0 和 1 是相连接的,且 G 中有它们都在链表中出现过。
同时,3 不在链表 G 中,所以不是组件。

示例 2:

输入: 
head: 0->1->2->3->4
G = [0, 3, 1, 4]
输出: 2
解释: 
链表中,0 和 1 是相连接的,3 和 4 是相连接的,且 G 中有它们都在链表中出现过。
注意: 

如果 N 是给定链表 head 的长度,范围在 [1, 10000]。
链表中每个节点的值范围在 [0, N - 1]。
1 <= G.length <= 10000
G 是链表中所有结点的值的一个子集。

## 解题思路

这道题让我们求链表 G 组件的个数,那么我们先遍历链表,用 HashMap 把链表中的值添加进去,然后再遍历一次链表,分割链表,找到组件的个数。

HashMap 的 key 存储链表中的值,value 值为 true,代表它在链表中存在。

对于链表的遍历,我们可以通过设置一个变量 `previous`,用来判断当前的节点和前一个节点是否都在集合 G 中,如果是,那么它们是同一组件的一部分,继续遍历,直到不在集合 G 中,说明已经遍历到一个组件的结束位置,计数器加 1 即可。

## 代码实现

我们可以分为两步来分别实现算法:

1. 遍历链表,用 HashMap 存储链表中的值;
2. 遍历链表,分割链表,找到组件的个数。

下面是代码实现(Java 语言):

```java
public int numComponents(ListNode head, int[] G) {
    Set<Integer> set = new HashSet<>();
    for (int g : G) {
        set.add(g);
    }

    int count = 0;
    boolean previousExist = false;
    while (head != null) {
        if (set.contains(head.val)) {
            if (previousExist == false) {
                count++;
            }
            previousExist = true;
        } else {
            previousExist = false;
        }
        head = head.next;
    }

    return count;
}

下面是代码实现(C++ 语言):

class Solution {
public:
    int numComponents(ListNode* head, vector<int>& G) {
        set<int> values(G.begin(), G.end());
        int count = 0;
        bool previousExist = false;
        while (head != nullptr) {
            if (values.count(head->val)) {
                if (previousExist == false) {
                    count++;
                }
                previousExist = true;
            } else {
                previousExist = false;
            }
            head = head->next;
        }
        return count;
    }
};

示例说明

示例 1

输入:

head: 0->1->2->3
G = [0, 1, 3]

输出:

2

解释:

链表中,0 和 1 是相连接的,且 G 中有它们都在链表中出现过。同时,3 不在链表 G 中,所以不是组件。所以一共有 2 个组件。

示例 2

输入:

head: 0->1->2->3->4
G = [0, 3, 1, 4]

输出:

2

解释:

链表中,0 和 1 是相连接的,3 和 4 是相连接的,且 G 中有它们都在链表中出现过。所以一共有 2 个组件。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Java C++题解leetcode817链表组件示例 - Python技术站

(0)
上一篇 2023年6月27日
下一篇 2023年6月27日

相关文章

  • C#面试题总结——程序设计基础

    C#面试题总结——程序设计基础 C#是一种面向对象的编程语言,广泛应用于Windows平台的开发。在C#的面试中,程序设计基础是一个重要的考察点。本攻略将详细介绍C#面试题中常见的程序设计基础问题,包括两个示例说明。 常见问题 1. 什么是面向对象编程? 面向对象编程是一种编程范式,它将数据和操作数据的方法封装在一起,形成对象。对象可以相互交互,从而实现程序…

    other 2023年5月6日
    00
  • Java基础之不简单的数组

    Java基础之不简单的数组:完整攻略 1. 数组的定义 Java中的数组是一种数据结构,用于存储相同类型的数据。数组定义时需要指定数据类型和长度,数组长度不能被改变。 // 定义int类型长度为3的数组 int[] nums = new int[3]; // 定义String类型长度为2的数组 String[] names = new String[2]; …

    other 2023年6月25日
    00
  • 一个命令行(批处理)延迟执行命令的语法

    通过批处理命令行语法,我们可以延迟执行命令。以下是一些示例说明: 使用ping命令延迟执行(示例一) 要在批处理命令行中使用ping命令延迟执行命令,请使用以下语法: ping -n 6 127.0.0.1 >nul && [command] 此语法中,-n参数表示为ping命令提供延迟时间(以秒为单位)。在上述示例中,我们使用“6”作…

    other 2023年6月26日
    00
  • python 安装教程之Pycharm安装及配置字体主题,换行,自动更新

    下面是Python安装教程之Pycharm安装及配置字体主题、换行、自动更新的完整攻略: 安装PyCharm 首先,从PyCharm官网(https://www.jetbrains.com/pycharm/)下载详细版本。 下载完成后,双击安装包进行安装,根据提示进行操作。 配置字体主题 打开PyCharm,在菜单栏中选择“File” -> “Sett…

    other 2023年6月27日
    00
  • 夯基础之手撕javascript继承详解

    夯基础之手撕JavaScript继承详解 本文将介绍JavaScript中继承的几种实现方式,并通过手写代码的方式,从底层原理上详解每种实现方式的具体过程。 一、JavaScript中继承的实现方式 1. 原型链继承 通过将子类的原型指向父类实例来实现继承。 function Parent() {} function Child() {} Child.pro…

    other 2023年6月26日
    00
  • Vue加载中动画组件使用方法详解

    Vue加载中动画组件是一种可以用来增强用户交互体验的组件。这个组件一般是在数据加载的时候使用,可以让用户知道此时正在加载数据,不会让用户误以为程序崩溃或者卡住了。本篇攻略将详细讲解Vue加载中动画组件的使用方法。 1. 安装和引入 首先我们需要安装该组件。在命令行中输入: npm install vue-loading-overlay –save 成功之后…

    other 2023年6月25日
    00
  • PowerToys首个Win10预览版发布 重启的Windows工具集

    PowerToys首个Win10预览版发布 重启的Windows工具集 微软 PowerToys 是一组免费的 Windows 工具,可以增强 Windows 系统的使用体验,最近其首个 Win10 预览版也已经发布。本文将为大家介绍 PowerToys 的主要功能及使用方法。 功能介绍 PowerToys 有多项功能,如下: FancyZones 该工具可…

    other 2023年6月27日
    00
  • quartzcron表达式:立即开始每10分钟运行一次作业

    以下是关于“quartzcron表达式:立即开始每10分钟运行一次作业”的完整攻略,包含两个示例。 Quartz Cron表达式 Quartz Cron表达式是一种用于调度作业的时间表达。它可以指定作业在何时运行,例如每天的特定时间、每周的特定日期、每月的特定日期等。Quartz Cron表达式由6个字段组成,分别秒、分、时、日、月和周几。以下是Quartz…

    other 2023年5月9日
    00
合作推广
合作推广
分享本页
返回顶部