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

简介: 题目描述:你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示,其中 fruits[i] 是第 i 棵树上的水果 种类 。你想要尽可能多地收集水果。然而,农场的主人设定了

904. 水果成篮

904. 水果成篮

题目描述:

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

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

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

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

解题思路:

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

解题代码:

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int,int> hash;
        int ret=0;
        for(int left=0,right=0;right<fruits.size();right++)
        {
            hash[fruits[right]]++;
            while(hash.size()>2)
            {
                hash[fruits[left]]--;
                if(hash[fruits[left]]==0)
                hash.erase(fruits[left]);
                left++;
            }
            ret=max(ret,right-left+1);
        }
        return ret;
    }
};

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

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

题目描述:

给定两个字符串 sp,找到 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的数组代替,并且速度更快

解题代码:

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int>ret;
        int length=p.size();
        unordered_map<char,int>hash1;
        for(int i=0;i<p.size();i++) hash1[p[i]]++;
        unordered_map<char,int>hash2;
        for(int left=0,right=0,count=0;right<s.size();right++)
        {
            char ch=s[right];
            //进窗口
            hash2[ch]++;
            if(hash2[ch]<=hash1[ch]) count++;
            //判断
            if(right-left+1>length)
            {
                char out=s[left];
                if(hash2[out]<=hash1[out]) count--;//在出窗口前更新count
                hash2[out]--;//出窗口
                left++;
            }
            //更新结果
            if(count==length)
                ret.push_back(left);
        }
        return  ret;
    }
};



相关文章
|
6月前
|
算法
【算法】滑动窗口——找到字符串中所有字母异位词
【算法】滑动窗口——找到字符串中所有字母异位词
|
4月前
|
算法
两个字符串匹配出最长公共子序列算法
本文介绍了最长公共子序列(LCS)问题的算法实现,通过动态规划方法求解两个字符串的最长公共子序列,并提供了具体的编程实现细节和示例。
140 1
两个字符串匹配出最长公共子序列算法
|
4月前
|
算法
条件运算符与条件if的姻缘,打擂台算法和大小写字母转换,if逻辑避坑
条件运算符与条件if的姻缘,打擂台算法和大小写字母转换,if逻辑避坑
44 1
|
6月前
|
算法 Java
掌握算法学习之字符串经典用法
文章总结了字符串在算法领域的经典用法,特别是通过双指针法来实现字符串的反转操作,并提供了LeetCode上相关题目的Java代码实现,强调了掌握这些技巧对于提升算法思维的重要性。
|
7月前
|
自然语言处理 算法 搜索推荐
字符串相似度算法完全指南:编辑、令牌与序列三类算法的全面解析与深入分析
在自然语言处理领域,人们经常需要比较字符串,这些字符串可能是单词、句子、段落甚至是整个文档。如何快速判断两个单词或句子是否相似,或者相似度是好还是差。这类似于我们使用手机打错一个词,但手机会建议正确的词来修正它,那么这种如何判断字符串相似度呢?本文将详细介绍这个问题。
432 1
|
6月前
|
算法 C++
惊爆!KPM算法背后的秘密武器:一行代码揭秘字符串最小周期的终极奥义,让你秒变编程界周期大师!
【8月更文挑战第4天】字符串最小周期问题旨在找出字符串中最短重复子串的长度。KPM(实为KMP,Knuth-Morris-Pratt)算法,虽主要用于字符串匹配,但其生成的前缀函数(next数组)也可用于求解最小周期。核心思想是构建LPS数组,记录模式串中每个位置的最长相等前后缀长度。对于长度为n的字符串S,其最小周期T可通过公式ans = n - LPS[n-1]求得。通过分析周期字符串的特性,可证明该方法的有效性。提供的C++示例代码展示了如何计算给定字符串的最小周期,体现了KPM算法在解决此类问题上的高效性。
130 0
|
7月前
|
算法 Java
KMP算法详解及其在字符串匹配中的应用
KMP算法详解及其在字符串匹配中的应用
|
2天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于GRU网络的MQAM调制信号检测算法matlab仿真,对比LSTM
本研究基于MATLAB 2022a,使用GRU网络对QAM调制信号进行检测。QAM是一种高效调制技术,广泛应用于现代通信系统。传统方法在复杂环境下性能下降,而GRU通过门控机制有效提取时间序列特征,实现16QAM、32QAM、64QAM、128QAM的准确检测。仿真结果显示,GRU在低SNR下表现优异,且训练速度快,参数少。核心程序包括模型预测、误检率和漏检率计算,并绘制准确率图。
78 65
基于GRU网络的MQAM调制信号检测算法matlab仿真,对比LSTM
|
7天前
|
算法
基于遗传优化算法的风力机位置布局matlab仿真
本项目基于遗传优化算法(GA)进行风力机位置布局的MATLAB仿真,旨在最大化风场发电效率。使用MATLAB2022A版本运行,核心代码通过迭代选择、交叉、变异等操作优化风力机布局。输出包括优化收敛曲线和最佳布局图。遗传算法模拟生物进化机制,通过初始化、选择、交叉、变异和精英保留等步骤,在复杂约束条件下找到最优布局方案,提升风场整体能源产出效率。
|
7天前
|
算法 安全 机器人
基于包围盒的机械臂防碰撞算法matlab仿真
基于包围盒的机械臂防碰撞算法通过构建包围盒来近似表示机械臂及其环境中各实体的空间占用,检测包围盒是否相交以预判并规避潜在碰撞风险。该算法适用于复杂结构对象,通过细分目标对象并逐级检测,确保操作安全。系统采用MATLAB2022a开发,仿真结果显示其有效性。此技术广泛应用于机器人运动规划与控制领域,确保机器人在复杂环境中的安全作业。

热门文章

最新文章