byu_rself

LC.P629[K个逆序对数组] 方法一：动态规划1234567891011121314151617class Solution { private static final int MOD = (int) 1e9 + 7; public int kInversePairs(int n, int k) { int[][] dp = new int[n + 1][k + 1], sum = new int[n + 1][k + 1]; dp[1][0] = 1; Arrays.fill(sum[1], 1); for (int i = 2; i <= n; ++i) { for (int j = 0; j <= k; ++j) { dp[i][j] = j < i ? sum[i - 1][j] : (sum[i - 1][j] - sum[i - 1][j - (i - 1) - 1] + MOD) % MOD ...

LC.P396[旋转函数] 方法一：前缀和+滑动窗口1234567891011121314class Solution { public int maxRotateFunction(int[] nums) { int n = nums.length, ans = 0; int[] sum = new int[n * 2 + 1]; for (int i = 1; i <= 2 * n; ++i) sum[i] = sum[i - 1] + nums[(i - 1) % n]; for (int i = 1; i <= n; ++i) ans += nums[i - 1] * (i - 1); for (int i = n + 1, cur = ans; i < 2 * n; ++i) { cur += nums[(i - 1) % n] * (n - 1); cur -= sum[i - 1] - sum[i - n]; ...

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