周口市住房和城乡建设局门户网站,重庆网站快速排名提升,宁波网站推广多少钱一个,标签化网站目录
力扣904. 水果成篮
解析及代码1#xff08;使用容器#xff09;
解析及代码2#xff08;开数组#xff09; 力扣904. 水果成篮
904. 水果成篮 - 力扣#xff08;LeetCode#xff09;
难度 中等
你正在探访一家农场#xff0c;农场从左到右种植了一排果树。这…目录
力扣904. 水果成篮
解析及代码1使用容器
解析及代码2开数组 力扣904. 水果成篮
904. 水果成篮 - 力扣LeetCode
难度 中等
你正在探访一家农场农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而农场的主人设定了一些严格的规矩你必须按照要求采摘水果
你只有 两个 篮子并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。你可以选择任意一棵树开始采摘你必须从 每棵 树包括开始采摘的树上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次你将会向右移动到下一棵树并继续采摘。一旦你走到某棵树前但水果不符合篮子的水果类型那么就必须停止采摘。
给你一个整数数组 fruits 返回你可以收集的水果的 最大 数目。
示例 1
输入fruits [1,2,1]
输出3
解释可以采摘全部 3 棵树。示例 2
输入fruits [0,1,2,2]
输出3
解释可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘则只能采摘 [0,1] 这两棵树。示例 3
输入fruits [1,2,3,2,2]
输出4
解释可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘则只能采摘 [1,2] 这两棵树。示例 4
输入fruits [3,3,3,1,2,1,1,2,3,3,4]
输出5
解释可以采摘 [1,2,1,1,2] 这五棵树。
提示
1 fruits.length 10^50 fruits[i] fruits.length
class Solution {
public:int totalFruit(vectorint fruits) {}
};
解析及代码1使用容器 研究的对象是⼀段连续的区间可以使用「滑动窗口」思想来解决问题。 让滑动窗口满足窗口内水果的种类只有两种。 做法右端水果进入窗口的时候用哈希表统计这个水果的频次。这个水果进来后判断哈希表的大小 如果大小超过2说明窗口内水果种类超过了两种。那么就从左侧开始依次将水果划出窗口直到哈希表的大小小于等于2然后更新结果 如果没有超过2说明当前窗口内水果的种类不超过两种直接更新结果 ret class Solution {
public:int totalFruit(vectorint fruits) {unordered_mapint, int hash;int ret 0, left 0, right 0;while(right fruits.size()){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);right;}return ret;}
}; 解析及代码2开数组
可以看到上面的代码的通过效率还是很差的因为容器的删除耗了时间注意到这题的范围此时就可以开一个数组来代替容器
class Solution {
public:int totalFruit(vectorint fruits) {// unordered_mapint, int hash;int hash[100001] { 0 }, kinds 0; // 有数据范围-数组代替容器-提高效率int ret 0, left 0, right 0;while(right fruits.size()){if(hash[fruits[right]] 0) // 维护数组水果种类{kinds; }hash[fruits[right]]; // 进窗口// while(hash.size() 2) // 判断while(kinds 2) // 判断{hash[fruits[left]]--; // 出窗口if(hash[fruits[left]] 0){// hash.erase(fruits[left]);--kinds;}left;}ret max(ret, right - left 1);right;}return ret;}
};
此时效率就会提高一些。
