网站怎么被搜到首页,怎样做网站权重,佛山网站建设优化制作公司,做美食网站的素材个人主页 #xff1a; zxctscl 如有转载请先通知 题目 1. 283. 移动零1.1 分析1.2 代码 2. 1089. 复写零2.1 分析2.2 代码 3. 202. 快乐数3.1 分析3.2 代码 4. 11. 盛最多水的容器4.1 分析4.2 代码 5. LCR 179. 查找总价格为目标值的两个商品5.1 分析5.2 代码 6. 15. 三数之和… 个人主页 zxctscl 如有转载请先通知 题目 1. 283. 移动零1.1 分析1.2 代码 2. 1089. 复写零2.1 分析2.2 代码 3. 202. 快乐数3.1 分析3.2 代码 4. 11. 盛最多水的容器4.1 分析4.2 代码 5. LCR 179. 查找总价格为目标值的两个商品5.1 分析5.2 代码 6. 15. 三数之和6.1 分析6.2 代码 1. 283. 移动零 1.1 分析
一、题目分析 要将0放在所有数组的最后而且非零元素的顺序保持不变要求原地对数组进行移动。
二、算法原理 用两个指针来讲数组进行划分一个cur从左往右扫描数组遍历数组一个dest已经处理的区间内非零元素的最后一个位置。 就将数组分为3个区间非零[0,dest]0区间[dest1,cur-1]待处理的区间:[cur,n-1]. 要想这样划分cur就得从前往后在遍历的过程中遇到0元素就加加遇到非零元素就将dest1位置和cur位置的值交换。 1.2 代码
class Solution {
public:void moveZeroes(vectorint nums) {for(int cur0,dest-1;curnums.size();cur){if(nums[cur]){swap(nums[dest],nums[cur]);}}}
};2. 1089. 复写零 2.1 分析
一、题目解析 要求每次遇到0就复写而且不能改变原数组的长度。
二、算法原理 如果用双指针从前往后遍历就拿例1来说 就会出现值被覆盖的情况 所以遍历顺序就不能从前往后。 那么就把顺序改为从后往前遍历但是不能超过原数组的长度就得先找一下cur和dest开始的位置。 可以先用双指针算法1.先判断cur位置2.决定dest向后移动一步或者两步3.判断一下dest是否已经到达结束位置4.在把cur加加。 但是可能会出现dest越界的情况如果n-1位置为0那么cur就减减dest就减2。 最后在从后往前开始复写0。 2.2 代码
class Solution {
public:void duplicateZeros(vectorint arr) {int cur0,dest-1;int narr.size();while(curn){if(arr[cur])dest;else dest2;if(destn-1)break;cur;}if(destn){arr[n-1]0;cur--;dest-2;}while(cur0){if(arr[cur])arr[dest--]arr[cur--];else {arr[dest--]0;arr[dest--]0;cur--;}}}
};3. 202. 快乐数 3.1 分析
一、题目分析 题目中所说最后的平方和为1才是快乐数如果不为1就一直循环其实可以看成两个都是循环一个一直循环的是1另一个循环的值都不相同。只需要判断循环里面的值是不是为1就可以。
二、算法原理 先用一个变量sum记录最后平方和然后把最后一位平方然后删掉原来的数一直重复这个过程直到最后一位为0最后返回这个平方和sum。
定义两个快慢指针用平方和来充当指针slow指向第一个数fast指向第二个数如果这两个指针一直不相等就一直循环slow走一步fast走两步。直到两个相遇为止等于1就是快乐数不等于就不是。
3.2 代码
class Solution {
public:int bitsum(int n){int sum0;while(n){int tn%10;sumt*t;n/10;}return sum;} bool isHappy(int n) {int slown,fastbitsum(n);while(slow!fast){slowbitsum(slow);fastbitsum(bitsum(fast));}return slow1;}
};4. 11. 盛最多水的容器 4.1 分析
一、题目分析 题目中的数组代表每一条线的高度来求最大的容积来看一下例1 选择的高度是8和7但是题目要求不能倾斜这里选择高度的就是7宽度就是下标之间的差值8-1也就是7那么容积最大就是7*749。
二、算法原理 用两个指针来记录容器两边的高度可以直接先选择最大的宽度记录下这个容积。 如果左边指针走一步宽度在减小高度可能会出现比之前的小那么体积就比原来的小高度如果不变那么宽度减小那么总容积也是在减小的。所以得干掉高度小的那一个值。 如果两个指针指向的值相等那么干掉谁都可以然后继续枚举里面相乘的容积直到两个指针相遇最后返回容积最大的值就行。
4.2 代码
class Solution {
public:int maxArea(vectorint height) {int left0,rightheight.size()-1,v0;int ret0;while(leftright){vmin(height[left],height[right])*(right-left);retmax(ret,v);if(height[left]height[right])left;else right--;}return ret;}
};5. LCR 179. 查找总价格为目标值的两个商品 5.1 分析
一、题目分析 只需要找到两个数他们的和等于目标值就可以但是题目中的数组是按照升序排列的暴力解法会超时就不考虑了。
二、算法原理 利用数组是有序的用双指针算法来算。 定义两个指针一个在左边一个在右边。 先计算两个指针指向值的和判断一下和目标值的大小会出现三种情况1.小于目标值那么左边指针就加加2.等于就返回这两个值3.大于目标值那么右边指针就减减。
5.2 代码
class Solution {
public:vectorint twoSum(vectorint price, int target) {int left0,rightprice.size()-1,sum0;while(leftright){sumprice[left]price[right];if(sumtarget)left;else if(sumtarget)right--;else return{price[left],price[right]};}return {-1,-1};}
};6. 15. 三数之和 6.1 分析
一、题目分析 题目要求返回三元数组和为1的三个不同的数而且要求去重来看一下例1 它里面有[-1,0,1]、[0,1,-1]、[-1,2,-1]但是第一组和第二组的元素是相同的就只能返回一个。 为了避免去重可以先给数组排个序。
二、算法原理 排序之后数据是有序的这里就用双指针算法。 这里是三个数的和可以先固定一个数a仅想要保证这个a是小于0就行在后面等于0相加的值不可能等于0然后在该数后面的区间内利用双指针算法快速找到两个数的和者两个数的和是a的相反数这样这三个数相加的时候值就为0。 这里还有可能不止一种情况所以不要漏掉在找到一种情况时候左边指针和右边指针继续缩小区间找直到两个指针相同。 那么怎么去重已经是有序的数组那么连续相同值的情况就不考虑了就是在左边指针和右边指针已经找到值就跳过重复的值。当使用完重复的元素时候固定值也得跳过重复值。还得避免越界的情况。
6.2 代码
class Solution {
public:vectorvectorint threeSum(vectorint nums) {sort(nums.begin(),nums.end());vectorvectorint ret;int nnums.size();for(int i0;in;){if(nums[i]0)break;int lefti1,rightn-1,target-nums[i];while(leftright){int sumnums[left]nums[right];if(sumtarget) left;else if(sumtarget)right--;else{ret.push_back({nums[i],nums[left],nums[right]});left;right--;while(leftrightnums[left]nums[left-1])left;while(leftrightnums[right]nums[right1])right--;}}i;while(innums[i]nums[i-1])i;}return ret;}
};有问题请指出大家一起进步
