byu_rself

LC.P2578[最小和分割] 方法一：排序+贪心1234567891011class Solution { public int splitNum(int num) { char[] s = Integer.toString(num).toCharArray(); Arrays.sort(s); int[] ans = new int[2]; for (int i = 0; i < s.length; ++i) { ans[i & 1] = ans[i & 1] * 10 + (s[i] - '0'); } return ans[0] + ans[1]; }} 时间复杂度：$O(nlogn)$ 空间复杂度：$O(n)$ 方法二：计数+贪心123456789101112131415161718class Solution { public int ...

LC.P901[股票价格跨度] 方法一：暴力123456789101112131415161718192021222324class StockSpanner { List<Integer> list; public StockSpanner() { list = new ArrayList<>(); } public int next(int price) { list.add(price); int ans = 0; for (int i = list.size() - 1; i >= 0; --i) { if (list.get(i) <= price) ++ans; else break; } return ans; }}/** * Your StockSpanner object will be i ...

举例考虑数组 $a = [2, 3, 5, 6, 8]$，对其中相邻元素两两做差（右边减左边），得到数组 $[1,2,1,2]$。然后在开头补上 $a[0]$，得到差分数组$$d = [2,1,2,1,2]$$这有什么用？如果从左到右累加 $d$ 的元素，即可「还原」回 $a$ 数组 $[2, 3, 5, 6, 8]$。 更进一步，现在把连续子数组 $a[1], a[2], a[3]$ 都加上 $10$，得到 $a^{‘} = [2,13,15,16,8]$。再次两两做差，并在开头补上 $a^{‘}[0]$，得到差分数组$$d^{‘} = [2,11,2,1,-8]$$对比 $d$ 和 $d^{‘}$，可以发现对 $a$ 中连续子数组的操作，可以转变成对差分数组 $d$ 中两个数的操作。 定义和性质对于数组 $a$，定义其差分数组（difference array）为$$d(i) =\begin{cases} a[0], & i = 0 \ a[i] - a[i - 1], & i \geq 1\end{c ...

LC.P1109[航班预订统计] 方法一：差分数组12345678910111213141516class Solution { public int[] corpFlightBookings(int[][] bookings, int n) { int[] d = new int[n]; for (int[] b : bookings) { int first = b[0], last = b[1], seat = b[2]; d[first - 1] += seat; if (last < n) { d[last] -= seat; } } for (int i = 1; i < n; ++i) { d[i] += d[i - 1]; } return d; ...

LC.P1094[拼车] 方法一：差分数组12345678910111213141516class Solution { public boolean carPooling(int[][] trips, int capacity) { int[] d = new int[1001]; for (int[] trip : trips) { int num = trip[0], from = trip[1], to = trip[2]; d[from] += num; d[to] -= num; } int sum = 0; for (int x : d) { sum += x; if (sum > capacity) return false; } return true; }} 时 ...

LC.P2251[花期内花的数目] 方法一：排序+二分查找1234567891011121314151617181920212223242526class Solution { public int[] fullBloomFlowers(int[][] flowers, int[] people) { int n = flowers.length; int[] starts = new int[n], ends = new int[n]; for (int i = 0; i < n; ++i) { starts[i] = flowers[i][0]; ends[i] = flowers[i][1]; } Arrays.sort(starts); Arrays.sort(ends); for (int i = 0; i < people.length; ++i) { ...

LC.P732[我的日程安排表III] 方法一：差分数组123456789101112131415161718192021222324252627class MyCalendarThree { private TreeMap<Integer, Integer> cnt; public MyCalendarThree() { cnt = new TreeMap<Integer, Integer>(); } public int book(int start, int end) { int ans = 0; int maxBook = 0; cnt.put(start, cnt.getOrDefault(start, 0) + 1); cnt.put(end, cnt.getOrDefault(end, 0) - 1); for (Map.Entry<Integer, Integer> entry : ...

LC.P1333[餐厅过滤器] 方法一：排序1234567891011121314151617181920class Solution { public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) { List<Integer> ans = new ArrayList<>(); List<int[]> list = new ArrayList<>(); for (int[] r : restaurants) { if (veganFriendly == 1 && r[2] == 0) continue; if (r[3] > maxPrice) continue; if (r[4] > maxDis ...

LC.P731[我的日程安排表II] 方法一：线段树123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566class MyCalendarTwo { public MyCalendarTwo() { } public boolean book(int start, int end) { if (query(root, 0, N, start, end - 1) == 2) return false; update(root, 0, N, start, end - 1, 1); return true; } private static class Node { // 左右孩子节点 Node left, right; / ...

线段树(动态开点)1234567891011121314151617181920212223242526272829303132333435363738394041424344454647public class SegmentTreeDynamic { class Node { Node left, right; int val, add; } private int N = (int) 1e9; private Node root = new Node(); public void update(Node node, int start, int end, int l, int r, int val) { if (l <= start && end <= r) { node.val += (end - start + 1) * val; node.add += val; ...