byu_rself

LC.P42[接雨水] 方法一：单调栈1234567891011121314151617class Solution { public int trap(int[] height) { Deque<Integer> stack = new ArrayDeque<>(); int ans = 0, n = height.length; for (int i = 0; i < n; ++i) { while (!stack.isEmpty() && height[i] > height[stack.peek()]) { int h = height[stack.pop()]; if (stack.isEmpty()) break; int length = i - stack.peek() - 1; int mi ...

LC.P860[柠檬水找零] 方法一：贪心+模拟123456789101112131415161718192021222324class Solution { public boolean lemonadeChange(int[] bills) { int cnt5 = 0, cnt10 = 0; for (int bill : bills) { switch (bill) { case 5 -> ++cnt5; case 10 -> { --cnt5; ++cnt10; } case 20 -> { if (cnt10 > 0) { --cnt10; ...

LC.P943[最短超级串] 方法一：动态规划+状态压缩123456789101112131415161718192021222324252627282930313233343536373839404142434445464748class Solution { public String shortestSuperstring(String[] words) { int n = words.length, mask = 1 << n; int[][] g = new int[n][n]; // g[i][j]表示words[i]的后缀与words[j]的前缀的重叠部分的长度 for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { String a = words[i], b = words[j]; int l1 = ...

LC.P1499[满足不等式的最大值] 方法一：双端队列1234567891011121314151617class Solution { public int findMaxValueOfEquation(int[][] points, int k) { int ans = Integer.MIN_VALUE; // (xi, yi - xi) Deque<int[]> q = new ArrayDeque<>(); for (int[] point : points) { int x = point[0], y = point[1]; while (!q.isEmpty() && q.peekFirst()[0] < x - k) q.pollFirst(); if (!q.isEmpty()) { ans = Math.max(ans, x ...

LC.P985[查询后的偶数和] 方法一：模拟123456789101112131415class Solution { public int[] sumEvenAfterQueries(int[] nums, int[][] queries) { int m = queries.length, sum = 0; int[] ans = new int[m]; for (int num : nums) sum += num % 2 == 0 ? num : 0; for (int i = 0; i < m; ++i) { int val = queries[i][0], idx = queries[i][1]; if (nums[idx] % 2 == 0) sum -= nums[idx]; nums[idx] += val; if (nums[idx] % 2 == 0) sum += nums[i ...

LC.P950[按递增顺序显示卡牌] 方法一：队列模拟1234567891011121314class Solution { public int[] deckRevealedIncreasing(int[] deck) { int n = deck.length; Deque<Integer> queue = new ArrayDeque<>(); for (int i = 0; i < n; ++i) queue.offer(i); int[] ans = new int[n]; Arrays.sort(deck); for (int x : deck) { ans[queue.poll()] = x; if (!queue.isEmpty()) queue.offer(queue.poll()); } return ans; } ...

LC.P918[环形子数组的最大和] 方法一：维护前缀最值1234567891011121314151617class Solution { public int maxSubarraySumCircular(int[] nums) { int maxSum = Integer.MIN_VALUE; // 最大子数组和，不能为空 int minSum = 0; // 最小子数组和，可以为空 int maxPre = 0, minPre = 0, sum = 0; for (int x : nums) { // 以 nums[i-1] 结尾的子数组选或不选（取 max）+ x = 以 x 结尾的最大子数组和 maxPre = Math.max(maxPre, 0) + x; maxSum = Math.max(maxSum, maxPre); // 以 nums[i-1] 结尾的子数组选或不选（取 min）+ ...

LC.P53[最大子数组和] 方法一：动态规划 f[i]表示以 $i$ 结尾的连续子数组的和 12345678910111213class Solution { public int maxSubArray(int[] nums) { int n = nums.length, ans = nums[0]; int[] f = new int[n]; f[0] = nums[0]; for (int i = 1; i < n; ++i) { if (f[i - 1] > 0) f[i] = f[i - 1] + nums[i]; else f[i] = nums[i]; ans = Math.max(ans, f[i]); } return ans; }} 时间复杂度：$O(n)$ 空间复杂度：$O(n)$ 方法二：优化空间由于 $f[i]$ 只与 ...

LC.P1222[可以攻击国王的皇后] 方法一：模拟12345678910111213141516171819202122232425class Solution { private static final int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, 1}, {1, 1}, {-1, -1}, {1, -1}}; public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) { List<List<Integer>> ans = new ArrayList<>(); int x = king[0], y = king ...

LC.P874[模拟行走机器人] 方法一：哈希表+模拟1234567891011121314151617181920212223242526272829303132333435class Solution { static int[][] dirs = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; public int robotSim(int[] commands, int[][] obstacles) { Set<Integer> set = new HashSet<>(obstacles.length); for (int[] obstacle : obstacles) { set.add(getIndex(obstacle[0], obstacle[1])); } int ...