力扣爆刷第103天之CodeTop100五连刷1-5

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

题目链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/
思路：求最长无重复子串，典型滑动窗口，用set记录是否重复，无重扩大窗口，有重缩小窗口，每次添加元素后更新最大值。

class Solution {public int lengthOfLongestSubstring(String s) {int max = 0;Set<Character> set = new HashSet<>();int slow = 0;for(int i = 0; i < s.length(); i++) {while(set.contains(s.charAt(i))) {set.remove(s.charAt(slow));slow++;}set.add(s.charAt(i));max = Math.max(max, set.size());}return max;}
}

二、206. 反转链表

题目链接：https://leetcode.cn/problems/reverse-linked-list/description/
思路：翻转链表采用头插法，一个指针指向虚拟头结点保持不动，另一个指针每次向后走，进行头插。

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

三、146. LRU 缓存

题目链接：https://leetcode.cn/problems/lru-cache/description/
思路：非常经典的题目，最近最少使用，我们需要构建一个双向链表和哈希表，其中双向链表应该有虚拟的头结点和尾结点，方便进行添加删除操作，其他的是常规操作。

class LRUCache {int capacity;Map<Integer, Node> map;DoubleList list;public LRUCache(int capacity) {this.capacity = capacity;map = new HashMap<>();list = new DoubleList();}public int get(int key) {if(!map.containsKey(key)) return -1;Node temp = map.get(key);makeRecently(temp);return temp.value;}public void put(int key, int value) {if(map.containsKey(key)) {Node temp = map.get(key);temp.value = value;makeRecently(temp);return;}if(list.size == capacity) {Node temp = list.deleteFirst();map.remove(temp.key);}Node temp = new Node(key, value);list.add(temp);map.put(key, temp);}void makeRecently(Node temp) {list.delete(temp);list.add(temp);}
}class DoubleList {int size = 0;Node start, end;DoubleList() {start = new Node();end = new Node();start.right = end;end.left = start;}void delete(Node temp) {temp.left.right = temp.right;temp.right.left = temp.left;temp.left = null;temp.right = null;size--;}Node deleteFirst() {if(start.right == end) return null;Node temp = start.right;delete(temp);return temp;}void add(Node temp) {end.left.right = temp;temp.left = end.left;temp.right = end;end.left = temp;size++;}
}class Node{int key, value;Node left, right;Node(){}Node(int k, int v) {key = k;value = v;}
}

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

题目链接：https://leetcode.cn/problems/kth-largest-element-in-an-array/description/
思路：使用快速排序超时，又要求时间复杂度为O(N)，使用桶排序最合数不过了。
桶排序：即把所有的数作为索引，放到一个新数组里去，即放到桶里，出现多次即累加，然后从后往前遍历减去次数，即可得到第K个最大的元素。

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

快排：

class Solution {public int findKthLargest(int[] nums, int k) {quickSort(nums, 0, nums.length-1);return nums[nums.length - k];}void quickSort(int[] nums, int left, int right) {if(left >= right) return;int base = nums[left];int i = left, j = right;while(i < j) {while(nums[j] >= base && i < j) j--;while(nums[i] <= base && i < j) i++;swap(nums, i, j);}swap(nums, left, j);quickSort(nums, left, j-1);quickSort(nums, j+1, right);}void swap(int[] nums, int x, int y) {int t = nums[x];nums[x] = nums[y];nums[y] = t;}
}

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

题目链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/description/
思路：

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 slow = root, fast =head;int i = 0;while(fast != null) {i++;fast = fast.next;if(i % k == 0) {slow = reverse(slow, fast);}}return root.next;}ListNode reverse(ListNode a, ListNode b) {ListNode r = a, p1 = a.next, p2 = p1;r.next = null;while(p1 != b) {ListNode pre = p1.next;p1.next = r.next;r.next = p1;p1 = pre;}p2.next = b;return p2;}}