专题【链表】【考试题】刷题日记

2024-04-07 01:28
文章标签 链表 刷题 专题 日记 考试题

本文主要是介绍专题【链表】【考试题】刷题日记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目列表

考试题（22题）

2024.04.04

146. LRU 缓存
707. 设计链表
138. 随机链表的复制
160. 相交链表
622. 设计循环队列
109. 有序链表转换二叉搜索树
460. LFU 缓存
355. 设计推特
725. 分隔链表
2487. 从链表中移除节点

日常复习题

876. 链表的中间结点
1171. 从链表中删去总和值为零的连续节点
2807. 在链表中插入最大公约数
117. 填充每个节点的下一个右侧节点指针 II
641. 设计循环双端队列
1669. 合并两个链表
114. 二叉树展开为链表
237. 删除链表中的节点
1206. 设计跳表
706. 设计哈希映射
1721. 交换链表中的节点
1019. 链表中的下一个更大节点
2181. 合并零之间的节点
2816. 翻倍以链表形式表示的数字
705. 设计哈希集合
2095. 删除链表的中间节点

2024.04.04

146. LRU 缓存

题目

请你设计并实现一个满足 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) 的平均时间复杂度运行。

示例：

输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

提示：

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

思路

  1. 维护kv（HashMap）
  2. 维护k的使用顺序，（最新的往前挪）（双向链表）

答案

class LRUCache {private class Node {int key;int value;Node pre;Node next;public void removeNode() {this.next.pre = this.pre;this.pre.next = this.next;}}private Node head;private Node tail;private int capacity;private Map<Integer, Node> map;public LRUCache(int capacity) {head = new Node();tail = new Node();head.next = tail;tail.pre = head;this.capacity = capacity;map = new HashMap<>();}private void addToHead(Node node) {node.next = head.next;head.next = node;node.pre = head;node.next.pre = node;}public int get(int key) {Node node = map.get(key);if (node != null) {node.removeNode();addToHead(node);}return Optional.ofNullable(map.get(key)).map(n -> n.value).orElse(-1);}public void put(int key, int value) {if (map.containsKey(key)) {Node oldNode = map.get(key);oldNode.pre.next = oldNode.next;oldNode.next.pre = oldNode.pre;map.remove(oldNode.key);}Node node = new Node();node.key = key;node.value = value;addToHead(node);map.put(key, node);if (map.size() > capacity) {removeTail();}}private void removeTail() {Node removeNode = tail.pre;removeNode.pre.next = tail;tail.pre = removeNode.pre;map.remove(removeNode.key);}
}/*** 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);*/

707. 设计链表

题目

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

  • MyLinkedList() 初始化 MyLinkedList 对象。
  • int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
  • void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
  • void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
  • void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
  • void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

示例：

输入
[“MyLinkedList”, “addAtHead”, “addAtTail”, “addAtIndex”, “get”, “deleteAtIndex”, “get”]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]

解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2); // 链表变为 1->2->3
myLinkedList.get(1); // 返回 2
myLinkedList.deleteAtIndex(1); // 现在，链表变为 1->3
myLinkedList.get(1); // 返回 3

提示：

  • 0 <= index, val <= 1000
  • 请不要使用内置的 LinkedList 库。
  • 调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。

思路

  1. 实现个node
  2. 各种边界要判断清除
  3. 要有个虚构的头结点

答案

class MyLinkedList {class Node {int value;Node next;}private int size;private Node dummy;public MyLinkedList() {size = 0;dummy = new Node();}public int get(int index) {if (index < 0 || index >= size) {return -1;}Node current = dummy;for (int i = 0; i <= index; i++) {current = current.next;}return current.value;}public void addAtHead(int val) {Node node = new Node();node.value = val;node.next = dummy.next;dummy.next = node;size++;}public void addAtTail(int val) {Node node = new Node();node.value = val;Node current = dummy;for (int i = 0; i < size; i++) {current = current.next;}current.next = node;size++;}public void addAtIndex(int index, int val) {if (index > size) {return;}Node node = new Node();node.value = val;Node current = dummy;for (int i = 0; i < index; i++) {current = current.next;}node.next = current.next;current.next = node;size++;}public void deleteAtIndex(int index) {if (index >= size) {return;}Node current = dummy;for (int i = 0; i < index; i++) {current = current.next;}current.next = current.next.next;size--;}
}/*** Your MyLinkedList object will be instantiated and called as such:* MyLinkedList obj = new MyLinkedList();* int param_1 = obj.get(index);* obj.addAtHead(val);* obj.addAtTail(val);* obj.addAtIndex(index,val);* obj.deleteAtIndex(index);*/

