C++怎么實現水果裝入果籃問題

這篇文章主要介紹“C++怎么實現水果裝入果籃問題”，在日常操作中，相信很多人在C++怎么實現水果裝入果籃問題問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”C++怎么實現水果裝入果籃問題”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

水果裝入果籃

先來看第一種，使用一個 HashMap 來記錄每個水果出現次數，當 HashMap 中當映射數量超過兩個的時候，我們需要刪掉一個映射，做法是滑動窗口的左邊界 start 的水果映射值減1，若此時減到0了，則刪除這個映射，否則左邊界右移一位。當映射數量回到兩個的時候，用當前窗口的大小來更新結果 res 即可，參見代碼如下：
解法一：

class Solution {
public:
    int totalFruit(vector<int>& tree) {
        int res = 0, start = 0, n = tree.size();
        unordered_map<int, int> fruitCnt;
        for (int i = 0; i < n; ++i) {
            ++fruitCnt[tree[i]];
            while (fruitCnt.size() > 2) {
                if (--fruitCnt[tree[start]] == 0) {
                    fruitCnt.erase(tree[start]);
                }
                ++start;
            }
            res = max(res, i - start + 1);
        }
        return res;
    }
};

我們除了用 HashMap 來映射字符出現的個數，我們還可以映射每個數字最新的坐標，比如題目中的例子 [0,1,2,2]，遇到第一個0，映射其坐標0，遇到1，映射其坐標1，當遇到2時，映射其坐標2，每次我們都判斷當前 HashMap 中的映射數，如果大于2的時候，那么需要刪掉一個映射，我們還是從 start=0 時開始向右找，看每個字符在 HashMap 中的映射值是否等于當前坐標 start，比如0，HashMap 此時映射值為0，等于 left 的0，那么我們把0刪掉，start 自增1，再更新結果，以此類推直至遍歷完整個數組，參見代碼如下：
解法二：

class Solution {
public:
    int totalFruit(vector<int>& tree) {
        int res = 0, start = 0, n = tree.size();
        unordered_map<int, int> fruitPos;
        for (int i = 0; i < n; ++i) {
            fruitPos[tree[i]] = i;
            while (fruitPos.size() > 2) {
                if (fruitPos[tree[start]] == start) {
                    fruitPos.erase(tree[start]);
                }
                ++start;
            }
            res = max(res, i - start + 1);
        }
        return res;
    }
};

后來又在網上看到了一種解法，這種解法是維護一個滑動窗口 sliding window，指針 left 指向起始位置，right 指向 window 的最后一個位置，用于定位 left 的下一個跳轉位置，思路如下：

• 若當前字符和前一個字符相同，繼續循環。

• 若不同，看當前字符和 right 指的字符是否相同：

• 若相同，left 不變，右邊跳到 i - 1。

• 若不同，更新結果，left 變為 right+1，right 變為 i - 1。

最后需要注意在循環結束后，我們還要比較結果 res 和 n - left 的大小，返回大的，這是由于如果數組是 [5,3,5,2,1,1,1]，那么當 left=3 時，i=5,6 的時候，都是繼續循環，當i加到7時，跳出了循環，而此時正確答案應為 [2,1,1,1] 這4個數字，而我們的結果 res 只更新到了 [5,3,5] 這3個數字，所以我們最后要判斷 n - left 和結果 res 的大小。

另外需要說明的是這種解法僅適用于于不同字符數為2個的情況，如果為k個的話，還是需要用上面兩種解法。

解法三：

class Solution {
public:
    int totalFruit(vector<int>& tree) {
        int res = 0, left = 0, right = -1, n = tree.size();
        for (int i = 1; i < n; ++i) {
            if (tree[i] == tree[i - 1]) continue;
            if (right >= 0 && tree[right] != tree[i]) {
                res = max(res, i - left);
                left = right + 1;
            }
            right = i - 1;
        }
        return max(n - left, res);
    }
};

還有一種不使用 HashMap 的解法，這里我們使用若干個變量，其中 cur 為當前最長子數組的長度，a和b為當前候選的兩個不同的水果種類，cntB 為水果b的連續個數。我們遍歷所有數字，假如遇到的水果種類是a和b中的任意一個，那么 cur 可以自增1，否則 cntB 自增1，因為若是新水果種類的話，默認已經將a種類淘汰了，此時候選水果由類型b和這個新類型水果構成，所以當前長度是 cntB+1。然后再來更新 cntB，假如當前水果種類是b的話，cntB 自增1，否則重置為1，因為 cntB 統計的就是水果種類b的連續個數。然后再來判斷，若當前種類不是b，則此時a賦值為b， b賦值為新種類。最后不要忘了用 cur 來更新結果 res，參見代碼如下：
解法四：

class Solution {
public:
    int totalFruit(vector<int>& tree) {
        int res = 0, cur = 0, cntB = 0, a = 0, b = 0;
        for (int fruit : tree) {
            cur = (fruit == a || fruit == b) ? cur + 1 : cntB + 1;
            cntB = (fruit == b) ? cntB + 1 : 1;
            if (b != fruit) {
                a = b; b = fruit;
            }
            res = max(res, cur);
        }
        return res;
    }
};

到此，關于“C++怎么實現水果裝入果籃問題”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！