AlgoPressAppearance
0904-水果成篮
https://leetcode.cn/problems/fruit-into-baskets
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 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^5
- 0 <= fruits[i] < fruits.length
思路1:暴力法(超时)
直接根据题目意思定义两个篮子，然后依次采摘并且统计个数
csharp
public class Solution {
public int TotalFruit(int[] fruits) {
int count = 0;
Dictionary<int,int> dict;
for(int i=0; i<fruits.Length; i++ ){
dict = new Dictionary<int,int>();
int curCount = 0;
//开始采摘
for(int j=i; j<fruits.Length; j++){
if(dict.ContainsKey(fruits[j])){
curCount++;
count = Math.Max(count,curCount);
}
else if(dict.Count <2){
dict.Add(fruits[j],1);
curCount++;
count = Math.Max(count,curCount);
}
else{
break;
}
}
}
return count;
}
}
思路2：滑动窗口
使用 selected 长度为2的数组表示已经选择的水果，注意是储存最后出现的索引 i 表示滑动窗口的起始位置，j表示当前循环的位置，当 selected一直小于2的时候，可以持续递增count 当 selected 出现第三个水果的时候，则设置 min(select[0],select[1])+1 作为 select[0] 而 select[1] 就是第三种水果
csharp
public class Solution{
public int TotalFruit(int[] fruits){
int count = 0 ;
int i=0; //左边界
int f1Index = -1;
int f2Index = -1;
for(int j=0; j<fruits.Length; j++){
int fruit = fruits[j];
if(f1Index == -1 || f2Index == -1){
//记录索引
if(f1Index == -1 || fruits[j] == fruits[f1Index]){
f1Index = j;
}
else{
f2Index = j;
}
count++;
}
else{
if(fruits[j] ==fruits[f1Index] || fruits[j] == fruits[f2Index]){ //保持前两种
count = Math.Max(count,j-i+1);
if(fruits[j] == fruits[f1Index]){
f1Index = j;
}
else{
f2Index = j;
}
}
else{ //第三种
f1Index = Math.Min(f1Index,f2Index)+1;
while(fruits[f1Index+1] == fruits[f1Index] ){
f1Index++;
}
f2Index = j;
i = f1Index;
count = Math.Max(count,j-i+1);
}
}
//Console.WriteLine("f1Index = {0}, f2Index = {1}, count={2}", f1Index, f2Index,count);
}
return count;
}
}
csharp
public class Solution{
public int TotalFruit(int[] fruits){
if(fruits == null || fruits.Length == 0){
return 0;
}
int n = fruits.Length;
Dictionary<int,int> dict = new Dictionary<int,int>();
int maxLength = 0;
int left = 0;
for(int i=0; i<fruits.Length; i++){
if(!dict.ContainsKey(fruits[i])){
dict.Add(fruits[i],1);
}
else{
//此处错误，不是 +=1 应该是更新为 i
dict[fruits[i]] += 1;
}
while(dict.Count > 2){
dict[fruits[left]] = dict[fruits[left]] - 1;
if(dict[fruits[left]] == 0){
dict.Remove(fruits[left]);
}
left++;
}
maxLength = Math.Max(maxLength, i - left + 1);
}
return maxLength;
}
}
思路3：【双指针】自己重新解出
思路：创建一个Hash表储存已经选择的水果 遍历数组，当新的水果出现是，加入hash表 定义left = 0 当少于两个水果时，一直累加 count 当出现第三种水果时，找出第三个水果的前一个水果的左边界(hash表里面小的那个边界+1)，设置为 left ，计算 i - left + 1 更新 maxCount 更新hash表
csharp
public class Solution {
public int TotalFruit(int[] fruits) {
//字典中储存的是索引
Dictionary<int,int> dict = new Dictionary<int,int>();
int left = 0; //左边界
int maxCount = 0; //最大值
for(int i=0; i<fruits.Length; i++){
//加入hash表
int fruit = fruits[i];
if(!dict.Keys.Contains(fruit)){
dict.Add(fruit,i);
}
else{
dict[fruit] = i;
}
//判断是否大于3
if(dict.Count == 3){
//此时hash表中有三个数，分别是他们最后一次出现的位置
//取出左边界(Hash表中坐标最小的那个)+1就是新的边界，说明这个窗口中只有两个数
//更新为左边界
int min = fruits.Length;
foreach(int key in dict.Keys){
min = Math.Min(min,dict[key]);
}
foreach(int key in dict.Keys){
if(dict[key] == min){
dict.Remove(key);
}
}
left = min + 1;
}
maxCount = Math.Max(i - left + 1, maxCount);
}
return maxCount;
}
}
另外一种方式是将水果个数加入到hash表中去，当hash表的key包含三个了，就不停的左移left指针并且删除一个数，当水果数目为0的时候。 就删除key保持hash表中只有两个数字
csharp
public class Solution {
public int TotalFruit(int[] fruits) {
Dictionary<int,int> dict = new Dictionary<int,int>();
int left = 0;
int maxCount = 0;
for(int i=0; i<fruits.Length; i++){
//将个数加入 hash 表
int fruit = fruits[i];
if(!dict.ContainsKey(fruit)){
dict.Add(fruit,1);
}
else{
dict[fruit]++;
}
//当hash表超过3的时候，更新 left 移除前面的水果
//注意是 while 一直到hash表中只有两种才行
//不停的去掉左边的水果，直到 hash表中只有两种水果
while(dict.Count > 2){
dict[fruits[left]]--;
if(dict[fruits[left]] == 0){
dict.Remove(fruits[left]);
}
left++;
}
//更新 maxCount
maxCount = Math.Max(maxCount, i - left + 1);
}
return maxCount;
}
}
思路4：双指针定位两个水果
csharp
public class Solution {
public int TotalFruit(int[] fruits) {
int left = 0;
int b1 = 0; //篮子默认放第一种水果
int b2 = 0; //篮子默认放第一种水果
int max = 1;
for(int i=1; i<fruits.Length; i++){
if(fruits[i] == fruits[b1] || fruits[i] == fruits[b2]){ //第一种水果出现
}
else if(fruits[i] != fruits[b1] && fruits[b1] == fruits[b2]){ //第二种水果出现
b2 = i;
}
else if(fruits[i] != fruits[b1] && fruits[i] != fruits[b2]){ //第三种水果出现
//调整left，最后出现的两个一定不一样
b1 = i-1;
b2 = i;
//找到最前面第一个水果不同的索引+1，即为新的left
for(int j=b1-1; j>=0;j--){
if(fruits[j] != fruits[b1] && fruits[j] != fruits[b2]){
left = j+1;
break;
}
}
}
max = Math.Max(max,i-left+1);
//Console.WriteLine("left={0},i={1},max={2}",left,i,max);
}
return max;
}
}
思路X：动态规划（错误：不能实现）
定义动态规划二维数组，分别表示选择了当前果树他的总和，和不选当前果树的和，然后后面去最大的值
dp[i,0] 表示第 i 棵树不选他的 count dp[i,1] 表示第 i 课数选择他的 count
dp[i,0] = if(fruits[i-2] == fruits[i] || fruites[i-1] == fruits[i] )
csharp
public class Solution {
public int TotalFruit(int[] fruits) {
if(fruits.Length <= 2){
return fruits.Length;
}
int[,] dp = new int[fruits.Length,2];
dp[0,0] = 0;
dp[0,1] = 1;
dp[1,0] = 1;
dp[1,1] = 2;
int count = 2;
for(int i=2; i<fruits.Length; i++){
dp[i,0] = Math.Max(dp[i-1,1],dp[i-1,0]);
if(fruits[i-2] == fruits[i] || fruits[i-1] == fruits[i]){
dp[i,1] = dp[i-1,1]+1;
}
else{
dp[i,1] = Math.Max(dp[i-1,0],dp[i-2,0])+1;
}
count = Math.Max(count, dp[i,1]);
}
return count;
}
}