160. 相交链表

题目

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：
在这里插入图片描述

题目数据 保证 整个链式结构中不存在环。

注意， 函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

  • intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
  • listA - 第一个链表
  • listB - 第二个链表
  • skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
  • skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
    评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：
在这里插入图片描述

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at ‘8’
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：
在这里插入图片描述

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at ‘2’
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：
在这里插入图片描述

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

  • listA 中节点数目为 m
  • listB 中节点数目为 n
  • 1 <= m, n <= 3 * 104
  • 1 <= Node.val <= 105
  • 0 <= skipA <= m
  • 0 <= skipB <= n
  • 如果 listA 和 listB 没有交点，intersectVal 为 0
  • 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

进阶： 你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

思路

假设俩链表相交。
A的长度为A = a + x，x为相交部分长度
B的长度为B = b + x，x为相交部分长度
所以，只需要将两个链表首尾相连
A走到x开头的位移为a + x + b，走完自己又走完B
B走到x开头的位移为b + x + a，走完自己又走完A
长度相同，会在相交节点相遇

答案

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode pA = headA, pB = headB;while (pA != pB) {pA = pA == null ? headB : pA.next;pB = pB == null ? headA : pB.next;}// 相交就在x的开头，否则最终，两个都为null，返回nullreturn pA;}
}

725. 分隔链表

题目

给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。
每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。
这 k 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。
返回一个由上述 k 部分组成的数组。

示例 1：
在这里插入图片描述

输入：head = [1,2,3], k = 5
输出：[[1],[2],[3],[],[]]
解释：
第一个元素 output[0] 为 output[0].val = 1 ，output[0].next = null 。
最后一个元素 output[4] 为 null ，但它作为 ListNode 的字符串表示是 [] 。

示例 2：
在这里插入图片描述

输入：head = [1,2,3,4,5,6,7,8,9,10], k = 3
输出：[[1,2,3,4],[5,6,7],[8,9,10]]
解释：
输入被分成了几个连续的部分，并且每部分的长度相差不超过 1 。前面部分的长度大于等于后面部分的长度。

提示：

  • 链表中节点的数目在范围 [0, 1000]
  • 0 <= Node.val <= 1000
  • 1 <= k <= 50

思路

  1. 10个节点是4, 3, 3。是10 / 3 = 3。3组3个节点的，从前往后10 % 3 = 1，从前向后加1。即(3+1), 3, 3
  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[] splitListToParts(ListNode head, int k) {int size = 0;ListNode current = head;while (current != null) {size++;current = current.next;}/// 算个数int mod = size % k;int minSize = size / k;current = head;ListNode[] result = new ListNode[k];for (int i = 0; i < k; i++) {int l = 0;int length = minSize + (i < mod ? 1 : 0);result[i] = current;// 拿到前一个节点while (l++ < length - 1) {if (current != null) {current = current.next;}}// 处理边界if (current == null) {return result;}// 断开ListNode next = current.next;current.next = null;current = next;}return result;}
}

2487. 从链表中移除节点

题目

给你一个链表的头节点 head 。
移除每个右侧有一个更大数值的节点。
返回修改后链表的头节点 head 。

示例 1：
在这里插入图片描述

输入：head = [5,2,13,3,8]
输出：[13,8]
解释：需要移除的节点是 5 ，2 和 3 。

  • 节点 13 在节点 5 右侧。
  • 节点 13 在节点 2 右侧。
  • 节点 8 在节点 3 右侧。

示例 2：

输入：head = [1,1,1,1]
输出：[1,1,1,1]
解释：每个节点的值都是 1 ，所以没有需要移除的节点。

提示：

  • 给定列表中的节点数目在范围 [1, 105] 内
  • 1 <= Node.val <= 105

思路

其实是，返回一个非递增的数组。
《移除每个右侧有一个更大值的节点》，意味着最右边的节点不会动（一定会保留）。
所以反转下，就是一个以第一个元素开头的，非递减的数组
如果，一个节点右边的元素，比当前值小，就删除右边的

