LeetCode 904. 水果成篮

题目

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果种类。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

• 你只有两个篮子，并且每个篮子只能装单一类型的水果。每个篮子能够装的水果总量没有限制。
• 你可以选择任意一棵树开始采摘，你必须从每棵树（包括开始采摘的树）上恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
• 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的最大数目。

方法：滑动窗口

start：出现非前一种水果类型的新水果类型的位置
end：向右移动
result：返回的水果数量
types：水果信息的字典（{水果类型：数量,...}）

• 若此时 types 中存在两种水果且此位置的水果并非前两种水果，那么 end 将回到最后一次出现不同水果的位置（即在这个数列中此位置之后的所有水果均与此水果种类相同）。
• 若此时 types 中不存在任何水果或只存在一种水果或者此位置的水果为前两种水果之一，那么此种水果的 value 将加一，并且若此水果在 types 中并不存在， 那么 start 将记录此位置，之后 end 继续向右移动。

class Solution(object):
    def totalFruit(self, fruits):
        start = end = 0
        result = 0
        types = {}
        while end < len(fruits):
            if len(types) == 2 and types.get(fruits[end]) is None:
                end = start
                types = {}
            else:
                types[fruits[end]] = types.get(fruits[end], 0) + 1
                if fruits[end] != fruits[start]:
                    start = end
                end = end + 1
            result = max(result, sum(types.values()))
        return result

相关知识

• 字典：
  dict = {key1: value1, key2: value2,...}
  get(key, default = None)： dict.get()
  返回指定键的值，若此指定键不存在，那么返回默认值。
  values()： dict.values()
  返回所有的值

报错

• TypeError: get() takes no keyword arguments
  types[fruits[end]] = types.get(fruits[end], default = 0) + 1
  default 并非内置参数不能直接使用，除去即可

参考

代码相关：https://leetcode-cn.com/problems/fruit-into-baskets/solution/python-shuang-zhi-zhen-ono1jie-fa-by-hardcandy/