【优选算法题练习】day6

摘星

发布于 2023-10-15 15:54:07

1280

发布于 2023-10-15 15:54:07

文章被收录于专栏：C/C++学习

一、76. 最小覆盖子串

1.题目简介

76. 最小覆盖子串给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。注意：对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。如果 s 中存在这样的子串，我们保证它是唯一的答案。

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.运行结果

二、704. 二分查找

1.题目简介

704. 二分查找给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

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.运行结果

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

1.题目简介

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

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};
    }
};