Fruit Into Baskets #算法#

2023-10-20 00:18

文章标签 算法 fruit baskets

本文主要是介绍Fruit Into Baskets #算法#，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题如下

In a row of trees, the i-th tree produces fruit with type tree[i].
有一行树，第i棵树产出tree[i]类型的水果。
You start at any tree of your choice, then repeatedly perform the following steps:

Add one piece of fruit from this tree to your baskets. If you cannot, stop.
Move to the next tree to the right of the current tree. If there is no tree to the right, stop.
Note that you do not have any choice after the initial choice of starting tree: you must perform step 1, then step 2, then back to step 1, then step 2, and so on until you stop.

You have two baskets, and each basket can carry any quantity of fruit, but you want each basket to only carry one type of fruit each.

What is the total amount of fruit you can collect with this procedure?
简单来说就是要找出数组中的最长连续元素的长度，这个序列只能由两个不相等的数字组成，比如“1，1，2，2”或“2，3，2，3”等。

Example 1:Input: [1,2,1]
Output: 3
Explanation: We can collect [1,2,1].Example 2:Input: [0,1,2,2]
Output: 3
Explanation: We can collect [1,2,2].
If we started at the first tree, we would only collect [0, 1].
其中只包含两个不同数字的连续序列有两个，{0，1}，{1，2，2}，后者更长，长度为3。Example 3:Input: [1,2,3,2,2]
Output: 4
Explanation: We can collect [2,3,2,2].
If we started at the first tree, we would only collect [1, 2].Example 4:Input: [3,3,3,1,2,1,1,2,3,3,4]
Output: 5
Explanation: We can collect [1,2,1,1,2].
If we started at the first tree or the eighth tree, we would only collect 4 fruits.

Note:

1 <= tree.length <= 40000
0 <= tree[i] < tree.length

思路

从左向右遍历，用两个变量type_one，type_two来记录当前的两种水果的类型，当遇到第三种类型时，就改变某一个type，每次记录序列的开始，然后计算该序列结束时的长度；每次遇到更大的长度则更新长度最大值，直到结束。

代码如下

class Solution {
public:int totalFruit(vector<int>& tree) {int start = 0; //记录每次符合条件的序列的开始位置 int total = 0; //记录最大长度 int type_one = -1; // 水果种类1 int type_two = -1; // 水果种类2 int index_1 = 0; // 从左向右遍历时水果种类1的最后一次出现的下标，用来确定下一次的start int index_2 = 0; // 同上 int i = 0;for(i = 0; i < tree.size(); i++){// 一开始 if(type_one == -1) type_one = tree[i];// 开始遇到第二种类型的水果 else if(type_two == -1 && tree[i] != type_one){type_two = tree[i];index_2 = i;}// 遇到第一种类型的水果，更新其index else if(tree[i] == type_one){index_1 = i;}// 遇到第二种类型的水果，更新其index else if(tree[i] == type_two){index_2 = i;}// 遇到第三种类型的水果 else if(tree[i] != type_one && tree[i] != type_two){// 计算当前最长长度 total = max(total, i - start);// 根据较小index确定下一start，并更新水果类型及其index if(index_1 <= index_2){start = index_1 + 1;type_one = tree[i];index_1 = i;}else{start = index_2 + 1;type_two = tree[i];index_2 = i;}}} return max(total, i - start);}
};