【LeetCode热题100】打卡第23天:最小覆盖&子集
⛅前言
大家好,我是知识汲取者,欢迎来到我的LeetCode热题100刷题专栏!
精选 100 道力扣(LeetCode)上最热门的题目,适合初识算法与数据结构的新手和想要在短时间内高效提升的人,熟练掌握这 100 道题,你就已经具备了在代码世界通行的基本能力。在此专栏中,我们将会涵盖各种类型的算法题目,包括但不限于数组、链表、树、字典树、图、排序、搜索、动态规划等等,并会提供详细的解题思路以及Java代码实现。如果你也想刷题,不断提升自己,就请加入我们吧!QQ群号:827302436。我们共同监督打卡,一起学习,一起进步。
LeetCode热题100专栏🚀:LeetCode热题100
Gitee地址📁:知识汲取者 (aghp) - Gitee.com
题目来源📢:LeetCode 热题 100 - 学习计划 - 力扣(LeetCode)全球极客挚爱的技术成长平台
PS:作者水平有限,如有错误或描述不当的地方,恳请及时告诉作者,作者将不胜感激
最小覆盖
🔒题目
原题链接:76.最小覆盖子串
🔑题解
-
解法一:滑动窗口算法
滑动窗口算法也写了好多遍了,这里就不再多做解释上,直接上代码
PS:上面的动图来自LeetCode官方题解,我感觉特别好,就没有自己制作动图了,直接把它的录制下来了
滑动窗口主要思路:
-
Step1:定义窗口。定义左右指针,一个是窗口左边界,一个是窗口右边界
-
Step2:滑动窗口。
- 扩充窗口,滑动右指针,判断窗口中的元素是否符合条件,不符合条件继续扩充窗口
- 缩小窗口,滑动左指针,判断窗口中的元素是否符合条件,符合条件继续缩小窗口
经过1.和2.不断迭代,最终让左右指针构造的窗口从左往右滑动起来,然后就能取得我们需要的极值
总的来说,滑动窗口思想还剩很简单的,核心是对于窗口条件扩充和缩小条件的判断
import java.util.HashMap; import java.util.Map; /** * @author ghp * @title 最小覆盖子串 */ class Solution { public String minWindow(String s, String t) { if (s.length() < t.length()) { // s的长度小于t,s不可能覆盖t return ""; } // map用于判断窗口是否可以缩小 Map<Character, Integer> map = new HashMap<>(); for (int k = 0; k < t.length(); k++) { char key = t.charAt(k); if (map.containsKey(key)) { map.put(t.charAt(k), map.get(key) + 1); } else { map.put(t.charAt(k), 1); } } // 存储窗口中的元素 Map<Character, Integer> contains = new HashMap<>(); for (int k = 0; k < t.length(); k++) { contains.put(t.charAt(k), 0); } // 左右指针 int i = 0; int j = 0; // 记录窗口的最小长度 int min = Integer.MAX_VALUE; // 记录窗口最小长度时的左右边界 int start = -1; // 从做左到右滑动窗口 while (j < s.length()) { if (contains.containsKey(s.charAt(j))) { Character key = s.charAt(j); Integer value = contains.get(key); contains.put(key, value + 1); } while (isCover(map, contains)) { // 窗口中的元素已经能够覆盖t,缩小窗口 if (min > (j - i + 1)) { // 如果当前窗口的长度为最小长度,则更新start和end min = j - i + 1; start = i; } if (contains.containsKey(s.charAt(i))) { // 移除左边界的元素 Character key = s.charAt(i); Integer value = contains.get(key); contains.put(key, value - 1); } // 滑动窗口左边界 i++; } // 滑动窗口右边界 j++; } // 返回最小窗口长度的字符串(这里要判断start是否是-1,防止索引越界) return start == -1 ? "" : s.substring(start, start + min); } private boolean isCover(Map<Character, Integer> map, Map<Character, Integer> contains) { // 遍历map,判断当前窗口中的元素是否覆盖t for (Character key : map.keySet()) { if (map.get(key) > contains.getOrDefault(key, 0)) { // 如果窗口中没有map对应等待元素 或者 窗口中的元素数量不够 return false; } } return true; } }
复杂度分析:
- 时间复杂度:最好 O ( s . l e n g t h ) O(s.length) O(s.length),最坏 O ( s . l e n g t h ∗ t . l e n g t h ) O(s.length*t.length) O(s.length∗t.length)
- 空间复杂度: O ( s . l e n g t h + t . l e g n t h ) O(s.length+t.legnth) O(s.length+t.legnth)
代码优化:
- 时间优化:上面代码比较简单,容易理解,但是每次都需要遍历两边map集合,判断窗口是否符合条件的判断,也需要遍历一遍map集合,耗时比较就,经过提交测试,发现平均耗时高达170ms,排名也比较低。后面我们使用一个count变量来判断当前是否符合条件,从而无需遍历map集合来判别
- 空间优化:上面代码采用了两个map集合,空间占用较多。所以我们可以单独使用一个数组,这个数组比较讲究,大小刚好是128,09AZa~z 的ASCII刚好是0~128。数组是一种比较简单的数据结构,空间占用较少
/** * @author ghp * @title 最小覆盖子串 */ class Solution { public String minWindow(String s, String t) { if (s.length() < t.length()) { return ""; } int[] letter = new int[128]; // 记录t中字符出现的次数 for (int i = 0; i < t.length(); i++) { letter[t.charAt(i)]++; } int l = 0; // 窗口左边界 int r = 0; // 窗口左右边界 int min = Integer.MAX_VALUE; // 记录当前能够覆盖t的最小窗口的长度 int start = -1; // 记录当前能够覆盖t的最小窗口的长度时的左边界 int count = t.length(); while (r < s.length()) { char ch = s.charAt(r); if (letter[ch] > 0) { // 当前字符被t包含,count-- count--; } // 把右边的字符加入窗口 letter[ch]--; if (count == 0) { // 窗口中的字母已经覆盖t,判断窗口是否需要缩小 while (l < r && letter[s.charAt(l)] < 0) { // 左侧元素已经超过了需要的次数,移除左侧元素 letter[s.charAt(l)]++; l++; } if (min > r - l + 1) { // 当前窗口中字符的长度为最小的,更新start和min min = r - l + 1; start = l; } // 移除左侧元素使窗口不能够覆盖t,重新开始循环 letter[s.charAt(l)]++; l++; count++; } r++; } return start == -1 ? "" : s.substring(start, start + min); } }
经过提交测试,平均耗时只有大约2ms(前面的代码平均耗时170ms),空间占用42MB(前面的代码占用43MB),毫无疑问这次优化是十分值得的(●’◡’●)
复杂度分析:
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( 1 ) O(1) O(1)
其中 n n n 为数组中元素的个数
-
子集
🔒题目
原题链接:78.子集
🔑题解
-
解法一:BFS
import java.util.*; /** * @author ghp * @title 最小覆盖子串 */ class Solution { private Deque<Integer> path = new LinkedList<>(); private Map<Integer, Integer> map; public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> ans = new ArrayList<>(); ans.add(Collections.emptyList()); boolean[] vis = new boolean[nums.length]; bfs(ans, path, vis, nums, 0); return ans; } private void bfs(List<List<Integer>> ans, Deque<Integer> path, boolean[] vis, int[] nums, int step) { if (path.size() > nums.length) { return; } for (int i = step; i < nums.length; i++) { if (!vis[i]) { path.addLast(nums[i]); vis[i] = true; ans.add(new ArrayList<>(path)); bfs(ans, path, vis, nums, i); vis[i] = false; path.removeLast(); } } } }
复杂度分析
时间复杂度: O ( n ! ) O(n!) O(n!)
空间复杂度: O ( n ! + n ) O(n!+n) O(n!+n)文章来源:https://www.toymoban.com/news/detail-487496.html
n为nums数组的元素个数文章来源地址https://www.toymoban.com/news/detail-487496.html
到了这里,关于【LeetCode热题100】打卡第23天:最小覆盖&子集的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!