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

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

文章目录

• • • 力扣爆刷第149天之TOP100五连刷（LRU、K个一组）
    • 一、3. 无重复字符的最长子串
    • 二、206. 反转链表
    • 三、146. LRU 缓存
    • 四、215. 数组中的第K个最大元素
    • 五、25. 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;
}
}