Leetcode 76. 最小覆盖子串和Leetcode 34. 在排序数组中查找元素的第一个和最后一个位置

文章目录

Leetcode 76. 最小覆盖子串
- 题目描述
- C语言题解和思路
- - 解题思路
Leetcode 34. 在排序数组中查找元素的第一个和最后一个位置
- 题目描述
- C语言题解和思路
- - 解题思路

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