【优选算法题练习】day5

摘星

发布于 2023-10-15 15:53:48

1560

发布于 2023-10-15 15:53:48

文章被收录于专栏：C/C++学习

一、904. 水果成篮

1.题目简介

904. 水果成篮你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果种类。你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：你只有两个篮子，并且每个篮子只能装单一类型的水果。每个篮子能够装的水果总量没有限制。你可以选择任意一棵树开始采摘，你必须从每棵树（包括开始采摘的树）上恰好摘一个水果。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。给你一个整数数组 fruits ，返回你可以收集的水果的最大数目。

2.解题思路

3.代码

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int left = 0, right = 0;
        int ret = 0;
        int kinds = 0;
        vector<int> ma(100000);
        while(right < fruits.size())
        {
            //入窗口
            if(ma[fruits[right]] == 0) kinds++;
            ma[fruits[right++]]++;
            //出窗口
            while(kinds > 2)
            {
                ma[fruits[left]]--;
                if(ma[fruits[left]] == 0) kinds--;
                left++;
            }
            //更新结果
            ret = max(ret, right - left);
        }
        return ret;
    }
};

4.运行结果

二、438. 找到字符串中所有字母异位词

1.题目简介

438. 找到字符串中所有字母异位词给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。异位词指由相同字母重排列形成的字符串（包括相同的字符串）。

2.解题思路

3.代码

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int n = s.size(), m = p.size();
        vector<int> vp(26, 0);
        for(auto& e : p)
        {
            vp[e - 'a']++;
        }
        vector<int> vc(26, 0);
        int left = 0, right = 0;
        int count = 0;
        vector<int> ret;
        while(right < n)
        {
            //ruchaungkou
            if(++vc[s[right] - 'a'] <= vp[s[right] - 'a']) count++;
            //chuchuangkou
            if(right - left + 1 > m)
            {
                if(vc[s[left] - 'a']-- <= vp[s[left] - 'a']) count--;
                left++;
            }
            if(count == m) ret.push_back(left);
            right++;
        }
        return ret;
    }
};

4.运行结果

三、30. 串联所有单词的子串

1.题目简介

30. 串联所有单词的子串给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串长度相同。 s 中的串联子串是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。例如，如果 words = [“ab”,“cd”,“ef”]，那么 “abcdef”， “abefcd”，“cdabef”， “cdefab”，“efabcd”，和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串，因为他不是任何 words 排列的连接。返回所有串联字串在 s 中的开始索引。你可以以任意顺序返回答案。

2.解题思路

3.代码

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, int> ma1;//words中单词及出现的频率
        //map<第一个元素, 第二个元素>
        for(auto& e : words)
        {
            ma1[e]++;
        }
        int len = words[0].size(), m = words.size();
        int left = 0, right = 0;
        vector<int> ret;
        for(int i = 0;i < len; ++i)
        {
            unordered_map<string, int> ma2;
            int count = 0;//
            for(int left = i, right = i;right + len <= s.size(); right += len)
            {
                //入窗口
                string t1 = s.substr(right, len);
                if(++ma2[t1] <= ma1[t1]) count++;
                //出窗口
                while(right - left + 1 > len * m)
                {
                    string t2 = s.substr(left, len);
                    if(ma2[t2]-- <= ma1[t2]) count--;
                    left += len;
                }
                //更新结果
                if(count == m)//判断当前滑动窗口是否满足题目要求
                {
                    ret.push_back(left);
                }
            }
        }
        return ret;
    }
};