记录力扣热题-100——从链表中找到刷题感觉

news/2024/4/29 11:17:57/文章来源:https://blog.csdn.net/m0_58847451/article/details/131560959

一. 🦁 前言

狮子此前已经很久没有碰过算法题了，对于之前好不容易攒起来的题感又没了…最近准备面试，又得重新将其捡起来。算法题是一种很奇妙的东西，如果刚开始刷很难找得到感觉，总得一步一步慢慢来，心急吃不到热豆腐，狮子建议如果刚开始刷题，先从简单的链表题开始刷，不断动笔演练解题过程，感觉慢慢就会好起来了，现在狮子来分享一下每日一题之——环形链表。

二. 🦁 解题过程

1. 题目

给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。否则，返回 false 。

在这里插入图片描述

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

2. 思路一

如果学过hash表，这个题最简单的方法就是建立一个HashSet，然后遍历整个链表，将结点一个一个存进去，如果遍历到第N个结点存不进去，则说明该链表存在环！！！

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public boolean hasCycle(ListNode head) {if(head == null) return false;Set<ListNode> set = new HashSet<>();ListNode pre = head;while(pre.next != null){if(! set.add(pre)){return true;}pre = pre.next;}return false;}
}

3. 思路二

第二种思路就是可以使用快慢指针pre和post，并且pre需要比post多走一步。在同一起点时，如果是直链则pre永远不会和post相遇！如果链表存在环，则终会相遇！！！代码如下：

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public boolean hasCycle(ListNode head) {if(head == null || head.next == null) return false;ListNode pre = head;ListNode post = head;while(pre != null && pre.next != null){post = post.next;pre = pre.next;pre = pre.next;if(post == pre) return true;}return false;}
}

三. 🦁 文末活动

在这里插入图片描述

🦁 送书抽奖活动 🦁

算法训练是一种很枯燥的东西，有一本好的辅助书本可以助你乘风破浪，现在市面上大多算法书都是基于C++的，对于Java选手非常不友好，现在给大家推荐一本好书，由机械出版社出版的《算法精粹：经典计算机科学问题的Java实现》，基于JDK11实现，非常实用，推荐入手！！！

本次活动由机械出版社友情赞助！！！

如果说计算机之于计算机科学就像望远镜之于天文学，那么编程语言就像望远镜的镜头。无论是在本科的课堂（计算机科学、软件工程等）上，还是在中级编程课本（例如，关于人工智能或算法的入门书）中，有些交给新手程序员解决的特定编程问题已经变得司空见惯了，以至于可以被视为经典。从简单的只需寥寥数行代码就能够解决的问题，到复杂的需要跨多个章节来构建系统的问题，这些问题范围很广。有些问题涉及人工智能，有些问题仅涉及常识，有些问题是实际存在的，而有些问题是虚构的。

20年来，Java已经成为世界上非常流行的编程语言之一。可以说，它已经成为企业、高等教育以及Android应用程序开发中的主导语言。通过本书，希望能够引领大家意识到Java不仅仅是实现最终目标的一种手段，还是解决计算问题的一种工具。本书中的问题能够帮助老练的程序员在学习某些编程语言高级特性的同时，反思之前学过的计算机科学课程内容并有新的收获。使用Java的在校生和自学型程序员都可以通过学习普遍适用的问题求解技术来加速计算机科学课程的学习进度。本书涵盖了各种各样的问题，因此所有人都能从中受益。

在这里插入图片描述

内容简介

无论何种软件开发问题，都有可能已经有了解决方案。本书收集了非常有用的解决方案，可以指导你学习那些经过千锤百炼的解决问题的技术。本书介绍的原则和算法可以保证你在一个又一个的项目中节省大量的时间。

本书包含50多个练习，这些练习是多年来一直在计算机科学课堂中使用的。你可以通过实践这些例子来探索核心算法、约束问题、人工智能应用等。

本书主要内容包括：

递归、记忆化和位操作。
搜索、图和遗传算法。
约束满足问题。
k均值聚类、神经网络和对抗搜索。

本书结构

第1章介绍大多数读者可能已经熟知的问题求解技术。像递归、记忆化和位运算这类内容是后续章节讨论其他技术的基础。
第2章重点介绍搜索问题。搜索是一个非常大的主题，本书中的大部分问题都可以归到这个主题下。本章介绍最基本的搜索算法，包括二分搜索、深度优先搜索、广度优先搜索和A*搜索。
第3章介绍如何建立一个框架来解决广泛的问题。这些问题可以用相互之间受到约束的有限领域变量来进行抽象，包括经典的八皇后问题、澳大利亚地图着色问题以及字谜问题。
第4章探索图算法。对于初学者来说，这些算法的适用范围非常广。本章将介绍如何构建图数据结构，然后使用它来解决几个经典的优化问题。
第5章探讨遗传算法，这种算法在不确定性上要比本书中的大多数算法大得多，但有时可以解决那些传统算法无法在合理的时间内解决的问题。
第6章介绍k均值聚类，这可能是本书中算法最具体的一章。这种聚类技术实现简单，易于理解，适用范围广。
第7章解释什么是神经网络，旨在让读者领略简单神经网络究竟是什么样子的。本章不会全面介绍这个令人兴奋而又不断发展的领域，而是介绍如何在不使用外部库的情况下根据基本原理来构建神经网络，让你真正了解神经网络究竟是如何工作的。
第8章介绍双人博弈中的对抗搜索。本章将探索一种被称为极小化极大的搜索算法，该算法可以用来开发国际象棋、国际跳棋和四子棋程序。
第9章涵盖一些书中其他章节没有提及的有趣问题。
第10章是对Oracle的Java语言架构师布赖恩·戈茨（Brian Goetz）的访谈，他指导了该语言的开发工作。他为读者提供了一些有关编程和计算机科学的明智建议。

关于代码

本书源代码是基于Java 11编写的，而且利用了Java 11的某些新特性。之所以选择Java 11版本，是因为该版本是撰写本文时Java所发布的最新LTS（Long-Term Support，长期维护）版本。事实上，其中大量代码都可以在Java 8及之后的版本中运行。据我所知，仍有很多程序员出于各种各样的原因（比如Android）在使用Java 8，但是我希望能在使用较新Java版本的同时，通过讲授一些该语言的新特性来为读者提供额外的价值。