力扣labuladong——一刷day10

这篇具有很好参考价值的文章主要介绍了力扣labuladong——一刷day10。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档文章来源地址https://www.toymoban.com/news/detail-718597.html


前言


一、力扣76. 最小覆盖子串

class Solution {
    public String minWindow(String s, String t) {
        Map<Character,Integer> need = new HashMap<>();
        Map<Character,Integer> window = new HashMap<>();
        for(char c : t.toCharArray()){
            need.put(c,need.getOrDefault(c,0)+1);
        }
        int left = 0, right = 0, indexLeft = 0, len = Integer.MAX_VALUE, vaild = 0;
        while(right < s.length()){
            char c = s.charAt(right);
            right ++;
            //扩大窗口
            if(need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if(window.get(c).equals(need.get(c))){
                    vaild ++;
                }
            }
            //缩小窗口
            while(vaild == need.size()){
                //更新收集结果
                if(right - left < len){
                    len = right - left;
                    indexLeft = left;
                }
                char cur = s.charAt(left);
                left ++;
                //缩小窗口
                if(need.containsKey(cur)){
                    if(need.get(cur).equals(window.get(cur))){
                        vaild --;
                    }
                    window.put(cur,window.get(cur)-1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(indexLeft,indexLeft+len);
    }
}

二、力扣567. 字符串的排列

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        Map<Character,Integer> need = new HashMap<>();
        Map<Character,Integer> window = new HashMap<>();
        for(char c : s1.toCharArray()){
            need.put(c,need.getOrDefault(c,0)+1);
        }
        int left = 0, right = 0, vaild = 0; boolean flag = false;
        while(right < s2.length()){
            char c = s2.charAt(right);
            right ++;
            if(need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if(need.get(c).equals(window.get(c))){
                    vaild ++;
                }
            }
            while(right - left >= s1.length()){
                if(vaild == need.size()){
                    return true;
                }
                char cur = s2.charAt(left);
                left ++;
                if(need.containsKey(cur)){
                    if(need.get(cur).equals(window.get(cur))){
                        vaild --;
                    }
                    window.put(cur,window.get(cur)-1);
                }
            }
        }
        return false;
    }
}

三、力扣438. 找到字符串中所有字母异位词

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        for(char c : p.toCharArray()){
            need.put(c,need.getOrDefault(c,0)+1);
        }
        int left = 0, right = 0, vaild = 0;
        while(right < s.length()){
            //窗口扩大
            char c = s.charAt(right);
            right ++;
            //调整窗口
            if(need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if(window.get(c).equals(need.get(c))){
                    vaild ++;
                }
            }
            while(right - left >= p.length()){
                //收集
                if(vaild == need.size()){
                    res.add(left);
                }
                //缩小窗口
                char cur = s.charAt(left);
                left ++;
                //调整窗口
                if(need.containsKey(cur)){
                    if(window.get(cur).equals(need.get(cur))){
                        vaild --;
                    }
                    window.put(cur,window.get(cur)-1);
                }
            }
        }
        return res;
    }
}

四、力扣3. 无重复字符的最长子串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0;
        Map<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0;
        while(right < s.length()){
            char c = s.charAt(right);
            right ++;
            window.put(c,window.getOrDefault(c,0)+1);
            while(window.get(c) > 1){
                char cur = s.charAt(left);
                left ++;
                window.put(cur,window.get(cur)-1);
            }
            res = Math.max(res,right-left);
        }
        return res;
    }
}

到了这里,关于力扣labuladong——一刷day10的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 力扣labuladong一刷day63天单词拆分

    力扣labuladong一刷day63天单词拆分 一、139. 单词拆分 题目链接:https://leetcode.cn/problems/word-break/description/ 思路:s是否能被拆分成字典中的单词,单词数量是不限的,故是完全背包问题,不限数量的单词是否能组成字符串s,可以看的出来,并不是要求你长度相等就可以,还得有

    2024年01月21日
    浏览(36)
  • 力扣labuladong一刷day59天动态规划

    力扣labuladong一刷day59天动态规划 一、509. 斐波那契数 题目链接:https://leetcode.cn/problems/fibonacci-number/description/ 思路:这是非常典型的一道题,下面是优化过的代码,a,b就是dp数组,因为每计算一个值,需要前两个值,这个a,b就是用来记录前两个值,避免重复计算,递推公式便

    2024年01月21日
    浏览(49)
  • 力扣labuladong一刷day39天最近公共祖先问题

    力扣labuladong一刷day39天最近公共祖先问题 一、236. 二叉树的最近公共祖先 题目链接:https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/ 思路:寻找最近公共祖先,在前序的位置判断,如果找到一个就返回,然后在后序的位置收尾,即左右子树都遍历过了,如果都找到的话

    2024年02月04日
    浏览(38)
  • 力扣labuladong一刷day40天计算完全二叉树节点数

    力扣labuladong一刷day40天计算完全二叉树节点数 一、222. 完全二叉树的节点个数 题目链接:https://leetcode.cn/problems/count-complete-tree-nodes/ 思路:计算完全二叉树直接全遍历的话很浪费时间,但是可以利用完全二叉树的特性来解题, 每到一个节点我们就计算它的left = node.left深度,

    2024年02月04日
    浏览(43)
  • 【Java数据结构与算法】Day2-高级排序(希尔、归并、快速、计数)

    ✅作者简介:热爱Java后端开发的一名学习者,大家可以跟我一起讨论各种问题喔。 🍎个人主页:Hhzzy99 🍊个人信条:坚持就是胜利! 💞当前专栏:【Java数据结构与算法】 🥭本文内容:Java数据结构与算法中的比较高级的排序,希尔排序、归并排序、快速排序、计数排序

    2024年02月02日
    浏览(64)
  • java数据结构与算法刷题-----LeetCode283. 移动零

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 双指针,用right和left两个指针,将非0元素,全部按顺序换到数组前面。left指向左边非0元素应该插入的位置,right找到非

    2024年01月21日
    浏览(49)
  • java数据结构与算法刷题-----LeetCode566. 重塑矩阵

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 代码:时间复杂度O(r*c).除题目要求外,算法本身没有需要额外空间,空间复杂度O(1) 从0开始算,一个3列n行矩阵中,每行就有3个元

    2024年01月21日
    浏览(46)
  • day19【LeetCode力扣】160.相交链表

    1.题目描述 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。 图示两个链表在节点 c1 开始相交**:** 题目数据 保证 整个链式结构中不存在环。 注意 ,函数返回结果后,链表必须 保持其原始结构

    2024年01月18日
    浏览(40)
  • java数据结构与算法刷题-----LeetCode287. 寻找重复数

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 弗洛伊德判圈法,也就是快慢指针判圈法(龟兔赛跑算法),此算法分为两个步骤 判断是否有环,并得到快慢指针相遇

    2024年01月24日
    浏览(43)
  • 力扣python刷题day03|LeetCode203、707、206

    题目 题目链接:203:移除链表元素 方法一: 知识点: 设置虚拟头结点 题目 来源:力扣(LeetCode) 提示: 0 = index, val = 1000 请不要使用内置的 LinkedList 库。 调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。 方法一:单链表法 方法二:双链表法 (有点难

    2024年02月16日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包