刚开始刷力扣,刷了几天发现刷完过两天就忘记了。索性就用写博客的方式记录一下,方便日后复盘回溯。
题目链接:https://leetcode.cn/problems/fruit-into-baskets/description/?envType=problem-list-v2&envId=fdmaj8E9
这道题依旧是使用双指针的思路来完成,首先有一个指针必定进行遍历,探索新元素是否符合篮子1和篮子2元素的指针,这里给遍历指针设置为j。
另一个指针也就是左边界,也就是滑动窗口的左界限,同时代表第一个篮子,这里设置为f1。
在遍历过程中我们要思考每个篮子的位置变化,比如说第一个篮子的下一个位置的元素必定等于第二个篮子的元素(注意这里并不是直接等于第二个篮子的位置,而是要判断第二个篮子最后一个元素的位置) 。例如[1,2,1,1,2,3,3,4] 当第二个篮子在3时,第一个篮子应在fruits[5]而非fruits[1].如果单纯的第一个篮子位置等于第二个篮子位置就会出现错误。
这就提示在遍历中我们要把最后一个符合篮子2元素的位置设置成 篮子1下个位置,也就是f1_next。
整体思路就是 :{
遍历整个数组{
if(fruits[f1] != fruits[j])&&(frutis[f2] != fruits[j]){
f1 = f1_next 同时 f2 = j; //这就是篮子更替的过程
}
随时判断第二个篮子最后一个元素的位置,用来作为f1_next,
这里暴力判断,只要符合第二个篮子的元素就等于f1_next,所以第二个篮子的最后
一个元素必定等于f1_next
if(fruits[j] == fruits[f2]) f1_next = j;
最后计算length = j - f1 + 1;
总体代码:
class Solution {
public:
int totalFruit(vector<int>& fruits) {
if(fruits.size() < 3) return fruits.size();
int result = 0;
//f1滑动窗口左(第一种水果起始) j为遍历(右边界)
//f2第二种水果起始 t为未来的两个篮子起始索引
for(int j=0,f1=0,f2=0,t=0;j<fruits.size();j++){
if(fruits[j]!=fruits[f1]&&fruits[j]!=fruits[f2]){
if(f1!=f2) {f1=t;}
f2=j; //第二个篮子
}
if(fruits[t]!=fruits[j]) t = j; //t始终为篮子的位置
result = (result>(j-f1+1))?result:(j-f1+1);
}
return result;
}
};
111
标签:f1,水果,遍历,f2,next,fruits,篮子,成篮
From: https://www.cnblogs.com/ink-bai/p/18205780