142. 环形链表 II【中等】
142.环形链表 II
中等
2.1K
相关企业
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：
链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引
进阶：你是否可以使用 O(1) 空间解决此题？
哈希表
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { if (head ==null){ return null; } //哈希表 Set<ListNode> set=new HashSet<>(); ListNode cur=head; while (cur!=null){ if (set.contains(cur)){ return cur; } set.add(cur); cur=cur.next; } return null; } }
前后指针
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { if (head ==null){ return null; } //前后指针 ListNode slow= head; ListNode fast= head; while (fast!=null){ slow=slow.next; if (fast.next != null) { //小心空指针 fast = fast.next.next; } else { return null; } //while(true) if(fast==null||fast.next == null) return null; if (fast==slow){ //ptr和slow相遇就是入环点 ListNode ptr = head; while (ptr != slow) { ptr = ptr.next; slow = slow.next; } return ptr; } } return null; } }
快慢指针
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { ListNode low=head; ListNode fast=head; while(fast!=null&&fast.next!=null){ low=low.next; fast=fast.next.next; if(low==fast){ ListNode node=head; while(node!=low){ node=node.next; low=low.next; } return node; } } return null; } }
146. LRU 缓存【中等】
146.LRU 缓存
中等
2.5K
相关企业
请你设计并实现一个满足 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
参考
哈希表+双向链表
public class LRUCache { class DLinkedNode { int key; int value; DLinkedNode prev; DLinkedNode next; public DLinkedNode() {} public DLinkedNode(int _key, int _value) {key = _key; value = _value;} } private Map<Integer, DLinkedNode> cache = new HashMap<Integer, 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; } // 如果 key 存在，先通过哈希表定位，再移到头部 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; if (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 res = tail.prev; removeNode(res); return res; } }
Java的API：LinkedHashMap
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); } @Override protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) { return size() > capacity; } }
148. 排序链表
148.排序链表
中等
2K
相关企业
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1： 输入：head = [4,2,1,3] 输出：[1,2,3,4] 示例 2： 输入：head = [-1,5,3,4,0] 输出：[-1,0,3,4,5] 示例 3： 输入：head = [] 输出：[]
提示：
链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105
进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
快排，超出时间限制
/** * 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 sortList(ListNode head) { quickSort(head,null); return head; } public void quickSort(ListNode head, ListNode end){ if(head != end){ ListNode p1 = head; ListNode p2 = head; while (p2 != end){ if(p2.val < head.val){ p1 = p1.next; int temp = p1.val; p1.val = p2.val; p2.val = temp; } p2 = p2.next; } //p1与基准交换 if(p1 != head){ int temp = p1.val; p1.val = head.val; head.val = temp; } quickSort(head,p1); quickSort(p1.next,end); } } }
参考-归并排序
/** * 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 sortList(ListNode head) { return sortList(head,null); } public ListNode sortList(ListNode head,ListNode tail){ if(head==null){ return head; } if(head.next==tail){ head.next=null; return head; } //快慢指针找中点 ListNode slow=head,fast=head; while(fast!=tail){ slow=slow.next; fast=fast.next; if(fast!=tail){ fast=fast.next; } } //分治 ListNode mid=slow; ListNode list1=sortList(head,mid); ListNode list2=sortList(mid,tail); ListNode sorted=merge(list1,list2); return sorted; } //合并 public ListNode merge(ListNode head1,ListNode head2){ ListNode dummyHead=new ListNode(0); ListNode temp=dummyHead,temp1=head1,temp2=head2; while(temp1!=null&&temp2!=null){ if(temp1.val<=temp2.val){ temp.next=temp1; temp1=temp1.next; }else{ temp.next=temp2; temp2=temp2.next; } temp=temp.next; } if(temp1!=null){ temp.next=temp1; }else if(temp2!=null){ temp.next=temp2; } return dummyHead.next; } }
152. 乘积最大子数组
152.乘积最大子数组
中等
2K
相关企业
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
示例 1: 输入: nums = [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。 示例 2: 输入: nums = [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
提示:
1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数
参考-动态规划
class Solution { public int maxProduct(int[] nums) { int length=nums.length; int[] maxF=new int[length]; int[] minF=new int[length]; System.arraycopy(nums, 0, maxF, 0, length); System.arraycopy(nums, 0, minF, 0, length); for(int i=1;i<length;i++){ maxF[i]=Math.max(maxF[i-1]*nums[i],Math.max(nums[i],minF[i-1]*nums[i])); minF[i]=Math.min(minF[i-1]*nums[i],Math.min(nums[i],maxF[i-1]*nums[i])); } int ans=maxF[0]; for(int i=1;i<length;i++){ ans=Math.max(ans,maxF[i]); } return ans; } }
155. 最小栈
155.最小栈
提示
中等
1.6K
相关企业
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
示例 1: 输入： ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] 输出： [null,null,null,null,-3,null,0,-2] 解释： MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.
提示：
-231 <= val <= 231 - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3 * 104 次
参考
class MinStack { Deque<Integer> xStack; //辅助栈 同步操作 Deque<Integer> minStack; public MinStack() { xStack = new LinkedList<Integer>(); minStack = new LinkedList<Integer>(); minStack.push(Integer.MAX_VALUE); } public void push(int val) { xStack.push(val); minStack.push(Math.min(val,minStack.peek())); } public void pop() { xStack.pop(); minStack.pop(); } public int top() { return xStack.peek(); } public int getMin() { return minStack.peek(); } } /** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(val); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */
160. 相交链表【简单】
简单
1.9K
相关企业
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
hash表
双指针
/** * 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) { if(headA==null||headB==null){ return null; } ListNode pA = headA, pB = headB; while (pA != pB) { pA = pA == null ? headB : pA.next; pB = pB == null ? headA : pB.next; } return pA; } }
