分享秋招面试题-Toy模板网

这篇具有很好参考价值的文章主要介绍了分享秋招面试题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

今天分享的是两道秋招面试题(来自于求职同学收集)

两道出自于国内两大刷题网站牛客网和leetcode

第一道题 (最小覆盖子串)

题目表述

给出两个字符串 s 和 t，要求在 s 中找出最短的包含 t 中所有字符的连续子串。

数据范围：0≤ ∣S∣≤100000,∣T∣≤10000，保证s和t字符串中仅包含大小写英文字母

要求：进阶：空间复杂度 O(n) ，时间复杂度 O(n)

例如：

S="XDOYEZODEYXNZ"
T="XYZ"
找出的最短子串为"YXNZ".

注意：
如果 s 中没有包含 t 中所有字符的子串，返回空字符串 “”；
满足条件的子串可能有很多，但是题目保证满足条件的最短的子串唯一。

示例

输入：
"XDOYEZODEYXNZ","XYZ"
返回值：
"YXNZ"

输入：
"abcAbA","AA"

复制返回值：
"AbA"

解体思路

要求s字串都包含t，并且要求s字串长度最小，我们可以想到使用双指针+哈希来写，双指针控制在left---right的区间中，哈希map可以直接判断left---right的各字符个数于t中比较。如果各字符的个数都大于等于t中各字符，将left++，进而缩短字串的长度，如果left---right的各字符个数于t中比较出现少于t中各字符，说明不能满足于题目条件，需要right++扩大字串长度。

每次满足题目中的条件（t的各个字符个数都小于等于s字串）记录取最小值。

代码展示

#include <unordered_map>
class Solution {
public:
    
    string minWindow(string S, string T) {
        string s=S;
        string t=T;
        unordered_map<char, int>mp1;
        unordered_map<char, int>mp2;
        vector<pair<int,int>>res;
        for(int i=0;i<T.size();i++)
        {
            mp1[t[i]]++;
        }
        int left=0;
        int right=0;
        mp2[s[0]]++;
        while(right<s.size())
        {
            bool flag=false;  
            for(int i=0;i<t.size();i++)  //对t中各字符数量比较
            {
                char ch=t[i];
                if(mp1[ch]>mp2[ch])
                {
                    flag=true;
                    break;
                }
            }
            if(flag==true)
            {
                right++;
                mp2[s[right]]++;
            }
            else {
                mp2[s[left]]--;
                res.push_back({left,right});
                left++;
            }
        }
        int index=s.size();
        for(int i=0;i<res.size();i++)
        {
            int l=res[i].second-res[i].first+1;
            index=min(index,l);
        }
        string st;
        for(int i=0;i<res.size();i++)
        {
            int l=res[i].second-res[i].first+1;
            if(l==index)
            {
                st=s.substr(res[i].first,l);
            }
        }
        return st;
    }
};

第二道题 (和可被k整除的子数组)

题目表述

给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的（连续、非空）子数组的数目。

子数组是数组的连续部分。

1 <= nums.length <= 3 * 10000
-104 <= nums[i] <= 10000
2 <= k <= 10000

示例

输入：nums = [4,5,0,-2,-3,1], k = 5
输出：7
解释：有 7 个子数组满足其元素之和可被 k = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

输入: nums = [5], k = 9
输出: 0

解题思路

首先我得先提醒一下，这里的题目表示不是很清楚，可被K整除就是可以把K整除，编程表达就是 x%k=0

题意就是求出来有多少段子数组的和对k求余为0，几乎很快就可以想到一个O（N*N）的方法，但是超出时间限制，我们可以想到通过前缀和来算出每个子数组的和，时间复杂度为O（N），定义arr为前缀和数组 arr[right]-arr[left]就是left---right的和；要求(arr[right]-arr[left])%k==0，也可以表示为arr[right]%k==arr[left]%k。所以对于每个arr(前缀和数组)来说，对k求余后结果一样就说明两个边界的区间之和能把k整除。

如果余数1的个数为1，则将k整除个数为0

如果余数1的个数为2，则将k整除个数为1

如果余数1的个数为3，则将k整除个数为3

我们可以通过将每次哈希保存每个余数对应的个数。

代码展示

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int,int>mp;
        long long ans=0;
        mp[0]=1;
        int arr[nums.size()];
        arr[0]=nums[0];
        for(int i=1;i<nums.size();i++)
        {
            arr[i]=arr[i-1]+nums[i];
        }
        for(int i=0;i<nums.size();i++)
        {
            int x=(arr[i])%k;
            x=(x+k)%k;
            ans+=mp[x];
            mp[x]++;
        }
        return ans;
    }
};