数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
广告