leetcode
- 16. 最小覆盖子串（hard）
- 17. 二分查找（easy）
- 18. 在排序数组中查找元素的第⼀个和最后⼀个位置（medium）
- 19.搜索插入位置（easy）
- 20. x的平方根（easy）
16. 最小覆盖子串（hard）
最小覆盖子串
#define MAX 100001
class Solution {
public:string minWindow(string s, string t) {int src_hash[128];int kind=0;//统计子串字符种类数int len=MAX;//标志最长数int begin=-1;for(auto ch:t){if(src_hash[ch]==0)kind++;src_hash[ch]++;}int des_hash[128];for(int left=0,right=0,count=0;right<s.size();right++){char in=s[right];des_hash[in]++;//进窗口if(des_hash[in]==src_hash[in])count++;//只有字符相同且数量相同才是相同的种类while(count==kind)//更新结果{if(len>right-left+1){len=right-left+1;begin=left;}char out=s[left];if(des_hash[out]==src_hash[out])count--;//只有字符相同且数量相同才是相同的种类des_hash[out]--;left++;}}if(begin==-1)return{};elsereturn s.substr(begin,len); }
};
17. 二分查找（easy）
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)right=mid-1;else if(nums[mid]<target)left=mid+1;else return mid;}return -1; }
};
18. 在排序数组中查找元素的第⼀个和最后⼀个位置（medium）
在排序数组中查找元素的第⼀个和最后⼀个位置
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {//处理边界情况if(nums.size()==0)return {-1,-1};//找左端点和右端点//找左端点//左端点的左区间是小于target，右区间是大于等于target//左端点就是左区间趋近右区间最后重合的地方//右端点的左区间是小于等于target，右区间是大于target//右端点就是右区间趋近左区间区间最后重合的地方int left=0,right=nums.size()-1;int begin=0;//标记左端点while(left<right)//left等于right时为左端点另做判断{int mid=left+(right-left)/2;//左区间在动因此向上取整if(nums[mid]<target){left=mid+1;}else{right=mid;}}if(nums[left]==target)begin=left;else return{-1,-1};left=0,right=nums.size()-1;while(left<right)//left等于right时为右端点另做判断{int mid=left+(right-left+1)/2;//左区间不动因此向下取整if(nums[mid]<=target){left=mid;}else{right=mid-1;}}return {begin,right};}
};
19.搜索插入位置（easy）
搜索插入位置
class Solution {
public:int searchInsert(vector<int>& nums, int target) {//找左端点//左端点的左区间小于target//左端点的右区间大于等于targetint left=0,right=nums.size()-1;while(left<right){int mid=left+(right-left)/2;if(nums[mid]<target)left=mid+1;elseright=mid;}if(nums[left]<target)return left+1;return left;}
};
20. x的平方根（easy）
x的平方根
class Solution {
public:int mySqrt(int x) {//右端点问题if(x<1)return 0;//处理边界情况int left=1,right=x;while(left<right){long long mid=left+(right-left+1)/2;long long sqrt=mid*mid;if(sqrt<=x){left=mid;}else{right=mid-1;}}return left; }
};
