(剑指offer)链表中环的入口结点【哈希集合的使用】

news/2024/4/24 5:24:29/

给一个长度为n链表,若其中包含环,请找出该链表的环的入口结点,否则,返回null。

数据范围:

1≤n≤10000,
1<=结点值<=10000
1<=结点值<=10000
要求:空间复杂度
(1)
O(1),时间复杂度 O(n)
例如,输入{1,2},{3,4,5}时,对应的环形链表如下图所示:

可以看到环的入口结点的结点值为3,所以返回结点值为3的结点。
输入描述:
输入分为2段,第一段是入环前的链表部分,第二段是链表环的部分,后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表
返回值描述:
返回链表的环的入口结点即可,我们后台程序会打印这个结点对应的结点值;若没有,则返回对应编程语言的空结点即可。
示例1
输入:
{1,2},{3,4,5}
复制
返回值:
3
复制
说明:
返回环形链表入口结点,我们后台程序会打印该环形链表入口结点对应的结点值,即3
示例2
输入:
{1},{}
复制
返回值:
“null”
复制
说明:
没有环,返回对应编程语言的空结点,后台程序会打印"null"
示例3
输入:
{},{2}
复制
返回值:
2
复制
说明:
环的部分只有一个结点,所以返回该环形链表入口结点,后台程序打印该结点对应的结点值,即2


