byu_rself

LC.P581[最短无序连续子数组] 方法一：排序+双指针12345678910class Solution { public int findUnsortedSubarray(int[] nums) { int[] arr = nums.clone(); Arrays.sort(arr); int left = 0, right = nums.length - 1; while (left <= right && nums[left] == arr[left]) ++left; while (left <= right && nums[right] == arr[right]) --right; return right - left + 1; }} 时间复杂度：$O(nlogn)$ 空间复杂度：$O(n)$ 方法二：一次遍历1234567891011121314class Solution  ...

LC.P220[存在重复元素III] 方法一：滑动窗口+有序集合12345678910111213class Solution { public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) { TreeSet<Long> treeSet = new TreeSet<>(); for (int i = 0; i < nums.length; ++i) { // 大于等于所给元素的最小值 Long u = treeSet.ceiling((long) nums[i] - (long) valueDiff); if (u != null && u <= (long) nums[i] + (long) valueDiff) return true; treeSet.add((lo ...

LC.P219[存在重复元素II] 方法一：哈希表1234567891011121314class Solution { public boolean containsNearbyDuplicate(int[] nums, int k) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; ++i) { if (map.containsKey(nums[i])) { int j = map.get(nums[i]); if (Math.abs(i - j) <= k) return true; map.put(nums[i], i); } map.put(nums[i], i); } ...

LC.P1388[3n块披萨] 方法一：动态规划12345678910111213141516171819202122232425class Solution { int n; public int maxSizeSlices(int[] slices) { n = slices.length / 3; int[] nums = new int[slices.length - 1]; System.arraycopy(slices, 1, nums, 0, nums.length); int a = getMax(nums); System.arraycopy(slices, 0, nums, 0, nums.length); int b = getMax(nums); return Math.max(a, b); } private int getMax(int[] nums) { int m = nu ...

LC.P560[和为K的子数组] 方法一：前缀和12345678910111213class Solution { public int subarraySum(int[] nums, int k) { int n = nums.length, ans = 0; int[] sum = new int[n + 1]; for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + nums[i - 1]; for (int i = 0; i < n; ++i) { for (int j = i; j < n; ++j) { if (sum[j + 1] - sum[i] == k) ++ans; } } return ans; }} 时间复杂度：$O(n^2)$ 空间复杂度：$O( ...

LC.P238[除自身以外数组的乘积] 方法一：前缀与后缀乘1234567891011class Solution { public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] ans = new int[n], left = new int[n], right = new int[n]; left[0] = right[n - 1] = 1; for (int i = 1; i < n; ++i) left[i] = left[i - 1] * nums[i - 1]; for (int i = n - 2; i >= 0; --i) right[i] = right[i + 1] * nums[i + 1]; for (int i = 0; i < n; ++i) ans[i] = left[i] * right[i]; return ans;
...

class MatrixSum { private final int[][] sum; public MatrixSum(int[][] matrix) { int m = matrix.length, n = matrix[0].length; sum = new int[m + 1][n + 1]; // 注意：如果 matrix[i][j] 范围很大，需要使用 long for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + matrix[i][j]; } } } // 返回左上角在 (r1,c1) 右下角在 (r2-1, ...

LC.P1444[切披萨的方案数] 方法一：DFS+二维前缀和+动态规划(超时)1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950class Solution { public static final int MOD = (int) 1e9 + 7; public int ways(String[] pizza, int k) { MatrixSum ms = new MatrixSum(pizza); return dfs(k - 1, 0, 0, ms, pizza.length, pizza[0].length()); } private int dfs(int c, int i, int j, MatrixSum ms, int m, int n) { // 无法再切了 if (c == 0) return ms.que ...

LCR.P114[火星词典] 方法一：拓扑排序123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657class Solution { int N = 26, M = N * N, idx, cnt; int[] he = new int[N], e = new int[M], ne = new int[M]; int[] in = new int[N], out = new int[N]; boolean[] visited = new boolean[N]; private void add(int a, int b) { e[idx] = b; ne[idx] = he[a]; he[a] = idx++; ++out[a]; ++in[b]; } public String al ...

LC.P2682[找出转圈游戏输家] 方法一：模拟123456789101112131415161718class Solution { public int[] circularGameLosers(int n, int k) { boolean[] visited = new boolean[n]; int cnt = 0; for (int i = 0, t = 1; !visited[i]; ++t) { visited[i] = true; ++cnt; i = (i + t * k) % n; } int[] ans = new int[n - cnt]; for (int i = 0, j = 0; i < n; ++i) { if (!visited[i]) { ans[j++] = i + 1; ...