discuz修改网站底部,cpa广告联盟网站建设教程,四川网站建设多少钱,自助建站的平台目录 第一题#xff1a;复写零
第二题#xff1a;快乐数#xff1a;
第三题#xff1a;盛水最多的容器
第四题#xff1a;有效三角形的个数 第一题#xff1a;复写零
力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
思路#xff1a;
上期…
目录 第一题复写零
第二题快乐数
第三题盛水最多的容器
第四题有效三角形的个数 第一题复写零
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
思路
上期介绍到双指针这次来用双指针实际操作。第一种从前往后复写会导致为复写的数字被覆盖因此选择从后往前复写那么先找到复写的最后一个元素再从后往前复写即可。
步骤
1.初始化指针
2.找复写
3.处理边界问题
4.开始复写
class Solution {
public:void duplicateZeros(vectorint arr) {int cur 0, dest -1, n arr.size();
while (cur n)
{if (arr[cur]) dest;//说明不用复写else dest 2;if (dest n - 1)break;cur;
}
//出来的时候cur就是莫位置
//处理边界
if (dest n)
{arr[n - 1] 0;cur--; dest - 2;
}
//从后往前面复写
while (cur 0)
{if (arr[cur])//非0arr[dest--] arr[cur--];else//为0{arr[dest--] 0;arr[dest--] 0;cur--;}
}}
};
第二题快乐数
力扣LeetCode官网 - 全球极客挚爱的技术成长平台 思路
这题通过在纸上演算可以发现给定一个数他按照快乐数的定义要么演变到1要么将会重复他在演变过程中的一个数字具体大家可以在纸上推算一遍
即
2 - 4 - 16 - 37 - 58 - 89 - 145 - 42 - 20 - 4 - 16即形成了一个循环圈 而另外一种变成一其实也可以看作是一个循环圈即给定一个数按照快乐数的定义我给出两个指针一个移动地快一个移动地慢最终两个数一定会相等倘若等于1那么就是快乐数倘若不等于1就不是快乐数 因此步骤 1.先把n的每一位提出直到n为0 2.接着只要两个指针不相等就一直重复快乐数定义直到相等退出循环判断是否为1 class Solution
{
public:int bitSum(int n)int sum 0;while (n){int t n % 10;sum t * t;n / 10;}bool isHappy(int n){int slow n, fast bitSum(n);while (slow ! fast){slow bitSum(slow);fast bitSum(bitSum(fast));}return slow 1;}
}; 第三题盛水最多的容器 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 思路 第一想法就是暴力枚举 sh高*w宽度 即弄两个for循环依次求出面积再比较最大值这样时间复杂度为n的平方会超时因此 第二种就是双指针观察发现面积的高是由左右两边的低边界为准。就以上图为例高是由右边那条高决定左边高往右移动由于w一定减小h要么减小要么不变那么面积一定减小所以我们就从两个边界开始来移动记录每一次的面积返回最大即可 注意每次移动的是那个h小的因为大h移动s要么减少要么不变而我们求的是最大的。 第一种暴力求解 class Solution {
public:int maxArea(vectorint height) {int n height.size();int ret 0;// 两层 for 枚举出所有可能出现的情况for (int i 0; i n; i) {for (int j i 1; j n; j) {// 计算容积找出最⼤的那⼀个ret max(ret, min(height[i], height[j]) * (j - i));}}return ret;}
}; 第二种 对撞指针 class Solution
{
public:int maxArea(vectorint height){int left 0, right height.size() - 1, ret 0;while (left right){int v min(height[left], height[right]) * (right - left);ret max(ret, v);// 移动指针if (height[left] height[right]) left;else right--;}return ret;}
};第四题有效三角形的个数 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 思路 在判断一个三角形时如果对于一对升序数组a,b,c 如果abc那么即可构成三角形不需要判断三次 原因如果上述条件成立那么bca,acb一定成立因为c是最大的数 第一思路就是暴力求解先把给定数组排序然后从第一个元素开始遍历用三个for循环实现但是时间复杂度较大运行会超时 class Solution {
public:int triangleNumber(vectorint nums) {// 1. 排序sort(nums.begin(), nums.end());int n nums.size(), ret 0;// 2. 从⼩到⼤枚举所有的三元组for (int i 0; i n; i) {for (int j i 1; j n; j) {for (int k j 1; k n; k) {// 当最⼩的两个边之和⼤于第三边的时候统计答案if (nums[i] nums[j] nums[k])ret;}}}return ret;}
}; 应次这里换一种高效方法就是用双指针来实现因为已经排完升序依据暴力解法可以先固定一条最长边然后找出比这条边小的二元组让着个二元组的和大于最长边即可利用对撞指针来实现。 最长边枚举i位置区间[left,right]是i位置左边区间 如果nums[left]nums[right]num[i]那么就有right-left种因为是升序 否则那么就舍弃left当前元素left进入下一轮循环 class Solution
{
public:int triangleNumber(vectorint nums){// 1. 优化sort(nums.begin(), nums.end());// 2. 利⽤双指针解决问题int ret 0, n nums.size();for (int i n - 1; i 2; i--) // 先固定最⼤的数{// 利⽤双指针快速统计符合要求的三元组的个数int left 0, right i - 1;while (left right){if (nums[left] nums[right] nums[i]){ret right - left;right--;}else{left;}}}return ret;}
};
