江西省住房和城乡建设网站企业网站建设报价清单

写在所有的前面：

本文采用C语言实现代码

题目说明

题目：力扣 904.水果成篮

题目出处

力扣 904.水果成篮
https://leetcode.cn/problems/fruit-into-baskets/

题目描述Description

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

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

输入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 最大量

一般情况

1. 当前水果可摘 if (fruits[i] == a || fruits[i] == b)
   1. 最近的 a b 果实数量allnum +1
   2. 水果相同则最近的相同果实数量nextnum +1
   3. 水果改变则最近的相同果实数量nextnum重置为 1
2. 当前水果是全新的果实
   1. 通过最近的两水果数量allnum更新最大数量maxnum（保留更大的）
   2. 通过最近的相同果实数量nextnum +1更新最近的两水果数量allnum
   3. 水果改变，最近的相同果实数量nextnum重置为 1
   4. 更新水果种类（保留较近的水果）

特殊情况

遍历所有水果后再更新一次最大数量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;
}

其他解释

可能有更优解，但是懒得看了