IT俱乐部 Java Java C++题解leetcode904水果成篮

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  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俱乐部其它相关文章!

本文收集自网络,不代表IT俱乐部立场,转载请注明出处。https://www.2it.club/code/java/7382.html
上一篇
下一篇
联系我们

联系我们

在线咨询: QQ交谈

邮箱: 1120393934@qq.com

工作时间:周一至周五,9:00-17:30,节假日休息

关注微信
微信扫一扫关注我们

微信扫一扫关注我们

返回顶部