上传的网站打不开 index.asp,企业宣传册免费模板网站,网站资源库建设报价,wap建站模板文章目录 前言1. 移动零题目描述代码 2. 复写零题目描述代码 3. 快乐数题目描述代码 4. 盛最多水的容器题目描述代码 5. 有效三角形的个数题目描述代码 6. 三数之和题目描述代码 7. 四数之和题目描述代码 总结 前言
学算法入门必学的一个章节#xff0c;双指针算法#xff0… 文章目录 前言1. 移动零题目描述代码 2. 复写零题目描述代码 3. 快乐数题目描述代码 4. 盛最多水的容器题目描述代码 5. 有效三角形的个数题目描述代码 6. 三数之和题目描述代码 7. 四数之和题目描述代码 总结 前言
学算法入门必学的一个章节双指针算法不说废话直接开始。
1. 移动零
我们先来一道经典的双指针题目试试水
题目链接283. 移动零
题目描述 怎么样才能在不创建新数组的情况下把 0 移动到数组的末尾呢如果不是有这个要求我肯定也无脑创建一个数组遍历解决来看代码
代码
func moveZeroes(nums []int) {slow, fast : 0, 0for fast len(nums) {if nums[fast] ! 0 {tmp : nums[fast]nums[fast] nums[slow]nums[slow] tmpslow}fast}
}我们设置 slowfast 两个指针都从 0 开始遍历fast 不断向后遍历查找不等于 0 的数交给 slow 位置这样就会出现一种情况
以 slow 为分界线左边的区间都是排好的数字右边就是没排好的数字最后左边就排好了而右边就都剩下 0 了
形象点说就是 fast 把数字都按序丢到了左边的区间
2. 复写零
像这样需要在数组中移动、删除、增加元素这类的操作都是离不开双指针的算法思想
题目链接1089. 复写零
题目描述 如果没有要求原地解决这道题目也会非常的简单但是如果需要我们原地求解又好像有点无从下手了如果使用 insert 方法来做这道题那复杂度会非常的高来看代码如何解决
代码
func duplicateZeros(arr []int) {left, right : 0, 0// 找到一共经过了几个 0, 调整好位置for right len(arr) {if arr[left] 0 { // 注意这里用的是 leftright}leftright}left--right--// 反向遍历for left 0 {if right len(arr) {arr[right] arr[left]}if arr[left] 0 { // 复写 0 的操作right--arr[right] 0}left--right--}
}这道题虽然是简单题但是想要按照题目的要求来做出这道题并不容易我们如果是第一次做是很难想到使用反向迭代的双指针来做所以还是重复我的一个观点多刷算法多积累见多识广才能思路开阔。至少下一次遇到类似的题目我们就能匹配一下这个思路了。
回到正题这道题如果使用双指针的话需要我们从后往前迭代使用直接用嘴说可能不太好理解我给出的建议是用题目给出的示例然后对着代码把流程跑一遍这样你能了解到这个算法的基本思路可以看看图解https://blog.csdn.net/Locky136/article/details/131537158
这里有两个需要注意的点
一开始根据 left 经过多少个零来调整两个指针的位置这里我用 left 和 right 命名是为了分辨两个指针的相对位置反向遍历时复写零的操作为什么只复写了一次因为还有一次和上一个操作合并了
3. 快乐数
双指针还有一个非常重要的思想就是快慢指针的思想其实听名字大家差不多都能猜到具体的用法但我们还是得来一道经典的题目试试水
题目链接202. 快乐数
题目描述 这道题题意很好理解所以我们直接根据示例不说废话直接上图题目的示例二我们来模拟他的流程 我们可以看到就像一个环用快慢指针遍历如果快指针追上了慢指针那不就代表这段代码无限循环了吗来看代码
代码
func isHappy(n int) bool {Sum : func(n int) int { // 进行一次快乐数的计算sum : 0for n 0 {tmp : n%10sum tmp*tmpn / 10}return sum}fast, slow : n, nfor {slow Sum(slow)fast Sum(Sum(fast))if fast slow {break;}}return fast 1
}其实这段算法的核心思想前面已经解释的很清楚了这里就不赘述了如果还有疑问跟着上面的图片走一遍代码就行~
4. 盛最多水的容器
再来一道经典的双指针题目练练手如果没刷过这道题你怎么敢说你刷过 LeetCode 呢~
题目链接11. 盛最多水的容器
题目描述 这道题的思路说难不难说简单其实也不一定想的出来首先把暴力排除用暴力匹配就没意思了更何况 10^5 的数据量用 O(N^2) 的算法不一定能过完这些样例可能会超时不然也不是中等难度的题目了那我们就来看看怎么用双指针来做出这道题吧~
代码
func maxArea(height []int) int {left, right, max : 0, len(height)-1, 0for left right {tmp : Min(height[left], height[right])*(right-left) // 计算当前容量max Max(max, tmp) // 迭代出最大容量if height[left] height[right] {right--} else {left}}return max
}func Min(a, b int) int {if a b {return b}return a
}func Max(a, b int) int {if a b {return a}return b
}在解释思路之前必须吐槽一下 LeetCode 的 Golang 编译器最新版本的 Go 其实已经实装了 max 和 min 让我们更方便的求最大值和最小值但是我试了一下LeetCode 的编译器并没有支持这个版本搞得我只好自己写找最大最小值的方法可恶
这道题其实知道想清楚核心的思路就很好做left 和 right 指针分别在两边我们只需要让比较矮的那一边的柱子移动即可因为如果让较高的柱子移动容量只可能更小而让较矮的柱子移动如果遇到更高的柱子容量就可能更大。这感觉也有一点贪心的思想在里面根据分析我们只要不断移动较矮的柱子就能求出最大的容量了。
5. 有效三角形的个数
咱们再来做一道题目练习双指针~
题目链接611. 有效三角形的个数
题目描述 听完题意有点算法经验的我们都能看出这道题目如果使用暴力来做那复杂度会非常的高而且也并不好写那我们该怎么设计算法来解决这道题目来看代码
代码
func triangleNumber(nums []int) int {sort.Ints(nums)ans : 0for i : len(nums)-1; i 0 ; i-- {left, right : 0, i-1for left right {if (nums[left]nums[right]) nums[i] {ans (right-left)right-- } else {left}}}return ans
}这段代码的核心流程就是将数组中最大的数作为三角形最长的那条边也就是 i利用三角形两边之长大于第三边的性质快速找出符合要求的三角形通过使用双指针的形式遍历余下的两条三角形的边
如果听完代码也模拟完之后还有疑问的话可以去看这篇文章我曾经写过的详细文字解答还配有清晰的图解https://blog.csdn.net/Locky136/article/details/131590581
6. 三数之和
刷了这么多双支指针的题目了怎么能错过 LeetCode 中大名鼎鼎的几数之和系列呢两数之和LeetCode 的第一道题那是多少人刷题的起点和梦想的开始呀但是我们肯定不能还去做这么简单的题目那必须是从三数之和开始刷起
题目链接15. 三数之和
题目描述 这道题目其实并没有什么高深的技巧抑或是复杂的算法更多的是考察我们对代码的掌控能力看看我们能不能写出一个像样的双指针算法来看代码
代码
func threeSum(nums []int) [][]int {sort.Ints(nums)var ans [][]intn : len(nums)-1for i, v : range nums[:n-1] {if i ! 0 v nums[i-1] { // 跳过重复数字continue}if vnums[i1]nums[i2] 0 { // 三数相加无论如何都会 0, 不需要再遍历 break}if vnums[n]nums[n-1] 0 { // 三数最大值 0, 让 i 继续遍历continue}// 双指针left, right : i1, nfor left right {s : vnums[left]nums[right]if s 0 {right--} else if s 0 {left} else {ans append(ans, []int{v, nums[left], nums[right]})// 跳过重复数字for left right nums[left] nums[left1] {left}for left right nums[right] nums[right-1] {right--}leftright--}}}return ans
}思路其实很简单依旧是遍历一个 i作为起点用双指针匹配出符合题目要求的值最后拼接在一起返回即可这里需要注意的是我们需要根据题目的要求跳过重复的数字不然最后还得去重那反而就更麻烦了。
7. 四数之和
接下来就是我们练习双指针的最后一道题目啦四数之和~
题目链接https://leetcode.cn/problems/4sum/
题目描述 四数之和相较于三数之和需要枚举的数字多了一个我们只需要在三数之和的条件下多枚举一个数即可不过对代码掌控能力的要求也随之升高了不少来看代码
代码
func fourSum(nums []int, target int) [][]int {sort.Ints(nums)var ans [][]intn : len(nums)-1for a : 0; a n-2; a {value1 : nums[a]if a ! 0 value1 nums[a-1] { // 跳过重复数字continue}if value1nums[a1]nums[a2]nums[a3] target { // 四数之和 target break}if value1nums[n-2]nums[n-1]nums[n] target { // 四数最大和 targetcontinue}for b : a1; b n-1; b {value2 : nums[b]if b ! a1 value2 nums[b-1] { // 跳过重复数字continue}if value1value2nums[b1]nums[b2] target { // 四数之和 target break}if value1value2nums[n-1]nums[n] target { // 四数最大和 targetcontinue}left, right : b1, nfor left right {sum : value1value2nums[left]nums[right]if sum target {right--} else if sum target {left} else {ans append(ans, []int{value1, value2, nums[left], nums[right]})// 跳过重复数字for left right nums[left] nums[left1] {left}for left right nums[right] nums[right-1] {right--}leftright--}}}}return ans
}省流其实跟三数之和换汤不换药就是多加上了一层循环仅此而已代码一下就能看的出来。不过为了更好的掌控代码我就没有再用 Golang 提供的语法糖而是老老实实的用 for 循环了。
总结
我刷过的个人喜欢的比较经典的数组相关的双指针问题大概就是这些了其实双指针并不能算是一个标准的算法我个人更倾向于这是一个思考的方向一个算法的基本素养。为什么这么说呢因为之后我们去做更多其他算法题多多少少都会用到这样一个思想在做链表专题的时候也会用到双指针的思想 所以想要学好算法打好每一步的基础都是非常重要滴~
