面试经典150题——链表（二）

文章目录

  • 1、删除链表的倒数第 N 个结点
    • 1.1 题目链接
    • 1.2 题目描述
    • 1.3 解题代码
    • 1.4 解题思路
  • 2、删除排序链表中的重复元素 II
    • 2.1 题目链接
    • 2.2 题目描述
    • 2.3 解题代码
    • 2.4 解题思路
  • 3、旋转链表
    • 3.1 题目链接
    • 3.2 题目描述
    • 3.3 解题代码
    • 3.4 解题思路
  • 4、分隔链表
    • 4.1 题目链接
    • 4.2 题目描述
    • 4.3 解题代码
    • 4.4 解题思路
  • 5、LRU 缓存
    • 5.1 题目链接
    • 5.2 题目描述
    • 5.3 解题代码
    • 5.4 解题思路

1、删除链表的倒数第 N 个结点

1.1 题目链接

点击跳转到题目位置

1.2 题目描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

提示：

  • 链表中结点的数目为 sz
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

1.3 解题代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode cur = dummyHead;
        int num = 0;
        while(cur.next != null){
            num++;
            cur = cur.next;
        }
        int deleteNum = num - n + 1; // 倒数第 n 个就是 整数第 num - n + 1个 
        cur = dummyHead;
        for(int i = 0; i < deleteNum - 1; ++i){
            cur = cur.next;
        }
        cur.next = cur.next.next;
    return dummyHead.next;
    }
}

1.4 解题思路

  1. 首先获取链表的总结点数num。
  2. 那么删除的结点就是正数第num - n + 1个结点。
  3. 按照链表的删除方式删除即可。

2、删除排序链表中的重复元素 II

2.1 题目链接

点击跳转到题目位置

2.2 题目描述

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

提示：

  • 链表中节点数目在范围 [0, 300] 内
  • -100 <= Node.val <= 100
  • 题目数据保证链表已经按升序 排列

2.3 解题代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode cur = dummyHead;
        while(cur.next != null){
            ListNode nextNode = cur.next;
            int flag = 0;
            while(nextNode.next != null && nextNode.next.val == nextNode.val){
                flag = 1;
                nextNode = nextNode.next;
            }
            if(flag == 0){
                cur = cur.next;
            } else{
                cur.next = nextNode.next;
            }
        }
        return dummyHead.next;
    }
}

2.4 解题思路

  1. 分情况讨论，cur指针指向判断结点的前1个结点，如果下一个结点存在相同的数字，则跳过这些数字，将cur.next与这些数字后面的一个数字所在的结点连接。否则的话，则需要保留这个结点，cur = cur.next。
  2. 当cur.next为空的时候不需要判断下个数字了，跳出循环即可。

3、旋转链表

3.1 题目链接

点击跳转到题目位置

3.2 题目描述

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

提示：

  • 链表中节点的数目在范围 [0, 500] 内
  • -100 <= Node.val <= 100
  • 0 <= k <= 2 * 109

3.3 解题代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null){
            return head;
        }
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode cur = dummyHead;
        int n = 0; // 链表中结点的个数
        while(cur.next != null){
            n++;
            cur = cur.next;
        }
        ListNode tail = cur;
        int step = k % n;
        if(step == 0){
            return head;
        }
        cur = dummyHead;
        for(int i = 0; i < n - step; ++i){
            cur = cur.next;
        }
        ListNode newHead = cur.next;
        tail.next = head;
        cur.next = null;
        return newHead;
    }
}

3.4 解题思路

  1. 解题思路看上去是统一右移动k位，实际上是将链表在第n - k位和 n - k + 1截断然后重新拼接。
  2. 第一段链表放在第二段链表的尾部即可。

4、分隔链表

4.1 题目链接

点击跳转到题目位置

4.2 题目描述

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

提示：

  • 链表中节点的数目在范围 [0, 200] 内
  • -100 <= Node.val <= 100
  • -200 <= x <= 200

