I1 Maximum Fruit

Ok let me recall this problem, Alice went to a farm for fruit picking, and she got two basket. Each tree is able to produce a single type of fruit and the trees are given in an array. Alice can start from any of the trees and then continue picking to the right. She wanted to pick same kind of fruit in each of the basket so she would stop either when she got the third type of fruit or reached the end of the trees. Given array A = [] of length n, return the maximum number of fruits that Alice can pick. Alice won’t throw any fruits she has picked.

  • 要求:
    给一个数组,求Alice可以摘到的最多水果数量。 Time complexity \(O(N)\), space complexity \(O(N)\)

  • 返回: max amount of fruit.

  • 例子:
    • input: A = [1,2,1,2,1]
    • output: 5


设置一个list当作basket, 记录[A[i-1], A[i]]的水果类型,遍历数组,如果水果在已有类型中,counter + 1, alice 终止采摘当前两类水果,进而考虑上一步所采摘的水果和当前水果品种,更新basket, 重复之前步骤。设置max_num变量,如果counter 大于max,更新max.


Note: this problem is similar to the leetcode 159 longest substring with most two distinct characters

def solution(A):
    # write your code in Python 3.6
    if len(list(set(A)))<=2:
        return len(A)
        basket = []
        max_num = 0
        cnt = 0
        same = 1
        for i in range(len(A)):
            if A[i] in basket:
                cnt +=1
                if A[i] == A[i-1]:
                    same += 1
                    same = 1
                if len(basket)<2:
                    cnt +=1
                    basket = [A[i-1], A[i]]
                    same = 1
            if cnt > max_num:
                max_num = cnt
        return max_num
B = [3,4,3,6,6,7]