Leetcode 76. 最小覆盖子串
题目描述
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”
解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。
示例 2：
输入：s = “a”, t = “a”
输出：“a”
解释：整个字符串 s 是最小覆盖子串。
示例 3：
输入: s = “a”, t = “aa”
输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
提示：
- m == s.length
- n == t.length
- 1 <= m, n <= 10^5
- s 和 t 由英文字母组成
进阶： 你能设计一个在 o(m+n) 时间内解决此问题的算法吗？
C语言题解和思路
char* minWindow(char* s, char* t) {
int sl = strlen(s), tl = strlen(t), left, right, count = sl + 1, start = 0;
if(tl > sl)
{
return "";
}
int hash[256] = {0};
for(int i = 0; i < tl; i++)
{
hash[t[i]]++;
}
for(left = 0, right = 0; right < sl; right++)
{
if(hash[s[right]]-- > 0)
{
tl--;
}
while(tl == 0)
{
if(count > right - left + 1)
{
count = right - left + 1;
start = left;
}
if(++hash[s[left]] > 0)
{
tl++;
}
left++;
}
}
if(count != sl + 1)
{
char *ret = (char *)malloc(sizeof(char) * (count + 1));
memcpy(ret, s + start, count);
ret[count] = '\0';
return ret;
}
return "";
}
解题思路
哈希表 + 滑动窗口
首先判断字符串 t 的长度和字符串 s 的长度，如果 t 长于 s ，说明字符串 s 不可能存在容纳 t 的子串，直接返回空。
创建一个哈希表并初始化为 0 ，然后循环字符串 t ，用哈希表记录 t 的字母的种类和数量。
将左右指针初始化为 0 ，将记录最小子串的长度的变量 count 初始化为字符串 s 的长度加一。
通过滑动窗口遍历字符串 s ， right 每将一个新元素纳入窗口，都先通过哈希表判断它是否在字符串 t 中出现过，如果出现过，则使字符串 t 的长度减一。当窗口将所有的字符串 t 中出现的元素都包含在内，也就是字符串 t 的长度归 0 时，开始循环判断窗口的左边界，同时 count 不断判断左右边界的距离，也就是最小覆盖子串的长度，并记录下此时左边界的位置，循环至窗口中无法覆盖所有的字符串 t 的元素为止。
循环结束后，判断 count 是否发生变化，如果它不再比字符串 s 还长，说明字符串 s 中存在满足条件的子串，此时将该子串通过memcpy函数、记录下来的左边界的值、最小的长度，将这段字符串复制到另一个字符数组当中，在新的字符串后添加上 ‘\0’ 后返回该字符串。
如果 count 没有发生改变，返回空。
Leetcode 34. 在排序数组中查找元素的第一个和最后一个位置
题目描述
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
提示：
- 0 <= nums.length <= 105
- -10 ^9 <= nums[i] <= 10 ^9
- nums 是一个非递减数组
- -10 ^9 <= target <= 10 ^9
C语言题解和思路
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
int *ret = (int *)malloc(sizeof(int) * 2);
ret[0] = -1;
ret[1] = -1;
*returnSize = 2;
if(numsSize == 0 || nums[0] > target || nums[numsSize - 1] < target )
{
return ret;
}
int left = 0, right = numsSize - 1, mid;
while(left <= right)
{
mid = (left + right) / 2;
if(nums[mid] == target)
{
left = mid;
right = mid;
while(left - 1 >= 0 && nums[left - 1] == target)
{
left--;
}
while(right + 1 < numsSize && nums[right + 1] == target)
{
right++;
}
ret[0] = left;
ret[1] = right;
return ret;
}
else if(nums[mid] > target)
{
right = mid - 1;
}
else if(nums[mid] < target)
{
left = mid + 1;
}
}
return ret;
}
解题思路
二分查找
首先将返回的数组 ret 初始化为-1，因为数组为有序数组，先判断数组个数是否为 0 ，数组的第一个元素是否大于 target 值，数组的最后一个元素是否小于 target 值，如果以上条件满足其一，直接返回数组 ret 。
进入循环，对数组进行二分查找，如果找到满足条件的值，将下标赋给左右指针，分别循环左右指针寻找数组中值等于 target 值的左右边界的下标，将左右下标传给数组 ret ，返回 ret 。
当二分查找完后数组仍没返回任何值，说明数组中不存在值等于 target 的元素，返回值为-1的数组 ret 。