4.3 解题代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummyHead1 = new ListNode(); // 存储所有小于x的结点
        ListNode dummyHead2 = new ListNode(); // 存储所有大于等于x的结点 
        ListNode cur1 = dummyHead1;
        ListNode cur2 = dummyHead2;
        ListNode cur = head;
        while(cur != null){
            if(cur.val < x){
                cur1.next = cur;
                cur1 = cur1.next;
                cur = cur.next;
                cur1.next = null;
            } else{
                cur2.next = cur;
                cur2 = cur2.next;
                cur = cur.next;
                cur2.next = null;
            }
        }
        cur1.next = dummyHead2.next;
        cur2.next = null;
        return dummyHead1.next;
    }
}

4.4 解题思路

  1. 用两个链表进行维护即可，一个链表用来存储值小于x的所有的结点，另一个链表存储大于等于x的所有的结点。
  2. 最后将两个链表拼接即可。

5、LRU 缓存

5.1 题目链接

点击跳转到题目位置

5.2 题目描述

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

提示：

  • 1 <= capacity <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 105
  • 最多调用 2 * 105 次 get 和 put

5.3 解题代码

public class DListNode{
    int key;
    int val;

    DListNode prev;
    DListNode next;

    DListNode(){}
    DListNode(int key, int val){this.key = key; this.val = val;}
    DListNode(int key, int val, DListNode prev, DListNode next){
        this.key = key;
        this.val = val;
        this.prev = prev;
        this.next = next;
    }
} 


