力扣904——水果成篮（动态规划）

本文主要是介绍力扣904——水果成篮（动态规划），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目（中等）

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 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 <= 105
0 <= fruits[i] < fruits.length

解题思路

看数据量，O(N^2)必超时，考虑dp做，dp[i]表示到i位置为止往前按规则拿水果的个数，dp数组中最大值就是答案。

先找出第三种水果，处理从头开始直到遇到第三种水果的情况；记录第三种水果的位置third_pos;

之后从第三种水果开始，记录near临近水果为第三种水果，和far远端水果为third_pos-1位置上的水果；
先计算dp[third_pos],也就是从连续far水果的起点开始取far_num个far水果，然后取1个third_pos上的第三种水果，
dp[third_pos] = far_num + 1;

之后从third_pos+1开始往后遍历，如果水果是near，那可以连着取，dp[i]=dp[i-1]+1,同时near_num也增加一个；
如果水果是far，也可以连着取，dp[i]=dp[i-1]+1，但要交换near和far，因为临近水果已经变成了far水果，且出现次数near_num要变为1；
如果出现near和far以外的水果，则只能取该水果和near水果，即该位置往前按规则取的dp值则变为dp[i]=near_num + 1；并更新far为near水果，near水果为当前水果，出现次数near_num也变为1。

最后dp数组中最大值就是答案。

另外dp更新只与上一位置有关，可以只用一个int进行优化。

代码

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int n = fruits.size();
        if(n < 3) return n;
        int dp = 0;
        int ans = 0;
        int near = -1;
        int near_num = 0;
        int far = fruits[0];
        int far_num = 0;
        int third_pos = 0;
        for(int i = 1; i < n; i++) {
            if(near == -1 && fruits[i] != far) {
                near = fruits[i];
            }
            else if(fruits[i] != far && fruits[i] != near) {
                third_pos = i;
                near = fruits[i];
                near_num = 1;
                break;
            }
        }
        if(third_pos == 0) return n;    //总共只有两种以内的水果，可以都取
        ans = third_pos;    //更新答案为从头开始取，取前两种水果
        far = fruits[third_pos-1];
        for(int i = third_pos-1; i >= 0; i--) {
            if(fruits[i] == far) far_num++;
            else break;
        }
        dp = far_num + 1;    //计算取第三种水果和它之前的那种水果
        for(int i = third_pos + 1; i < n; i++) {
            if(fruits[i] == near) {
                dp++;
                near_num++;
            }
            else if(fruits[i] == far) {
                dp++;
                swap(near, far);
                near_num = 1;
            }
            else {
                far = near;
                near = fruits[i];
                dp = near_num + 1;
                near_num = 1;
            }
            ans = max(ans, dp);
        }
        return ans;
    }
};

这篇关于力扣904——水果成篮（动态规划）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！