中铁雄安建设有限公司网站,镇江网页设计工作室,asp.net免费网站,如何做移动端网站移动零问题
https://leetcode.cn/problems/move-zeroes/submissions/
1.题目解析
必须在原数组进行修改#xff0c;不可以新建一个数组
非零元素相对顺序不变
2.算法原理
【数组划分】【数组分块】
这一类题会给我们一个数组#xff0c;让我们划分区间#xff0c;比如…
移动零问题
https://leetcode.cn/problems/move-zeroes/submissions/
1.题目解析
必须在原数组进行修改不可以新建一个数组
非零元素相对顺序不变
2.算法原理
【数组划分】【数组分块】
这一类题会给我们一个数组让我们划分区间比如说这题最后会划分为两个区间前一段是非零元素后一段是零一般我们只要看到这样的特性脑海里就应该想到用双指针算法来解决利用数组下标充当指针
定义两个指针 两个指针的作用
cur 从左往后扫描数组遍历数组。
dest : 已处理的区间内非零元素的最后一个位置
如何做到 cur从前往后遍历的过程中
1.遇到0元素cur
2.遇到非零元素
交换
相关知识快速排序
双指针的思想其实就是快排的核心思想 class Solution {
public:void moveZeroes(vectorint nums) {for(int cur0,dest-1;curnums.size();cur){if(nums[cur]){swap(nums[dest],nums[cur]);}}}
};复写零问题
https://leetcode.cn/problems/duplicate-zeros/
1.题目解析
长度固定不能越界
在原始数组进行操作
2.算法原理 解法双指针算法 先根据异地操作然后优化成双指针下的“就地操作” 根据异地操作得出先模拟一遍复写的操作然后从后向前进行覆盖从前往后会发生覆盖多的值。 总结
1.先找到最后一个复写的数
用双指针模拟一遍 cur0dest-1
先判断cur位置的值决定dest向后移动几步判断dest是否已经到了最后的位置cur
2.从后向前进行操作
特例数组越界 所以要加上一个步骤处理越界
3.解题代码
class Solution {
public:void duplicateZeros(vectorint arr) {int cur0,dest-1,narr.size();//先模拟while(curn){if(arr[cur]) dest;else dest2;if(destn-1) break;cur;}//判断边界if(destn){arr[n-1]0;dest-2;cur--;}//从后向前while(cur0){if(arr[cur]0){arr[dest--]0;arr[dest--]0;cur--;}else arr[dest--]arr[cur--];}}
};快乐数问题
https://leetcode.cn/problems/happy-number/
1.题目解析
一直替换
分为两种情况
变成一
无限循环 两种情况
2.算法原理 有没有发现一直平方到最后一定会成环
解法快慢双指针
1.定义快慢双指针
2.慢指针每次向后移动一步快指针每次走两步
3.判断相遇的时候的值即可 双指针只是一种思想不需要一定定义双指针在这个题中快指针就是平方两次慢指针平方一次 为什么会一定会重复
证明方法
鸽巢原理抽屉原理
n个巢穴 n1个鸽子--至少有一个巢穴里面的鸽子数量大于1 3.解题代码
class Solution {
public:int Sum(int n){int sum0;while(n){int gn%10;sumg*g;n/10;}return sum;}bool isHappy(int n) {int slown,fastSum(n);while(slow!fast){slowSum(slow);fastSum(Sum(fast));}return slow1;}
};盛水最多的容器
https://leetcode.cn/problems/container-with-most-water/
1.题目解析
只能水平放置也就是找最大的矩形
2.算法原理
解法一暴力枚举双重循环
优点想法简单
缺点时间复杂度过高 解法二头尾双指针
vh*w 宽度一直在减小而高度有两种情况变大或变小在宽度一直在变小的情况下我们高度必须选择更高的
3.解题代码 class Solution {
public:int maxArea(vectorint height) {int left0,rightheight.size()-1;int v-1;while(leftright){int tvmin(height[left],height[right])*(right-left);vmax(tv,v);if(height[left]height[right]) right--;else left;}return v;}
};和为s的两个数字问题 1.题目解析
有序数组
随意输出一对
2.算法原理
解法一暴力枚举 双重循环 n^2复杂度 解法二利用单调性使用双指针算法解决问题
首尾相加
判断数值如果大于目标值right--反之left因为数组是有序的 3.解题代码
vectorint twosum(vector nums,int t)
{int left 0,rightnums.size()-1;while(leftright){int sumnums[left]nums[right];if(sumt) right--;else if(sumt) left;else return {num[left],nums[right]};}//照顾编译器return {-1,-1};
}有效三角形个数
https://leetcode.cn/problems/valid-triangle-number/
1.题目解析
相同的不算一个
2.讲解算法原理
补充数学知识给我们三个数判断是否能构成三角形
我们仅需要一个公式就能判断是否能构成三角形
如果我们已经知道三个数的大小顺序只需要abcc是最大的数 优化先对整个数组排序 解法一暴力枚举
for(i0;in;i)
for(ji1;jn;j)for(kj1;kn;k)check(i,j,k)解法二利用单调性使用双指针算法来解决问题
①先固定最大的数
②在最大的数的左区间里使用双指针算法快速统计 3.解题代码 class Solution {
public:int triangleNumber(vectorint nums) {int nnums.size();int ret0;sort(nums.begin(),nums.end());for(int in-1;i2;i--){int left0,righti-1;while(leftright){if(nums[left]nums[right]nums[i]){retright-left;right--;}else{left;}}}return ret;}
};三数之和问题
https://leetcode.cn/problems/3sum/ 1.题目解析
三个数的下标不同
答案不可重复去重
有可能没有答案
2.算法原理
解法一先排序暴力枚举利用set去重o(n^3)
解法二排序双指针 找到右边区间两数之和为左边数字的相反即可
1.排序
2.固定一个数a
3.在该数后边的区间利用双指针的算法快速找到和为-a的两个数
处理细节问题
1.去重
找到一种结果之后left和right指针要跳过重复元素。
当使用完一次双指针算法之后i也要跳过重复元素避免越界
2.不漏
找到一种结果后不要“停”缩小区间继续寻找
3。解题代码
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,t-nums[i];while(leftright){int sumnums[left]nums[right];if(sumt) left;else if(sumt) 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;}
};四数之和
https://leetcode.cn/problems/4sum/
1.题目解析
三数之和的进阶版本基本算法原理和三数之和大差不差
2.算法原理
解法一排序暴力枚举
四个循环绝对超时
解法二排序双指针
1.依次固定一个数i
2.在i后面的区间内利用三数之和找到三个数让他们三个的和等于target-i
{
1.依次固定一个j
2.在j后边的区间里利用“双指针找到两个数使得这两个数之和等于target-i-j”
}
处理细节问题
不重不漏
3.解题代码
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint ret;//1.排序sort(nums.begin(),nums.end());//2.利用双指针解决问题int nnums.size();for(int i0;in;){//利用三数之和for(int ji1;jn;){int leftj1,rightn-1;long long aim(long long)target-nums[i]-nums[j];while(leftright){int sumnums[left]nums[right];if(sumaim) left;else if(sumaim) right--;else{ret.push_back({nums[i],nums[j],nums[left],nums[right--]});//去重1while(leftrightnums[left]nums[left-1]) left;while(leftrightnums[right]nums[right1]) right--;}}//去重2j;while(jnnums[j]nums[j-1]) j; }//去重3i;while(innums[i]nums[i-1]) i;} return ret;}
};觉得有帮助的惯用老爷麻烦点点关注
