本文主要是介绍力扣爆刷第103天之CodeTop100五连刷1-5,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
力扣爆刷第103天之CodeTop100五连刷1-5
文章目录
- 力扣爆刷第103天之CodeTop100五连刷1-5
- 一、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) {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;}}
这篇关于力扣爆刷第103天之CodeTop100五连刷1-5的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!