首页 > 其他分享 >水果成篮

水果成篮

时间:2024-05-22 11:11:17浏览次数:19  
标签:f1 水果 遍历 f2 next fruits 篮子 成篮

刚开始刷力扣,刷了几天发现刷完过两天就忘记了。索性就用写博客的方式记录一下,方便日后复盘回溯。
题目链接: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

相关文章