题目列表
考试题(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
思路
- 维护kv(HashMap)
- 维护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 。
思路
- 实现个node
- 各种边界要判断清除
- 要有个虚构的头结点
答案
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,返回null
return 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
思路
- 10个节点是4, 3, 3。是10 / 3 = 3。3组3个节点的,从前往后10 % 3 = 1,从前向后加1。即(3+1), 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[] 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. 设计推特