[LeetCode]Fruit Into Baskets

看到此文,是否觉得体内洪荒之力爆发,饥渴难耐想吐槽、情不自禁想捐赠
本文为原创文章,尊重辛勤劳动,可以免费摘要、推荐或聚合,亦可完整转载,但完整转载需要标明原出处,违者必究。

支付宝微  信

原题

In a row of trees, the i-th tree produces fruit with type tree[i].

You start at any tree of your choice, then repeatedly perform the following steps:

  1. Add one piece of fruit from this tree to your baskets.  If you cannot, stop.
  2. 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?

 

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].

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. 1 <= tree.length <= 40000
  2. 0 <= tree[i] < tree.length

题解

该题属于双指针(Two Pointers)范畴,主要的思路是利用两个指针来构造一个滑动窗口,且要求窗口中的元素类型不得超过2种。所以,经过一遍for循环,即可拿到所有不超过两个类型元素的窗口长度,即拿到其中最大的长度。

所以,难度在于怎么来构造这个窗口。这里,我们可以巧妙的利用映射(Map)这种数据结构,用映射来维护for循环过程中,经过的数据类型总数,以及每种类型的个数。

以原题中第一个案例为例,在第一次for循环中,我们将第一个元素加入到map中,如下:


map m;

m.insert(make_pair(1, 1)); // 第一个元素代表类型为1,第二个元素代表类型为1的出现的个数

同时,可以很容易的拿到某时刻的状态信息:


m.size(); // 当前不同类型的总数

m.find(1)->second; // 类型为1的出现的次数

代码

class Solution {
    public:
        int totalFruit(vector<int>& tree) {
            map<int, int> m;
            map<int, int>::iterator it;
            int l = 0, r = 0, len = tree.size(), a = 0;
            while (r < len) {
                if (m.size() <= 2) {
                    it = m.find(tree[r]);
                    if (it != m.end()) {
                        it->second++;
                        m.insert(make_pair(tree[r], it->second + 1));
                    } else {
                        m.insert(make_pair(tree[r], 1));
                    }
                    r++;
                    if (a < r - l) a = r - l;
                } else {
                    it = m.find(tree[l]);
                    m.erase(tree[l]);
                    if (it->second != 1) {
                        m.erase(tree[l]);
                        m.insert(make_pair(tree[l], it->second - 1));
                        it = m.find(tree[l]);
                    }
                    l++; 
                }
            }
            return a;
        }
};

原题:https://leetcode.com/problems/fruit-into-baskets/description/
Github 源码:https://github.com/GenialX/leetcode-cpp/blob/master/2018/09/fruit-into-baskets.cpp

文章来源:胡小旭 => [LeetCode]Fruit Into Baskets


这是一篇原创文章,如果您觉得有价值,可以通过捐赠来支持我的创作~
捐赠者会展示在博客的某个页面,钱将会用在有价值的地方,思考中...


分类: C/C++, 技术, 算法, 编程 | 标签: , , , , , , , | 评论 | Permalink

发表评论

电子邮件地址不会被公开。