做电影网站的程序,长春建站价格,江苏省住房和城乡建设网站,server2012 wordpress提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 目录
文章目录
前言
一、有效三角形的个数#xff08;medium#xff09;
1.1、题目
1.2、讲解算法原理
1.3、编写代码
二、和为s的两个数字
2.1、题目
2.2、讲解算… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 目录
文章目录
前言
一、有效三角形的个数medium
1.1、题目
1.2、讲解算法原理
1.3、编写代码
二、和为s的两个数字
2.1、题目
2.2、讲解算法原理
2.3、编写代码
三、三数之和
3.1、题目
3.2、讲解算法原理
3.3、编写代码
四、四数之和
4.1、题目
4.2、讲解算法原理
4.3、编写代码
总结 前言
世上有两种耀眼的光芒一种是正在升起的太阳一种是正在努力学习编程的你!一个爱学编程的人。各位看官我衷心的希望这篇博客能对你们有所帮助同时也希望各位看官能对我的文章给与点评希望我们能够携手共同促进进步在编程的道路上越走越远 提示以下是本篇文章正文内容下面案例可供参考
一、有效三角形的个数medium 1.1、题目 1.2、讲解算法原理
补充数学知识给我们三个数判断是都能够构成三角形。 步骤利用单调性使用双指针算法来解决问题。
先固定最大的数在最大的数的左区间内使用双指针算法快速统计出符合要求的三元组的个数。
来举例一个区间[22344910]来说明一下情况
优化先对整个数组排序用于固定最大的数。我们根据三角形的满足条件得出的两个结论因为数组是升序的所以设a和b为最小的两边c为最大的边a b c就能构成三角形a b c便不能构成三角形。我们使用双指针的思想假设数组的下标为指针设left指针指向数组下标为0的位置设right指针指向数组中最大的数的左区间中的最大值。
拿上面的数组为例先固定最大的数为10设left为第一个2所在的位置right为9所在的位置left right大于10因为是升序所以当right不变left指向2~9之间的任意数时都符合三角形的条件因此得出的结论下标right - left的值为满足三角形的情况9所在的位置可以划掉right--。此时left为第一个2right为5最大值依旧为102 5 10不构成三角形的条件left再次判断三角形的条件重复操作直到left和right相遇最大值为10所在的情况查看完毕更新最大值。
1.3、编写代码
class Solution
{
public:int triangleNumber(vectorint nums) {// 先进行排序sort(nums.begin(), nums.end());// 利用双指针解决问题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;}
}; 二、和为s的两个数字
2.1、题目 2.2、讲解算法原理
利用单调性使用双指针算法解决问题。
举一个数组[2711151921]t 30为例设left指针指向2right指针指向21让两数相加来和t值(30)比较。
分为三种情况
sum tleft为2right为21相加得23 t(30)因为数组为递增顺序left和right区间的数字都比21要小因此划掉2leftsum tleft为11right为21相加得32 t(30)left和right区间的数值都比left(11)要大因此划掉21right--sum t(30)返回结果。
2.3、编写代码
class Solution
{
public:vectorint twoSum(vectorint price, int target) {int left 0,right price.size() - 1;while(left right){if(price[left] price[right] target){right--;}else if(price[left] price[right] target){left;}else{return {price[left],price[right]};}}// 照顾编译器return {-1,-1};}
}; 三、三数之和
3.1、题目 3.2、讲解算法原理 步骤
排序固定一个数a(小优化对于下面的数组来说a 0之后不管left 和 right 两个指针指向哪里和 a 相加之后都不会等于0因此 a 0之后就可以结束了)在该固定的数a后面的区间内利用“双指针算法”快速找到两个的和等于 -a 即可。
处理细节问题
1、去重
找到一种结果之后left 和 right 指针要跳过重复元素当使用完一次双指针算法之后i 也需要跳过重复的元素避免越界。
2、不漏
找到一种结果之后不要“停”缩小区间继续寻找。 3.3、编写代码
class Solution
{
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint ret;// 定义一个二级数组用于储存数组// 排序sort(nums.begin(), nums.end());int i 0, n nums.size();// 固定一个数afor(i 0; i n; ) // for()循环中初始化、判断和调整这三个部分都可以写为空{// 小优化if(nums[i] 0) break;int left i 1, right n - 1, target -nums[i];// target两个指针所指向的数相加固定数的负数while(left right){int sum nums[left] nums[right];if(sum target) right--;else if(sum target) left;else {ret.push_back({nums[i], nums[left], nums[right]});left, right--;// 去重操作 left rightwhile(left right nums[left] nums[left - 1]) left;while(left right nums[right] nums[right 1]) right--;}}i;// 去重操作 iwhile(i n nums[i] nums[i - 1]) i;}return ret;}
}; 四、四数之和
4.1、题目 4.2、讲解算法原理
排序 双指针
依次固定一个数a在 a 后面的区间内利用三数之和找到三个数使这三个数的和等于 target -a 即可。
三数之和
依次固定一个数 b在 b 后面的区间内利用双指针找到两个数使这两个数的和等于 target - a - b 即可。
处理细节问题
1、去重
找到一种结果之后left 和 right 指针要跳过重复元素当使用完一次双指针算法之后i 也需要跳过重复的元素避免越界。
2、不漏
找到一种结果之后不要“停”缩小区间继续寻找。 4.3、编写代码
class Solution
{
public:vectorvectorint fourSum(vectorint nums, int target) {// 定义一个二级数组用来存放数组vectorvectorint ret;// 排序sort(nums.begin(),nums.end());// 固定一个数aint i 0,n nums.size();for(i 0; i n; ){// 固定数b --- 将四数求和转换成三数求和for(int j i 1; j n; ){// 利用双指针的算法int left j 1, right n -1; while(left right){// 这个地方用int类型有可能会超出int的范围用long longlong long aim (long long)target - nums[i] - nums[j];int sum nums[left] nums[right];if(sum aim) right--;else if(sum aim) left;else{ret.push_back({nums[i], nums[j], nums[left], nums[right]});left, right--;// 去重操作 left rightwhile(left right nums[left] nums[left-1]) left;while(left right nums[right] nums[right1]) right--;}}j;// 去重操作 jwhile(j n nums[j] nums[j-1]) j;}i;// 去重操作 iwhile(i n nums[i] nums[i-1]) i;}return ret;}
}; 总结
好了本篇博客到这里就结束了如果有更好的观点请及时留言我会认真观看并学习。不积硅步无以至千里不积小流无以成江海。
