题目要求
阅读理解
读完题的我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 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 win = new HashMap(); int l = 0, res = 0; for (int r = 0; r 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& fruits) { int res = 0; int win[fruits.size() + 10]; memset(win, 0, sizeof(win)); for (int l = 0, r = 0, tot = 0; r 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& fruits) { unordered_map win; int l = 0, res = 0; for (int r = 0; r 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了……主体和这两种语言差不多,要多些类型转换balabala的内容
以上就是Java C++题解leetcode904水果成篮的详细内容,更多关于Java C++题解水果成篮的资料请关注IT俱乐部其它相关文章!