byu_rself

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) { // 更新每列的元素和 ...

LC.P1488[避免洪水泛滥] 方法一：贪心+哈希表+有序集合12345678910111213141516171819202122232425class Solution { public int[] avoidFlood(int[] rains) { int n = rains.length; int[] ans = new int[n]; Arrays.fill(ans, -1); TreeSet<Integer> sunny = new TreeSet<>(); Map<Integer, Integer> rainy = new HashMap<>(); for (int i = 0; i < n; ++i) { int k = rains[i]; if (k > 0) { if (rainy.containsKey ...

LC.P1201[丑数III] 方法一：容斥原理+二分12345678910111213141516171819202122class Solution { public int nthUglyNumber(int n, int a, int b, int c) { long ab = lcm(a, b), ac = lcm(a, c), bc = lcm(b, c), abc = lcm(a, lcm(b, c)); long left = 0, right = (long) Math.min(a, Math.min(b, c)) * n; while (left < right) { long mid = left + right >> 1; if (mid / a + mid / b + mid / c - mid / ab - mid / ac - mid / bc + mid / abc >= n) right = mid; ...