【基础算法】双指针

举报
一颗小谷粒 发表于 2024/10/29 21:22:57 2024/10/29
【摘要】 一、双指针算法的定义双指针是一种常用的算法技巧,通过使用两个指针在数组、链表或其他数据结构上进行遍历,以解决各种问题。这两个指针可以同向移动、反向移动或一个快指针一个慢指针等不同的方式移动,根据具体问题的需求来选择合适的移动策略。二、双指针算法的应用场景数组排序和去重:可以使用双指针来对数组进行排序或去除重复元素。例如,在有序数组中,一个指针用于遍历数组,另一个指针用于指向不重复的元素位置。...
一、双指针算法的定义


双指针是一种常用的算法技巧,通过使用两个指针在数组、链表或其他数据结构上进行遍历,以解决各种问题。这两个指针可以同向移动、反向移动或一个快指针一个慢指针等不同的方式移动,根据具体问题的需求来选择合适的移动策略。


二、双指针算法的应用场景


  1. 数组排序和去重:可以使用双指针来对数组进行排序或去除重复元素。例如,在有序数组中,一个指针用于遍历数组,另一个指针用于指向不重复的元素位置。
  2. 链表操作:在链表问题中,双指针可以用于判断链表是否有环、找到链表的中间节点等。
  3. 字符串处理:对于字符串问题,双指针可以用于判断回文字符串、字符串的子串问题等。


三、代码实现


以下是一些用 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

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。