第一题复写零

上期介绍到双指针这次来用双指针实际操作。

第一种从前往后复写会导致为复写的数字被覆盖因此选择从后往前复写那么先找到复写的最后一个元素再从后往前复写即可。

1.初始化指针

arr[cur--];else//为0{arr[dest--]

0;arr[dest--]

这题通过在纸上演算可以发现给定一个数他按照快乐数的定义要么演变到1要么将会重复他在演变过程中的一个数字具体大家可以在纸上推算一遍

145

而另外一种变成一其实也可以看作是一个循环圈即给定一个数按照快乐数的定义我给出两个指针一个移动地快一个移动地慢最终两个数一定会相等倘若等于1那么就是快乐数倘若不等于1就不是快乐数

因此步骤

2.接着只要两个指针不相等就一直重复快乐数定义直到相等退出循环判断是否为1

class

即弄两个for循环依次求出面积再比较最大值这样时间复杂度为n的平方会超时因此

第二种就是双指针观察发现面积的高是由左右两边的低边界为准。

就以上图为例高是由右边那条高决定左边高往右移动由于w一定减小h要么减小要么不变那么面积一定减小所以我们就从两个边界开始来移动记录每一次的面积返回最大即可

注意每次移动的是那个h小的因为大h移动s要么减少要么不变而我们求的是最大的。

第一种暴力求解

原因如果上述条件成立那么bca,acb一定成立因为c是最大的数

第一思路就是暴力求解先把给定数组排序然后从第一个元素开始遍历用三个for循环实现但是时间复杂度较大运行会超时

class

应次这里换一种高效方法就是用双指针来实现因为已经排完升序依据暴力解法可以先固定一条最长边然后找出比这条边小的二元组让着个二元组的和大于最长边即可利用对撞指针来实现。

如果nums[left]nums[right]num[i]那么就有right-left种因为是升序

class

left;right--;}else{left;}}}return

ret;}