服装设计类网站,asp做微网站,恋爱网页生成,莱阳网站定制想成功先发疯#xff0c;不顾一切向前冲。
第一种
定长滑动窗口
. - 力扣#xff08;LeetCode#xff09;1456.定长子串中的元音的最大数目. - 力扣#xff08;LeetCode#xff09;
No.1
定长滑窗套路 我总结成三步#xff1a;入-更新-出。 1. 入#xff1a;下标为…想成功先发疯不顾一切向前冲。
第一种
定长滑动窗口
. - 力扣LeetCode1456.定长子串中的元音的最大数目. - 力扣LeetCode
No.1
定长滑窗套路 我总结成三步入-更新-出。 1. 入下标为 i 的元素进入窗口更新相关统计量。如果 ik−1 则重复第一步。 2. 更新更新答案。一般是更新最大值/最小值。 3. 出下标为 i−k1 的元素离开窗口更新相关统计量。 以上三步适用于所有定长滑窗题目。
class Solution {public int maxVowels(String S, int k) {char[] s S.toCharArray();int ans 0;int temp 0;for (int i 0; i s.length; i) {// 1. 进入窗口if (s[i] a || s[i] e || s[i] i || s[i] o || s[i] u) {temp;}if (i k - 1) { // 窗口大小不足 kcontinue;}// 2. 更新答案ans Math.max(ans, temp);// 3. 离开窗口char out s[i - k 1];if (out a || out e || out i || out o || out u) {temp--;}}return ans;}
}复杂度分析
时间复杂度O(n)其中 n 是 s 的长度。空间复杂度O(1)。仅用到若干额外变量。
这里对于字符串的处理及java的String类做一个详细说明 toCharArray() 是 Java 中 String 类的一个方法用于将字符串转换为字符数组 (char[])。每个字符数组中的元素对应于字符串中的一个字符。 用法 String str Hello, World!; char[] charArray str.toCharArray(); 解释 str 是一个 String 对象。调用 str.toCharArray() 会将字符串 Hello, World! 转换为一个字符数组。charArray 将包含{H, e, l, l, o, ,, , W, o, r, l, d, !} 常见用途 字符串处理你可以更方便地遍历字符串中的每个字符。字符修改字符数组可以修改单个字符而 String 是不可变的即一旦创建不能更改其内容。 1. length() 作用: 返回字符串的长度字符数。 示例: String str Hello, World!;
int len str.length(); // len 13 2. charAt(int index) 作用: 返回指定索引处的字符索引从 0 开始。示例: String str Hello;
char ch str.charAt(1); // ch e 3. substring(int beginIndex) / substring(int beginIndex, int endIndex) 作用: 返回从指定索引开始或在索引区间内的子字符串。示例: String str Hello, World!;
String subStr1 str.substring(7); // subStr1 World!
String subStr2 str.substring(0, 5); // subStr2 Hello 4. indexOf(String str) / indexOf(char ch) 作用: 返回指定字符或子字符串在原字符串中第一次出现的索引若未找到则返回 -1。示例: String str Hello, World!;
int index1 str.indexOf(W); // index1 7
int index2 str.indexOf(World); // index2 7 5. toUpperCase() / toLowerCase() 作用: 返回将字符串转换为大写或小写后的新字符串。示例: String str Hello;
String upperStr str.toUpperCase(); // upperStr HELLO
String lowerStr str.toLowerCase(); // lowerStr hello 6. trim() 作用: 去除字符串开头和结尾的空白字符。示例: String str Hello, World! ;
String trimmedStr str.trim(); // trimmedStr Hello, World! 7. replace(char oldChar, char newChar) / replace(CharSequence target, CharSequence replacement) 作用: 替换字符串中的指定字符或子字符串。示例: String str Hello, World!;
String replacedStr1 str.replace(o, a); // replacedStr1 Hella, Warld!
String replacedStr2 str.replace(World, Java); // replacedStr2 Hello, Java! 8. equals(Object anObject) / equalsIgnoreCase(String anotherString) 作用: 比较两个字符串的内容是否相等。equalsIgnoreCase 不区分大小写。示例: String str1 Hello;
String str2 hello;
boolean isEqual str1.equals(str2); // isEqual false
boolean isEqualIgnoreCase str1.equalsIgnoreCase(str2); // isEqualIgnoreCase true 9. split(String regex) 作用: 根据正则表达式将字符串分割为子字符串数组。示例: String str apple,banana,orange;
String[] fruits str.split(,); // fruits [apple, banana, orange] 10. contains(CharSequence s) 作用: 判断字符串是否包含指定的字符序列。示例: String str Hello, World!;
boolean containsHello str.contains(Hello); // containsHello true No.2
给你一个 下标从 0 开始 的整数数组 nums 其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k 。
从数组中选出任意 k 名学生的分数使这 k 个分数间 最高分 和 最低分 的 差值 达到 最小化 。
返回可能的 最小差值 。 示例 1
输入nums [90], k 1
输出0
解释选出 1 名学生的分数仅有 1 种方法
- [90] 最高分和最低分之间的差值是 90 - 90 0
可能的最小差值是 0示例 2
输入nums [9,4,1,7], k 2
输出2
解释选出 2 名学生的分数有 6 种方法
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 4 5
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 1 8
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 7 2
- [9,4,1,7] 最高分和最低分之间的差值是 4 - 1 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 4 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 1 6
可能的最小差值是 2
class Solution {public int minimumDifference(int[] nums, int k) {Arrays.sort(nums);int len nums.length;int res Integer.MAX_VALUE;for (int i 0; i len - k; i) {res Math.min(res,nums[ik-1]-nums[i]);}return res;}
}
这个题要注意的地方是i 只有在 len-k 的条件下可以运行在后续的nums[ ]读数的时候左右节点要进行移动读数
No.3
1343. - 力扣LeetCode
class Solution {public int numOfSubarrays(int[] arr, int k, int threshold) {int len arr.length;int ans 0;for (int i 0; i k; i) {ans arr[i];}int res 0;
//很典型的一个坑初次忘记考虑当 i 0 取 k 个数的时候的 ans 的大小的判断if(ansk*threshold){res;}for (int i k; i len; i) {ans ans-arr[i-k] arr[i];if(ans/kthreshold){res;}}return res;}
}
不定长滑动窗口求最长或最大
No.1
3.无重复字符的最长子串
我认为思考的重点在于滑动窗口的起始位置与一般规律的总结
我们不妨以示例一中的字符串 abcabcbb 为例找出从每一个字符开始的不包含重复字符的最长子串那么其中最长的那个字符串即为答案。对于示例一中的字符串我们列举出这些结果其中括号中表示选中的字符以及最长的字符串
以 (a)bcabcbb 开始的最长字符串为 (abc)abcbb 以 a(b)cabcbb 开始的最长字符串为 a(bca)bcbb 以 ab(c)abcbb 开始的最长字符串为 ab(cab)cbb 以 abc(a)bcbb 开始的最长字符串为 abc(abc)bb 以 abca(b)cbb 开始的最长字符串为 abca(bc)bb 以 abcab(c)bb 开始的最长字符串为 abcab(cb)b 以 abcabc(b)b 开始的最长字符串为 abcabc(b)b 以 abcabcb(b) 开始的最长字符串为 abcabcb(b)。
class Solution {public int lengthOfLongestSubstring(String S) {int len S.length();char[] s S.toCharArray();SetCharacter hs new HashSet();int res 0;for (int left 0, right 0; right len; right) {char ch s[right];while (hs.contains(ch)) {hs.remove(s[left]);left;}hs.add(s[right]);res Math.max(res, right - left 1);}return res;}
}
right: 当前子串的右边界索引。left: 当前子串的左边界索引。
子串的长度计算公式是 右边界索引 - 左边界索引 1。寓意着包含左右边界的字符串
No.2
1695.删除子数组的最大得分. - 力扣LeetCode
给你一个正整数数组 nums 请你从中删除一个含有 若干不同元素 的子数组。删除子数组的 得分 就是子数组各元素之 和 。
返回 只删除一个 子数组可获得的 最大得分 。
如果数组 b 是数组 a 的一个连续子序列即如果它等于 a[l],a[l1],...,a[r] 那么它就是 a 的一个子数组。 示例 1
输入nums [4,2,4,5,6]
输出17
解释最优子数组是 [2,4,5,6]示例 2
输入nums [5,2,1,2,5,2,1,2,5]
输出8
解释最优子数组是 [5,2,1] 或 [1,2,5]
class Solution {public int maximumUniqueSubarray(int[] nums) {int len nums.length; // 获取数组的长度SetInteger hs new HashSet(); // 创建一个 HashSet 用来存储当前子数组的元素int res 0, ans 0; // res 用于存储当前子数组的元素和ans 用于存储最大得分int i 0; // i 指针表示当前子数组的起点// j 指针表示当前子数组的终点for (int j 0; j len; j) {// 当 hs 中已经包含 nums[j] 时说明存在重复元素需要移动 i 指针while (hs.contains(nums[j])) {hs.remove(nums[i]); // 从 HashSet 中移除子数组的第一个元素res - nums[i]; // 从当前子数组的和中减去该元素的值i; // 移动起点指针 i}hs.add(nums[j]); // 将 nums[j] 添加到 HashSet 中res nums[j]; // 将 nums[j] 的值加到当前子数组的和中ans Math.max(res, ans); // 更新最大得分}return ans; // 返回只删除一个子数组可以获得的最大得分}
}
No.3 上难度
1004.最大连续1的个数III. - 力扣LeetCode
给定一个二进制数组 nums 和一个整数 k如果可以翻转最多 k 个 0 则返回 数组中连续 1 的最大个数 。 示例 1
输入nums [1,1,1,0,0,0,1,1,1,1,0], K 2
输出6
解释[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1最长的子数组长度为 6。
示例 2
输入nums [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K 3
输出10
解释[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1最长的子数组长度为 10。
这个题有个特点就是数组内只有 0 1
那我们就围绕这一特点进行攻破及cnt 1 - nums[right]; // 如果 nums[right] 是 0cnt 增加1如果是 1cnt 不变 class Solution {public int longestOnes(int[] nums, int k) {int cnt 0; // 记录当前窗口内0的个数int ans 0; // 记录最长的全1子数组的长度int left 0; // 滑动窗口的左边界// 右边界 right 从 0 开始遍历整个数组for (int right 0; right nums.length; right) {cnt 1 - nums[right]; // 如果 nums[right] 是 0cnt 增加1如果是 1cnt 不变// 如果当前窗口内的0的个数超过了允许的k个则需要收缩窗口while (cnt k) {cnt - 1 - nums[left]; // 移动左边界移除 nums[left] 的影响left; // 将左边界右移}// 更新最长子数组的长度ans Math.max(ans, right - left 1);}return ans; // 返回找到的最长的全1子数组的长度}
}
