优秀手机网站,网页设计流程图绘制,网站备案管理系统网站,带dede后台的整套网站源码 怎么进入dede后台目录 前言#xff1a;
双指针介绍
对撞指针
快慢指针
题目练习
1.移动零
2.复写零
3.快乐数
4.盛水最多的容器
5.有效三角形的个数
6.和为s的两个数
7.三数之和
8.四数之和 前言#xff1a;
此章节介绍一些算法#xff0c;主要从leetcode上的题来讲解#xff…目录 前言
双指针介绍
对撞指针
快慢指针
题目练习
1.移动零
2.复写零
3.快乐数
4.盛水最多的容器
5.有效三角形的个数
6.和为s的两个数
7.三数之和
8.四数之和 前言
此章节介绍一些算法主要从leetcode上的题来讲解讲解内容为做题思路附加代码。
欢迎与我大家一起学习共同进步沉淀passion
双指针介绍
双指针的常见形式有两种对撞指针快慢指针。
对撞指针
对撞指针也称为左右指针一个在最左边一个在最右边逐渐往中间逼近。对撞指针的终止条件一般是两个指针相遇或者是错开也有可能是找到了结果直接跳出循环。 left right 两个指针指向同⼀个位置 left right 两个指针错开
快慢指针
其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。这种方法对于处理环形链表或数组非常有用。其实不单单是环形链表或者是数组如果我们要研究的问题出现循环往复的情况时均可考虑使用快慢指针的思想。快慢指针的实现方式有很多种最常用的⼀种就是
• 在⼀次循环中每次让慢的指针向后移动⼀位而快的指针往后移动两位实现⼀快⼀慢。
题目练习
1.移动零
leetcode题目链接 给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。 请注意 必须在不复制数组的情况下原地对数组进行操作。 示例 1:输入: nums [0,1,0,3,12] 输出: [1,3,12,0,0] 示例 2:输入: nums [0] 输出: [0] 解法快排的思想数组划分区间 - 数组分两块 算法思路 cur 从前往后遍历的过程中: 1、遇到0 cur; 2、遇到非0元素 swap(dest1,cur) destcur; class Solution {
public:void moveZeroes(vectorint nums) {for(int cur 0, dest -1; cur nums.size(); cur)if(nums[cur]) // 处理⾮零元素swap(nums[dest], nums[cur]);}
};
2.复写零
leetcode题目链接 给你一个长度固定的整数数组 arr 请你将该数组中出现的每个零都复写一遍并将其余的元素向右平移。 注意请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改不要从函数返回任何东西。 示例 1输入arr [1,0,2,3,0,4,5,0] 输出[1,0,0,2,3,0,0,4] 解释调用函数后输入的数组将被修改为[1,0,0,2,3,0,0,4] 示例 2输入arr [1,2,3] 输出[1,2,3] 解释调用函数后输入的数组将被修改为[1,2,3] 解法 先根据“异地”操作然后优化成双指针下的“就地”操作。异地就是再开辟一个数组cur遇到非0dest复制下来是0的话就复写两边。但是现在是要就地操作cur和dest都放在同一个数组如果从前往后直接复写的话复写会覆盖后面的元素。所以考虑从后往前操作。 1、先找到最后一个”复写“的数 双指针算法 cur 0, dest -1 1.先判断cur的位置的值 2.决定dest向后移动一步或者两步 3.判断一下dest是否已经到结束为止 4.cur 5.处理边界情况[ 1,0,2,3,0,4] n-1 0 cur-- dest - 2 2、”从后向前“完成复写操作 代码
class Solution {
public:void duplicateZeros(vectorint arr) {int n arr.size(), cur 0, dest -1;//找到最后一个复写元素while (cur n){if (arr[cur]) dest;else dest 2;if (dest n - 1) break;cur;}//2.处理边界情况if (dest n){arr[n - 1] 0;cur--;dest - 2;}//3.从后往前完成复写操作while (cur 0){if (arr[cur]) arr[dest--] arr[cur--];else{arr[dest--] 0;arr[dest--] 0;cur--;}}}
};
3.快乐数
leetcode题目链接 编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」 定义为 对于一个正整数每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1也可能是 无限循环 但始终变不到 1。如果这个过程 结果为 1那么这个数就是快乐数。 如果 n 是 快乐数 就返回 true 不是则返回 false 。 示例 1输入n 19 输出true 解释 12 92 82 82 22 68 62 82 100 12 02 02 1 示例 2输入n 2 输出false 示例1的解释就是每位数的平方相加最后等于1 示例2则是 2 - 4 - 16 - 37 - 58 - 89 - 145 - 42 - 20 - 4 最后会变成这些数其中的一位跟链表中的环形链表相似我们则可以把它抽象成环形链表相遇的问题当相遇的时候bool值不是1则不是快乐数。是1则是快乐数。 class Solution
{
public:int bitSum(int n) // 返回 n 这个数每⼀位上的平⽅和{int sum 0;while (n){int t n % 10;sum t * t;n / 10;}return sum;}bool isHappy(int n){int slow n, fast bitSum(n);while (slow ! fast){slow bitSum(slow);fast bitSum(bitSum(fast));}return slow 1;}
};
4.盛水最多的容器
leetcode题目链接 给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明你不能倾斜容器。 示例 1输入[1,8,6,2,5,4,8,3,7] 输出49 解释图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下容器能够容纳水表示为蓝色部分的最大值为 49。 示例 2输入height [1,1] 输出1 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;}
};
5.有效三角形的个数
leetcode题目链接 给定一个包含非负整数的数组 nums 返回其中可以组成三角形三条边的三元组个数。 示例 1:输入: nums [2,2,3,4] 输出: 3 解释:有效的组合是: 2,3,4 (使用第一个 2) 2,3,4 (使用第二个 2) 2,2,3 示例 2:输入: nums [4,2,3,4] 输出: 4 class Solution {
public:int triangleNumber(vectorint nums) {sort(nums.begin(), nums.end());int ret 0;//记录有多少个三角形int n nums.size();for (int i n - 1; i 2; i--) {int left 0;int right i - 1;while (left right) {if (nums[left] nums[right] nums[i]){ret right - left;right--;}else left;}}return ret;}
};
6.和为s的两个数
leetcode题目链接 购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况返回任一结果即可。 示例 1输入price [3, 9, 12, 15], target 18 输出[3,15] 或者 [15,3] 示例 2输入price [8, 21, 27, 34, 52, 66], target 61 输出[27,34] 或者 [34,27] 解法思路 首先肯定想的就是暴力枚举双重循环。其实很多方法都是在暴力枚举上进行优化的。此题一样可以优化。 观察题目可知要得出 target 那么在两数相加(sum)时就得有三种判断 target sum ---- sum target sum ---- sum-- target sum ---- return{leftright} 我们顺着这个思路来既然是两数使用双指针对撞指针一个在最左边一个在最右边如果两个指针发生了对撞那么就证明这个数组中是没有答案的。 class Solution {
public:vectorint twoSum(vectorint price, int target) {int n price.size();int left 0, right n -1;while(leftright){int sum price[left] price[right];if (sum target){return {price[left],price[right]};}else if(sum target){right--;}else{left;}}return {0,0};}
};
7.三数之和
leetcode题目链接 给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。 注意答案中不可以包含重复的三元组。 示例 1输入nums [-1,0,1,2,-1,-4] 输出[[-1,-1,2],[-1,0,1]] 解释 nums[0] nums[1] nums[2] (-1) 0 1 0 。 nums[1] nums[2] nums[4] 0 1 (-1) 0 。 nums[0] nums[3] nums[4] (-1) 2 (-1) 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意输出的顺序和三元组的顺序并不重要。 示例 2输入nums [0,1,1] 输出[] 解释唯一可能的三元组和不为 0 。 示例 3输入nums [0,0,0] 输出[[0,0,0]] 解释唯一可能的三元组和为 0 。 想法思路 其实做这个题目可以在上一个题目的基础下来建立思路这是一个三数之和相加为0上一题是两数相加为0。那么多出来的一个数则就可以看成是另外两个数之和的相反数。两数相加为sum还有一个数则为-sum如果这两个条件成立的情况下那么就是三数之和的答案但是还需要去重这题难在去重。 解法步骤 1.暴力枚举排序枚举利用容器去重O^3) 2.优化排序双指针 排序 固定一个数sum 利用双指针left和right在后面区间找到相加 -sum的两个数 3.处理细节问题 去重利用set但是这里利用其他方法考虑越界问题 1.left 和 right 跳过相同的元素 2.sum也要跳过相同的元素 不漏 找到一种结果后不要停继续缩小区间 解法思路
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint ret;//存储三数之和等于0的三个数组二维数组//排序sort(nums.begin(), nums.end());//用双指针int n nums.size();for (int i 0; i n;){if (nums[i] 0) break;int left i 1, right n - 1, target -nums[i]; //确定基数targetwhile (left right){int sum nums[left] nums[right];if (sum target) right--;//while() 去重再添加这一步也可以else if (sum target) left;//while() 去重再添加这一步也可以else {ret.push_back({ nums[i],nums[left],nums[right] });left, right--;//这连个while只能写在这个if里面因为其他两个条件分别对left/right 单独进行操作而这里是对两个都进行了操作如果放在外面的话可能导致越界访问的情况。while (left right nums[left] nums[left - 1]) left;//去重leftwhile (left right nums[right] nums[right 1])right--;//去重right}}//去重基数nums[i]i;while (i n nums[i] nums[i - 1]) i;}return ret;}
};
8.四数之和
leetcode题目链接 给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复 0 a, b, c, d na、b、c 和 d 互不相同nums[a] nums[b] nums[c] nums[d] target 你可以按 任意顺序 返回答案 。 示例 1输入nums [1,0,-1,0,-2,2], target 0 输出[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] 示例 2输入nums [2,2,2,2,2], target 8 输出[[2,2,2,2]] 这题的解法和三数之和的解法一样只是多定义了一个基数而已。没有本质上的区别。 class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint ret;sort(nums.begin(),nums.end());int n nums.size();//定第一个基数for (int i 0; i n;){for (int j i 1; j n;)//第二个基数{int left j 1, right n - 1;long long aim (long long)target - nums[i] - nums[j];while (left right){int sum nums[left] nums[right];if (sum aim) right--;//while() 去重else if (sum aim) left;//wihle() 去重else{ret.push_back({nums[i],nums[j],nums[left],nums[right]});left, right--;//去重双指针只能在sum aim 里这两步才能写不然没有进来的话if/else if都只是对left/right进行了操作另外一个可能导致越界访问while (left right nums[left] nums[left - 1]) left;while (left right nums[right] nums[ right 1]) right--;}}//去重第二个数j;while (j n nums[j] nums[j - 1]) j;}//去重第一个数i;while (i n nums[i] nums[i - 1]) i;}return ret;}
};
