甜品网站建设策划书,2019年的阜南县建设修路网站,什么叫门户网站,室内设计有哪些网站文章目录 前言什么是双指针算法1.移动零1.1 题目要求1.2 做题思路1.3 Java代码实现 2.复写零2.1 题目要求2.2 做题思路2.3 Java代码实现 3.快乐数3.1 题目要求3.2 做题思路3.3 Java代码实现 4.盛最多水的容器4.1 题目要求4.2 做题思路4.3 Java代码实现 5.有效三角形的个数5.1 题… 文章目录 前言什么是双指针算法1.移动零1.1 题目要求1.2 做题思路1.3 Java代码实现 2.复写零2.1 题目要求2.2 做题思路2.3 Java代码实现 3.快乐数3.1 题目要求3.2 做题思路3.3 Java代码实现 4.盛最多水的容器4.1 题目要求4.2 做题思路4.3 Java代码实现 5.有效三角形的个数5.1 题目要求5.2 做题思路5.3 Java代码实现 6.和为S的两个数字6.1 题目要求6.2 做题思路6.3 Java代码实现 7.三数之和7.1 题目要求7.2 做题思路7.3 Java代码实现 8.四数之和8.1 题目要求8.2 做题思路8.3 Java代码实现 前言
朋友们大家好啊从今天开始我将陆续为大家更新关于算法方面的文章如果大家对于算法感兴趣的话欢迎大家订阅我的算法专栏。
什么是双指针算法
双指针算法Two Pointers Algorithm是一种常用的算法技巧通常用于数组、链表或其他线性数据结构中的问题。该算法使用两个指针在数据结构上进行迭代、搜索或比较以解决特定的问题。
在双指针算法中通常使用两个指针分别称为快指针和慢指针。快指针和慢指针起始位置通常相同然后根据问题的要求以不同的步长移动指针。快指针可能会每次移动多个位置而慢指针则每次只移动一个位置。
双指针算法有几种常见的应用方式 对撞指针Two Pointers Approach快指针从数组的首部开始慢指针从数组的尾部开始两者向中间移动直到它们相遇或交叉。这种方法通常用于有序数组中的搜索、求和等问题。 快慢指针Fast and Slow Pointers快指针和慢指针以不同的速度遍历链表。这种方法通常用于解决链表中的环检测、找到链表中点、链表的反转等问题。 滑动窗口Sliding Window使用两个指针在数组或字符串上定义一个固定大小的窗口然后根据问题要求移动窗口的起始位置或结束位置。这种方法通常用于字符串或数组中的子串或子数组问题。
双指针算法的优点在于它的时间复杂度通常较低并且在遍历数据时只需要常量级的额外空间。它可以有效地降低问题的时间复杂度并且常常用于解决一些数组、链表相关的问题。
1.移动零
https://leetcode.cn/problems/move-zeroes/
1.1 题目要求
给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。
请注意 必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums [0,1,0,3,12] 输出: [1,3,12,0,0]
示例 2:
输入: nums [0] 输出: [0]
class Solution {public void moveZeroes(int[] nums) {}
}1.2 做题思路
这个题目的目的就是将数组中的所有零给移动到非0数字的右边部分而我们使用双指针就刚好可以将一个数组分为三部分第一部分是非零部分第二部分是数字0第三部分是待移动的部分。 而这三个部分我们使用两个指针 slow 和 fast 来维护当 fast 所指的数字不为 0 时就与 slow 所指的数字进行交换。这样就可以保证 slow 左边是已经移动之后的非 0 数字slow 与 fast 之间是移动之后的 0 数字fast 右边是待移动的部分。 1.3 Java代码实现
class Solution {public void moveZeroes(int[] nums) {int slow -1;int fast 0;int n nums.length;while(fast n) {if(nums[fast] ! 0) {int tmp nums[slow];nums[slow] nums[fast];nums[fast] tmp;}fast;}}
}2.复写零
https://leetcode.cn/problems/duplicate-zeros/
2.1 题目要求
给你一个长度固定的整数数组 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]
class Solution {public void duplicateZeros(int[] arr) {}
}2.2 做题思路
很多人拿到这个题首先想的是从前往后使用双指针当遇到0的时候将0写两次但是如果这样的话会将后面的数字给覆盖这就会显得很麻烦。我们不妨换个思路可以先找到复写之后数组的最后一个数字然后从后往前进行数据的写入当遇到0就写两次非0就写一次。
所以做这个题目大致分为两步1.找到复写之后数组的最后一个数字 2.从后往前写入数据 2.3 Java代码实现
class Solution {public void duplicateZeros(int[] arr) {int slow 0;int fast -1;int n arr.length;//1.找到复写之后数组的最后一个数字while(fast n-1) {if(arr[slow] ! 0) fast;else fast 2;if(fast n-1) break;slow;}//2.调整边界//当fastn的时候说明slow所指的最后一个数字为0if(fast n) {arr[n-1] 0;fast n-2;slow--;}//3.从后往前写入数据while(slow 0) {if(arr[slow] ! 0) {arr[fast--] arr[slow--];}else {arr[fast--] 0;arr[fast--] 0;slow--;}}}
}3.快乐数
https://leetcode.cn/problems/happy-number/
3.1 题目要求
编写一个算法来判断一个数 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
class Solution {public boolean isHappy(int n) {}
}3.2 做题思路
要判断是否为快乐数我们需要知道当我们进行每位数的平方和这个操作的时候最终都会形成一个环。 既然都会形成环那么我们只需要使用快慢指针来找到这个环然后判断这个环是否为1如果是快乐数的话他会在1-1之间形成环而非快乐数就不一定了。
3.3 Java代码实现
class Solution {private int bitSum(int n) {int sum 0;while(n ! 0) {int tmp n % 10;sum tmp*tmp;n / 10;}return sum;}public boolean isHappy(int n) {int slow n;int fast bitSum(n); //这里先将快指针进行一次求和操作防止刚开始就相等了//slow每次进行一次操作fast一次进行两次操作while(slow ! fast) {slow bitSum(slow);fast bitSum(bitSum(fast));if(slow fast) break;}return slow 1;}
}4.盛最多水的容器
https://leetcode.cn/problems/container-with-most-water/
4.1 题目要求
给定一个长度为 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(int[] height) {}
}4.2 做题思路
容器的容量跟 xy 的乘积有关所以我们既需要考虑 x也需要考虑 y但是无法保证一上来 x 和 y 就是最大的我们只能保证 x 或者 y 其中一个是最大的然后再找 xy 最大的时候。所以这里我们先保证 x 是最大的left 指针指向最左边right 指针指向最右边接着再找 x*y 乘积最大。
容积这样计算 (right - left) * min(height[left],height[right])。设置一个变量来存放体积并不断更新这个变量保证这个变量存储的是容积最大的数据。left 和 right 的值也是需要不断改变的需要更换掉 left 和 right 所指向的数据较小的指针因为我们要找的是乘积最大的数据。
容器的宽度⼀定变⼩。由于左边界较⼩决定了⽔的⾼度。如果改变左边界新的⽔⾯⾼度不确定但是⼀定不会超过右边的柱⼦⾼度因此容器的容积可能会增⼤。如果改变右边界⽆论右边界移动到哪⾥新的⽔⾯的⾼度⼀定不会超过左边界也就是不会超过现在的⽔⾯⾼度但是由于容器的宽度减⼩因此容器的容积⼀定会变⼩的
4.3 Java代码实现
class Solution {public int maxArea(int[] height) {int n height.length;int left 0;int right n-1;int ret 0; //用来存储体积while(left right) {int v (right - left) * Math.min(height[left],height[right]);ret Math.max(v,ret);if(height[left] height[right]) left;else right--;}return ret;}
}5.有效三角形的个数
https://leetcode.cn/problems/valid-triangle-number/
5.1 题目要求
给定一个包含非负整数的数组 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(int[] nums) {}
}5.2 做题思路
说的有效的三角形大家应该都不陌生吧任意两边之和大于第三边但是我们真的需要两两组合都判断一遍吗其实并不是的只需要判断两个较短的边之和大于较长的那个边就可以了。
既然知道了只需要判断一次就可以判断是否是有效的三角形所以我们可以先对数组进行一个升序排序从数组的最后开始将它作为三角形的最长的边然后在前面的数组范围内left 指针指向前面部分的最左边right 指针指向最右边通过移动 left 和right 的位置来统计有效三角形的个数。如果 nums[left] nums[right} 最长的边那么从 left 开始到 right - 1 的边和 right、最长的边都可以组合成一个有效的三角形所以以该长度为最长边的三角形的个数为 right -left然后right–继续该操作直到left right如果 nums[left] nums[right} 最长的边就需要移动 left 的位置直到遇到 nums[left] nums[right} 最长的边 的位置再统计有效三角形的个数。 5.3 Java代码实现
class Solution {public int triangleNumber(int[] nums) {Arrays.sort(nums);int sum 0;for(int i nums.length-1; i 1; i--) {int left 0;int right i-1;while(left right) {if(nums[left] nums[right] nums[i]) {sum sum right - left;right--;}else {left;}}}return sum;}
}6.和为S的两个数字
https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/
6.1 题目要求
输入一个递增排序的数组和一个数字s在数组中查找两个数使得它们的和正好是s。如果有多对数字的和等于s则输出任意一对即可。
示例 1
输入nums [2,7,11,15], target 9 输出[2,7] 或者 [7,2] 示例 2
输入nums [10,26,30,31,47,60], target 40 输出[10,30] 或者 [30,10]
class Solution {public int[] twoSum(int[] nums, int target) {}
}6.2 做题思路
这个题目的思路跟上面的思路差不多。使用双指针left 指向数组的最左边也就是最小值right 指向数组的最右边最大值然后判断 nums[left] nums[right] 跟target 的关系如果 nums[left] nums[right] target 就调整 right 的值如果 nums[left] nums[right] target 就调整 left 的值如果相等就存下来。
6.3 Java代码实现
class Solution {public int[] twoSum(int[] nums, int target) {int left 0;int right nums.length-1;while(left right) {int sum nums[left] nums[right];if(sum target) {right--;}else if(sum target) {left;}else {return new int[]{nums[left],nums[right]};}}return new int[]{-1,-1};}
}7.三数之和
https://leetcode.cn/problems/3sum/
7.1 题目要求
给你一个整数数组 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 。
class Solution {public ListListInteger threeSum(int[] nums) {}
}7.2 做题思路
当直到了如何解决两数之和的问题之后求三数值和其实也很简单还是现将数组以升序的方式排序我们每次固定一个数字然后在剩下的数组中找到和为 target - nums[i] 的值但是真的有这么简单吗注意看题目答案中不可出现重复的三元组什么叫做重复的三元组看第一个示例它等于 target 的三个数有 (-1,0,1),(0,1,-1),(-1,2,-1) 但是最终输出的结果只有[[-1,-1,2],[-1,0,1]]所以这道题关键难在去重这个问题上那么我们应该如何去重呢当调整 left、right 和那个固定的数字的时候如果所指的数字等于前面的数字那么就跳过。 7.3 Java代码实现
class Solution {public ListListInteger threeSum(int[] nums) {ListListInteger list new ArrayList();Arrays.sort(nums);int n nums.length;int i 0;while(i n nums[i] 0) {int left i 1;int right n - 1;int target -nums[i];while(left right) {int sum nums[left] nums[right];if(sum target) {right--;}else if(sum target) {left;}else {ListInteger list1 new ArrayList();list1.add(nums[i]);list1.add(nums[left]);list1.add(nums[right]);list.add(list1);left;right--;//去重并且防止越界while(left right nums[left] nums[left-1]) left;while(left right nums[right] nums[right1]) right--;}}i;while(i n nums[i] 0 nums[i] nums[i-1]) i;}return list;}
}8.四数之和
https://leetcode.cn/problems/4sum/
8.1 题目要求
给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复
0 a, b, c, d n a、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 ListListInteger fourSum(int[] nums, int target) {}
}8.2 做题思路
这个求四数之和如果前面的两数之和和三数之和会做了这个题目也很简单我们只需要先固定一个数字然后在后面的数组内找到和为 target - nums[i] 的三个数就行了唯一需要注意的就是去重。那么这个题目我就不过多介绍了大家直接看代码就行了。
8.3 Java代码实现
class Solution {public ListListInteger fourSum(int[] nums, int target) {ListListInteger list new ArrayList();int i 0;int n nums.length;Arrays.sort(nums);while(i n) {int j i 1;long tmp1 target-nums[i];while(j n) {int slow j 1;int fast n-1;long tmp2 tmp1 - nums[j];while(slow fast) {int sum nums[slow] nums[fast];if(sum tmp2) {fast--;}else if(sum tmp2) {slow;}else {ListInteger list1 new ArrayList();list1.add(nums[i]);list1.add(nums[j]);list1.add(nums[slow]);list1.add(nums[fast]);list.add(list1);slow;fast--;while(slow fast nums[slow] nums[slow-1]) slow;while(slow fast nums[fast] nums[fast1]) fast--;}}j;while(j n nums[j] nums[j-1]) j;}i;while(i n nums[i] nums[i-1]) i;}return list;}
}
