Leetcode1206（设计跳表）

2024-02-21 02:44
文章标签 设计 跳表 leetcode1206

本文主要是介绍Leetcode1206（设计跳表），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

例题：

分析：

我们先来找一找跳表与单链表的相同点和不同点。

相同点：

跳表和单链表一样，都是由一个一个的节点组成的链表。

不同点：

①：跳表中的元素已经是排好序的（图中从小到大），而链表中的元素对顺序没有要求，可以乱序。

②：跳表中的next指针可以有多个，可以分别指向不同的元素；而单链表只有一个next指针，只能指向离当前节点最近的元素。

不难发现，跳表在查询数据时有一个规律：

下楼梯方式查找

- 若next指针为null， 或者next指向的节点值 >= 目标值，则向下找

- 若next指针不为null， 且next指向的节点值 < 目标值，则向右找

可以先设计一个方法，根据节点值查找，并且记录所经过的节点路径：

        //查找指定节点并记录查询过程中所经过的节点public Node[] find(int val){Node curr = head;Node[] path = new Node[MAX];for(int level = MAX - 1; level >= 0; level--){  //向下找while (curr.next[level] != null && curr.next[level].value < val) { //向右找curr = curr.next[level];}path[level] = curr;}return path;}

这段代码根据  curr.next[level].value < val 这个条件，我们最后找到的节点是目标节点的前一个节点，当然目标节点也可能不存在。这个方法在实现添加、删除方法时会经常用到。

注意：这里向下找的条件 和 向右找的条件是互斥的，所以不用再写一个向下找的判断逻辑

下图表示新加入一个节点

新加入节点时核心思想：

①：确定新加入节点的位置（把val当作目标查询，经过的路径就可以确定添加位置）

②：创建新节点随机高度，高度尽可能小（如果跳表的每个节点都很高，那么查询效率就低了）

③：修改新节点的next指针 和 路径节点的next指针

        static Random r = new Random();//随机返回 1~max 的数字/*** 从 1 开始，数字的几率逐级减半，例如 max = 4 ，让大概* - 50% 的几率返回 1* - 25% 的几率返回 2* - 12.5% 的几率返回 3* - 12.5% 的几率返回 4*/static int randomLevel(int max){int x = 1;while(x < max){if(r.nextBoolean()){return x;}x++;}return x;}//添加节点public void add(int num) {//1.确定新加入节点的位置（把val当作目标查询，经过的路径就可以确定添加位置）Node[] path = find(num);//2.创建新节点随机高度，高度尽可能小Node node = new Node(num);int level = randomLevel(MAX);//3.修改新节点的next指针， 路径节点的next指针for(int i = 0; i < level; i++){node.next[i] = path[i].next[i];path[i].next[i] = node;}}
