byu_rself

LC.P1713[得到子序列的最少操作次数] 方法一：贪心+动态规划+二分123456789101112131415161718192021222324252627282930class Solution { public int minOperations(int[] target, int[] arr) { int n = target.length; Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < n; ++i) map.put(target[i], i); List<Integer> list = new ArrayList<>(); for (int x : arr) { if (map.containsKey(x)) { list.add(map.get(x)); ...

LC.P1726[同积元组] 方法一：数学+哈希表12345678910111213141516class Solution { public int tupleSameProduct(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 1; i < nums.length; ++i) { for (int j = 0; j < i; ++j) { int x = nums[i] * nums[j]; map.merge(x, 1, Integer::sum); } } int ans = 0; for (int v : map.values()) { ans += v * (v - 1) / ...

LC.P926[将字符串翻转到单调递增] 方法一：动态规划1234567891011121314class Solution { public int minFlipsMonoIncr(String s) { int n = s.length(); int dp0 = 0, dp1 = 0; for (int i = 0; i < n; ++i) { char c = s.charAt(i); int dp0New = dp0 + (c == '1' ? 1 : 0); int dp1New = Math.min(dp0, dp1) + (c == '0' ? 1 : 0); dp0 = dp0New; dp1 = dp1New; } return Math.min(dp0, dp1); }} ...

LC.P2530[执行K次操作后的最大分数] 方法一：优先队列(大根堆)123456789101112131415class Solution { public long maxKelements(int[] nums, int k) { long ans = 0; PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a); for (int num : nums) { q.offer(num); } while (k-- > 0) { int x = q.poll(); ans += x; q.offer((x + 2) / 3); } return ans; }} 时间复杂度：$O(n + klogn ...

LC.P446[等差数列划分II-子序列] 方法一：动态规划+哈希表123456789101112131415161718class Solution { public int numberOfArithmeticSlices(int[] nums) { int ans = 0, n = nums.length; Map<Long, Integer>[] f = new Map[n]; for (int i = 0; i < n; ++i) { f[i] = new HashMap<>(); } for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { long d = (long) nums[i] - nums[j]; int cnt = f[j ...

LC.P136[只出现一次的数字III] 方法一：位运算1234567891011121314151617class Solution { public int[] singleNumber(int[] nums) { int xs = 0; for (int x : nums) { xs ^= x; } int lowbit = xs & -xs; int a = 0; for (int x : nums) { if ((x & lowbit) != 0) { a ^= x; } } int b = xs ^ a; return new int[] {a, b}; }} 时间复杂度：$O(n)$ 空间复杂度：$O(1 ...

LC.P136[只出现一次的数字II] 方法一：位运算1234567891011121314class Solution { public int singleNumber(int[] nums) { int ans = 0; for (int i = 0; i < 32; i++) { int cnt = 0; for (int num : nums) { cnt += num >> i & 1; } cnt %= 3; ans |= cnt << i; } return ans; }} 时间复杂度：$O(nlogM)$，其中$M$为元素的数据范围为$2^{32}$ 空间复杂度：$O(1)$

LC.P136[只出现一次的数字] 方法一：位运算123456789class Solution { public int singleNumber(int[] nums) { int x = 0; // a ^ a = 0 // 0 ^ a = a for (int num : nums) x ^= num; return x; }} 时间复杂度：$O(n)$ 空间复杂度：$O(1)$

LC.P1744[你能在你最喜欢的那天吃到你最喜欢的糖果吗？] 方法一：前缀和12345678910111213141516class Solution { public boolean[] canEat(int[] candiesCount, int[][] queries) { int n = candiesCount.length, m = queries.length; boolean[] ans = new boolean[m]; long[] sum = new long[n + 1]; for (int i = 1; i <= n; ++i) { sum[i] = sum[i - 1] + candiesCount[i - 1]; } for (int i = 0; i < m; ++i) { int type = queries[i][0], day = queries[i][ ...

LC.P1074[元素和为目标值的子矩阵数量] 方法一：前缀和+哈希表123456789101112131415161718192021222324252627282930313233class Solution { public int numSubmatrixSumTarget(int[][] matrix, int target) { int m = matrix.length, n = matrix[0].length, ans = 0; // 枚举上边界 for (int i = 0; i < m; ++i) { int[] sum = new int[n]; // 枚举下边界 for (int j = i; j < m; ++j) { for (int k = 0; k < n; ++k) { // 更新每列的元素和 ...