Java教程

力扣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进行优化。
image.png

代码

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——水果成篮(动态规划)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!