力扣爆刷第149天之TOP100五连刷（LRU、K个一组）

力扣爆刷第149天之TOP100五连刷（LRU、K个一组）

一、3. 无重复字符的最长子串

题目链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/
思路：求最长无重复子串，非常经典的一个题目，使用滑动窗口，外加一个set集合，只要元素不重复就一直扩大窗口，重复了就缩小窗口。

class Solution {public int lengthOfLongestSubstring(String s) {Set<Character> set = new HashSet<>();int left = 0, right = 0, max = 0;while(right < s.length()) {char cr = s.charAt(right++);while(set.contains(cr)) {set.remove(s.charAt(left++));}max = Math.max(max, right - left);set.add(cr);}return max;}
}

二、206. 反转链表

题目链接：https://leetcode.cn/problems/reverse-linked-list/description/
思路：经典翻转链表，头插法、尾插法任军选择。

class Solution {public ListNode reverseList(ListNode head) {ListNode root = new ListNode();ListNode cur = head, pre = null;while(cur != null) {pre = cur.next;cur.next = root.next;root.next = cur;cur = pre;}return root.next;}
}

三、146. LRU 缓存

题目链接：https://leetcode.cn/problems/lru-cache/description/
思路：LRU经典题目，最近最少使用，内部结构是map和双向链表，每次访问之后的节点都会移动到链表尾部，往链表里添加元素数量超过容量以后，会删除最久未访问的，就是删除链表的首部，由此便理解了LRU该如果设计。
首先需要设计一个map和一个双向链表，链表节点需要有key和value和前驱和后继，由此定义结构。
然后定义行为，双向链表的行为，要从双向链表本身出发，即双向链表添加节点和删除节点。
以上便完成了基础建设，要开始构造LRU的行为了，添加元素，需要看看是否超出容量，然后把修改后的节点或者新节点移动到尾部，获取元素，也是把访问之后的节点，从链表中删除然后加入尾部。
理解上面的几句话便可以写出LRU的代码。

class LRUCache {Map<Integer, Node> map;DoubleList list;int capacity;public LRUCache(int capacity) {map = new HashMap<>(capacity);this.capacity = capacity;list = new DoubleList();}public int get(int key) {if(map.containsKey(key)) {Node n = map.get(key);list.remove(n);list.add(n);return n.v;}else{return -1;}}public void put(int key, int value) {if(map.containsKey(key)) {Node n = map.get(key);n.v = value;list.remove(n);list.add(n);}else{Node n = new Node(key, value);map.put(key, n);list.add(n);if(map.size() > capacity) {Node t = list.removeFirst();map.remove(t.k);}}}}class DoubleList {Node head, tail;public DoubleList() {head = new Node();tail = new Node();head.right = tail;tail.left = head;}void add(Node n) {tail.left.right = n;n.left = tail.left;n.right = tail;tail.left = n;}Node removeFirst() {Node t = head.right;head.right = t.right;t.right.left = head;t.left = null;t.right = null;return t;}void remove(Node t) {t.left.right = t.right;t.right.left = t.left;t.left = null;t.right = null;}
}class Node {int k, v;Node left, right;public Node(){}public Node(int k, int v) {this.k = k;this.v = v;}
}

四、215. 数组中的第K个最大元素

题目链接：https://leetcode.cn/problems/kth-largest-element-in-an-array/description/
思路：求数组中的第K个最大的元素，本题可以先不着急排序，可以先看看数值的边界条件，正负10000，数据量不大，可以空间换时间，采用桶排序，桶排序顾名思义就是根据数值范围设置一系列的桶，元素只要出现了就添加到桶里面去，要求最大的第K个元素然后从最大的桶开始遍历即可，非常便捷。

class Solution {public int findKthLargest(int[] nums, int k) {int[] bucket = new int[20001];for(int i : nums) {bucket[10000+i]++;}for(int i = 20000; i >= 0; i--) {k = k - bucket[i];if(k <= 0) return i - 10000;}return -1;}}

五、25. K 个一组翻转链表

题目链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/description/
思路：K个一组翻转链表，给链表加上虚拟头结点，然后每K个一组进行翻转，具体采用头插法或者尾插法都可以，本题我采用头插法，如果采用头插法需要在知道头和尾的情况下进行，头是不动的，属于需要翻转的k个节点的前一个，尾也也是不动的，是需要翻转的k个节点的下一个。然后每次翻转都需要知道这两个节点，然后才能进行翻转，并且把翻转过程抽离出来。

/*** 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 reverseKGroup(ListNode head, int k) {ListNode root = new ListNode(-1, head);ListNode left = root, right = head;int i = 0;while(right != null) {right = right.next;i++;if(i % k == 0) {left = reverse(left, right);left.next = right;}}return root.next;}ListNode reverse(ListNode start, ListNode end) {ListNode cur = start.next, pre = null, res = start.next;start.next = null;while(cur != end) {pre = cur.next;cur.next = start.next;start.next = cur;cur = pre;}return res;}}