byu_rself

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 ...

LC.P2069[模拟行走机器人II] 方法一：模拟1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556class Robot { int width, height; int loc; // 有效的移动步数 boolean moved; String[] dir = new String[]{"East", "North", "West", "South"}; public Robot(int width, int height) { this.width = width; this.height = height; } public void step(int num) { moved = true; ...

LC.P1851[包含每个查询的最小区间] 方法一：排序+离线查询+优先队列(小根堆)1234567891011121314151617181920212223242526272829303132333435class Solution { public int[] minInterval(int[][] intervals, int[] queries) { int n = intervals.length, m = queries.length; // 区间按照左端点从小到大排序 Arrays.sort(intervals, (a, b) -> a[0] - b[0]); int[][] qs = new int[m][2]; for (int i = 0; i < m; ++i) { qs[i] = new int[]{queries[i], i}; } // 查询按照从小到大排序 ...