网站开发的项目开发计划,最大的高仿手表网站,阿里巴巴网站更新怎么做,为什么要建微网站目录
双指针
左右指针(对撞指针)
快慢指针
移动零
双指针解题
复写零
暴力解题
双指针解题(快慢指针)
快乐数
双指针解题(快慢指针)
盛最多水的容器
暴力解题(会超时)
双指针解题(左右指针)
有效三角形的个数
暴力解题
双指针解题(左右指针) 双指针
常见的双指…目录
双指针
左右指针(对撞指针)
快慢指针
移动零
双指针解题
复写零
暴力解题
双指针解题(快慢指针)
快乐数
双指针解题(快慢指针)
盛最多水的容器
暴力解题(会超时)
双指针解题(左右指针)
有效三角形的个数
暴力解题
双指针解题(左右指针) 双指针
常见的双指针有两种形式一种是左右指针(对撞指针)一种是快慢指针 左右指针(对撞指针)
·左右指针从顺序结构的两端向中间移动。一个指针从最左端开始另一个从最右端开始然后逐渐往中间逼近
·左右指针的终止条件无非就只有两种情况(也可能在循环内部找到结果直接跳出循环)
·leftright(两个指针指向同一个位置)
·leftright(两个指针错开) 快慢指针
又称为龟兔赛跑算法其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动
这种方法对于处理环形链表或数组非常有用
其实不单单是环形链表或者是数组如果我们要研究的问题出现循环往复的情况时均可考虑使用快慢指针的思想
快慢指针的实现方式有很多种最常用的一种就是
·在一次循环中每次让慢的指针向后移动一位而快的指针往后移动两位实现一快一慢 【数组分两块】是非常常见的一种提醒主要就是根据一种划分方式将数组的内容分成左右两部分。这种类型的题一般就是使用双指针来解决
移动零
题目链接283. 移动零 - 力扣LeetCode 题目描述 给定⼀个数组 nums 编写⼀个函数将所有 0 移动到数组的末尾同时保持⾮零元素的相对顺 序。 请注意 必须在不复制数组的情况下原地对数组进⾏操作。 ⽰例 1: 输⼊: nums [0,1,0,3,12] 输出: [1,3,12,0,0] ⽰例 2: 输⼊: nums [0] 输出: [0] 双指针解题
解题思路(快排的思想数组划分区间--数组分成两块)
使用双指针。用一个cur指针来遍历整个数组另一个dest指针用来记录非零数序列的最后一个位置。然后根据cur指针遍历到的数进行分类处理。 大致流程为
1.初始化cur0dest-1。
注意我们这里初始化dest-1。这里不将dest设置为0的原因是如若将dest设置为0dest的指向便不再是非零数序列的最后一个位置了。(因为下标为0的话也占一个元素啊) 2.令cur遍历数组遍历到的元素有两种情况
·遇到的元素不是0dest。并交换cur和dest位置处的元素之后让cur。
这里dest有两个含义首先是因为cur指针找到一个非0数所以dest后移一位表示非0数的序列1。其次是因为dest之后指向的元素就是0元素(因为非0元素区间末尾的后一个元素就是0)。
·遇到的元素是0cur直接。 解题代码
class Solution {public void moveZeroes(int[] nums) {for(int cur0,dest-1;curnums.length;cur){if(nums[cur]!0){dest;//交换cur和dest位置处的元素int tempnums[cur];nums[cur]nums[dest];nums[dest]temp;}}}
} 我们上述代码是初始化dest -1。让dest指向非0序列的最后一个位置。
现在我们初始化dest0。看看代码有哪里不同
class Solution {public void moveZeroes(int[] nums) {for(int cur0,dest0;curnums.length;cur){if(nums[cur]!0){int tempnums[cur];nums[cur]nums[dest];nums[dest]temp;dest;}}}
}
我们发现表面来看不过是dest 一个放前面和一个后面。但我们要清楚里面的门道。将dest初始为0的则令dest指向非0序列末尾的后一个元素。 复写零
题目链接1089. 复写零 - 力扣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] 暴力解题
思路让指针L1遍历数组一旦遇到元素0便从此处开始一直到数组末尾每个元素后移一位。由于元素后移一位实现复写0所以指针L1需要格外进行一次跳过复写的0不然会导致后续元素都为0.
注意如果我们只用一个指针L1无法【从前向后】实现所有元素后移一位。因为如果【从前向后】实现元素后移的话会把未移动的元素给覆盖掉。所以我们这里【从后向前】实现元素后移 解题代码
class Solution {public void duplicateZeros(int[] arr) {int l10;int lengtharr.length;for(;l1length;l1){if(arr[l1]0){for(int jlength-1;jl1;j--){arr[j]arr[j-1];}l1;}}}
} 双指针解题(快慢指针)
解题思路
由于复写0会使元素1然而数组长度不变数组便从末尾开始舍弃元素。所以我们只需找到 新复写数组的最后一个元素(即旧数组中最后一个复写的数)。然后进行复写
核心步骤
·先找到最后一个复写的数
·然后【从后向前】进行复写
注意由于【从前向后】进行原地复写操作会导致没有复写的数【被覆盖掉】。所以这里选择【从后往前】进行复写 大致流程为
a.初始化两个指针cur0dest-1
b.找到最后一个复写的数
·当cur数组长度执行下面循环
1.若cur位置处的元素为0dest后移两位否则后移一位。注意这里的dest指针可以看作记录元素个数(每移动一步相等于记录一个元素)。(保证移动步数元素个数即可但当最后一个复写的数为0时移动步数会多1步dest指针会越界)
2.判断dest指针此时是否已经到结束位置(数组末尾亦或者是越界)如果到了便终止循环
3.如果没有结束cur继续循环判断 c.判断dest是否越界(最后一个复写的数是否为0)如果越界便执行下面三步
将数组最后一个元素的值修改成0cur指针向前移动一步(跳过最后一个复写的数(0)dest指针向前移动两步(指向倒数第二个数--跳过数组最后一个元素)
注意我们要知道数组最后一个元素和最后一个复写的数这两个名词并不等同 d.从cur位置开始往前遍历原数组还原出复写后的数组 解题代码
class Solution {public void duplicateZeros(int[] arr) {int cur0;int dest-1;int narr.length;//找到最后一个复写的数while(curn){if(arr[cur]!0){dest;}else{dest2;}if(destn-1)break;//结束条件cur;}//处理越界情况--即最后一个复写的数为0if(destn){arr[n-1]0;cur--;dest-2;}//从后往前还原出复写后的数组for(;cur0;cur--){if(arr[cur]!0){arr[dest--]arr[cur];}else{arr[dest--]0;arr[dest--]0;}}}
} 快乐数
题目链接202. 快乐数 - 力扣LeetCode
题目描述 编写⼀个算法来判断⼀个数 n 是不是快乐数。 「快乐数」 定义为 ◦ 对于⼀个正整数每⼀次将该数替换为它每个位置上的数字的平⽅和。 ◦ 然后重复这个过程直到这个数变为 1也可能是⽆限循环但始终变不到 1 。 ◦ 如果这个过程 结果为 1 那么这个数就是快乐数。 ◦ 如果 n 是 快乐数 就返回 true 不是则返回 false 。 ⽰例 1 输⼊ n 19 输出 true 解释 19 - 1 * 1 9 * 9 82 82 - 8 * 8 2 * 2 68 68 - 6 * 6 8 * 8 100 100 - 1 * 1 0 * 0 0 * 0 1 ⽰例 2 输⼊ n 2 输出 false 解释这⾥省去计算过程只列出转换后的数
2 - 4 - 16 - 37 - 58 - 89 - 145 - 42 - 20 - 4 - 16
往后就不必再计算了因为出现了重复的数字最后结果肯定不会是 1 题目解析
我们将 【对于一个正整数每一次将该数替换为它每个位置上的数字的平方和】这一操作用 function方法来解决。 重点是题目定义中的【无限循环】。
意思是
1.如果这个数n不是快乐数就会【无限循环】但始终变不到1。
2.然而如果这个数是快乐数即最终会变到1此时1便会【无限循环】。 所以无论这个数n是不是快乐数都会【无限循环】
所以当我们不断循环function方法计算一定会【无限循环】【无限循环】的方式有两种
情况1在旧的数据中【无限循环】但始终变不到1。 情况2一直在1中进行【无限循环】 【无限循环】原理解释
由于int最大值2^31-12147483647哪怕是9999999999这样大的数据各个位置上的数字的平方和为810。所以在int范围内的数n其各个位置上的数字的平方和一定在[1,810]区间内。极限情况下一个数变化811次之后必然会形成一个循环。因此使用【快慢指针】来解决本题 双指针解题(快慢指针)
解题思路
当我们重复使用function方法时数据会陷入【无限循环】中。
【快慢指针】的一个特性就是在一个圆圈中快指针总是会追上慢指针的。也就是说它们总会相遇在一个位置上。如果这个位置是1那么这个数一定是快乐数否则这个数便不是快乐数
重点相遇位置以及该数是不是1 大致流程为
写一个function方法用来求数n每个位置上的数字的平方和让slow每次走一步fast每次走两步判断相遇位置处的元素是否为1。如果是1输出true否则输出false 题目代码
class Solution {public static boolean isHappy(int n) {int slownint fastfunction(n);//注意这里初始化fastslow是因为我们要求它俩相遇的位置//当fast指针追上slow指针并且都为1时返回truewhile(slow!fast){slowfunction(slow);//走一步fastfunction(function(fast));//走两步}return slow1;}private static int function(int n) {int sum0;while(n!0){int gn%10;sumg*g;n/10;}return sum;}
} 盛最多水的容器
题目链接11. 盛最多水的容器 - 力扣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 暴力解题(会超时)
思路一个一个进行遍历找出其中容积(V)最大的值
容积公式长*宽
设两指针ij初始化i0ji1我们知道两指针之间的距离宽度j-i。由于容器的高度由两板中的短板决定所以容积公式为v(j-i)*min(height[i],height[j]) 解题代码
class Solution {public int maxArea(int[] height) {int nheight.length;int v0;//v(j-i)*min(height[i],height[j])int sum0;for(int i0;in;i){for(int ji1;jn;j){v(j-i)*Math.min(height[i],height[j]);if(vsum){sumv;}}}return sum;}
} 双指针解题(左右指针)
解题思路
设两个指针leftright分别指向容器的左右两个端点。
此时容器的容积v(right-left)*min(height[left],height[right])
容器的【左边界】为height[left],【右边界】为height[right] 我们先假设【左边界】小于【右边界】
如果我们固定一个边界改变另一个边界容积v会有以下变化形式 1.容器的宽度一定变小 2.由于【左边界】小所以决定了容器的高度。如果改变【左边界】容器的高度便不确定(相较于原先的【左边界】)但是一定不会超过【右边界】的高度因此容器的容积v可能会增大 3.如果改变右边界无论【右边界】移动到哪里新容器的高度一定不会超过【左边界】也就是容器的高小于等于【左边界】但是容器的宽度随着【右边界】的移动而减少因此容器的容积v一定会变小 我们这里可以把【左边界】替换为较小值【右边界】替换为较大值。
根据上述假设移动【右边界】会导致容积v变小所以我们这里只移动【较小值】并比较容积v便能得到最大值 解题代码
class Solution {public static int maxArea(int[] height) {int left0;int rightheight.length-1;int v0;int max0;while(leftright){v(right-left)*Math.min(height[left],height[right]);if(vmax){maxv;}if(height[left]height[right]) {left;}else{right--;}}return max;}
} 有效三角形的个数
题目链接611. 有效三角形的个数 - 力扣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 解释 4,2,3 4,2,4 4,3,4 2,3,4 暴力解题
解题思路三层for循环枚举出所有的三元组
构成三角形的条件需要满足任意两边之和大于第三边。但是实际上只需让较小的两条边之和大于第三边即可。因此我们这里先排序再枚举。 解题代码
lass Solution {public static int triangleNumber(int[] nums) {Arrays.sort(nums);int nnums.length;int count0;for(int i0;in;i){for(int ji1;jn;j){for(int tj1;tn;t){if(nums[i]nums[j]nums[t]){count;}}}}return count;}
} 双指针解题(左右指针)
由于我们左右指针只能表示两个元素但为了找出这个三元组可以尝试固定一条边这样只需要找到一个二元组即可。 解题思路
1.先将数组排序
2.我们这里选择固定一个【最长边】然后在比【最长边】小的有序数组中找出一个二元组使这个二元组之和大于这个【最长边】。由于数组是有序的我们这里采用【左右指针】。 假设最长边在下标i处区间[left,right]是i位置左边的区间--也就是比i小的区间 如果nums[left]nums[right]nums[i] ·说明[left,right-1](因为left处的元素是最小的)区间上的所有元素都可以和nums[right]构成一个二元组使其之和大于nums[i] ·满足条件的有(right-1-left)1right-left种 ·此时right处的元素的所有情况相当于全部考虑完毕right--进入下一轮判断 如果nums[left]nums[right]nums[i] ·说明left处的元素是不能和[left1,right](因为right处的元素已经是最大的了)区间上的元素构成一个二元组使其之和大于nums[i] ·left处的元素舍去left 解题代码
class Solution {public static int triangleNumber(int[] nums) {Arrays.sort(nums);int nnums.length;int count0;//左右指针固定一个最长边(i)---下标[2,n-1]for(int in-1;i2;i--){int left0;int righti-1;while(leftright){if(nums[left]nums[right]nums[i]){//[left,right-1]区间上的元素 和nums[right]的和都大于nums[i]countright-left;//注意这里不用count因为right--;//选择较小的数 判断是否大于固定的最长边}else{left;}}}return count;}
}