完整代码：
package leetcodeup;import java.util.Random;public class SkipListLeetcode1206 {static class Skiplist {private static final int MAX = 10;  //节点的最大next指针数private final Node head = new Node(-1); //头节点static Random r = new Random();//随机返回 1~max 的数字/*** 从 1 开始，数字的几率逐级减半，例如 max = 4 ，让大概* - 50% 的几率返回 1* - 25% 的几率返回 2* - 12.5% 的几率返回 3* - 12.5% 的几率返回 4*/static int randomLevel(int max){int x = 1;while(x < max){if(r.nextBoolean()){return x;}x++;}return x;}static class Node{int value;Node[] next = new Node[MAX];public Node(int value) {this.value = value;}}//查找指定节点并记录查询过程中所经过的节点public Node[] find(int val){Node curr = head;Node[] path = new Node[MAX];for(int level = MAX - 1; level >= 0; level--){  //向下找while (curr.next[level] != null && curr.next[level].value < val) { //向右找curr = curr.next[level];}path[level] = curr;}return path;}//查找节点public boolean search(int target) {Node[] path = find(target);Node node = path[0].next[0];return node != null && node.value == target;}//添加节点public void add(int num) {//1.确定新加入节点的位置（把val当作目标查询，经过的路径就可以确定添加位置）Node[] path = find(num);//2.创建新节点随机高度，高度尽可能小Node node = new Node(num);int level = randomLevel(MAX);//3.修改新节点的next指针， 路径节点的next指针for(int i = 0; i < level; i++){node.next[i] = path[i].next[i];path[i].next[i] = node;}}//删除节点public boolean erase(int num) {Node[] path = find(num);Node node = path[0].next[0];//要删除的节点可能不存在if(node == null || node.value != num){return false;}//节点存在，开始删除节点for(int i = 0; i < MAX; i++){if(path[i].next[i] != node){break;}path[i].next[i] = node.next[i];}return true;}}
}

这篇关于Leetcode1206（设计跳表）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/730344。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
怎么让1台电脑共享给7人同时流畅设计

怎么让1台电脑共享给7人同时流畅设计

在当今的创意设计与数字内容生产领域，图形工作站以其强大的计算能力、专业的图形处理能力和稳定的系统性能，成为了众多设计师、动画师、视频编辑师等创意工作者的必备工具。 设计团队面临资源有限，比如只有一台高性能电脑时，如何高效地让七人同时流畅地进行设计工作，便成为了一个亟待解决的问题。 一、硬件升级与配置 1.高性能处理器（CPU）：选择多核、高线程的处理器，例如Intel的至强系列或AMD的Ry
阅读更多...
基于51单片机的自动转向修复系统的设计与实现

基于51单片机的自动转向修复系统的设计与实现

文章目录 前言资料获取设计介绍功能介绍设计清单具体实现截图参考文献设计获取 前言 💗博主介绍：✌全网粉丝10W+,CSDN特邀作者、博客专家、CSDN新星计划导师，一名热衷于单片机技术探索与分享的博主、专注于 精通51/STM32/MSP430/AVR等单片机设计 主要对象是咱们电子相关专业的大学生，希望您们都共创辉煌！✌💗 👇🏻 精彩专栏 推荐订阅👇🏻 单片机
阅读更多...
SprinBoot+Vue网络商城海鲜市场的设计与实现

SprinBoot+Vue网络商城海鲜市场的设计与实现

目录 1 项目介绍2 项目截图3 核心代码3.1 Controller3.2 Service3.3 Dao3.4 application.yml3.5 SpringbootApplication3.5 Vue 4 数据库表设计5 文档参考6 计算机毕设选题推荐7 源码获取 1 项目介绍 博主个人介绍：CSDN认证博客专家，CSDN平台Java领域优质创作者，全网30w+
阅读更多...
单片机毕业设计基于单片机的智能门禁系统的设计与实现

单片机毕业设计基于单片机的智能门禁系统的设计与实现

文章目录 前言资料获取设计介绍功能介绍程序代码部分参考 设计清单具体实现截图参考文献设计获取 前言 💗博主介绍：✌全网粉丝10W+,CSDN特邀作者、博客专家、CSDN新星计划导师，一名热衷于单片机技术探索与分享的博主、专注于 精通51/STM32/MSP430/AVR等单片机设计 主要对象是咱们电子相关专业的大学生，希望您们都共创辉煌！✌💗 👇🏻 精彩专栏 推荐订
阅读更多...
Spring的设计⽬标——《Spring技术内幕》

Spring的设计⽬标——《Spring技术内幕》

读《Spring技术内幕》第二版，计文柯著。 如果我们要简要地描述Spring的设计⽬标，可以这么说，Spring为开发者提供的是⼀个⼀站式的轻量级应⽤开发框架（平台）。 作为平台，Spring抽象了我们在 许多应⽤开发中遇到的共性问题；同时，作为⼀个轻量级的应⽤开发框架，Spring和传统的J2EE开发相⽐，有其⾃⾝的特点。 通过这些⾃⾝的特点，Spring充分体现了它的设计理念：在
阅读更多...
开题报告中的研究方法设计：AI能帮你做什么？

开题报告中的研究方法设计：AI能帮你做什么？

AIPaperGPT，论文写作神器~ https://www.aipapergpt.com/ 大家都准备开题报告了吗？研究方法部分是不是已经让你头疼到抓狂？ 别急，这可是大多数人都会遇到的难题！尤其是研究方法设计这一块，选定性还是定量，怎么搞才能符合老师的要求？ 每次到这儿，头脑一片空白。 好消息是，现在AI工具火得一塌糊涂，比如ChatGPT，居然能帮你在研究方法这块儿上出点主意。是不
阅读更多...
创业者该如何设计公司的股权架构

创业者该如何设计公司的股权架构

本文来自七八点联合IT橘子和车库咖啡的一系列关于设计公司股权结构的讲座。 主讲人何德文： 在公司发展的不同阶段，创业者都会面临公司股权架构设计问题： 1.合伙人合伙创业第一天，就会面临股权架构设计问题（合伙人股权设计）； 2.公司早期要引入天使资金，会面临股权架构设计问题（天使融资）； 3.公司有三五十号人，要激励中层管理与重要技术人员和公司长期走下去，会面临股权架构设计问题（员工股权激
阅读更多...
分布式文件系统设计

分布式文件系统设计

分布式文件系统是分布式领域的一个基础应用，其中最著名的毫无疑问是 HDFS/GFS。如今该领域已经趋向于成熟，但了解它的设计要点和思想，对我们将来面临类似场景 / 问题时，具有借鉴意义。并且，分布式文件系统并非只有 HDFS/GFS 这一种形态，在它之外，还有其他形态各异、各有千秋的产品形态，对它们的了解，也对扩展我们的视野有所俾益。本文试图分析和思考，在分布式文件系统领域，我们要解决哪些问题、有
阅读更多...
（入门篇）JavaScript 网页设计案例浅析-简单的交互式图片轮播

（入门篇）JavaScript 网页设计案例浅析-简单的交互式图片轮播

网页设计已经成为了每个前端开发者的必备技能，而 JavaScript 作为前端三大基础之一，更是为网页赋予了互动性和动态效果。本篇文章将通过一个简单的 JavaScript 案例，带你了解网页设计中的一些常见技巧和技术原理。今天就说一说一个常见的图片轮播效果。相信大家在各类电商网站、个人博客或者展示页面中，都看到过这种轮播图。它的核心功能是展示多张图片，并且用户可以通过点击按钮，左右切换图片。
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2