双指针算法是一种比较常用于搜索链表或数组相关的问题,很多算法的基本的解题思路就是使用暴力搜索法。而双指针是对暴力搜索的一种优化,通过双指针可以减少数据的遍历次数。通常双指针是有两个指针,叫做 light 左指针和 right 右指针,或者叫做快指针和慢指针。
- 作为左右指针的话,一般是在数组的或者链表的头尾两侧,从两遍往中间收缩,获取到符合条件的答案。
- 作为快慢指针的话,主要应用于解决链表问题。通常快指针移动的比慢指针移动的快,这种方法可以用来检测链表中是否有环、寻找链表的中间结点。
LeetCode 题解
11.盛最多水的容器
题目描述
解题思路
这题可以暴力破解法,双循环遍历出来,查出所有存在的情况,但是时服务器托管网间复杂是O(N),实现简单,但是比较耗时。而且本题也无需遍历所有的情况,分析一下解题思路:
本题求解的是最大的盛水面积,盛水面积是由宽和高组成,也就是找到横坐标的长度 * 两条竖线中更端的线的乘积。
最开始时候,左右指针分别指向数组的左右两端,获取到容量 min(1,7) * 8。
然后两遍指针往中间收缩,需要往中间移动一个指针,重点是需要移动哪一个?往中间收缩,宽度一定是变短,而高度是由两条竖线中的最短的一条决定。移动更大竖线的指针,面积肯定会减少,因为宽度和高度都在减少,所以需要移动竖线更小的指针,面积才可能增加。上面移动左边的竖线。面积由原来的 min(1,7) * 8 = 8 到 min (8,7) * 7 = 49,面积增多了。
使用 max 变量记录当前最大的面积,和每次搜索的面积做对比,获取到最大值。代码如下所示:
class Solution {
public int maxArea(int[] height) {
int left = 0;
int right = height.length -1;
int max = 0;
while (left
15.三数之和
题目描述
解题思路 for + 双指针
无论是两数之和或者三数之和都可以使用到双指针,但是双指针只有两个指针无法同时记录三个数,所以就需要使用一个 for 循环,for 每次遍历记录一个值,再使用双指针记录左右两个值。
为了减少遍历的次数,需要对数组做一个排序。然后 for 循环定位到第一个元素,左右两个指针的目标值就是 target – for 循环定位元素。左右指针相加得到总和 sum。
- 如果sum
- 如果sum > target,右指针往左移动。
- 如果sum = target,符合条件,返回值。
然后定位到第二个元素,继续使用双指针收缩遍历。
代码如下:
class Solution {
public List> threeSum(int[] nums) {
List> lists = new ArrayList();
Arrays.sort(nums);
//for循环 + 双指针
for (int i = 0; i 0 && nums[i] == nums[i - 1]) {
continue;
}
int target = -nums[i];
int left = i +1,right = nums.length - 1;
while (left list = new ArrayList();
list.add(nums[i]);
list.add(nums[left]);
list.add(nums[right]);
lists.add(list);
break;
} else if (sum
142. 环形链表 II
题目描述
解决方案
这道题在链表那篇文章也有,求解使用了 hash 表,遍历链表,存储在 hash 表中。如果有相同的数据,说明链表是有环了。本题采用快慢指针的办法。
起始的时候,快慢指针都在首节点。
慢指针一次走一步,快指针一次走两步,移动第一次之后。
fast 指针走过链表末端,说明链表无环,此时直接返回 null。如果两个指针遇上,说明链表有环,当两个指针第一次相遇时,fast 走的步数是 slow 的两倍。
从相遇点到入环点的距离加上 n−1 圈的环长,恰好等于从链表头部到入环点的距离。当 slow 和 fast 相遇时,可以在使用一个额外的指针 ptr,开始指向链表头部,随后它和 slow 每次往后移动,最后他们会在入环结点相遇,此时就能获取到入环结点。
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
ListNode slow = h服务器托管网ead, fast = head;
while (fast != null) {
slow = slow.next;
if (fast.next != null) {
fast = fast.next.next;
} else {
return null;
}
if (fast == slow) {
ListNode ptr = head;
while (ptr != slow) {
ptr = ptr.next;
slow = slow.next;
}
return ptr;
}
}
return null;
}
}
总结
双指针算法是一种常用于解决数组或链表相关问题的算法技巧。该算法通常涉及到使用两个指针(索引),它们可以从数组或链表的不同位置出发,根据问题的要求,以一定的方式移动这些指针,从而在数组或链表上执行一些特定的操作。一般使用左右指针和快慢指针两种方式。
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net
相关推荐: ChatGPT/GPT-4 或将从根本上改变软件工程
一、前言
二、主要内容文章目录 一、前言 二、主要内容 🍉 CSDN 叶庭云:https://yetingyun.blog.csdn.net/ 一、前言 编程也可能是最容易被 AI 技术取代的工作之一,软件的构建方式将产生根本性的转变。 今年以来,相信大家都听说过 ChatGPT、…