• 【算法挨揍日记】day07——904. 水果成篮、438. 找到字符串中所有字母异位词


     904. 水果成篮

    904. 水果成篮

    题目描述:

    你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示,其中 fruits[i] 是第 i 棵树上的水果 种类 。

    你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果:

    • 你只有 两个 篮子,并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
    • 你可以选择任意一棵树开始采摘,你必须从 每棵 树(包括开始采摘的树)上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次,你将会向右移动到下一棵树,并继续采摘。
    • 一旦你走到某棵树前,但水果不符合篮子的水果类型,那么就必须停止采摘。

    给你一个整数数组 fruits ,返回你可以收集的水果的 最大 数目。

    解题思路: 

    本题可以转化为最长的连续子数组(最多只能有两种种类的水果),可以用滑动窗口来解决

    我们从左往右right一直走,当找到了一段符合条件的子序列,我们需要继续向右验证最长的这个特性,该如何操作呢?我们来看一下,以下【left,right】是寻找过程中符合题目条件的一个子序列

     此时right需要向右++,这个时候可能会出现两种情况:

    • right++后,kind(水果的种类)不变
    • right++后,kind减小,

    这里值得注意的是当水果的种类减少后需要进行一下处理

     解题代码:

    1. class Solution {
    2. public:
    3. int totalFruit(vector<int>& fruits) {
    4. unordered_map<int,int> hash;
    5. int ret=0;
    6. for(int left=0,right=0;rightsize();right++)
    7. {
    8. hash[fruits[right]]++;
    9. while(hash.size()>2)
    10. {
    11. hash[fruits[left]]--;
    12. if(hash[fruits[left]]==0)
    13. hash.erase(fruits[left]);
    14. left++;
    15. }
    16. ret=max(ret,right-left+1);
    17. }
    18. return ret;
    19. }
    20. };

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

    力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

    题目描述: 

    给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。

    异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。

     解题思路:

    我们先通过暴力解法来分析一下题目:

    我们可以遍历s中每个位置,让他们跟p进行判断是否为异位词

    我们发现这是一个滑动区间【left,right】的解法,我们来想办法实现其优化

    首先我们可以利用哈希表hash1来存储p中每个字符和其个数 ,并且可以在滑动期间中利用hash2来记录s中的字符和个数

    我们这里还需要一个变量length=p.size(),以及一个变量count来记录有效字符的个数

    1.进窗口——hash2[s[right]]++

    if(hash2[s[right]]<=hash1[s[right]]) count++;

    2.当right-left+1>length进行判断

    3.出窗口——hash2[s[left]]--

    if(hash2[s[left]]<=hash1[s[left]]) count--;//在出窗口前更新count

    4.更新结果——count==length

    !这里的哈希表可以用大小为26的数组代替,并且速度更快

    解题代码:

    1. class Solution {
    2. public:
    3. vector<int> findAnagrams(string s, string p) {
    4. vector<int>ret;
    5. int length=p.size();
    6. unordered_map<char,int>hash1;
    7. for(int i=0;isize();i++) hash1[p[i]]++;
    8. unordered_map<char,int>hash2;
    9. for(int left=0,right=0,count=0;rightsize();right++)
    10. {
    11. char ch=s[right];
    12. //进窗口
    13. hash2[ch]++;
    14. if(hash2[ch]<=hash1[ch]) count++;
    15. //判断
    16. if(right-left+1>length)
    17. {
    18. char out=s[left];
    19. if(hash2[out]<=hash1[out]) count--;//在出窗口前更新count
    20. hash2[out]--;//出窗口
    21. left++;
    22. }
    23. //更新结果
    24. if(count==length)
    25. ret.push_back(left);
    26. }
    27. return ret;
    28. }
    29. };

  • 相关阅读:
    MySQL 8 - 能够成功创建其他用户但无法修改 root 用户的密码
    漫画脸头像怎么制作?这几种方法可以帮到你
    Linux学习03
    HandlerThread使用
    asp毕业设计——基于asp+access的在线考试系统设计与实现(毕业论文+程序源码)——在线考试系统
    Linux笔记 - - gcc/g++和make/Makefile的使用
    ASP.NET限流器的简单实现
    链表之反转链表
    Android问题笔记四十五:解决SeekBar操作thumb周围产生的圆形阴影/灰色阴影/白色圆圈的解决办法
    数据可视化【原创】vue+arcgis+threejs 实现流光立体墙效果
  • 原文地址:https://blog.csdn.net/m0_69061857/article/details/132993527