byu_rself

LC.P11[盛最多水的容器] 方法一：双指针1234567891011class Solution { public int maxArea(int[] height) { int ans = 0, left = 0, right = height.length - 1; while (left < right) { ans = Math.max(ans, (right - left) * Math.min(height[left], height[right])); if (height[left] < height[right]) ++left; else --right; } return ans; }} 时间复杂度：$O(n)$ 空间复杂度：$O(1)$

LC.P318[最大单词长度乘积] 方法一：位运算1234567891011121314151617class Solution { public int maxProduct(String[] words) { int n = words.length, ans = 0; int[] mask = new int[n]; for (int i = 0; i < n; ++i) { for (char c : words[i].toCharArray()) { mask[i] |= 1 << (c - 'a'); } for (int j = 0; j < i; ++j) { if ((mask[i] & mask[j]) == 0) { ans = Mat ...

LC.P430[扁平化多级双向链表] 方法一：迭代1234567891011121314151617181920212223242526272829/*// Definition for a Node.class Node { public int val; public Node prev; public Node next; public Node child;};*/class Solution { public Node flatten(Node head) { Node dummy = new Node(); for (dummy.next = head; head != null; head = head.next) { if (head.child != null) { Node temp = head.next; Node child = head.child; ...

LC.P725[分隔链表] 方法一：模拟12345678910111213141516171819202122232425262728293031323334/** * 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[] splitListToParts(ListNode head, int k) { ListNode p = head; int n = 0 ...

LC.P117[填充每个节点的下一个右侧节点指针II] 方法一：BFS123456789101112131415161718192021222324252627282930313233343536373839404142434445464748/*// Definition for a Node.class Node { public int val; public Node left; public Node right; public Node next; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, Node _left, Node _right, Node _next) { val = _val; left = _left; right = _right; next = _next; ...

LC.P992[K个不同整数的子数组] 方法一：滑动窗口123456789101112131415161718192021222324252627282930class Solution { int n; int[] nums; public int subarraysWithKDistinct(int[] nums, int k) { this.nums = nums; this.n = nums.length; int[] lower = new int[n], upper = new int[n]; find(lower, k); // 找到距离当前位置i为右边界的满足k个不同字符的下标 find(upper, k - 1); // 找到距离当前位置i为右边界的满足k - 1个不同字符的下标 int ans = 0; for (int i = 0; i < n; ++i) { ans += upper[i] ...

LC.P904[水果成篮] 方法一：滑动窗口1234567891011121314class Solution { public int totalFruit(int[] fruits) { int n = fruits.length, ans = 0, total = 0; int[] cnt = new int[n + 1]; for (int i = 0, j = 0; i < n; ++i) { if (++cnt[fruits[i]] == 1) ++total; while (total > 2) { if (--cnt[fruits[j++]] == 0) --total; } ans = Math.max(ans, i - j + 1); } return ans; }} 时间复 ...

LC.P2103[环和杆] 方法一：位运算1234567891011121314151617181920class Solution { public int countPoints(String rings) { int n = rings.length(); int[] d = new int['Z']; d['R'] = 1; d['G'] = 2; d['B'] = 4; int[] mask = new int[10]; for (int i = 0; i < n; i += 2) { char c = rings.charAt(i); int j = rings.charAt(i + 1) - '0'; mask[j] |= d[c]; } ...

LC.P2003[每棵子树内缺失的最小基因值] 方法一：DFS12345678910111213141516171819202122232425262728293031323334353637383940class Solution { public int[] smallestMissingValueSubtree(int[] parents, int[] nums) { int n = parents.length, node = -1; int[] ans = new int[n]; Arrays.fill(ans, 1); for (int i = 0; i < n; ++i) { if (nums[i] == 1) { node = i; // 出发点 break; } } if (node == -1) return ...

LC.P871[最低加油次数] 方法一：贪心+优先队列1234567891011121314151617181920class Solution { public int minRefuelStops(int target, int startFuel, int[][] stations) { int ans = 0, remain = startFuel, x = 0, n = stations.length, i = 0; PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a); while (x < target) { if (remain == 0) { if (!q.isEmpty()) { remain += q.poll(); ++ans; ...