byu_rself

LC.P1751[最多可以参加的会议数目II] 方法一：动态规划+二分查找12345678910111213141516171819202122232425class Solution { public int maxValue(int[][] events, int k) { Arrays.sort(events, (a, b) -> a[1] - b[1]); int n = events.length; int[][] f = new int[n + 1][k + 1]; for (int i = 0; i < n; ++i) { int p = search(events, i, events[i][0]); for (int j = 1; j <= k; ++j) { f[i + 1][j] = Math.max(f[i][j], f[p + 1][j - 1] + events[i] ...

LC.P1375[二进制字符串前缀一致的次数] 方法一：维护最大值12345678910class Solution { public int numTimesAllBlue(int[] flips) { int ans = 0, max = 0, n = flips.length; for (int i = 0; i < n; ++i) { max = Math.max(max, flips[i]); if (max == i + 1) ++ans; } return ans; }} 时间复杂度：$O(n)$ 空间复杂度：$O(1)$

Offer.P4[二维数组中的查找] 方法一：Z字形查找1234567891011class Solution { public boolean findNumberIn2DArray(int[][] matrix, int target) { int i = matrix.length - 1, j = 0; while (i >= 0 && j < matrix[0].length) { if (matrix[i][j] > target) --i; else if (matrix[i][j] < target) ++j; else return true; } return false; }} 时间复杂度：$O(m + n)$ 空间复杂度：$O(1)$ 方法二：二分查找12345678910111213141516class Solution ...

LC.P1760[袋子里最少数目的球] 方法一：二分查找123456789101112131415class Solution { public int minimumSize(int[] nums, int maxOperations) { int left = 1, right = (int) 1e9; while (left < right) { int mid = left + right >> 1; long s = 0; for (int x : nums) { s += (x - 1) / mid; } if (s <= maxOperations) right = mid; else left = mid + 1; } return right; }& ...

LC.P2475[数组中不等三元组的数目] 方法一：暴力12345678910111213class Solution { public int unequalTriplets(int[] nums) { int n = nums.length, ans = 0; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { for (int k = j + 1; k < n; ++k) { if (nums[i] != nums[j] && nums[i] != nums[k] && nums[j] != nums[k]) ++ans; } } } return ans; } ...

LC.P1483[树节点的第K个祖先] 方法一：倍增12345678910111213141516171819202122232425262728293031323334class TreeAncestor { int[][] p; int m; public TreeAncestor(int n, int[] parent) { m = 32 - Integer.numberOfLeadingZeros(n); // n的二进制长度 p = new int[n][m]; for (int i = 0; i < n; ++i) p[i][0] = parent[i]; for (int i = 0; i < m - 1; ++i) { for (int x = 0; x < n; ++x) { int cur = p[x][i]; p[x][i + 1] = cur < ...

LC.P438[找到字符串中所有字母异位词] 方法一：滑动窗口123456789101112131415161718192021class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> ans = new ArrayList<>(); int n = s.length(), m = p.length(); int[] c1 = new int[26], c2 = new int[26]; for (int i = 0; i < m; ++i) ++c2[p.charAt(i) - 'a']; for (int l = 0, r = 0; r < n; ++r) { ++c1[s.charAt(r) - 'a']; if (r - l + ...

LC.P1171[从链表中删去总和值为零的连续节点] 方法一：前缀和+哈希表12345678910111213141516171819202122232425262728293031/** * 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 removeZeroSumSublists(ListNode head) { ListNode dummy = new ListNo ...

LC.P215[数组中的第K个最大元素] 方法一：大根堆12345678910class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a); for (int num : nums) q.offer(num); while (k-- > 1) { q.poll(); } return q.peek(); }} 时间复杂度：$O(nlogn)$ 空间复杂度：$O(n)$ 方法二：小根堆1234567891011121314class Solution { public int findKthLargest(int[] nums, int k) { Prio ...

LC.P1170[比较字符串最小字母出现频次] 方法一：后缀和12345678910111213141516171819202122232425262728293031class Solution { public int[] numSmallerByFrequency(String[] queries, String[] words) { int n = queries.length; int[] cnt = new int[12]; for (String word : words) ++cnt[f(word)]; for (int i = 9; i >= 1; --i) { cnt[i] += cnt[i + 1]; } int[] ans = new int[n]; for (int i = 0; i < n; ++i) { String s = queries[i]; ...