2019/10/15【水果成篮】

在一排树中，第 i 棵树产生 tree[i] 型的水果。
你可以从你选择的任何树开始，然后重复执行以下步骤：

把这棵树上的水果放进你的篮子里。如果你做不到，就停下来。
移动到当前树右侧的下一棵树。如果右边没有树，就停下来。
请注意，在选择一颗树后，你没有任何选择：你必须执行步骤 1，然后执行步骤 2，然后返回步骤 1，然后执行步骤 2，依此类推，直至停止。

你有两个篮子，每个篮子可以携带任何数量的水果，但你希望每个篮子只携带一种类型的水果。
用这个程序你能收集的水果总量是多少？

 

示例 1：

输入：[1,2,1]
输出：3
解释：我们可以收集 [1,2,1]。
示例 2：

输入：[0,1,2,2]
输出：3
解释：我们可以收集 [1,2,2].
如果我们从第一棵树开始，我们将只能收集到 [0, 1]。
示例 3：

输入：[1,2,3,2,2]
输出：4
解释：我们可以收集 [2,3,2,2].
如果我们从第一棵树开始，我们将只能收集到 [1, 2]。
示例 4：

输入：[3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：我们可以收集 [1,2,1,1,2].
如果我们从第一棵树或第八棵树开始，我们将只能收集到 4 个水果。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fruit-into-baskets
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#!/bin/bash
#水果成篮
#
declare -A fruits    #定义一个数组用于存放果树的类型，即数字的类型
declare -A guolan    #定义一个数组，作用是果篮，用于存放选择的数字类型   
declare -i jilu=0    #定义一个初始值
declare -i flag=0    #定义一个标志位
declare -i sz=0      #定义一个初始值
read -t 20 -p "请输入每棵果树水果的类型：" number   #获取用户输入的数值类型
for item in $number   #for循环将数字类型存放于数组fruits中
do
        fruits[$sz]=$item
        sz=$[$sz+1]
done
echo "${#fruits[@]}"   #获取用户输入的数字类型数量
count=`echo "${#fruits[@]}"`
read -t 10 -p "请选择从那一棵果树[1-$count]摘果：" num    #获取用户从哪一个元素开始选择
weizhi=$[$num - 1 ]        #选择数组中对应的元素，元素下标数是其位数减一
if [ $count -lt $num ];then    #判断逻辑
        echo "我们没有这么多棵树!! "
else
        while [ $[$weizhi+1] -le $count ]
        do
                echo "${guolan[@]}"|grep "${fruits[$weizhi]}" &>/dev/null
                if [ $? -eq 0 ];then
                        guolan[$jilu]=${fruits[$weizhi]}
                        jilu=$[$jilu+1]
                        weizhi=$[$weizhi+1]
                else
                        flag=$[$flag+1]
                        if [ $flag -le 2 ];then
                                guolan[$jilu]=${fruits[$weizhi]}
                                jilu=$[$jilu+1]
                                weizhi=$[$weizhi+1]
                        else
                                echo "${#guolan[@]}"
                                exit 0
                        fi
                fi
        done
        echo "${#guolan[@]}"
fi

【效果】：

[[email protected] leetcode]# ./tree_style.sh
请输入每棵果树水果的类型：1 2 1
3
请选择从那一棵果树[1-3]摘果：1
3
[[email protected] leetcode]# ./tree_style.sh
请输入每棵果树水果的类型：0 1 2 2
4
请选择从那一棵果树[1-4]摘果：1
2
[[email protected] leetcode]# ./tree_style.sh
请输入每棵果树水果的类型：0 1 2 2
4
请选择从那一棵果树[1-4]摘果：2
3
[[email protected] leetcode]# ./tree_style.sh
请输入每棵果树水果的类型：1 2 3 2 2
5
请选择从那一棵果树[1-5]摘果：2
4

此题的关键是对题目的理解：一个数组，有两个篮子，在数组中选择一个开始的元素，并把其放到一个篮子中，继续往元素查找，如果与第一个篮子的数字不一样则放到第二个篮子，一样则放到第一个篮子；遇到如下一种情况停止摘果并返回果篮的”数量“：1、此元素为数组最后一个元素 2、下一个元素与两个篮子中的元素均不一样。