class LRUCache {
    Map<Integer, DListNode> hash = new HashMap<Integer, DListNode>(); 
    int size;
    int capacity;
    DListNode dummyHead = new DListNode();
    DListNode dummyTail = new DListNode();

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }
    
    public int get(int key) {
        if(hash.containsKey(key)){
            hash.get(key).prev.next = hash.get(key).next;
            hash.get(key).next.prev = hash.get(key).prev;
            moveToHead(hash.get(key));
            return hash.get(key).val; 
        }
        return -1;
    }
    
    public void put(int key, int value) {
        DListNode node = new DListNode(key, value);
        if(hash.containsKey(key)){
            hash.get(key).val = value;
            hash.get(key).prev.next = hash.get(key).next;
            hash.get(key).next.prev = hash.get(key).prev;
            moveToHead(hash.get(key));
        } else{
            if(size < capacity){
                ++size;
                moveToHead(node);
            } else{
                moveToHead(node);
                deleteTail();
            }
            hash.put(key, node);
        }
    }

    public void moveToHead(DListNode node){
        node.next = dummyHead.next;
        dummyHead.next = node;
        node.prev = dummyHead;
        node.next.prev = node;
    }

    public void deleteTail(){
        int key = dummyTail.prev.key;
        hash.remove(key);
        dummyTail.prev = dummyTail.prev.prev;
        dummyTail.prev.next = dummyTail;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

5.4 解题思路

  1. 使用双向链表解决问题。
  2. 对使用过的/新的值插入到链表开头。
  3. 删除链表末尾的结点。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/949285.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

macos安装java8

macos安装java8

下载 dmg方式安装 安装 双击pkg运行 输入java -version验证 配置环境变量 cd ~ ls -a输入 ls -a后查看是否已经存在.bash_profile文件&#xff0c;如果已经存在就不需要创建&#xff0c;如果不存在&#xff0c;继续执行下方命令创建文件 touch .bash_profile /usr/l…
阅读更多...
【每日学点鸿蒙知识】自定义键盘光标、Cavas绘制、XComponent触发键盘抬起等

【每日学点鸿蒙知识】自定义键盘光标、Cavas绘制、XComponent触发键盘抬起等

【每日学点鸿蒙知识】24.08.25 【每日学点鸿蒙知识】自定义键盘光标、Cavas绘制、XComponent触发键盘抬起等 1、基于自定义键盘如何设置光标位置&#xff1f; 可以参考如下代码&#xff1a; class MyKeyboardController {public onInputChanged?: (value: string) > vo…
阅读更多...
在Mysql环境下对数据进行增删改查

在Mysql环境下对数据进行增删改查

一、插入数据&#xff1a; insert into 表名 [(字段名)] values (字段对应的值1,字段对应的值2,…)[,(字段对应的值1,字段对应的值2,…)]; insert into students (id,name,age,height,gender,cls_id,is_delete) values (0,小明,18,180.00,2,1,0)在学生表中插入“小明”数据的…
阅读更多...
Web网页制作之JavaScript的应用

Web网页制作之JavaScript的应用

---------------&#x1f4e1;&#x1f50d;K学啦 更多学习资料&#x1f4d5; 免费获取--------------- 实现的功能&#xff1a;1.通过登录界面跳转至主页面&#xff0c;用户名统一为“admin”&#xff0c;密码统一为“admin123”&#xff0c;密码可显示或隐藏&#xff0c;输入…
阅读更多...
Markdown编辑器——Typora（Picgo+Github图床）

Markdown编辑器——Typora（Picgo+Github图床）

Markdown编辑器——Typora&#xff08;PicgoGithub图床&#xff09; 文章目录 Markdown编辑器——Typora&#xff08;PicgoGithub图床&#xff09;安装Typora安装PicGoPicGo软件下载PicGo的npm版本下载 GitHub图床配置PicGo配置PicGo的软件配置PicGo的npm版本信息配置 配置Typo…
阅读更多...
Unity 3D游戏开发从入门进阶到高级

Unity 3D游戏开发从入门进阶到高级

本文精心整理了Unity3D游戏开发相关的学习资料&#xff0c;涵盖入门、进阶、性能优化、面试和书籍等多个维度&#xff0c;旨在为Unity开发者提供全方位、高含金量的学习指南.欢迎收藏。 学习社区 Unity3D开发者 这是一个专注于Unity引擎的开发者社区&#xff0c;汇聚了众多Un…
阅读更多...
Python 21:Debug

Python 21:Debug

1. Debug的作用 当程序的预期结果和实际结果不一致时&#xff0c;可以用Debug模式进行调试来定位问题的位置。 2. Debug使用 1&#xff09;设置断点 点击行号&#xff0c;出现”断点“ 2&#xff09;执行Debug 点击Debug 或者右键&#xff0c;点击debug进入debug模式 3.Debu…
阅读更多...
（CICD）自动化构建打包、部署(Jenkins + maven+ gitlab+tomcat)

（CICD）自动化构建打包、部署(Jenkins + maven+ gitlab+tomcat)

一、平滑发布与灰度发布 **什么叫平滑&#xff1a;**在发布的过程中不影响用户的使用&#xff0c;系统不会因发布而暂停对外服务&#xff0c;不会造成用户短暂性无法访问&#xff1b; **什么叫灰度&#xff1a;**发布后让部分用户使用新版本&#xff0c;其它用户使用旧版本&am…
阅读更多...
强化学习入门谈

强化学习入门谈

之前我们见识到很多机器学习大展手脚的任务场景了&#xff0c;但是机器学习依旧有很多软肋。 回忆一下&#xff0c;我们之前做的机器学习&#xff08;深度学习&#xff09;策略基本都是类似于"supervised learning"的方法&#xff0c;比如你想用CNN实现一个classifi…
阅读更多...
colnames看似简单，却能优化数据处理流程

colnames看似简单，却能优化数据处理流程

引言 在数据处理和分析中&#xff0c;变量名称是至关重要的&#xff0c;它们决定了数据的可读性和操作的简便性。在R语言中&#xff0c;colnames 函数以其简单的语法设计&#xff0c;提供了高效管理数据框列名的能力&#xff0c;尤其是在复杂的爬虫任务中显得尤为重要。本篇文…
阅读更多...
【分布式】Hadoop完全分布式的搭建（零基础）

【分布式】Hadoop完全分布式的搭建（零基础）

Hadoop完全分布式的搭建 环境准备&#xff1a; &#xff08;1&#xff09;VMware Workstation Pro17&#xff08;其他也可&#xff09; &#xff08;2&#xff09;Centos7 &#xff08;3&#xff09;FinalShell &#xff08;一&#xff09;模型机配置 0****&#xff09;安…
阅读更多...
ArcGIS中怎么把数据提取到指定范围(裁剪、掩膜提取)

ArcGIS中怎么把数据提取到指定范围(裁剪、掩膜提取)

最近&#xff0c;经常能收到怎么把数据提取到指定范围、栅格数据怎么裁剪、矢量数据怎么裁剪、栅格数据怎么掩膜提取的咨询。 下面是我对这个问题的解决思路&#xff1a; 对于矢量数据&#xff1a; ①首先把数据加载进来 ②软件界面上面的工具栏找到→地理处理→裁剪&#x…
阅读更多...
intra-mart环境搭建笔记

intra-mart环境搭建笔记

一、前言 最近在做intra-mart项目&#xff0c;网上这些笔记比较少&#xff0c;在此做一下笔记。 intra-mart是由日本intra-mart公司开发和销售的工作流平台&#xff0c;国内确实不怎么用&#xff0c;日本企业用的多些&#xff0c;面试时会问有没有intra-mart经验。 这个自学…
阅读更多...
智能型电瓶车充电桩在老居民区充电站中的应用优势

智能型电瓶车充电桩在老居民区充电站中的应用优势

摘要 随着电瓶车数量的快速增长&#xff0c;小区内的电瓶车充电需求日益增加&#xff0c;但传统充电方式存在诸多安全隐患。电瓶车智能充电桩作为一种新型充电解决方案&#xff0c;能够有效解决充电难题&#xff0c;并提升充电安全性和便捷性。本文以ACX10A型电瓶车充电桩为…
阅读更多...
生产看板真的有用吗？

生产看板真的有用吗？

​看板&#xff0c;对于从事制造行业的人员来说&#xff0c;这并不陌生。但是对于看板起到的作用&#xff0c;那可就是众说纷纭&#xff0c;有人说&#xff0c;看板是领导的“面子工程”&#xff0c;是混淆上级视察的工具&#xff1b;也有人说&#xff0c;看板真切地帮助车间提…
阅读更多...
刷服务器固件

刷服务器固件

猫眼淘票票 大麦 一 H3C通用IP 注:算力服务器不需要存储 二 刷服务器固件 1 登录固定IP地址 2 升级BMC版本 注 虽然IP不一致但是步骤是一致的 3 此时服务器会出现断网现象&#xff0c;若不断网等上三分钟ping一下 4 重新登录 5 断电拔电源线重新登录查看是否登录成功
阅读更多...
机器学习算法在推荐系统中的应用：从数据预处理到模型部署实战指南

机器学习算法在推荐系统中的应用：从数据预处理到模型部署实战指南

机器学习算法在推荐系统中的应用&#xff1a;从数据预处理到模型部署实战指南 介绍 在当今信息爆炸的时代&#xff0c;推荐系统扮演了越来越重要的角色&#xff0c;它可以帮助用户发现和获取个性化的信息、产品或服务。而推荐系统中的机器学习算法则是其核心引擎&#xff0c;能…
阅读更多...
上门按摩系统架构与功能分析

上门按摩系统架构与功能分析

一、系统架构 服务端用Java语言&#xff08;最低JDK1.8&#xff0c;支持JDK11以及JDK17&#xff09;、MySQL数据库&#xff08;标配5.7版本&#xff0c;支持MySQL8&#xff09;&#xff0c;Mybatis ORM框架&#xff0c;Redis缓存&#xff0c;nginx代理&#xff0c;前端用uniap…
阅读更多...
使用mne对运动想象数据bciIV进行预处理

使用mne对运动想象数据bciIV进行预处理

需要的库 mne numpy scipy scikit-learn pip install mne numpy scipy scikit-learn 数据下载 对Data sets 2a ‹4-class motor imagery› 四分类的运动想象来进行mne的处理。 BCI Competition IV 数据的说明如下 [22 EEG channels (0.5-100Hz; notch filtered), 3 EOG chann…
阅读更多...
设计模式 行为型 策略模式（Strategy Pattern）与 常见技术框架应用 解析

设计模式 行为型 策略模式（Strategy Pattern）与 常见技术框架应用 解析

策略模式&#xff08;Strategy Pattern&#xff09;核心思想是将算法的实现从使用该算法的类中分离出来&#xff0c;作为独立的对象&#xff0c;通过接口来定义算法家族&#xff0c;这样就可以很容易地改变或扩展算法。通过这种方式&#xff0c;可以避免在客户端代码中使用大量…
阅读更多...
最新文章

Copyright @ 2022~2023