答案

/*** 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 removeNodes(ListNode head) {ListNode newHead = iterationReverse(head);ListNode current = newHead;while (current.next != null) {// 有小的就删除if (current.next.val < current.val) {current.next = current.next.next;} else {current = current.next;}}// 最后别忘了转回来return iterationReverse(newHead);}// 这个翻转比递归快private ListNode iterationReverse(ListNode head) {ListNode current = head, next = head;while (current != null && current.next != null) {next = current.next.next;current.next.next = head;head = current.next;current.next = next;}return head;}
}

待进行

138. 随机链表的复制
622. 设计循环队列
109. 有序链表转换二叉搜索树
460. LFU 缓存
355. 设计推特

这篇关于专题【链表】【考试题】刷题日记的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

【专题】2024飞行汽车技术全景报告合集PDF分享（附原数据表）

【专题】2024飞行汽车技术全景报告合集PDF分享（附原数据表）

原文链接： https://tecdat.cn/?p=37628 6月16日，小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞，这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示，公司准备量产，并计划今年四季度开启预售小鹏汇天分体式飞行汽车，探索分体式飞行汽车城际通勤。阅读原文，获取专题报告合集全文，解锁文末271份飞行汽车相关行业研究报告。 据悉，业内人士对飞行汽车行业
阅读更多...
csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
深入手撕链表

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-
阅读更多...
建立升序链表

建立升序链表

题目1181：遍历链表 时间限制：1 秒 内存限制：32 兆 特殊判题：否 提交：2744 解决：1186 题目描述： 建立一个升序链表并遍历输出。 输入： 输入的每个案例中第一行包括1个整数：n(1<=n<=1000)，接下来的一行包括n个整数。 输出： 可能有多组测试数据，对于每组数据， 将n个整数建立升序链表，之后遍历链表并输出。 样例输
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
音视频入门基础：WAV专题（10）——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

音视频入门基础：WAV专题（10）——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

一、引言 从文章《音视频入门基础：WAV专题（6）——通过FFprobe显示WAV音频文件每个数据包的信息》中我们可以知道，通过FFprobe命令可以打印WAV音频文件每个packet（也称为数据包或多媒体包）的信息，这些信息包含该packet的pts、dts： 打印出来的“pts”实际是AVPacket结构体中的成员变量pts，是以AVStream->time_base为单位的显
阅读更多...
学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一：循环解法二：递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1：（图一）输入：head = [1,1,2]输出：[1,2]示例 2：（图
阅读更多...
【每日刷题】Day113

【每日刷题】Day113

【每日刷题】Day113 🥕个人主页：开敲🍉 🔥所属专栏：每日刷题🍍 🌼文章目录🌼 1. 91. 解码方法 - 力扣（LeetCode） 2. LCR 098. 不同路径 - 力扣（LeetCode） 3. 63. 不同路径 II - 力扣（LeetCode） 1. 91. 解码方法 - 力扣（LeetCode） //思路：动态规划。 cl
阅读更多...
专题二_滑动窗口_算法专题详细总结

专题二_滑动窗口_算法专题详细总结

目录 滑动窗口，引入： 滑动窗口，本质：就是同向双指针； 1.⻓度最⼩的⼦数组（medium） 1.解析：给我们一个数组nums，要我们找出最小子数组的和==target，首先想到的就是暴力解法 1）暴力： 2）优化，滑动窗口: 1.进窗口 2.出窗口 3.更新值 2.⽆重复字符的最⻓⼦串（medium） 1）仍然是暴力解法： 2）优化： 进窗口：hash[s[rig
阅读更多...
hot100刷题第1-9题，三个专题哈希，双指针，滑动窗口

hot100刷题第1-9题，三个专题哈希，双指针，滑动窗口

求满足条件的子数组，一般是前缀和、滑动窗口，经常结合哈希表； 区间操作元素，一般是前缀和、差分数组 数组有序，更大概率会用到二分搜索 目前已经掌握一些基本套路，重零刷起leetcode hot 100， 套路题按套路来，非套路题适当参考gpt解法。 一、梦开始的地方， 两数之和 class Solution:#注意要返回的是数组下标def twoSum(self, nums: Lis
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2