【LeetCode热题100】打卡第23天:最小覆盖&子集

这篇具有很好参考价值的文章主要介绍了【LeetCode热题100】打卡第23天:最小覆盖&子集。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【LeetCode热题100】打卡第23天:最小覆盖&子集

⛅前言

大家好,我是知识汲取者,欢迎来到我的LeetCode热题100刷题专栏!

精选 100 道力扣(LeetCode)上最热门的题目,适合初识算法与数据结构的新手和想要在短时间内高效提升的人,熟练掌握这 100 道题,你就已经具备了在代码世界通行的基本能力。在此专栏中,我们将会涵盖各种类型的算法题目,包括但不限于数组、链表、树、字典树、图、排序、搜索、动态规划等等,并会提供详细的解题思路以及Java代码实现。如果你也想刷题,不断提升自己,就请加入我们吧!QQ群号:827302436。我们共同监督打卡,一起学习,一起进步。

LeetCode热题100专栏🚀:LeetCode热题100

Gitee地址📁:知识汲取者 (aghp) - Gitee.com

题目来源📢:LeetCode 热题 100 - 学习计划 - 力扣(LeetCode)全球极客挚爱的技术成长平台

PS:作者水平有限,如有错误或描述不当的地方,恳请及时告诉作者,作者将不胜感激

最小覆盖

🔒题目

原题链接:76.最小覆盖子串

【LeetCode热题100】打卡第23天:最小覆盖&子集

🔑题解

  • 解法一:滑动窗口算法

    滑动窗口算法也写了好多遍了,这里就不再多做解释上,直接上代码

    【LeetCode热题100】打卡第23天:最小覆盖&子集

    PS:上面的动图来自LeetCode官方题解,我感觉特别好,就没有自己制作动图了,直接把它的录制下来了

    滑动窗口主要思路:

    • Step1:定义窗口。定义左右指针,一个是窗口左边界,一个是窗口右边界

    • Step2:滑动窗口。

      1. 扩充窗口,滑动右指针,判断窗口中的元素是否符合条件,不符合条件继续扩充窗口
      2. 缩小窗口,滑动左指针,判断窗口中的元素是否符合条件,符合条件继续缩小窗口

      经过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.lengtht.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.子集

【LeetCode热题100】打卡第23天:最小覆盖&子集

🔑题解

  • 解法一:BFS

    【LeetCode热题100】打卡第23天:最小覆盖&子集

    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)

    n为nums数组的元素个数文章来源地址https://www.toymoban.com/news/detail-487496.html

到了这里,关于【LeetCode热题100】打卡第23天:最小覆盖&子集的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode热题100】打卡第42天:滑动窗口最大值&搜索二维矩阵II

    大家好,我是知识汲取者,欢迎来到我的LeetCode热题100刷题专栏! 精选 100 道力扣(LeetCode)上最热门的题目,适合初识算法与数据结构的新手和想要在短时间内高效提升的人,熟练掌握这 100 道题,你就已经具备了在代码世界通行的基本能力。在此专栏中,我们将会涵盖各种

    2024年02月10日
    浏览(48)
  • 【LeetCode热题100】打卡第39天:数组中第K个最大元素&最大正方形

    大家好,我是知识汲取者,欢迎来到我的LeetCode热题100刷题专栏! 精选 100 道力扣(LeetCode)上最热门的题目,适合初识算法与数据结构的新手和想要在短时间内高效提升的人,熟练掌握这 100 道题,你就已经具备了在代码世界通行的基本能力。在此专栏中,我们将会涵盖各种

    2024年02月16日
    浏览(42)
  • LeetCode热题HOT100:76. 最小覆盖子串,84.柱状图中最大的矩形、96. 不同的二叉搜索树

    题目 :给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。 注意: 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串,我们保

    2023年04月19日
    浏览(56)
  • 螺旋矩阵 LeetCode热题100

    给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。 模拟,朝一个方向走,走过的点标记一下,直到碰到边界或碰到已经走过的路,换个方向。右-下,下-左,左-上,上-右。直到走完所有点。

    2024年02月14日
    浏览(54)
  • LeetCode 热题100——单调栈

    ​   个人主页: 日刷百题 系列专栏 : 〖C语言小游戏〗 〖Linux〗 〖数据结构〗   〖C语言〗 🌎 欢迎各位 → 点赞 👍+ 收藏 ⭐️+ 留言 📝  ​ ​ 递增单调栈:栈中元素从栈底到栈顶依次增大 递减单调栈:栈中元素从栈底到栈顶依次减小 在学习完朴素的数据结构栈之后,

    2024年02月04日
    浏览(40)
  • LeetCode 热题 HOT 100

    重点是当有一个链表为空了不单独处理,按节点为0处理。 滑动窗口! 首先要判断slow需不需要更新,怎么判断?slow = max(umap[s[fast]], slow);什么意思,就是说:**umap[s[fast]]的意义是,为了在slow和fast之间不出现重复字符,slow能处于的最左位置。**如图,当j第一次到d,将umap[s[j

    2024年02月07日
    浏览(46)
  • LeetCode热题 100整理

    35. 搜索插入位置 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: 输入: nums = [1,3,5,6], target = 5 输出: 2 示例 2: 输入: nums = [1,3,5,6], target

    2024年02月13日
    浏览(38)
  • LeetCode 热题 100 | 哈希

    目录 1  基础知识 1.1  定义哈希表 1.2  遍历哈希表 1.3  查找某一个键 1.4  插入键值对 1.5  获取键值对的值 1.6  搜索功能 2  三道题 2.1  1. 两数之和 2.2  49. 字母异位词分组 2.3  128. 最长连续序列 菜鸟做题第一周,语言是 C++ 1  基础知识 1.1  定义哈希表 unordered_map 用于定义

    2024年01月18日
    浏览(44)
  • LeetCode 热题 100 | 链表(上)

    目录 1  基础知识 1.1  空指针 1.2  结构体 1.3  指针访问 1.4  三目运算符 2  160. 相交链表 3  206. 反转链表 4  234. 回文链表 菜鸟做题第三周,语言是 C++ 1  基础知识 1.1  空指针 使用 nullptr 来判断是否为空指针: “NULL 在 C++ 中就是 0,这是因为在 C++ 中 void* 类型是不允许隐式

    2024年02月19日
    浏览(40)
  • LeetCode热题100——链表

    给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。 给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。 给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回

    2024年02月05日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包