网站访客qq获取系统 报价,文明网站建设培训体会,网站产品设计规范 模板,官网推广方法有哪些写在所有的前面#xff1a;
本文采用C语言实现代码 目录 写在所有的前面#xff1a;题目说明题目#xff1a;力扣 904.水果成篮题目出处题目描述Description输入Input输出Output样例Sample限制Hint 解答说明方案解题思路一般情况特殊情况 代码实现其他解释 题目说明
题目…写在所有的前面
本文采用C语言实现代码 目录 写在所有的前面题目说明题目力扣 904.水果成篮题目出处题目描述Description输入Input输出Output样例Sample限制Hint 解答说明方案解题思路一般情况特殊情况 代码实现其他解释 题目说明
题目力扣 904.水果成篮
题目出处
力扣 904.水果成篮 https://leetcode.cn/problems/fruit-into-baskets/
题目描述Description 你正在探访一家农场农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示其中 fruits[i] 是第 i 棵树上的水果种类 。 你想要尽可能多地收集水果。然而农场的主人设定了一些严格的规矩你必须按照要求采摘水果 你只有 两个 篮子并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。你可以选择任意一棵树开始采摘你必须从每棵树包括开始采摘的树上恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次你将会向右移动到下一棵树并继续采摘。一旦你走到某棵树前但水果不符合篮子的水果类型那么就必须停止采摘。 输入Input 一个整数数组 fruits 一个整数 水果数量fruitsSize 输出Output 你可以收集的水果的最大数目。 样例Sample
输入1 fruits [1,2,1] 输出1 3 解释1 可以采摘全部 3 棵树 输入2 fruits [0,1,2,2] 输出2 3 解释2 可以采摘 [1,2,2] 这三棵树。 如果从第一棵树开始采摘则只能采摘 [0,1] 这两棵树。 更多样例见连接
限制Hint 1 fruits.length 105 0 fruits[i] fruits.length C语言的代码接口为
int totalFruit(int* fruits, int fruitsSize) {}自测用主函数部分
int main()
{int fruits[] { 1,2,1 };printf(%d, totalFruit(fruits, 3));
}解答说明
方案
解题思路
a 果实b 果实 nextnum 最近的相同果实数量 allnum 最近的 a b 果实数量 maxnum 最大量
一般情况
当前水果可摘 if (fruits[i] a || fruits[i] b) 最近的 a b 果实数量allnum 1水果相同则最近的相同果实数量nextnum 1水果改变则最近的相同果实数量nextnum重置为 1 当前水果是全新的果实 通过最近的两水果数量allnum更新最大数量maxnum保留更大的通过最近的相同果实数量nextnum 1更新最近的两水果数量allnum水果改变最近的相同果实数量nextnum重置为 1更新水果种类保留较近的水果
特殊情况
遍历所有水果后再更新一次最大数量maxnum 第一颗水果必定更新水果种类if (i 0)
代码实现
int totalFruit(int* fruits, int fruitsSize)
{int i 0;//第i颗果树int a -1, b -1, nextnum 0, allnum 0, maxnum 0;//a果实b果实最近的相同果实数量最近的ab果实数量最大量//从前向后遍历while (i fruitsSize){//如果水果符合if (fruits[i] a || fruits[i] b){allnum;//如果水果相同if (i 0 fruits[i] fruits[i - 1])nextnum;//如果水果改变elsenextnum 1;}else //全新的果实{//更新最大数量if (allnum maxnum)maxnum allnum;//更新最近的ab果实数量allnum nextnum 1;//更新最近相同果实数量nextnum 1;//更新果实种类if (i 0 || fruits[i - 1] b)a fruits[i];else if (fruits[i - 1] a)b fruits[i];}//下一颗果树i;}//更新最大数量if (allnum maxnum)maxnum allnum;return maxnum;
}其他解释
可能有更优解但是懒得看了
