LeetCode904.水果成篮
题目链接:904. 水果成篮 - 力扣(LeetCode)
1.常规解法(会超时)
由于题目中要求对水果的种类进行判断,于是可以用一个链表来存储水果的种类;
先对这个数组进行双重遍历,内层循环从外层循环的下一个数开始遍历,在进入外层循环之前,先将计数器加一,再将外层循环的起始水果类型放入链表中,在内层循环中,先判断这个水果类型在链表中是否存在,若存在,将计数器加一;若不存在,在判断链表中有几种水果类型,若已经有两种水果类型,直接退出内层循环,若还没到两种类型,就将这种水果的类型添加到链表中,并将计数器加一,流程图与代码如下:
public int totalFruit(int[] fruits) {int n = fruits.length;int max = 0;//最多能放的水果的个数List<Integer> list = new LinkedList<>();//放水果类型for (int i = 0; i < n; i++) {int count = 1;//计数器list.add(fruits[i]);for (int j = i + 1; j < n; j++) {if (list.contains(fruits[j])) {count++;} else {if (list.size() == 2) {break;} else {count++;list.add(fruits[j]);}}}max = Math.max(count, max);list.clear();//清空链表中的水果种类}return max;}
2.滑动窗口
在常规解法中,第一次结果与第二次结果存在重合的部分,如下图:
我们可以在第一次判断完成之后,只将3类型的水果移出篮子即可。
先定义两个指针left和right,这两个指针均指向第一个元素;定义一个数组用来存放每种类型的水果的个数(相当于水果篮);再定义一个变量kind用来统计篮子里有多少种水果;
我们先让right指针向右移动,若right指向的水果类型再数组中有没有,即若数组中对应类型的值为0,就将kind++,并将arr[kind]++;若数组中对应类型值非0,就直接将arr[kind]++;
当篮子中水果类型超过2时(数组中非0的类型超过3),就要将left向右移动以去除一种水果,将数组中left指向的元素的数据减一,若该数据减到0时,就相当于篮子中没有这种类型的水果,统计篮子中水果的个数,再次进行循环,流程图与代码如下:
public int totalFruit(int[] fruits) {int n = fruits.length;int[] arr = new int[n];//每种类型是否有水果int max = 0;int kind = 0;//记录类型个数for (int left = 0, right = 0; right < n; right++) {int typeRight = fruits[right];if (arr[typeRight] == 0) {kind++;}arr[typeRight]++;while (kind > 2) {arr[fruits[left]]--;if (arr[fruits[left]] == 0) {kind--;}left++;}max = Math.max(max, right - left + 1);}return max;}
希望大家积极指导!