LFU缓存结构设计&&重排链表&&删除有序链表中重复的元素-I
1、解题思路
使用LinkedHashMap解决，LinkedHashMap能保证插入的顺序，能解决相同set，get次数找到最早get和set的那个key。
2、代码
import java.util.*; public class Solution { private int getMinFreqKey(Map<Integer, Integer> map) { int count = Integer.MAX_VALUE; int key = 0; for (Map.Entry<Integer, Integer> entry : map.entrySet()) { if (entry.getValue() < count) { count = entry.getValue(); key = entry.getKey(); } } return key; } public int[] LFU(int[][] operators, int k) { Map<Integer, Integer> map = new LinkedHashMap<>(); Map<Integer, Integer> keyToFreq = new LinkedHashMap<>(); List<Integer> list = new LinkedList<>(); for (int i = 0; i < operators.length; i++) { int operator = operators[i][0]; int key = operators[i][1]; if (operator == 1) { int value = operators[i][2]; if (map.containsKey(key)) { map.put(key, value); keyToFreq.put(key, keyToFreq.get(key) + 1); } else { if (map.size() == k) { int minKey = getMinFreqKey(keyToFreq); map.remove(minKey); keyToFreq.remove(minKey); } map.put(key, value); keyToFreq.put(key, keyToFreq.getOrDefault(key, 0) + 1); } } else { if (map.containsKey(key)) { int val = map.get(key); keyToFreq.put(key, keyToFreq.get(key) + 1); list.add(val); } else { list.add(-1); } } } int[] arr = new int[list.size()]; for (int i = 0; i < arr.length; i++) { arr[i] = list.get(i); } return arr; } } 复制代码NC2 重排链表
题目链接
1、解题思路
找到尾部的进行截断，对后半部分采取头插逆序，然后两个链表交叉插入就行。注意，截断的时候，要把尾结点的next置空。
2、代码
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { private int getLen(ListNode head) { int res = 0; ListNode temp = head; while (temp != null) { res = res + 1; temp = temp.next; } return res; } public void reorderList(ListNode head) { int len = getLen(head); if(len == 0 || len == 1){ return; } ListNode temp = head; ListNode dummy = new ListNode(0); ListNode pre = null; for (int i = 1; i < (len + 1) / 2; i++) { temp = temp.next; } pre = temp.next; temp.next = null; temp = pre; while (temp != null) { ListNode node = temp.next; temp.next = dummy.next; dummy.next = temp; temp = node; } ListNode head1 = dummy.next; temp = head; while (head1 != null) { System.out.printf("%d %d\n", temp.val, head1.val); ListNode node = head1.next; head1.next = temp.next; temp.next = head1; temp = temp.next.next; head1 = node; } } } 复制代码NC25 删除有序链表中重复的元素-I
题目链接
1、解题思路
题目中没有给头结点，创造头结点，然后while循环模拟删除就可以了。
2、代码
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * * @param head ListNode类 * @return ListNode类 */ public ListNode deleteDuplicates (ListNode head) { // write code here ListNode temp = head; while (temp != null) { int val = temp.val; ListNode node = temp.next; while (node != null && node.val == val) { temp.next = node.next; node = temp.next; } temp = node; } return head; } }
作者：jdq8576
链接：https://juejin.cn/post/7023945192965144590