byu_rself

举例考虑数组 $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; ...

LC.P729[我的日程安排表I] 方法一：模拟12345678910111213141516171819202122232425class MyCalendar { List<int[]> booked; public MyCalendar() { booked = new ArrayList<int[]>(); } public boolean book(int start, int end) { for (int[] arr : booked) { int left = arr[0], right = arr[1]; if (left < end && start < right) { return false; } } booked.add(new int[]{st ...

LC.P2582[递枕头] 方法一：模拟123456789101112class Solution { public int passThePillow(int n, int time) { int ans = 1, k = 1; while (time-- > 0) { ans += k; if (ans == 1 || ans == n) { k *= -1; } } return ans; }} 时间复杂度：$O(time)$ 空间复杂度：$O(1)$ 方法二：数学1234567class Solution { public int passThePillow(int n, int time) { int k = time / (n - 1); int mod = time ...