【优选算法题练习】day6

这篇具有很好参考价值的文章主要介绍了【优选算法题练习】day6。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


一、76. 最小覆盖子串

1.题目简介

76. 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。
注意:对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串,我们保证它是唯一的答案。
【优选算法题练习】day6,优选算法题练习,算法,leetcode
【优选算法题练习】day6,优选算法题练习,算法,leetcode

2.解题思路

3.代码

class Solution {
public:
    string minWindow(string s, string t) {
        int n = s.size(), m = t.size();
        vector<int> vt(128);
        for(auto& e : t)
        {
            vt[e]++;
        }
        vector<int> vs(128, 0);
        int count = 0;
        int len = INT_MAX;
        int begin = 0;
        for(int left = 0, right = 0;right < n; ++right)
        {
            char t = s[right];
            if(++vs[t] <= vt[t]) count++;
            while(count == m)
            {
                len < (right - left + 1) ? len : (len = (right - left + 1), begin = left);
                char t = s[left];
                if(vs[t]-- <= vt[t]) count--;
                left++;
            }
        }
        if(len == INT_MAX) return "";
        return s.substr(begin, len);
    }
};

4.运行结果

【优选算法题练习】day6,优选算法题练习,算法,leetcode

二、704. 二分查找

1.题目简介

704. 二分查找
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
【优选算法题练习】day6,优选算法题练习,算法,leetcode

2.解题思路

3.代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target)
            {
                left = mid + 1;
            }
            else if(nums[mid] > target)
            {
                right = mid - 1;
            }
            else
            {
                return mid;
            }
        }
        return -1;
    }
};

4.运行结果

【优选算法题练习】day6,优选算法题练习,算法,leetcode

三、34. 在排序数组中查找元素的第一个和最后一个位置

1.题目简介

34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
【优选算法题练习】day6,优选算法题练习,算法,leetcode

2.解题思路

3.代码

class Solution {
public:
    int _bsearch(vector<int>& nums, int target)
    {
        int left = 0, right = nums.size() - 1;
        while(left <= right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target)
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }
        return right + 1;
    }
    int _esearch(vector<int>& nums, int target)
    {
        int left = 0, right = nums.size() - 1;
        while(left <= right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] <= target)
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }
        return left - 1;
    }
    vector<int> searchRange(vector<int>& nums, int target) {
        int begin = _bsearch(nums, target);
        int end = _esearch(nums, target);
        if(begin <= end && end < nums.size() && begin >= 0)
        return {begin, end};
        return {-1, -1};
    }
};

4.运行结果

【优选算法题练习】day6,优选算法题练习,算法,leetcode


总结

今天是算法练习的第6天。
锲而不舍,金石可镂 ,继续加油。
来源:力扣(LeetCode),著作权归领扣网络所有。
如果本篇文章对你有所启发的话,希望可以多多支持作者,谢谢大家!文章来源地址https://www.toymoban.com/news/detail-565320.html

到了这里,关于【优选算法题练习】day6的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 算法练习Day30 (Leetcode/Python-动态规划)

    62. Unique Paths There is a robot on an  m x n  grid. The robot is initially located at the  top-left corner  (i.e.,  grid[0][0] ). The robot tries to move to the  bottom-right corner  (i.e.,  grid[m - 1][n - 1] ). The robot can only move either down or right at any point in time. Given the two integers  m  and  n , return  the number of possible

    2024年01月20日
    浏览(41)
  • 【算法训练(day6)】双指针模板

    通常情况下我们可能会遇到在某些可遍历的集合中寻找满足某种性质的字串或元素。这时候我们采取暴力的思路就会面临多重循环。我们可以利用题目中所给的集合并利用其性质将多重循环降成一重循环。光用语言描述可能不太好理解。接下来看几个双指针典型案例 请从字符

    2024年02月06日
    浏览(32)
  • 新星计划Day6【数据结构与算法】 链表Part2

    👩‍💻博客主页:京与旧铺的博客主页 ✨欢迎关注🖱点赞🎀收藏⭐留言✒ 🔮本文由京与旧铺原创,csdn首发! 😘系列专栏:java学习 💻首发时间:🎞2022年4月30日🎠 🎨你做三四月的事,八九月就会有答案,一起加油吧 🀄如果觉得博主的文章还不错的话,请三连支持一

    2023年04月08日
    浏览(56)
  • Day.1 LeetCode刷题练习(最长公共前缀 C/C++两种解法)

    题目: 例子: 分析题目: 主要目的:求出各个字符串的公共前缀 思路(本人解法): 用所给实例来看,不难看出我们可以直接以竖着对应来查看是否是公共前缀 ,  这样就有了一定的思路 , 然后接着想如何让他找到最长的公共前缀后就 停止下来呢  这样就能想到,从最

    2024年02月11日
    浏览(38)
  • 贪心算法练习day.1

    贪心算法是一种常见的解决优化问题的方法,其基本思想就是在问题的每个决策阶段,都选择当前看起来最优的选择,即 贪心地做出局部的最优决策,以此得到全局的最优解, 例如在十张面额不同的钞票,让我们去取5张,那如何拿到最多的钱呢?那我们每次取钞票时只需要

    2024年04月27日
    浏览(33)
  • 贪心算法练习day2

    1)初始化最小字母为‘Z’,确保任何字母都能与之比较 2)遍历单词,找到当前未删除字母中的最小字母 3)获取当前位置的字母  current = word.charAt(i); 4)删除最小字母之前的所有字母  word=word.substring(index+1); 5)  将最小字母添加到结果字符,更新剩余可删除字母数量 t -=

    2024年02月20日
    浏览(38)
  • 算法练习--leetcode 数组

    输入n阶楼梯,每次爬1或者2个台阶,有多少种方法可以爬到楼顶? 示例1:输入2, 输出2 一次爬2阶; 一次爬1阶; 故两种方法。 示例2: 输入3, 输出3 三个1; 一个1 + 一个 2; 一个2 + 一个1; 思路分析: 采用递归求解 python实现: java实现 : 类似爬楼梯问题。   给定一个 整

    2024年02月14日
    浏览(39)
  • 【算法练习Day51】柱状图中最大的矩形

    ​📝个人主页:@Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:练题 🎯 长路漫漫浩浩,万事皆有期待 力扣题目链接 给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。 求在该柱状图中,能够勾勒出来的矩

    2024年01月22日
    浏览(41)
  • 每天一道算法练习题--Day18 && 第一章 --算法专题 --- ----------前缀树

    字典树也叫前缀树、Trie。它本身就是一个树型结构,也就是一颗多叉树,学过树的朋友应该非常容易理解,它的核心操作是插入,查找。删除很少使用,因此这个讲义不包含删除操作。 截止目前(2020-02-04) 前缀树(字典树) 在 LeetCode 一共有 17 道题目。其中 2 道简单,8 个

    2024年02月02日
    浏览(51)
  • 代码随想录算法练习Day1:二分查找

    题目链接:704. 二分查找 卡哥视频讲解:手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode:704. 二分查找 二分法概述: 二分法(Binary Search)是一种在有序数组或列表中查找目标元素的算法。 二分法使用前提 : 有序数组或列表 :二分法要求在查找的数据结

    2024年04月23日
    浏览(52)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包