椒江住房和城乡建设部网站,网站开发步骤,设计报价网站,个人网站特点文章目录双指针简介快慢指针快慢指针介绍快慢指针例题快慢指针优缺点#xff1a;对撞指针对撞指针介绍#xff1a;对撞指针例题对撞指针优缺点#xff1a;更新中——未完总结更多宝藏双指针简介
#x1f60e;#x1f973;#x1f60e;#x1f920;#x1f62e;#x…
文章目录双指针简介快慢指针快慢指针介绍快慢指针例题快慢指针优缺点对撞指针对撞指针介绍对撞指针例题对撞指针优缺点更新中——未完总结更多宝藏双指针简介 双指针算法是一种通过设置两个指针不断进行单向移动来解决问题的算法。 它包含两种形式快慢指针和对撞指针。 快慢指针是一种设置步长不同的两个指针用于解决链表中的问题如判断是否有环找到中间节点等。 对撞指针是一种设置在序列两端向中间移动的两个指针用于解决数组中的问题如找到两数之和反转元音字母等。 双指针算法的核心思想是利用单调性或者有序性减少不必要的遍历优化时间复杂度。下面我们将分别介绍这两种形式的双指针算法并给出一些例题和解析。 快慢指针 快慢指针介绍
快慢指针是一种设置步长不同的两个指针用于解决链表中的问题如判断是否有环找到中间节点等。 快慢指针的基本思想是让一个指针每次移动一步另一个指针每次移动两步这样当两个指针相遇时就可以得到一些有用的信息。下面我们将通过一些例题来展示快慢指针的用法和技巧。
快慢指针例题
例题1判断链表是否有环
给定一个链表判断链表中是否有环。如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。为了表示给定链表中的环我们使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。 思路我们可以使用快慢指针来解决这个问题。首先我们定义两个指针 fast 和 slow 并让它们都指向链表的头节点。然后我们让 fast 每次移动两个节点slow 每次移动一个节点。如果链表中没有环那么 fast 最终会遇到空节点结束循环。如果链表中有环那么 fast 和 slow 最终会在环内相遇也结束循环。我们只需要判断循环结束时 fast 和 slow 是否相等就可以知道链表是否有环。 代码
public boolean hasCycle(ListNode head) { if (head null || head.next null) { return false; } ListNode fast head; ListNode slow head; while (fast ! null fast.next ! null) { fast fast.next.next; slow slow.next; if (fast slow) { return true; } } return false; } 例题2找到链表的中间节点
给定一个头结点为 head 的非空单链表返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。 思路我们可以使用快慢指针来解决这个问题。首先我们定义两个指针 fast 和 slow 并让它们都指向链表的头节点。然后我们让 fast 每次移动两个节点slow 每次移动一个节点。当 fast 到达链表的末尾时slow 就恰好在链表的中间节点。如果链表的长度是偶数那么 fast 会停在最后一个节点的后面此时 slow 在中间两个节点的前面一个我们需要返回 slow 的下一个节点。 代码
public ListNode middleNode(ListNode head) {if (head null || head.next null) {return head;}ListNode fast head;ListNode slow head;while (fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;}return slow;
}快慢指针优缺点
快慢指针是一种常用的优化技巧它有以下的优点
它可以在不使用额外空间的情况下解决一些链表或数组的问题如判断是否有环找到中间节点找到倒数第k个节点等。它可以在一次遍历中得到一些有用的信息如环的长度环的入口链表的长度等。它可以简化代码的逻辑避免使用多重循环或递归。
快慢指针也有一些缺点如
它需要对链表或数组的结构有一定的了解才能正确地设置快慢指针的步长和终止条件。它可能会遇到一些边界情况如链表为空链表只有一个节点链表长度为偶数或奇数等需要特别注意处理。它可能会造成一些误解或困惑如快慢指针相遇时它们是否在环的入口是否在环的中点是否在链表的中点等。需要仔细分析和证明。
对撞指针
对撞指针介绍
对撞指针是一种设置在序列两端向中间移动的两个指针用于解决数组中的问题如找到两数之和反转元音字母等。对撞指针的核心思想是利用数组的有序性根据两个指针所指元素的和与目标值的大小关系决定移动哪个指针从而减少不必要的遍历优化时间复杂度。下面我们将通过一些例题来展示对撞指针的用法和技巧。
对撞指针例题
例题1找到两数之和
给定一个已按照 升序排列 的有序数组 nums 和一个目标值 target 。请你在该数组中找出 和为目标值 的那 两个 整数并返回它们的数组下标。
假设每种输入只会对应一个答案但是数组中同一个元素不能使用两遍。
你可以按任意顺序返回答案。
示例 1
输入nums [2,7,11,15], target 9 输出[0,1] 解释因为 nums[0] nums1 9 返回 [0, 1] 。 示例 2
输入nums [2,3,4], target 6 输出[0,2] 示例 3
输入nums [-1,0], target -1 输出[0,1] 来源力扣LeetCode 链接https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted 思路我们可以使用对撞指针来解决这个问题。首先我们定义两个指针 left 和 right 并让它们分别指向数组的首尾元素。然后我们计算 left 和 right 所指元素的和 sum 并与目标值 target 比较。如果 sum 等于 target 那么我们就找到了答案返回 left 和 right 的下标。如果 sum 小于 target 那么我们就让 left 向右移动一位增大 sum 的值。如果 sum 大于 target 那么我们就让 right 向左移动一位减小 sum 的值。我们重复这个过程直到找到答案或者 left 和 right 相遇。 代码
public int[] twoSum(int[] numbers, int target) {if (numbers null || numbers.length 2) {return new int[0];}int left 0;int right numbers.length - 1;while (left right) {int sum numbers[left] numbers[right];if (sum target) {return new int[]{left 1, right 1};} else if (sum target) {left;} else {right--;}}return new int[0];
}例题2反转元音字母
编写一个函数以字符串作为输入反转该字符串中的元音字母。
示例 1
输入“hello” 输出“holle” 示例 2
输入“leetcode” 输出“leotcede” 思路我们可以使用对撞指针来解决这个问题。首先我们定义两个指针 left 和 right 并让它们分别指向字符串的首尾字符。然后我们判断 left 和 right 所指字符是否都是元音字母a,e,i,o,u。 如果是那么我们就交换 left 和 right 所指字符的位置然后让 left 向右移动一位right 向左移动一位。如果不是那么我们就让不是元音字母的指针向中间移动直到找到元音字母或者 left 和 right 相遇。 代码
public String reverseVowels(String s) {if (s null || s.length() 2) {return s;}char[] chars s.toCharArray();int left 0;int right chars.length - 1;String vowels aeiouAEIOU;while (left right) {if (!vowels.contains(chars[left] )) {left;} else if (!vowels.contains(chars[right] )) {right--;} else {char temp chars[left];chars[left] chars[right];chars[right] temp;left;right--;}}return new String(chars);
}对撞指针优缺点
对撞指针有以下的优点
它可以在不使用额外空间的情况下解决一些有序数组的问题如找到两数之和反转元音字母等。它可以在一次遍历中得到一些有用的信息如数组中是否存在满足条件的元素对反转后的字符串等。它可以简化代码的逻辑避免使用多重循环或二分查找。
对撞指针也有一些缺点如
它需要对数组的有序性有一定的了解才能正确地设置对撞指针的移动方向和终止条件。它可能会遇到一些边界情况如数组为空数组只有一个元素数组中没有满足条件的元素对等需要特别注意处理。它可能会造成一些误解或困惑如对撞指针相遇时它们是否在数组的中点是否在满足条件的元素对的最小或最大位置等。需要仔细分析和证明。
更新中——未完 总结 ☝️ ⭐
如果你对这篇文章感兴趣欢迎在评论区留言分享你的想法和建议。如果你喜欢我的博客请记得点赞、收藏和关注我我会持续更新更多有用的网页技巧和教程。谢谢大家 更多宝藏 项目仓库看这里 https://github.com/w-x-x-w https://gitee.com/w-_-x 博客文章看这里 https://blog.csdn.net/weixin_62650212 视频推送看这里 https://space.bilibili.com/1909782963
