byu_rself

LC.P373[查找和最小的K对数字] 方法一：优先队列123456789101112131415class Solution { public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) { PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> (nums1[a[0]] + nums2[a[1]]) - (nums1[b[0]] + nums2[b[1]])); for (int i = 0; i < Math.min(nums1.length, k); ++i) { q.offer(new int[]{i, 0}); } List<List<Integer>> ans = new ArrayList<> ...

LC.P1419[数青蛙] 方法一：计数+模拟123456789101112131415161718192021222324252627class Solution { public int minNumberOfFrogs(String croakOfFrogs) { int c = 0, r = 0, o = 0, a = 0, k = 0, ans = 0; for (char x : croakOfFrogs.toCharArray()) { if (x == 'c') { if (k > 0) --k; else ++ans; ++c; } else if (x == 'r') { --c; ++r; } else ...

LC.P641[设计循环双端队列] 方法一：双指针+数组1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071class MyCircularDeque { int[] data; int size, head, tail; public MyCircularDeque(int k) { data = new int[k]; size = 0; head = 0; tail = k - 1; } public boolean insertFront(int value) { if (isFull()) return false; head = head == 0 ? data.length - 1 : head - 1; // ...

LC.P432[全O(1)的数据结构] 方法一：双向链表+哈希表123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108class AllOne { Node head, tail; Map<String, Node> map; public AllOne() { map = new HashMap<>(); head = new Node(-1); tail = new Node(-1); head.next = tail; tail.prev = head; } ...

LC.P2432[处理用时最长的那个任务的员工] 方法一：直接遍历123456789101112131415class Solution { public int hardestWorker(int n, int[][] logs) { int ans = 0, max = 0, last = 0; for (int[] log : logs) { int id = log[0], time = log[1]; time -= last; if (max < time || (max == time && ans > id)) { max = time; ans = id; } last += time; } return ans; }} 时 ...

LC.P146[LRU缓存] 方法一：手写LRU12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970class LRUCache { private static class Node { int key, value; Node prev, next; Node(int key, int value) { this.key = key; this.value = value; } } int capacity; Node dummy = new Node(0, 0); // 哨兵节点 Map<Integer, Node> map = new HashMap<>(); pu ...

LC.P2106[摘水果] 方法一：双指针1234567891011121314class Solution { public int maxTotalFruits(int[][] fruits, int startPos, int k) { int ans = 0, sum = 0; for (int i = 0, j = 0; j < fruits.length; ++j) { int pos = fruits[j][0], cnt = fruits[j][1]; sum += cnt; while (i <= j && pos - fruits[i][0] + Math.min(Math.abs(startPos - fruits[i][0]), Math.abs(startPos - pos)) > k) { sum -= fruits[i++][1]; ...

LC.P460[LFU缓存] 方法一：哈希表+双向链表12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091class LFUCache { Map<Integer, Node> keyToNode = new HashMap<>(); Map<Integer, Node> freqToDummy = new HashMap<>(); int capacity; int minFreq; public LFUCache(int capacity) { this.capacity = capacity; } public int get(int key) { ...

LC.P1003[检查替换后的词是否有效] 方法一：栈1234567891011121314class Solution { public boolean isValid(String s) { int n = s.length(); if (n % 3 != 0) return false; StringBuilder stack = new StringBuilder(); for (char c : s.toCharArray()) { stack.append(c); if (stack.length() >= 3 && "abc".equals(stack.substring(stack.length() - 3))) { stack.delete(stack.length() - 3, stack.length()); } ...

LC.P138[复制带随机指针的链表] 方法一：哈希表12345678910111213141516171819202122232425262728293031323334/*// Definition for a Node.class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; }}*/class Solution { public Node copyRandomList(Node head) { if (head == null) return null; Node p = head; // key:原节点 value:新节点 Map<Node, Node> map = new HashMap ...