链表
环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
题解答看下面那题就行了
环形链表二
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。
public ListNode detectCycle(ListNode head) {
if (null == head || null == head.next) {
return null;
}
ListNode slow = head;
ListNode fast = head.next;
//环的长度
int count = 1;
while (fast != null && fast.next != null && !slow.equals(fast)) {
slow = slow.next;
fast = fast.next.next;
count++;
}
if (fast == null || fast.next == null) {
return null;
}
ListNode l = head;
ListNode t = head;
while (count-- > 0) {
//其实这个就是slow指针
t = t.next;
}
while(!l.equals(t)){
l = l.next;
t = t.next;
}
return l;
}
反转链表
简单的经典题，不贴详情了
public ListNode reverseList(ListNode head) {
if(null == head || null == head.next){
return head;
}
ListNode pre = head;
ListNode cur = head.next;
head.next = null;
while(cur != null){
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
160. 相交链表
题目详情
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
题目解答
散列表
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Set<ListNode> aNodes = new HashSet<>();
while(headA != null){
aNodes.add(headA);
headA = headA.next;
}
while(headB != null && !aNodes.contains(headB)){
headB = headB.next;
}
return headB;
}
双指针
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (null == headA || null == headB) {
return null;
}
ListNode originHeadA = headA;
ListNode originHeadB = headB;
int aCount = 1, bCount = 1;
while (headA != null) {
aCount++;
headA = headA.next;
}
while (headB != null) {
bCount++;
headB = headB.next;
}
if (aCount >= bCount) {
for (int i = 0; i < aCount - bCount; i++) {
originHeadA = originHeadA.next;
}
} else {
for (int i = 0; i < bCount - aCount; i++) {
originHeadB = originHeadB.next;
}
}
while(originHeadA != originHeadB && null != originHeadA && null != originHeadB){
originHeadA = originHeadA.next;
originHeadB = originHeadB.next;
}
if(originHeadA == null || originHeadB == null){
return null;
} else {
return originHeadA;
}
}
234.回文链表
题目详情
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
题目解答
双指针，反转后面一半比对。
public boolean isPalindrome(ListNode head) {
if (null == head || null == head.next) {
return true;
}
ListNode halfStart = halfNode(head);
ListNode reverseHead = reverse(halfStart.next);
while (null != head && null != reverseHead) {
if(head.val != reverseHead.val){
return false;
}
head = head.next;
reverseHead = reverseHead.next;
}
reverse(halfStart.next);
return true;
}
private ListNode halfNode(ListNode head) {
ListNode slow = head;//1
ListNode fast = head;//1
while (null != fast.next && null != fast.next.next) {
slow = slow.next;//2
fast = fast.next.next;//2
}
return slow;
}
private ListNode reverse(ListNode head) {
ListNode pre = head;
ListNode next = pre.next;
head.next = null;
while (next != null) {
ListNode tmp = next.next;
next.next = pre;
pre = next;
next = tmp;
}
return pre;
}
148.排序链表
题目详情
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
题目解答
链表插入排序 O(n^2)，超时
public ListNode sortList(ListNode head) {
ListNode virtual = new ListNode(Integer.MAX_VALUE);
virtual.next = head;
ListNode cur = head;
ListNode pre = virtual;
while (null != cur) {
ListNode stPre = pre;
ListNode st = cur;
ListNode minPre = pre;
ListNode minNode = st;
while(null != st){
if(st.val < minNode.val){
minNode = st;
minPre = stPre;
}
stPre = st;
st = st.next;
}
minPre.next = minNode.next;
insertNext(minNode, pre);
pre = pre.next;
cur = pre.next;
}
return virtual.next;
}
private void insertNext(ListNode node, ListNode pre) {
ListNode next = pre.next;
pre.next = node;
node.next = next;
}
2022-11-11 因为要参加婚礼，先停一下，归并排序太麻烦了，今天的指标用个简单的题目
2022-11-15 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) 的平均时间复杂度运行。
题目解答
使用linkedHashMap
public static class LRUCache extends LinkedHashMap<Integer, Integer> {
private final 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
public boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}
少个hash表快了不少。
public static class LRUCache {
private int size;
private final int capacity;
private final Node head;
private final Node tail;
private final Map<Integer, Node> nodeMap;
public LRUCache(int capacity) {
this.capacity = capacity;
this.size = 0;
head = new Node(-1, -1);
tail = new Node(-1, -1);
head.next = tail;
tail.pre = head;
nodeMap = new HashMap<>(capacity);
}
public int get(int key) {
if (!nodeMap.containsKey(key)) {
return -1;
}
move2Head(nodeMap.get(key));
return nodeMap.get(key).value;
}
public void put(int key, int value) {
if(nodeMap.containsKey(key)){
Node node = nodeMap.get(key);
node.value = value;
move2Head(node);
return;
}
if(size >= capacity){
removeLast();
size--;
}
insert2Head(new Node(key, value));
size++;
}
private void move2Head(Node node){
Node pre = node.pre;
Node next = node.next;
pre.next = next;
next.pre = pre;
Node curFir = head.next;
head.next = node;
node.pre = head;
node.next = curFir;
curFir.pre = node;
}
private void insert2Head(Node node){
nodeMap.put(node.key, node);
Node next = head.next;
head.next = node;
node.pre = head;
node.next = next;
next.pre = node;
}
private void removeLast(){
Node last = tail.pre;
Node lastPre = last.pre;
lastPre.next = tail;
tail.pre = lastPre;
last.pre = null;
last.next = null;
nodeMap.remove(last.key);
}
public static class Node {
private Node pre;
private Node next;
private int key;
private int value;
public Node(int key, int value) {
this.key = key;
this.value = value;
pre = null;
next = null;
}
public Node(int key, int value, Node pre, Node next) {
this.key = key;
this.value = value;
this.pre = pre;
this.next = next;
}
}
}
简单链表实现，实际上移除元素是O(n)
public static class LRUCache {
private int size;
private final int capacity;
private final LinkedList<Integer> keySet;
private final Map<Integer, Integer> dataMap;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
keySet = new LinkedList<>();
dataMap = new HashMap<>(capacity);
}
public int get(int key) {
if(!dataMap.containsKey(key)){
return -1;
}
keySet.remove((Object)key);
keySet.addFirst(key);
return dataMap.get(key);
}
public void put(int key, int value) {
//是否存在，如果存在放到首位
if (dataMap.containsKey(key)) {
dataMap.put(key, value);
//O(n)
keySet.remove((Object)key);
keySet.addFirst(key);
return;
}
//是否满了，满了淘汰
if (size == capacity) {
int removeKey = keySet.removeLast();
dataMap.remove((Object)removeKey);
size--;
}
//插入
keySet.addFirst(key);
dataMap.put(key, value);
size++;
}
}
思考了下，可以用哈希表记录链表的位置，这样删除插入都是O(1)，使用LinkList比较难搞，官方答案自己写了个链表。 自己写了个，快了不少但还是很慢。
public static class LRUCache {
private int size;
private final int capacity;
private final Node head;
private final Node tail;
private final Map<Integer, Node> nodeMap;
private final Map<Integer, Integer> dataMap;
public LRUCache(int capacity) {
this.capacity = capacity;
this.size = 0;
head = new Node(-1);
tail = new Node(-1);
head.next = tail;
tail.pre = head;
nodeMap = new HashMap<>(capacity);
dataMap = new HashMap<>(capacity);
}
public int get(int key) {
if (!dataMap.containsKey(key)) {
return -1;
}
move2Head(nodeMap.get(key));
return dataMap.get(key);
}
public void put(int key, int value) {
if(dataMap.containsKey(key)){
dataMap.put(key, value);
move2Head(nodeMap.get(key));
return;
}
if(size >= capacity){
Node lastNode = removeLast();
dataMap.remove(lastNode.val);
size--;
}
insert2Head(new Node(key));
dataMap.put(key, value);
size++;
}
private void move2Head(Node node){
Node pre = node.pre;
Node next = node.next;
pre.next = next;
next.pre = pre;
Node curFir = head.next;
head.next = node;
node.pre = head;
node.next = curFir;
curFir.pre = node;
}
private void insert2Head(Node node){
nodeMap.put(node.val, node);
Node next = head.next;
head.next = node;
node.pre = head;
node.next = next;
next.pre = node;
}
private Node removeLast(){
Node last = tail.pre;
Node lastPre = last.pre;
lastPre.next = tail;
tail.pre = lastPre;
last.pre = null;
last.next = null;
nodeMap.remove(last.val);
return last;
}
public static class Node {
private Node pre;
private Node next;
private int val;
public Node(int val) {
this.val = val;
pre = null;
next = null;
}
public Node(int val, Node pre, Node next) {
this.val = val;
this.pre = pre;
this.next = next;
}
}
}
少个hash表快了不少。
public static class LRUCache {
private int size;
private final int capacity;
private final Node head;
private final Node tail;
private final Map<Integer, Node> nodeMap;
public LRUCache(int capacity) {
this.capacity = capacity;
this.size = 0;
head = new Node(-1, -1);
tail = new Node(-1, -1);
head.next = tail;
tail.pre = head;
nodeMap = new HashMap<>(capacity);
}
public int get(int key) {
if (!nodeMap.containsKey(key)) {
return -1;
}
move2Head(nodeMap.get(key));
return nodeMap.get(key).value;
}
public void put(int key, int value) {
if(nodeMap.containsKey(key)){
Node node = nodeMap.get(key);
node.value = value;
move2Head(node);
return;
}
if(size >= capacity){
removeLast();
size--;
}
insert2Head(new Node(key, value));
size++;
}
private void move2Head(Node node){
Node pre = node.pre;
Node next = node.next;
pre.next = next;
next.pre = pre;
Node curFir = head.next;
head.next = node;
node.pre = head;
node.next = curFir;
curFir.pre = node;
}
private void insert2Head(Node node){
nodeMap.put(node.key, node);
Node next = head.next;
head.next = node;
node.pre = head;
node.next = next;
next.pre = node;
}
private void removeLast(){
Node last = tail.pre;
Node lastPre = last.pre;
lastPre.next = tail;
tail.pre = lastPre;
last.pre = null;
last.next = null;
nodeMap.remove(last.key);
}
public static class Node {
private Node pre;
private Node next;
private int key;
private int value;
public Node(int key, int value) {
this.key = key;
this.value = value;
pre = null;
next = null;
}
public Node(int key, int value, Node pre, Node next) {
this.key = key;
this.value = value;
this.pre = pre;
this.next = next;
}
}
}
23. 合并K个升序链表
题目详情
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6
题目解答
集体遍历的方法，通过了，但很慢 O(nk^2)
public ListNode mergeKLists(ListNode[] lists) {
if (null == lists || lists.length == 0) {
return null;
}
if (lists.length == 1) {
return lists[0];
}
CurListNodes listNodes = new CurListNodes(lists);
ListNode faker = new ListNode(-1);
ListNode pre = faker;
int oneList = listNodes.oneList();
if (oneList == -1) {
return null;
}
while (oneList == -2) {
int index = listNodes.maxNode();
pre.next = listNodes.curs[index];
pre = pre.next;
listNodes.indexPlus(index);
oneList = listNodes.oneList();
}
ListNode last = listNodes.curs[oneList];
while (last != null) {
pre.next = last;
pre = pre.next;
last = last.next;
}
return faker.next;
}
private static class CurListNodes {
private ListNode[] curs;
public CurListNodes(ListNode[] nodes) {
curs = new ListNode[nodes.length];
System.arraycopy(nodes, 0, curs, 0, nodes.length);
}
public int maxNode() {
int min = Integer.MAX_VALUE;
int index = -1;
for (int i = 0; i < curs.length; i++) {
if (null != curs[i] && curs[i].val < min) {
min = curs[i].val;
index = i;
}
}
return index;
}
public void indexPlus(int index) {
curs[index] = curs[index].next;
}
public int oneList() {
int count = 0;
int index = -1;
for (int i = 0; i < curs.length; i++) {
if (curs[i] != null) {
count++;
index = i;
}
}
if (count == 0) {
return -1;
}
return count == 1 ? index : -2;
}
}
分治法 O(nk*log(n))
public ListNode mergeKLists(ListNode[] lists) {
return merge(lists, 0, lists.length - 1);
}
public ListNode merge(ListNode[] lists, int l, int r) {
if (l == r) {
return lists[l];
}
if (l > r) {
return null;
}
int mid = (l + r) >> 1;
return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
}
public ListNode mergeTwoLists(ListNode a, ListNode b) {
if (a == null || b == null) {
return a != null ? a : b;
}
ListNode head = new ListNode(0);
ListNode tail = head, aPtr = a, bPtr = b;
while (aPtr != null && bPtr != null) {
if (aPtr.val < bPtr.val) {
tail.next = aPtr;
aPtr = aPtr.next;
} else {
tail.next = bPtr;
bPtr = bPtr.next;
}
tail = tail.next;
}
tail.next = (aPtr != null ? aPtr : bPtr);
return head.next;
}
