[LeetCode] 904. Fruit Into Baskets

Warren 发布于2019-08-16 13:33 / 2505人阅读

Problem

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:

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?

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

Solution

class Solution {
    public int totalFruit(int[] tree) {
        if (tree.length <= 2) return tree.length;
        Map map = new HashMap<>();
        int start = 0, max = 0;
        for (int i = 0; i < tree.length; i++) {
            map.put(tree[i], map.getOrDefault(tree[i], 0)+1);
            while (map.size() > 2) {
                map.put(tree[start], map.get(tree[start])-1);
                if (map.get(tree[start]) == 0) map.remove(tree[start]);
                start++;
            }
            max = Math.max(max, i-start+1);
        }
        return max;
    }
}

云服务器 GPU云服务器 Baskets Fruit LeetCode into

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71941.html

PHP 数据库操作

摘要：操作数据库的种形式使用扩展类库推荐使用扩展类库这是类库的升级版，但已经不推荐使用扩展包含哪三个类与区别可以支持多种数据库，而且操作方法一致只支持数据库如何使用连接数据库什么是如何关闭连接通过来连接数据库，其中必须传入数据源名称数据源名称是 PHP操作数据库的2种形式使用 PDO 扩展类库（推荐）使用 Mysqli 扩展类库（这是Mysql类库的升级版，但已经不推荐使用） PDO...

Jingbin_ 2019-06-28 13:26 评论0 收藏0
容器最大盛水量

摘要：容器最大盛水量给定个非负整数，，，，其中每个表示坐标，处的点。找到两条线，它们与轴一起形成一个容器，使得容器含有最多的水。容器最大盛水量 Container With Most Water 给定n个非负整数a1，a2，...，an，其中每个表示坐标（i，ai）处的点。绘制n条垂直线，使得线i的两个端点在（i，ai）和（i，0）处。找到两条线，它们与x轴一起形成一个容器，使得容器...

luckyw 2019-07-25 12:04 评论0 收藏0
904-水果成篮

摘要：前言的第一题水果成篮在一排树中，第棵树产生型的水果。你有两个篮子，每个篮子可以携带任何数量的水果，但你希望每个篮子只携带一种类型的水果。前言 Weekly Contest 102的第一题水果成篮：在一排树中，第 i 棵树产生 tree[i] 型的水果。你可以从你选择的任何树开始，然后重复执行以下步骤：把这棵树上的水果放进你的篮子里。如果你做不到，就停下来。移动到当前树右侧的...

linkFly 2019-08-19 11:10 评论0 收藏0
[LeetCode] 708. Insert into a Cyclic Sorted List

Problem Given a node from a cyclic linked list which is sorted in ascending order, write a function to insert a value into the list such that it remains a cyclic sorted list. The given node can be a r...

qpwoeiru96 2019-08-16 13:50 评论0 收藏0