网站策划需要什么,wordpress前台加速,什么是网站建设整体策划方案,浦东做网站目录 一#xff1a;双指针的介绍
1#xff1a;快慢指针
2#xff1a;对撞指针
二#xff1a;对撞指针例题讲述 一#xff1a;双指针的介绍
在做题中常用两种指针#xff0c;分别为对撞指针与快慢指针。
1#xff1a;快慢指针
简称为龟兔赛跑算法#xff0c;它的基…目录 一双指针的介绍
1快慢指针
2对撞指针
二对撞指针例题讲述 一双指针的介绍
在做题中常用两种指针分别为对撞指针与快慢指针。
1快慢指针
简称为龟兔赛跑算法它的基本思想是使用两个移动速度不同的指针在数组或链表等序列结构上移动。
这种对于处理环形链表和数组以及循环重复问题是非常好用的。
2对撞指针
简称为左右指针它的基本思想是一个指针从最左端开始一个从最右端开始逐渐往中间逼近。一般终止条件是两个指针相遇或者错开。
一般用于顺序结构中。
注意这里的指针并不是C语言中的指针而是指在数组中设置的两个下标通过改变两个下标来改变所在数组的位置。
二对撞指针例题讲述
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
1盛最多水容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明你不能倾斜容器。
算法原理
解法1暴力枚举是很简单的但是我们可以发现他的时间复杂度是超时的。
解法2双指针法题中让求v,那么vh*w.
186254837
就以上面的数组举例。
我们设左指针left为数组最左边的下标右指针right为数组最右边的下标。
那么我们要取最大的V只有一种情况就要h变大w变小。因为最开始的W最大。
int nheight.size();
int left0,rightn-1;设置左右指针。
int ret0;
while(leftright)
{int summin(height[left],height[right])*(right-left) //求vretmax(ret,sum)//求出最大的v.if(height[left]height[right])left;elseright--;}
return ret; 力扣LeetCode官网 - 全球极客挚爱的技术成长平台
2:有效三角形的个数
给定一个包含非负整数的数组 nums 返回其中可以组成三角形三条边的三元组个数。 示例 1:
输入: nums [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
需要的判断条件就是两个最小边之和大于最大边。
算法原理
第一种:暴力求解。明显的是超出时间限制的。
第二种双指针 。利用单调性。
1.先固定最大的数。
2.在最大的数的左区域内使用双指针算法快速统计出符合要求的三元组的个数。
sort(nums.begin(),nums.end());//这一步是排序。
int nnums.size();
int in-1;
int ret0;for(i;i2;i--){int left0;int righti-1;while(leftright)//基本条件{ if(nums[left]nums[right]nums[i]) left;else {retright-left;right--;}}}
return ret;}力扣LeetCode官网 - 全球极客挚爱的技术成长平台
购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况返回任一结果即可。
示例 1
输入price [3, 9, 12, 15], target 18
输出[3,15] 或者 [15,3]
算法思路
1暴力枚举。显然还是超过时间限制。
2双指针。比较简单就不再详解。 int left 0, right nums.size() - 1;while(left right){int sum nums[left] nums[right];if(sum target) right--;else if(sum target) left;else return {nums[left], nums[right]};}// 照顾编译器return {-4941, -1};
