Java C++题解leetcode904水果成篮

题目要求

阅读理解

读完题的我be like:

去看了遍英文版就懂了，题目中的种类【type】不是种类数……每个数字代表一种树【用个字母啥的表示或者翻译成类型就好理解多了】，那么目标就是找从哪里开始可以维持两种数字（种类）无规律交替出现的状态最久，这个最久是多少棵树。

思路：滑动窗口

• 窗口里可放两棵树，一棵是枣树，另一棵还是枣树。 向后遍历整排树，并更新最长状态。

Java

数组

class Solution {
   public int totalFruit(int[] fruits) {
       int res = 0;
       int[] win = new int[fruits.length + 10];
       for (int l = 0, r = 0, tot = 0; r < fruits.length; r++) {
           if (++win[fruits[r]] == 1)
               tot++; // 当前种类统计
           while (tot > 2) {
               if (--win[fruits[l++]] == 0)
                   tot--;
           }
           res = Math.max(res, r - l + 1); // 维护最长状态
       }
       return res;
   }
}

• 时间复杂度：O(n)

• 空间复杂度：O(n)

哈希表

可使用哈希表构建窗口，降低空间复杂度。

• 键对应篮子，值对应同类树数量；

• 当值为000注意要彻底删掉键。

class Solution {
   public int totalFruit(int[] fruits) {
       Map<Integer, Integer> win = new HashMap<Integer, Integer>();
       int l = 0, res = 0;
       for (int r = 0; r < fruits.length; r++) {
           win.put(fruits[r], win.getOrDefault(fruits[r], 0) + 1);
           while (win.size() > 2) { // 窗口大小即种类数
               win.put(fruits[l], win.get(fruits[l]) - 1);
               if (win.get(fruits[l]) == 0)
                   win.remove(fruits[l]); // 彻底删除键值
               l++;
           }
           res = Math.max(res, r - l + 1);
       }
       return res;
   }
}

• 时间复杂度：O(n)

• 空间复杂度：O(1)

C++

数组

class Solution {
public:
   int totalFruit(vector<int>& fruits) {
       int res = 0;
       int win[fruits.size() + 10];
       memset(win, 0, sizeof(win));
       for (int l = 0, r = 0, tot = 0; r < fruits.size(); r++) {
           if (++win[fruits[r]] == 1)
               tot++; // 当前种类统计
           while (tot > 2) {
               if (--win[fruits[l++]] == 0)
                   tot--;
           }
           res = max(res, r - l + 1); // 维护最长状态
       }
       return res;
   }
};

• 时间复杂度：O(n)

• 空间复杂度：O(n)

哈希表

可使用哈希表构建窗口，降低空间复杂度。

class Solution {
public:
   int totalFruit(vector<int>& fruits) {
       unordered_map<int, int> win;
       int l = 0, res = 0;
       for (int r = 0; r < fruits.size(); r++) {
           if (win.count(fruits[r]))
               win[fruits[r]]++;
           else
               win[fruits[r]] = 1;
           while (win.size() > 2) { // 窗口大小即种类数
               win[fruits[l]]--;
               if (win[fruits[l]] == 0)
                   win.erase(fruits[l]); // 彻底删除键值
               l++;
           }
           res = max(res, r - l + 1);
       }
       return res;
   }
};

• 时间复杂度：O(n)

• 空间复杂度：O(1)

总结

• 今天不想rust了&hellip;&hellip;主体和这两种语言差不多，要多些类型转换balabala的内容

来源：https://juejin.cn/post/7155315083826954248