Java C 解析：如何高效解决LeetCode 904 水果成篮问题？

本文共计912个文字，预计阅读时间需要4分钟。

目录+主题要求+阅读理解+思路：滑动窗口+Java+数组+哈希表+C+++数组+哈希表+总结+主题要求+阅读理解+读完后我的感受：看了英文版就懂了，题目中的[类型]不是[类型数]+每个数“

目录

• 题目要求
• 阅读理解
• 思路：滑动窗口
• Java
• 数组
• 哈希表
• C++
• 数组
• 哈希表
• 总结

题目要求

阅读理解

读完题的我be like:

去看了遍英文版就懂了，题目中的种类不是种类数……每个数字代表一种树，那么目标就是找从哪里开始可以维持两种数字（种类）无规律交替出现的状态最久，这个最久是多少棵树。

思路：滑动窗口

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

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了……主体和这两种语言差不多，要多些类型转换balabala的内容

以上就是Java C++题解leetcode904水果成篮的详细内容，更多关于Java C++题解水果成篮的资料请关注自由互联其它相关文章！