博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
LeetCode - Fruit Into Baskets
阅读量:6715 次
发布时间:2019-06-25

本文共 2664 字,大约阅读时间需要 8 分钟。

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: 3Explanation: We can collect [1,2,1].Example 2:Input: [0,1,2,2]Output: 3Explanation: 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: 4Explanation: 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: 5Explanation: 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 <= 400000 <= tree[i] < tree.length

用 two points 去维护一个 window, 注意一些coner case

class Solution {    public int totalFruit(int[] tree) {        if(tree == null || tree.length == 0){            return 0;        }        int len = tree.length;        int p = 0;        int q = 0;        int max = 0;        Set
set = new HashSet<>(); while(p < len){ if(set.size() == 0){ set.add(tree[p]); p++; } else if(set.contains(tree[p])){ p++; } else{ if(set.size() == 1){ set.add(tree[p]); p++; } else{ if(p - q > max){ max = p - q; } set.clear(); int temp = p - 1; int type = tree[temp]; set.add(tree[p - 1]); set.add(tree[p]); while(tree[temp] == type){ temp --; } q = temp+1; } } } if(p - q > max){ max = p - q; } return max; }}

 

转载于:https://www.cnblogs.com/incrediblechangshuo/p/9982370.html

你可能感兴趣的文章
js插件大全 jquery插件大全
查看>>
解决ubuntu 14.04删ibus导致系统设置项目的损失后,,退出关机问题是不正常的
查看>>
理解vmp
查看>>
CentOS6.4下Mysql数据库的安装与配置
查看>>
[转]GC简介
查看>>
poj 1466 Girls and Boys (最大独立集)
查看>>
辛星与您使用CSS导航条
查看>>
统计一个文件中出现字符'a'的次数
查看>>
将Eclipse包括第一3正方形jar包裹Project Export并产生能够执行jar
查看>>
Google Pagespeed,自动压缩优化JS/CSS/Image
查看>>
Gentoo源码安装图解
查看>>
【转载】COM 组件设计与应用(三)——数据类型
查看>>
Python yield与实现
查看>>
购物车特效收集
查看>>
Access中一句查询代码实现Excel数据导入导出
查看>>
2015第49周二
查看>>
Sphinx/Coreseek 4.1的安装流程
查看>>
邮件服务器Postfix的管理 重启php-fpm
查看>>
Android Studio 项目代码全部消失--出现原因及解决方法
查看>>
SQL Server---存储过程
查看>>