/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};
*/
class Solution {
public:ListNode* EntryNodeOfLoop(ListNode* pHead) {unordered_set<ListNode*>st;//哈希集合ListNode* res = pHead;while(res!=nullptr){if(st.count(res)){return res;}st.insert(res);res=res->next;}return nullptr;}
};

这一题的主要解法就是利用哈希集合不能插入已有的值的特点来实现。实际上这题也可以不用哈希集合来写,不过那个方法数学思维更多。简单来说就是快慢指针来实现。如果有环,最后慢指针一定可以追上快指针。不过想知道头节点是哪个就需要一定数学证明了


http://www.ppmy.cn/news/675086.html

相关文章

关于Long的前后端传参,精度丢失问题

若后端接受格式为 List<Long> 则前端传参时不能为 int型 需要改为 &#xff0c;加上双引号

【计算机视觉】最新综述:南洋理工和上海AI Lab提出基于Transformer的视觉分割综述

文章目录 一、导读二、摘要三、内容解读3.1 研究动机3.2 这篇综述的特色&#xff0c;以及与以往的Transformer综述有什么区别&#xff1f;3.3 Transformer-Based 分割和检测方法总结与对比3.4 相关研究领域的方法总结与对比3.5 不同方法的实验结果对比3.6 未来可以进行的方向 一…

java中对数据进行脱敏操作(证件号,手机号,移动电话,邮箱)

**敏感信息处理包括&#xff1a; /*要考虑到证件号是否为身份证号或者学生证&#xff0c;因为数字位数不同全部按身份证的方式托面&#xff0c;第三位至最后四位都进行脱敏操作*/1.证件号非空时第3位到第14位显示时以*号代替2.移动电话非空时第2位-第7位显示时以*号代替3.手机号…

手机号证件号正则

var myreg /^[1][3,4,5,7,8][0-9]{9}$/; myreg.test(this.input) 手机号正则 var reg /(^\d{15}$)|(^\d{18}$)|(^\d{17}(\d|X|x)$)/reg.test(str);

JAVA将证件号打星号

/*** 证件打星号(*)* * param id 身份证* return String*/public static String idAsterisk(String id) {try {//身份证不为空if (StringUtil.isNotEmpty(id) && id.length() > 18) {id id.replace(id.substring(6, 14), "********");}} catch (Exceptio…

证件类型与证件号码前端验证

身份证、回乡证、台胞证验证 // 证件类型、证件号码验证idNumberCheck(strType, strNum) {// 身份证 最后一位X需要大写var idCard /^(^\d{18}$|^\d{17}(\d|X))$///港澳通行证验证、回乡证var hgIdCrad /^[HM]{1}([0-9]{10}|[0-9]{8})$///台胞证验证var tbIdCrad /(^\d{8})…

姓名、手机号、证件号掩码

public static void main(String[] args) {String fullName "王五一一";String name StringUtils.left(fullName, 1);String s StringUtils.rightPad(name, StringUtils.length(fullName), "*");System.out.println(s);String idno "110110202102…

证件号通用脱敏、名称脱敏

证件号通用脱敏 function privacyCardNo (val) {if (!val || typeof val ! string || val null || val undefined || val.length < 6) return vallet cnl val.length < 11 ? 4 : val.length > 15 ? 8 : 6let at Math.floor((val.length - cnl) / 2)let strStar…

什么是数字证书

整理了几篇关于CA证书的经典文章&#xff1a; 文章目录 一、数字证书二、数字证书原理的形象理解 一、数字证书 什么是数字证书 一文看懂HTTPS、证书机构&#xff08;CA&#xff09;、证书、数字签名、私钥、公钥 二、数字证书原理的形象理解 数字证书原理与自建CA证书 第一…

注册百家号一直都提示证件照片不清晰请重新上传

百家号身份认证不通过 注册百家号一直都提示证件照片不清晰 实验例子&#xff1a;我手机拍摄的时候为这个样子&#xff0c;紧挨着照片的边框 导致我验证了1个多小时&#xff0c;同时对百度的设计这个认证的畜生以及百度的总裁产生了技术方面的怀疑并对其进行了送社区送温暖般的…

身份证号的解读

我们的身份证号是一种特征号码的组合,有一定的规律,我们可以通过身份证号读取出部分的信息的。 特征信息号意思是:前6位是地址码,代码了省市区县,再8位是出生日期,再3位是顺序位,最后一位是校验码;其中顺序位奇数是男性,偶数是女性。 了解了特征意思,我们就比较容易…

身份证地址码对照表

公民身份号码是由17位数字码和1位校验码组成。排列顺序从左至右分别为&#xff1a;6位地址码&#xff0c;8位出生日期码&#xff0c;3位顺序码和1位校验码。 地址码&#xff08;身份证地址码对照表见下面附录&#xff09;和出生日期码很好理解&#xff0c;顺序码表示在同一地址…

中国身份证的格式

中国身份证现在格式是18码 首6码为地方码, 例如深圳市的地方码为440300 7~14码为出生日期码 15~18码为顺序编号, 用于同年同月同日同地方出生的人 第17码则为 GENDER码, 男单数, 女双数 例如, 深圳市, 男, 1980年1月1日出生(现年30岁已成年) 身份证号码可能会是以下这样子 4403…

如何从证件号中提取员工籍贯区号?

今天小西跟大家分享一下如何从证件号中提取员工籍贯区号&#xff1f; 1.首先我们打开excel文件&#xff0c;然后选中身份证号码所在单元格区域 ​ 2.接着鼠标点击【DIY工具箱】 ​ 3.然后点击【身份证】选择【提取区号】 ​ 4.鼠标点击【确定】 ​ 5.最后选择一个合适的保存位置…

12306中前端验证身份证件(及其他证件号)的方法

之前做一个门票预约系统的时候&#xff0c;需要用到身份证件的验证功能&#xff0c;第一个想法就是去12306网站上去参考验证方法&#xff0c;于是开始了第一步&#xff1a; 1.登录到12306网站->常用联系人->添加 试了一下&#xff0c;果然有证件号的验证&#xff0c;而且…

java身份证件号格式校验

/** * 判断身份证格式 * * param idNum 身份证号 * return 结果 / public static boolean isIdNum(String idNum) { // 中国公民身份证格式&#xff1a;长度为15或18位&#xff0c;最后一位可以为字母 Pattern idNumPattern Pattern.compile("(\d{14}[0-9a-zA-Z])|(\d{17…

【Android从零单排系列二十九】《Android布局介绍——LinerLayout》

目录 前言 一 LinerLayout基本介绍 二 LinerLayout使用方法 三 LinerLayout常见属性及方法 四 LinerLayout简单案例 五 总结 前言 小伙伴们&#xff0c;在前面的系列文章中&#xff0c;我们重点介绍了Android开发中用到的视图组件&#xff0c;从本文开始我们继续盘点And…

证件照制作小程序源码下载-超级实用工具

证件照制作是一款可以在线手机拍摄制作证件照的小程序 证件照制作是实用性较广的工具&#xff0c;行业规模大&#xff0c;发展前景好&#xff0c;使用人群广泛&#xff0c;从不过时&#xff0c;同时也是证件照行业线下到线上的变革&#xff0c;抓住时代的红利&#xff0c;错过这…

大陆二代居民身份证校验代码

感谢b站的穆哥学堂老师 19-验证特定格式(下)_哔哩哔哩_bilibili /** * 身份证号码最后一位的取值数组 */ public static final String[] CHECK_CODE_ARR new String[] {"1","0","X","9","8","7"…

手机号证件号等加密方案

思路&#xff1a;前端通过判断是否存在【】来替换掉加密内容&#xff0c;比如手机号实际为180【加密串】0000&#xff0c;页面显示为180****0000。 package util;import java.util.regex.Matcher; import java.util.regex.Pattern;/*** description: 对证件号等加密解密* auth…