java算法题每日多道六

138. 随机链表的复制

题目

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

• val：一个表示 Node.val 的整数。
• random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码 只 接受原链表的头节点 head 作为传入参数。

答案

class Solution {Map<Node,Node> map = new HashMap();public Node copyRandomList(Node head) {if(head==null){return null;}if(!map.containsKey(head)){Node newHead = new Node(head.val);map.put(head,newHead);newHead.next = copyRandomList(head.next);newHead.random = copyRandomList(head.random);}return map.get(head);}
}

92. 反转链表 II

题目

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

答案

class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {ListNode dummy = new ListNode(0,head);ListNode pre = dummy;ListNode curr = null;for(int i=0;i<left-1;i++){pre = pre.next;}curr = pre.next;ListNode post = null;for(int i=left;i<right;i++){post = curr.next;curr.next = post.next;post.next = pre.next;pre.next = post;}return dummy.next;}
}

19. 删除链表的倒数第 N 个结点

题目

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

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

答案

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0,head);ListNode fast = dummy;ListNode slow = dummy;for(int i=0;i<=n;i++){fast = fast.next;}while(fast!=null){fast = fast.next;slow = slow.next;}slow.next = slow.next.next;return dummy.next;}
}

82. 删除排序链表中的重复元素 II

题目

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

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

输入：head = [1,1,1,2,3]
输出：[2,3]

答案

class Solution {public ListNode deleteDuplicates(ListNode head) {ListNode dummy = new ListNode(0,head);ListNode pre = dummy;ListNode curr = head;while(curr!=null && curr.next!=null){if(curr.val==curr.next.val){while(curr.next!=null && curr.val==curr.next.val){curr = curr.next;}pre.next = curr.next;curr = curr.next;}else{curr = curr.next;pre = pre.next;}}return dummy.next;}
}

61. 旋转链表

题目

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

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

输入：head = [0,1,2], k = 4
输出：[2,0,1]

答案

class Solution {public ListNode rotateRight(ListNode head, int k) {if(head==null || k==0 || head.next==null){return head;}ListNode curr = head;int num = 1;while(curr.next!=null){curr = curr.next;num++;}int temp = num - k%num;if(temp==num){return head;}curr.next = head; while(temp-->0){curr = curr.next;}ListNode res = curr.next;curr.next = null;return res;}
}

86. 分隔链表

题目

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

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

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

示例 2：

输入：head = [2,1], x = 2
输出：[1,2]

答案

class Solution {public ListNode partition(ListNode head, int x) {ListNode small = new ListNode(0);ListNode smallHead = small;ListNode large = new ListNode(0);ListNode largeHead = large;while(head!=null){if(head.val<x){small.next = head;small = small.next;head = head.next;}else{large.next = head;large = large.next;head = head.next;}}small.next = largeHead.next;large.next = null;return smallHead.next;}
}

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

答案

class LRUCache extends LinkedHashMap<Integer,Integer>{private int capacity;public LRUCache(int capacity) {super(capacity,0.75F,true);this.capacity = capacity;}public int get(int key) {return super.getOrDefault(key,-1);}public void put(int key, int value) {super.put(key,value);}@Overrideprotected boolean removeEldestEntry(Map.Entry<Integer,Integer> eldest){return super.size() > capacity;}}