byu_rself

LC.P1834[单线程CPU] 方法一：排序+优先队列1234567891011121314151617181920212223242526272829class Solution { public int[] getOrder(int[][] tasks) { int n = tasks.length; int[] ans = new int[n]; int[][] index = new int[n][3]; // {入队时间,执行时间,原任务编号} for (int i = 0; i < n; ++i) index[i] = new int[]{tasks[i][0], tasks[i][1], i}; Arrays.sort(index, (a, b) -> a[0] - b[0]); // 按入队时间进行升序 // 先按 执行时间 排序，再按 任务编号 排序 PriorityQueue<int[ ...

LC.P1010[总持续时间可被60整除的歌曲] 方法一：数学1234567891011121314class Solution { public int numPairsDivisibleBy60(int[] time) { int[] cnt = new int[60]; int ans = 0; for (int i : time) { i %= 60; int j = (60 - i) % 60; // 先查询再更新，题目要求 i < j ans += cnt[j]; ++cnt[i]; } return ans; }} 时间复杂度：$O(n)$ 空间复杂度：$O(M)$，$M = 60$

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) { ...