一、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};
}
};
4.运行结果
文章来源:https://www.toymoban.com/news/detail-565320.html
总结
今天是算法练习的第6天。
锲而不舍,金石可镂 ,继续加油。
来源:力扣(LeetCode),著作权归领扣网络所有。
如果本篇文章对你有所启发的话,希望可以多多支持作者,谢谢大家!文章来源地址https://www.toymoban.com/news/detail-565320.html
到了这里,关于【优选算法题练习】day6的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!