資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中的水果放入籃子
假設我們有一排樹，第 i 棵樹產出的水果型別為 tree[i]。我們可以從任意一棵樹開始，然後重複執行以下步驟：
- 從這棵樹上摘一個水果放入我們的籃子。如果沒有水果可摘，則停止。
- 移到當前樹右側的下一棵樹。如果沒有右側的樹，則停止。
我們有兩個籃子，每個籃子可以裝任意數量的水果，但我們希望每個籃子只裝一種水果。我們必須找到使用此過程可以收集的水果總數？所以如果樹木像 [0, 1, 2, 2]，那麼輸出將是 3。如果我們從第一棵樹開始，我們可以收集 [1, 2, 2]，那麼我們只會收集 [0, 1]
為了解決這個問題，我們將遵循以下步驟：
- n := 樹的大小，j := 0，ans := 0
- 建立一個 map m
- 對於 i 從 0 到 n – 1
- 將 m[tree[i]] 增加 1
- 當 m 的大小 > 2 且 j <= i 時，則
- 將 m[tree[j]] 減少 1
- 如果 m[tree[j]] = 0，則從 m 中刪除 tree[j]
- 將 j 增加 1
- ans := i – j + 1 和 ans 的最大值
- 返回 ans
讓我們看看以下實現以獲得更好的理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int totalFruit(vector<int>& tree) {
int n = tree.size();
int j = 0;
map <int, int> m;
int ans = 0;
for(int i = 0; i < n; i++){
m[tree[i]] += 1;
while(m.size() > 2 && j <= i){
m[tree[j]]--;
if(m[tree[j]] == 0)m.erase(tree[j]);
j++;
}
ans = max(i - j + 1, ans);
}
return ans;
}
};
main(){
vector<int> v = {3,3,3,1,2,1,1,2,3,3,4};
Solution ob;
cout <<(ob.totalFruit(v));
}輸入
[3,3,3,1,2,1,1,2,3,3,4]
輸出
5
更新於： 2020年4月30日
904 次瀏覽
廣告