网站开发哪里接业务,广东省农业农村厅领导,腾讯域名购买,红塔网站制作题目#xff1a; 题目解析#xff1a; fruits[i]表示第i棵树#xff0c;这个fruits[i]所表示的数字是果树的种类例如示例1中的[1,2,1]#xff0c;表示第一棵树 的种类是 1#xff0c;第二个树的种类是2 第三个树的种类是1随后每一个篮子只能装一种类型的水果#xff0c;我…
题目 题目解析 fruits[i]表示第i棵树这个fruits[i]所表示的数字是果树的种类例如示例1中的[1,2,1]表示第一棵树 的种类是 1第二个树的种类是2 第三个树的种类是1随后每一个篮子只能装一种类型的水果我们有两个篮子所以最后求的是可以采摘几棵树问题转化就是求最长的连续的子数组而且这个数组只能有两种数字 算法原理 根据题目的解析我们需要知道本题需要 用于计算水果种类的 kinds 、用于存储水果的果篮 hash、用于寻找连续数组的指针 right、left
使用left指针进行固定从最左端开始而right指针开始移动进行水果的摘取 同时一边摘取水果一边将水果放入篮子内部同时更新right和left之间的距离长度以此来获取最大的连续子数组长度。
在水果摘取的过程中因为篮子内部只能是两种水果所以使用数组把代表水果的数字作为下标进行水果的数量记载当遇到第三个水果时right停止移动表示篮子内部的两种水果的组合在当前结束了。
而当right停止移动时left就要开始移动因为篮子只能存在两种水果且需要子数组连续所以可以让left一边移动的同时一边减去指向的元素的个数使得水果的数量减少的同时也能够将果篮内的另一个水果排除让水果篮内部至少留下一个水果和新种类的水果组成新的组合。
当水果蓝内的水果只剩下一种时left停止移动而right开始重新移动直到遇见另一个新的水果停下之后重复之前的操作。 代码编写 使用一个内容巨大的数组来充当水果篮子hash[f[right]]和hash[f[left]]表示的是这个元素的数量。相当于是让这个元素变成一种下标索引在这个超级大的数组内部进行数量的统计kinds表示一共有多少种类的元素最多只能是2当kind大于2时我们需要减去left指向的元素的个数同时因为种类的原因且需要进行连续所以在种类重新编程小于等于2之前元素的个数都必须减少直到某一个元素消失kind小于等于2为止
