一、双指针算法的定义
双指针是一种常用的算法技巧,通过使用两个指针在数组、链表或其他数据结构上进行遍历,以解决各种问题。这两个指针可以同向移动、反向移动或一个快指针一个慢指针等不同的方式移动,根据具体问题的需求来选择合适的移动策略。
二、双指针算法的应用场景
- 数组排序和去重:可以使用双指针来对数组进行排序或去除重复元素。例如,在有序数组中,一个指针用于遍历数组,另一个指针用于指向不重复的元素位置。
- 链表操作:在链表问题中,双指针可以用于判断链表是否有环、找到链表的中间节点等。
- 字符串处理:对于字符串问题,双指针可以用于判断回文字符串、字符串的子串问题等。
三、代码实现
以下是一些用 Java 实现的双指针算法的例子:
1. 数组去重
public class ArrayDeduplication {
public static int[] removeDuplicates(int[] nums) {
if (nums.length == 0) {
return nums;
}
int slow = 0;
for (int fast = 1; fast < nums.length; fast++) {
if (nums[fast]!= nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
}
return Arrays.copyOf(nums, slow + 1);
}
}
2. 链表找中间节点
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
public class LinkedListMid {
public ListNode findMiddle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast!= null && fast.next!= null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
3. 判断回文字符串
public class PalindromeCheck {
public boolean isPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
while (left < right &&!Character.isLetterOrDigit(s.charAt(left))) {
left++;
}
while (left < right &&!Character.isLetterOrDigit(s.charAt(right))) {
right--;
}
if (Character.toLowerCase(s.charAt(left))!= Character.toLowerCase(s.charAt(right))) {
return false;
}
left++;
right--;
}
return true;
}
}
【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
评论(0)