当前位置 : 主页 > 编程语言 > java >

Java C++题解leetcode904水果成篮

来源:互联网 收集:自由互联 发布时间:2023-01-30
目录 题目要求 阅读理解 思路:滑动窗口 Java 数组 哈希表 C++ 数组 哈希表 总结 题目要求 阅读理解 读完题的我be like: 去看了遍英文版就懂了,题目中的 种类 【type】不是 种类数 每个数
目录
  • 题目要求
  • 阅读理解
    • 思路:滑动窗口
  • Java
    • 数组
    • 哈希表
  • C++
    • 数组
    • 哈希表
  • 总结

    题目要求

    阅读理解

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

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

    上一篇:Java必会的Synchronized底层原理剖析
    下一篇:没有了
    网友评论