快捷導(dǎo)航

Java?C++題解leetcode904水果成籃

更新時間：2022年10月19日 11:53:45 作者：AnjaVon

這篇文章主要為大家介紹了Java?C++題解leetcode904水果成籃示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目要求

閱讀理解

讀完題的我be like:

去看了遍英文版就懂了，題目中的種類【type】不是種類數(shù)……每個數(shù)字代表一種樹【用個字母啥的表示或者翻譯成類型就好理解多了】，那么目標(biāo)就是找從哪里開始可以維持兩種數(shù)字（種類）無規(guī)律交替出現(xiàn)的狀態(tài)最久，這個最久是多少棵樹。

思路：滑動窗口

窗口里可放兩棵樹，一棵是棗樹，另一棵還是棗樹。向后遍歷整排樹，并更新最長狀態(tài)。

Java

數(shù)組

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++; // 當(dāng)前種類統(tǒng)計
            while (tot > 2) {
                if (--win[fruits[l++]] == 0)
                    tot--;
            }
            res = Math.max(res, r - l + 1); // 維護(hù)最長狀態(tài)
        }
        return res;
    }
}

時間復(fù)雜度：O(n)
空間復(fù)雜度：O(n)

哈希表

可使用哈希表構(gòu)建窗口，降低空間復(fù)雜度。

鍵對應(yīng)籃子，值對應(yīng)同類樹數(shù)量；
當(dāng)值為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) { // 窗口大小即種類數(shù)
                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;
    }
}

時間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)

C++

數(shù)組

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++; // 當(dāng)前種類統(tǒng)計
            while (tot > 2) {
                if (--win[fruits[l++]] == 0)
                    tot--;
            }
            res = max(res, r - l + 1); // 維護(hù)最長狀態(tài)
        }
        return res;
    }
};

時間復(fù)雜度：O(n)
空間復(fù)雜度：O(n)

哈希表

可使用哈希表構(gòu)建窗口，降低空間復(fù)雜度。

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) { // 窗口大小即種類數(shù)
                win[fruits[l]]--;
                if (win[fruits[l]] == 0)
                    win.erase(fruits[l]); // 徹底刪除鍵值
                l++;
            }
            res = max(res, r - l + 1);
        }
        return res;
    }
};