做网站有哪些好公司,奉贤集团公司网站建设,老兵老兵建设集团有限公司,做散热网站目录
19.删除链表的倒数第N个结点 82.删除排序链表中的重复元素Ⅱ 61. 旋转链表 86.分隔链表 146.LRU缓存 19.删除链表的倒数第N个结点 题意#xff1a; 给你一个链表#xff0c;删除链表的倒数第 n 个结点#xff0c;并且返回链表的头结点。 【输入样例】head [1,2,3,4,5…
目录
19.删除链表的倒数第N个结点 82.删除排序链表中的重复元素Ⅱ 61. 旋转链表 86.分隔链表 146.LRU缓存 19.删除链表的倒数第N个结点 题意 给你一个链表删除链表的倒数第 n 个结点并且返回链表的头结点。 【输入样例】head [1,2,3,4,5],n2 【输出样例】[1,2,3,5] 解题思路 1. 双指针p和q初始哈指向头节点 2. 移动q直到p和q之间相隔的元素为n 3. 同时移动p和q直到q指向链表结尾的null 4. p.next p.next.next /*** 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(0,head);ListNode p dummyHead;ListNode q head;for(int i0; i n; i){q q.next;}while(q ! null){q q.next;p p.next;}p.next p.next.next;ListNode ans dummyHead.next;return ans;}
} 时间 击败了100.00% 内存 击败了64.22% 82.删除排序链表中的重复元素Ⅱ 题意 给定一个已排序的链表的头 head 删除原始链表中所有重复数字的节点只留下不同的数字 。返回 已排序的链表 。 【输入样例】head [1,1,1,2,3] 【输出样例】[2,3] 解题思路 1. 定义一个哑节点指向链表的头节点 2. 指针cur指向哑节点遍历链表 3. 如果cur.next.val cur.next.next.val,将cur.next以及后面拥有相同元素x(xcur.next.val)的节点全部删除 4. 不断移除重复元素直到cur.next是空节点或元素值不等于x /*** 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) {if(head null){return head;}ListNode dummy new ListNode(0,head);ListNode cur dummy;while(cur.next ! null cur.next.next ! null){if(cur.next.val cur.next.next.val){int x cur.next.val;while(cur.next ! null cur.next.val x){cur.next cur.next.next;//不断跳过重复值的数}}else{cur cur.next;//继续往下遍历}}return dummy.next;//指向head}
} 时间 击败了100.00% 内存 击败了86.54% 61. 旋转链表 题意 给你一个链表的头节点 head 旋转链表将链表每个节点向右移动 k 个位置。 【输入样例】head [1,2,3,4,5],k2 【输出样例】[4,5,1,2,3] 解题思路 1. 定义一个哑节点指向链表的头节点 2. 遍历链表统计链表的长度优化移动次数为k%n; 3. 将原始链表形成闭环并计算count n-k%n,表示从当前节点开始遍历count次可以找到尾节点 4. 不断移动指针直到count 0此时定义一个新节点指向dummy.next作为新链表的头节点dummy.next赋值null实现断链 /*** 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(k 0 || headnull || head.next null){return head;}//一次遍历统计链表的长度n移动k次相当于移动k%n次int n 1;ListNode dummy head;while(dummy.next !null){dummy dummy.next;n;}int count n - k % n;if(count n){return head;}dummy.next head;//形成闭环while(count-- 0){dummy dummy.next;}ListNode result dummy.next;dummy.next null;return result;}
} 时间 击败了100.00% 内存 击败了68.97% 86.分隔链表 题意 给你一个链表的头节点 head 和一个特定值 x 请你对链表进行分隔使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 你应当 保留 两个分区中每个节点的初始相对位置。 【输入样例】head [1,4,3,2,5,2],x3 【输出样例】[1,2,2,4,3,5] 解题思路 1.借助两个链表一个存储小于x的节点一个存储大于等于x的节点之后将两个链表进行拼接即可。 /*** 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 minNext new ListNode(0);ListNode minhead minNext;ListNode maxNext new ListNode(0);ListNode maxhead maxNext;while(head!null){if(head.val x){minNext.next head;minNext minNext.next;}else{maxNext.next head;maxNext maxNext.next;}head head.next;}maxNext.next null;minNext.next maxhead.next;return minhead.next;}
} 时间 击败了100.00% 内存 击败了20.49% 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); // 缓存是 {11}
lRUCache.put(2, 2); // 缓存是 {11, 22}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废缓存是 {11, 33}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废缓存是 {44, 33}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4 解题思路哈希表双向链表 1. 双向链表按照被使用的顺序存储键值对最靠近头部的键值对是最近使用的最靠近尾部的键值对是最久未使用的。 2. 哈希表缓存数据的键映射到其在双向链表中的位置 3. 使用哈希表进行定位找出缓存项在双向链表中的位置并将其移动到双向链表的头部如果key不存着哈希表中则返回-1或者在链表的头部新建一个节点。 public class LRUCache {private MapInteger,DLinkedNode cache new HashMapInteger,DLinkedNode();private int size;private int capacity;private DLinkedNode head,tail;public LRUCache(int capacity) {this.size 0;this.capacity capacity;head new DLinkedNode();tail new DLinkedNode();head.next tail;tail.prev head;}public int get(int key) {DLinkedNode node cache.get(key);if(node null){//链表中不存在此值return -1;}//存在将其移动到双向链表的头部moveToHead(node);return node.value;}public void put(int key, int value) {DLinkedNode node cache.get(key);if(node null){//如果key不存着要创建一个新节点//需要判断插入之后长度是否会超过容量DLinkedNode newNode new DLinkedNode(key,value);cache.put(key,newNode);addToHead(newNode);size;//每加进来一个元素sizeif(size capacity){//删除尾部节点和哈希表中的对应项DLinkedNode tail removeTail();cache.remove(tail.key);--size;}}else{//key存在哈希表定位修改value移到头部node.value value;moveToHead(node);}}private void addToHead(DLinkedNode node){//添加到双向链表头部node.prev head;node.next head.next;head.next.prev node;head.next node;}private void removeNode(DLinkedNode node){//从当前位置移走node.prev.next node.next;node.next.prev node.prev;}private void moveToHead(DLinkedNode node){removeNode(node);addToHead(node);}private DLinkedNode removeTail(){DLinkedNode node tail.prev;removeNode(node);return node;}
}class DLinkedNode{int key;int value;DLinkedNode prev;DLinkedNode next;public DLinkedNode(){}public DLinkedNode(int key, int value){this.key key;this.value value;}
}
/*** 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);*/ 时间 击败了23.27% 内存 击败了97.38%
