黑色企业网站,如何自己做个人微信小程序,wordpress怎样修改主题模版,大型网站的设计文章目录 3. 无重复字符的最长子串1493. 删掉一个元素以后全为 1 的最长子数组904. 水果成篮1695. 删除子数组的最大得分2841. 几乎唯一子数组的最大和2024. 考试的最大困扰度1004. 最大连续1的个数 III1438. 绝对差不超过限制的最长连续子数组2401. 最长优雅子数组解法1——维… 文章目录 3. 无重复字符的最长子串1493. 删掉一个元素以后全为 1 的最长子数组904. 水果成篮1695. 删除子数组的最大得分2841. 几乎唯一子数组的最大和2024. 考试的最大困扰度1004. 最大连续1的个数 III1438. 绝对差不超过限制的最长连续子数组2401. 最长优雅子数组解法1——维护窗口内int各位出现的次数解法2——利用位运算的性质 维护窗口 1658. 将 x 减到 0 的最小操作数1838. 最高频元素的频数2831. 找出最长等值子数组解法1——双哈希表频次哈希表 和 频次的频次哈希表解法2——分组 双指针 2106. 摘水果1610. 可见点的最大数目⭐坐标转换成极角159. 至多包含两个不同字符的最长子串340. 至多包含 K 个不同字符的最长子串 题单来源
https://leetcode.cn/problems/minimum-size-subarray-in-infinite-array/solutions/2464878/hua-dong-chuang-kou-on-shi-jian-o1-kong-cqawc/ 3. 无重复字符的最长子串
https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/ 提示 0 s.length 5 * 10^4 s 由英文字母、数字、符号和空格组成
枚举右端点根据窗口内计数情况移动左端点。
class Solution {public int lengthOfLongestSubstring(String s) {int ans 0;int[] cnt new int[128];for (int l 0, r 0; r s.length(); r) {char ch s.charAt(r);cnt[ch];while (cnt[ch] 1) cnt[s.charAt(l)]--;ans Math.max(r - l 1, ans);}return ans;}
}1493. 删掉一个元素以后全为 1 的最长子数组
https://leetcode.cn/problems/longest-subarray-of-1s-after-deleting-one-element/description/ 提示
1 nums.length 10^5 nums[i] 要么是 0 要么是 1 。
窗口内最多有 1 个0用 id 记录上一个出现 0 的位置当出现新的 0 时将左端点设置为 l id 1。 这样就保持了窗口内始终最多有 1 个 0。
class Solution {public int longestSubarray(int[] nums) {int n nums.length, ans 0;for (int l 0, r 0, id -1; r n; r) {if (nums[r] 0) {l id 1;id r;}ans Math.max(r - l, ans);}return ans;}
}904. 水果成篮
https://leetcode.cn/problems/fruit-into-baskets/description/ 提示
1 fruits.length 10^5 0 fruits[i] fruits.length
class Solution {public int totalFruit(int[] fruits) {MapInteger, Integer m new HashMap();int ans 0;for (int l 0, r 0; r fruits.length; r) {m.merge(fruits[r], 1, Integer::sum);while (m.size() 2) {m.merge(fruits[l], -1, Integer::sum);if (m.get(fruits[l]) 0) m.remove(fruits[l]);l;}ans Math.max(ans, r - l 1);}return ans;}
}1695. 删除子数组的最大得分
https://leetcode.cn/problems/maximum-erasure-value/description/ 提示
1 nums.length 10^5 1 nums[i] 10^4
class Solution {public int maximumUniqueSubarray(int[] nums) {int n nums.length, ans 0, s 0;int[] cnt new int[10001];for (int l 0, r 0; r n; r) {s nums[r];cnt[nums[r]];while (cnt[nums[r]] 1) {s - nums[l];cnt[nums[l]]--;}if (s ans) ans s;}return ans;}
}用 s ans 判断会比使用 s Math.max(ans, s) 快一些。
2841. 几乎唯一子数组的最大和
https://leetcode.cn/problems/maximum-sum-of-almost-unique-subarray/description/ 提示
1 nums.length 2 * 10^4 1 m k nums.length 1 nums[i] 10^9
class Solution {public long maxSum(ListInteger nums, int m, int k) {long ans 0, n nums.size(), 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 l 0, r k - 1; r n; l, r) {s nums.get(r);cnt.merge(nums.get(r), 1, Integer::sum);if (cnt.size() m) ans Math.max(ans, s);s - nums.get(l);cnt.merge(nums.get(l), -1, Integer::sum);if (cnt.get(nums.get(l)) 0) cnt.remove(nums.get(l));}return ans;}
}2024. 考试的最大困扰度
https://leetcode.cn/problems/maximize-the-confusion-of-an-exam/description/ 提示 n answerKey.length 1 n 5 * 10^4 answerKey[i] 要么是 T 要么是 F 1 k n
维护一个滑动窗口枚举右端点当窗口中T和F的较小数量大于k时将左端点向右移。 在这个过程中用窗口长度更新答案。
class Solution {public int maxConsecutiveAnswers(String answerKey, int k) {int n answerKey.length(), ans 0;int t 0, f 0;for (int l 0, r 0; r n; r) {char a answerKey.charAt(r);if (a T) t;else f;// 将左端点向右移while (t k f k) {a answerKey.charAt(l);if (a T) t--;else f--;}ans Math.max(r - l 1, ans);}return ans;}
}1004. 最大连续1的个数 III
https://leetcode.cn/problems/max-consecutive-ones-iii/description/ 提示
1 nums.length 10^5 nums[i] 不是 0 就是 1 0 k nums.length
维护一个窗口中最多出现 k 个 0 的滑动窗口。
class Solution {public int longestOnes(int[] nums, int k) {int n nums.length, c0 0, ans 0;for (int l 0, r 0; r n; r) {if (nums[r] 0) c0;while (c0 k) {if (nums[l] 0) c0--;}ans Math.max(r - l 1, ans);}return ans;}
}1438. 绝对差不超过限制的最长连续子数组
https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/description/ 提示
1 nums.length 10^5 1 nums[i] 10^9 0 limit 10^9
同时维护窗口内的最大值和最小值。 可以使用 TreeMap 或者 单调队列来做。
class Solution {public int longestSubarray(int[] nums, int limit) {TreeMapInteger, Integer tm new TreeMap();int ans 0;for (int l 0, r 0; r nums.length; r) {tm.merge(nums[r], 1, Integer::sum);while (tm.lastKey() - tm.firstKey() limit) {tm.merge(nums[l], -1, Integer::sum);if (tm.get(nums[l]) 0) tm.remove(nums[l]);l;}ans Math.max(r - l 1, ans);}return ans;}
}2401. 最长优雅子数组
https://leetcode.cn/problems/longest-nice-subarray/description/ 提示 1 nums.length 10^5 1 nums[i] 10^9
解法1——维护窗口内int各位出现的次数
题目要求即为int的32位中每一位都最多出现一次。
class Solution {public int longestNiceSubarray(int[] nums) {int n nums.length, ans 0;int[] cnt new int[32];for (int l 0, r 0; r n; r) {op(cnt, nums[r], 1);while (!check(cnt)) op(cnt, nums[l], -1);ans Math.max(ans, r - l 1);}return ans;}public void op(int[] cnt, int x, int m) {for (int i 0; i cnt.length; i) {if ((x i 1) 1) cnt[i] m;}}public boolean check(int[] cnt) {for (int c: cnt) {if (c 1) return false;}return true;}
}解法2——利用位运算的性质 维护窗口
充分 利用了 ^ | 三种运算的性质。
使用 判断是否有交集。 使用 ^ 模拟去除。 使用 | 模拟加入。
class Solution {public int longestNiceSubarray(int[] nums) {int ans 0;for (int left 0, right 0, or 0; right nums.length; right) {// 有交集while ((or nums[right]) 0) {or ^ nums[left]; // 从 or 中去掉集合 nums[left]}or | nums[right]; // 把集合 nums[right] 并入 or 中ans Math.max(ans, right - left 1);}return ans;}
}
1658. 将 x 减到 0 的最小操作数
https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/description/ 提示 1 nums.length 10^5 1 nums[i] 10^4 1 x 10^9
等价于找到窗口内和为 sum - x 的最长子数组的长度。
class Solution {public int minOperations(int[] nums, int x) {// 等价于找到窗口内和为 sum - x 的最长子数组的长度。int n nums.length, t Arrays.stream(nums).sum() - x, ans -1, s 0;for (int l 0, r 0; r n; r) {s nums[r];while (l r s t) s - nums[l];if (s t) ans Math.max(ans, r - l 1); }return ans ! -1? n - ans: -1;}
}1838. 最高频元素的频数
https://leetcode.cn/problems/frequency-of-the-most-frequent-element/description/ 提示 1 nums.length 10^5 1 nums[i] 10^5 1 k 10^5
排序 滑动窗口。 每个窗口都假设变成最大的那个数字不能变的移出窗口。
class Solution {public int maxFrequency(int[] nums, int k) {Arrays.sort(nums);int n nums.length, ans 1;long s 0;for (int l 0, r 0; r n; r) {s nums[r];while ((long)(r - l 1) * nums[r] - k s) s - nums[l];if ((long)(r - l 1) * nums[r] - k s) ans Math.max(ans, r - l 1);}return ans;}
}2831. 找出最长等值子数组
https://leetcode.cn/problems/find-the-longest-equal-subarray/description/ 提示 1 nums.length 10^5 1 nums[i] nums.length 0 k nums.length
解法1——双哈希表频次哈希表 和 频次的频次哈希表
频次的频次哈希表 用于 快速找到最大的频次。
class Solution {public int longestEqualSubarray(ListInteger nums, int k) {int n nums.size(), ans 0;MapInteger, Integer cnt new HashMap();// 频次 哈希表 用于快速找到最大的频次TreeMapInteger, Integer pCnt new TreeMap();for (int l 0, r 0; r n; r) {cnt.merge(nums.get(r), 1, Integer::sum);pCnt.merge(cnt.get(nums.get(r)), 1, Integer::sum);pCnt.merge(cnt.get(nums.get(r)) - 1, -1, Integer::sum);while (r - l 1 - pCnt.lastKey() k) {cnt.merge(nums.get(l), -1, Integer::sum);pCnt.merge(cnt.get(nums.get(l)), 1, Integer::sum);pCnt.merge(cnt.get(nums.get(l)) 1, -1, Integer::sum);if (pCnt.get(cnt.get(nums.get(l)) 1) 0) pCnt.remove(cnt.get(nums.get(l)) 1);l;}ans Math.max(pCnt.lastKey(), ans);}return ans;}
}解法2——分组 双指针
https://leetcode.cn/problems/find-the-longest-equal-subarray/solutions/2396401/fen-zu-shuang-zhi-zhen-pythonjavacgo-by-lqqau/
算法思路见下图。
class Solution {public int longestEqualSubarray(ListInteger nums, int k) {int n nums.size(), ans 0;MapInteger, ListInteger m new HashMap();for (int i 0; i n; i) {if (!m.containsKey(nums.get(i))) {m.put(nums.get(i), new ArrayList());}ListInteger ls m.get(nums.get(i));ls.add(i - ls.size());}for (ListInteger ls: m.values()) {int res 0;for (int l 0, r 0; r ls.size(); r) {while (ls.get(r) - ls.get(l) k) l;res Math.max(res, r - l 1);}ans Math.max(ans, res);}return ans;}
}2106. 摘水果
https://leetcode.cn/problems/maximum-fruits-harvested-after-at-most-k-steps/description/ 维护一个窗口窗口中是可以被采集的水果。 随着右端点的枚举左端点也会随着窗口的扩大导致不合理从而将左端点右移。
class Solution {public int maxTotalFruits(int[][] fruits, int startPos, int k) {int ans 0, s 0;for (int l 0, r 0; r fruits.length; r) {s fruits[r][1];while (l r !check(fruits[l][0], fruits[r][0], startPos, k)) s- fruits[l][1];ans Math.max(ans, s);}return ans;}// 检查窗口是否合理public boolean check(int a, int b, int x, int k) {if (a x b x) return x - a k; // 都在左边if (a x b x) return b - x k; // 都在右边// a在左边b在右边a x - a;b b - x;return Math.min(a, b) * 2 Math.max(a, b) k;}
}1610. 可见点的最大数目⭐坐标转换成极角
https://leetcode.cn/problems/maximum-number-of-visible-points/description/ 提示 1 points.length 10^5 points[i].length 2 location.length 2 0 angle 360 0 posx, posy, xi, yi 100
坐标转成极角的方法为 Math.atan2()见https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/Math.html#atan2(double,double)
将极角存入列表之后再重复加入 2pi 的元素这是为了计算完全。 最后使用滑动窗口计算。
class Solution {public int visiblePoints(ListListInteger points, int angle, ListInteger location) {int sameCnt 0;ListDouble polarDegrees new ArrayList();int x0 location.get(0), y0 location.get(1);for (int i 0; i points.size(); i) {int x points.get(i).get(0), y points.get(i).get(1);if (x x0 y y0) {sameCnt;continue;}Double degree Math.atan2(y - y0, x - x0);polarDegrees.add(degree);}Collections.sort(polarDegrees);int m polarDegrees.size();for (int i 0; i m; i) {polarDegrees.add(polarDegrees.get(i) 2 * Math.PI);}int maxCnt 0;double toDegree angle * Math.PI / 180;for (int l 0, r 0; l m; l) {Double curr polarDegrees.get(l) toDegree;while (r polarDegrees.size() polarDegrees.get(r) curr) {r;}maxCnt Math.max(maxCnt, r - l);}return maxCnt sameCnt;}
} 159. 至多包含两个不同字符的最长子串
https://leetcode.cn/problems/longest-substring-with-at-most-two-distinct-characters/description/ 维护各个字符的出现次数当哈希表中字符种类大于 2 的时候将左端点右移。
class Solution {public int lengthOfLongestSubstringTwoDistinct(String s) {int n s.length(), ans 0;MapCharacter, Integer cnt new HashMap();for (int l 0, r 0; r n; r) {cnt.merge(s.charAt(r), 1, Integer::sum);while (cnt.size() 2) {cnt.merge(s.charAt(l), -1, Integer::sum);if (cnt.get(s.charAt(l)) 0) cnt.remove(s.charAt(l));l;}ans Math.max(ans, r - l 1);}return ans;}
}340. 至多包含 K 个不同字符的最长子串
https://leetcode.cn/problems/longest-substring-with-at-most-k-distinct-characters/description/ 把上一题的 2 换成 k 就好了。
class Solution {public int lengthOfLongestSubstringKDistinct(String s, int k) {int n s.length(), ans 0;MapCharacter, Integer cnt new HashMap();for (int l 0, r 0; r n; r) {cnt.merge(s.charAt(r), 1, Integer::sum);while (cnt.size() k) {cnt.merge(s.charAt(l), -1, Integer::sum);if (cnt.get(s.charAt(l)) 0) cnt.remove(s.charAt(l));l;}ans Math.max(ans, r - l 1);}return ans;}
}
