免费自助建站,郑州官网seo费用,设计网站的目的,南昌做网站开发的公司文章目录 1456. 定长子串中元音的最大数目2269. 找到一个数字的 K 美丽值1984. 学生分数的最小差值#xff08;排序#xff09;643. 子数组最大平均数 I1343. 大小为 K 且平均值大于等于阈值的子数组数目2090. 半径为 k 的子数组平均值2379. 得到 K 个黑块的最少涂色次数1052… 文章目录 1456. 定长子串中元音的最大数目2269. 找到一个数字的 K 美丽值1984. 学生分数的最小差值排序643. 子数组最大平均数 I1343. 大小为 K 且平均值大于等于阈值的子数组数目2090. 半径为 k 的子数组平均值2379. 得到 K 个黑块的最少涂色次数1052. 爱生气的书店老板2841. 几乎唯一子数组的最大和2461. 长度为 K 子数组中的最大和1423. 可获得的最大点数转换成找中间窗口最小2134. 最少交换次数来组合所有的 1 II2653. 滑动子数组的美丽值⭐解法1——利用二分维护窗口中的排序超时了解法2——滑动窗口暴力枚举 ⭐牛逼的暴力枚举 567. 字符串的排列438. 找到字符串中所有字母异位词2156. 查找给定哈希值的子串⭐⭐⭐解法1——倒序滚动哈希解法2——倒序滑动窗口 O ( 1 ) O(1) O(1) 额外空间小技巧将a——z转成1——26 346. 数据流中的移动平均值用队列维护窗口1100. 长度为 K 的无重复字符子串 题单来源https://leetcode.cn/problems/minimum-size-subarray-in-infinite-array/solutions/2464878/hua-dong-chuang-kou-on-shi-jian-o1-kong-cqawc/
1456. 定长子串中元音的最大数目
https://leetcode.cn/problems/maximum-number-of-vowels-in-a-substring-of-given-length/description/ 提示
1 s.length 10^5 s 由小写英文字母组成 1 k s.length
定长滑动窗口进来一个加一个出去一个减一个。
class Solution {public int maxVowels(String s, int k) {int n s.length(), cnt 0, ans 0;SetCharacter vowel Set.of(a, e, i, o, u);for (int l 0, r 0; r n; r) {if (vowel.contains(s.charAt(r))) cnt;if (r l k) {if (vowel.contains(s.charAt(l))) cnt--;l;}ans Math.max(ans, cnt);}return ans;}
}2269. 找到一个数字的 K 美丽值
https://leetcode.cn/problems/find-the-k-beauty-of-a-number/ 提示 1 num 10^9 1 k num.length 将 num 视为字符串
以240为例 起初 x100y1. 取出 240 % 100 / 1 40; 之后 x1000y10 取出 240 % 1000 / 10 24;
class Solution {public int divisorSubstrings(int num, int k) {int ans 0;long x 1, y 1;for (int i 0; i k; i) x * 10;for (; x / 10 num; x * 10, y * 10) {long z (long)num % x / y;if (z ! 0 num % z 0) ans;}return ans;}
}1984. 学生分数的最小差值排序
https://leetcode.cn/problems/minimum-difference-between-highest-and-lowest-of-k-scores/description/ 排序之后的区间两边一定是一个最大值和一个最小值。 逐个枚举即可。
class Solution {public int minimumDifference(int[] nums, int k) {Arrays.sort(nums);int n nums.length, ans nums[n - 1] - nums[0];for (int l 0, r k - 1; r n; l, r) {ans Math.min(ans, nums[r] - nums[l]);}return ans;}
}643. 子数组最大平均数 I
https://leetcode.cn/problems/maximum-average-subarray-i/description/
注意可能会溢出的问题。
class Solution {public double findMaxAverage(int[] nums, int k) {double ans -10001, s 0;for (int l 0, r 0; r nums.length; r) {s nums[r];if (r - l 1 k) {ans Math.max(ans, s / k);s - nums[l];}}return ans;}
}1343. 大小为 K 且平均值大于等于阈值的子数组数目
https://leetcode.cn/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold/description/ 提示 1 arr.length 10^5 1 arr[i] 10^4 1 k arr.length 0 threshold 10^4
class Solution {public int numOfSubarrays(int[] arr, int k, int threshold) {int ans 0;long t threshold * k, s 0;for (int i 0; i k - 1; i) s arr[i];for (int i k - 1; i arr.length; i) {s arr[i];if (s t) ans;s - arr[i - k 1];}return ans;}
}2090. 半径为 k 的子数组平均值
https://leetcode.cn/problems/k-radius-subarray-averages/description/ 提示
n nums.length 1 n 10^5 0 nums[i], k 10^5
用 s 维护长度为 2*k1 窗口内所有值的总和。
class Solution {public int[] getAverages(int[] nums, int k) {int n nums.length;int[] ans new int[n];Arrays.fill(ans, -1);long s 0, l 2 * k 1;for (int i 0; i 2 * k i n; i) s nums[i];for (int i 2 * k; i n; i) {s nums[i];ans[i - k] (int)(s / l);s - nums[i - 2 * k];}return ans;}
}2379. 得到 K 个黑块的最少涂色次数
https://leetcode.cn/problems/minimum-recolors-to-get-k-consecutive-black-blocks/description/ 提示 n blocks.length 1 n 100 blocks[i] 要么是 W 要么是 B 。 1 k n
固定长度滑动窗口。
class Solution {public int minimumRecolors(String blocks, int k) {int ans k, n blocks.length(), s 0;for (int i 0; i k - 1; i) {if (blocks.charAt(i) W) s;}for (int i k - 1; i n; i) {if (blocks.charAt(i) W) s;ans Math.min(ans, s);if (blocks.charAt(i - k 1) W) s--;}return ans;}
}1052. 爱生气的书店老板
https://leetcode.cn/problems/grumpy-bookstore-owner/description/ 提示
n customers.length grumpy.length 1 minutes n 2 * 10^4 0 customers[i] 1000 grumpy[i] 0 or 1
变量 s 维护长度为minutes的窗口中 生气时的顾客数量这些顾客可以通过秘密技巧变得满意。 变量 total 计算本来就满意的顾客数量。
最后的答案是本来就满意的顾客数量使用技巧变得满意的最多顾客数量。
class Solution {public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {int n customers.length, s 0, mx 0, total 0;for (int i 0; i minutes - 1; i) {if (grumpy[i] 1) s customers[i];else total customers[i];}for (int i minutes - 1; i n; i) {if (grumpy[i] 1) s customers[i];else total customers[i];mx Math.max(mx, s);if (grumpy[i - minutes 1] 1) s - customers[i - minutes 1];}return total mx;}
}2841. 几乎唯一子数组的最大和
https://leetcode.cn/problems/maximum-sum-of-almost-unique-subarray/submissions/ 提示 1 nums.length 2 * 10^4 1 m k nums.length 1 nums[i] 10^9
用 s 维护和。 用 cnt 维护不同数字的种类数量。
class Solution {public long maxSum(ListInteger nums, int m, int k) {long ans 0, s 0;MapInteger, Integer cnt new HashMap();for (int i 0; i k - 1; i) {s nums.get(i);cnt.merge(nums.get(i), 1, Integer::sum);}for (int i k - 1; i nums.size(); i) {s nums.get(i);cnt.merge(nums.get(i), 1, Integer::sum);if (cnt.size() m) ans Math.max(ans, s);s - nums.get(i - k 1);cnt.merge(nums.get(i - k 1), -1, Integer::sum);if (cnt.get(nums.get(i - k 1)) 0) cnt.remove(nums.get(i - k 1));}return ans;}
}2461. 长度为 K 子数组中的最大和
https://leetcode.cn/problems/maximum-sum-of-distinct-subarrays-with-length-k/description/ 提示 1 k nums.length 10^5 1 nums[i] 10^5
class Solution {public long maximumSubarraySum(int[] nums, int k) {long ans 0, s 0;MapInteger, Integer cnt new HashMap();for (int i 0; i nums.length; i) {s nums[i];cnt.merge(nums[i], 1, Integer::sum);if (cnt.size() k) ans Math.max(ans, s);if (i k - 1) {int x nums[i - k 1];s - x;cnt.merge(x, -1, Integer::sum);if (cnt.get(x) 0) cnt.remove(x);}}return ans;}
}1423. 可获得的最大点数转换成找中间窗口最小
https://leetcode.cn/problems/maximum-points-you-can-obtain-from-cards/description/
提示 1 cardPoints.length 10^5 1 cardPoints[i] 10^4 1 k cardPoints.length
从两边拿要取最大也就是找中间连续的最小。 可以使用固定长度滑动窗口。
class Solution {public int maxScore(int[] cardPoints, int k) {int n cardPoints.length, l n - k, total 0, s 0, mn Integer.MAX_VALUE;if (l 0) return Arrays.stream(cardPoints).sum();for (int i 0; i n; i) {s cardPoints[i];total cardPoints[i];if (i l - 1) {mn Math.min(mn, s);s - cardPoints[i - l 1];}}return total - mn;}
}2134. 最少交换次数来组合所有的 1 II
https://leetcode.cn/problems/minimum-swaps-to-group-all-1s-together-ii/description/ 提示 1 nums.length 10^5 nums[i] 为 0 或者 1
最后所以的 1 一定会相邻。 所以转换成求固定长度窗口中 1 出现的最大值其它不在窗口中的 1 都需要交换过来。
class Solution {public int minSwaps(int[] nums) {int k Arrays.stream(nums).sum(), mx 0, s 0, n nums.length;for (int x 0; x 2 * n; x) {int i x % n;s nums[i];if (x k - 1) {mx Math.max(mx, s);s - nums[(x - k 1) % n];}}return k - mx;}
}2653. 滑动子数组的美丽值⭐
https://leetcode.cn/problems/sliding-subarray-beauty/description/ 提示
n nums.length 1 n 10^5 1 k n 1 x k -50 nums[i] 50
解法1——利用二分维护窗口中的排序超时了
class Solution {public int[] getSubarrayBeauty(int[] nums, int k, int x) {int n nums.length;ListInteger ls new ArrayList();int[] ans new int[n - k 1];for (int i 0; i n; i) {int t nums[i];int id bs(ls, t);ls.add(id, t);if (ls.size() k) {id bs(ls, nums[i - k]);ls.remove(id);}if (ls.size() k) {if (ls.get(x - 1) 0) ans[i - k 1] ls.get(x - 1);else ans[i - k 1] 0;}}return ans;}public int bs(ListInteger ls, int t) {int l 0, r ls.size();while (l r) {int mid l r 1;if (ls.get(mid) t) l mid 1;else r mid;}return l;}
}把 ArrayList 换成 LinkedList 超时会更多。
解法2——滑动窗口暴力枚举 ⭐牛逼的暴力枚举
https://leetcode.cn/problems/sliding-subarray-beauty/solutions/2241294/hua-dong-chuang-kou-bao-li-mei-ju-by-end-9mvl/ 虽然是暴力枚举但是充分利用了数值的值域很小的特性。
class Solution {public int[] getSubarrayBeauty(int[] nums, int k, int x) {final int BIAS 50;int[] cnt new int[BIAS * 2 1]; // 计数数组int n nums.length;int[] ans new int[n - k 1];for (int i 0; i n; i) {cnt[nums[i] BIAS]; // 进入窗口if (i k - 1) { // 计算该位置的答案int left x; // 计算剩余的xfor (int j 0; j BIAS; j) {left - cnt[j];if (left 0) { // 找到了答案ans[i - k 1] j - BIAS;break;}}--cnt[nums[i - k 1] BIAS]; // 移出窗口}}return ans;}
}567. 字符串的排列
https://leetcode.cn/problems/permutation-in-string/description/ 提示
1 s1.length, s2.length 10^4 s1 和 s2 仅包含小写字母
如果 s1 的排列之一是 s2 的 子串。那么应该满足 s2 的一个字串中各个字符的数量和 s1 相同。
用计数数组维护窗口中各个字符的数量即可。
class Solution {public boolean checkInclusion(String s1, String s2) {int[] cnt new int[128];for (char ch: s1.toCharArray()) cnt[ch];for (int l 0, r 0; r s2.length(); r) {cnt[s2.charAt(r)]--;if (r - l s1.length()) cnt[s2.charAt(l)]; boolean f true;for (char ch a; ch z; ch) {if (cnt[ch] ! 0) {f false;break;}}if (f) return true;}return false;}
}438. 找到字符串中所有字母异位词
https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/ 提示:
1 s.length, p.length 3 * 10^4 s 和 p 仅包含小写字母
维护 s 中长度等于 p 的滑动窗口检查 窗口中的各个字符数量和 p 中的字符数量是否相等即可。
class Solution {public ListInteger findAnagrams(String s, String p) {ListInteger ans new ArrayList();int[] cnt new int[128];for (char ch: p.toCharArray()) cnt[ch];for (int l 0, r 0; r s.length(); r) {cnt[s.charAt(r)]--;if (r - l p.length()) cnt[s.charAt(l)];boolean f true;for (char ch a; ch z; ch) {if (cnt[ch] ! 0) {f false;break;}}if (f) ans.add(l);} return ans;}
}2156. 查找给定哈希值的子串⭐⭐⭐
https://leetcode.cn/problems/find-substring-with-given-hash-value/description/ 提示 1 k s.length 2 * 10^4 1 power, modulo 10^9 0 hashValue modulo s 只包含小写英文字母。 测试数据保证一定 存在 满足条件的子串。
解法1——倒序滚动哈希
https://leetcode.cn/problems/find-substring-with-given-hash-value/solutions/1249153/cha-zhao-gei-ding-ha-xi-zhi-de-zi-chuan-fi8jd/ 倒序处理 先处理出 p o w e r ( k − 1 ) m o d m o d u l o power^(k-1) \mod modulo power(k−1)modmodulo。
class Solution {public String subStrHash(String s, int power, int modulo, int k, int hashValue) {int n s.length(), pos -1;// h:子串哈希值 mult:power^(k-1) mod modulolong h 0, mult 1;// 预处理最后一个子串的哈希值和 power^k mod modulofor (int i n - 1; i n - k; --i) {h (h * power (s.charAt(i) - a 1)) % modulo;if (i ! n - k) {mult mult * power % modulo;}}if (h hashValue) pos n - k;// 向前计算哈希值并尝试更新下标for (int i n - k - 1; i 0; --i) {h ((h - (s.charAt(i k) - a 1) * mult % modulo modulo) * power (s.charAt(i) - a 1)) % modulo;if (h hashValue) {pos i;}}return s.substring(pos, pos k);}
}解法2——倒序滑动窗口 O ( 1 ) O(1) O(1) 额外空间
class Solution {public String subStrHash(String s, int power, int modulo, int k, int hashValue) {int n s.length(), pos -1;// h:子串哈希值 mult:power^(k-1) mod modulolong h 0, mult 1;// 预处理最后一个子串的哈希值和 power^k mod modulofor (int i n - 1; i n - k; --i) {h (h * power (s.charAt(i) 31)) % modulo;if (i ! n - k) {mult mult * power % modulo;}}if (h hashValue) pos n - k;// 向前计算哈希值并尝试更新下标for (int i n - k - 1; i 0; --i) {h ((h - (s.charAt(i k) 31) * mult % modulo modulo) * power (s.charAt(i) 31)) % modulo;if (h hashValue) {pos i;}}return s.substring(pos, pos k);}
}小技巧将’a’——z’转成1——26
只需要 31 即可。
346. 数据流中的移动平均值用队列维护窗口
https://leetcode.cn/problems/moving-average-from-data-stream/description/ 提示 1 size 1000 -10^5 val 10^5 最多调用 next 方法 10^4 次
class MovingAverage {QueueInteger q new LinkedList();int sz;double sum;public MovingAverage(int size) {sz size;sum 0;}public double next(int val) {q.offer(val);sum val;if (q.size() sz) sum - q.poll();return sum / q.size();}
}/*** Your MovingAverage object will be instantiated and called as such:* MovingAverage obj new MovingAverage(size);* double param_1 obj.next(val);*/1100. 长度为 K 的无重复字符子串
https://leetcode.cn/problems/find-k-length-substrings-with-no-repeated-characters/description/ 提示 1 S.length 10^4 S 中的所有字符均为小写英文字母 1 K 10^4
维护长度为 k 的滑动窗口中各个字符出现的数量。
class Solution {public int numKLenSubstrNoRepeats(String s, int k) {int[] cnt new int[128];int ans 0;for (int l 0, r 0; r s.length(); r) {cnt[s.charAt(r)];if (r - l k) cnt[s.charAt(l)]--;if (r k - 1 check(cnt)) ans;}return ans;}public boolean check(int[] cnt) {for (char ch a; ch z; ch) {if (cnt[ch] 1) {return false;}}return true;}
}
