IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 双指针的应用 -> 正文阅读

[数据结构与算法]双指针的应用

双指针的应用

一. 双指针可分为:快慢指针,对撞指针。
二. 双指针技巧主要应用在解决 数组,链表 以及 字符串 问题
三. 双指针的应用场景:
(1)快慢指针:主要运用于处理链表内部环路的问题,再就是可以解决数组内是否有重复项的问题。
eg-1. 删除有序数组中的重复项(leetcode 第26题 - 难度 easy)

class Solution {
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if(len == 0 || len == 1){
            return len;
        }
        int slow = 0;
        for(int fast=0;fast<len;fast++){
            if(nums[fast] != nums[slow]){
                nums[++slow] = nums[fast];
            }
        }
        return slow+1;
    }
}

思路:快指针一直走,如果(快指针指向的值)==(慢指针指向的值)则直接跳过,而(快指针指向的值)!=(慢指针指向的值)则让慢指针先向前移动一位,再让让(快指针指向的值)把(慢指针指向的值)覆盖,最终得到删除重复元素的数组。

eg-2. 判断链表内部是否有环(leetcode 第141题 - 难度 easy)

public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null){
            return false;
        }
        ListNode slow, fast;
        slow = fast = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }
}

思路:快指针走得快,慢指针走得慢,若链表中存在环路,则两指针一定会相遇,并且快指针会快慢指针一周(经典的相遇问题);若链表中不存在环路,则快指针一定会指向null。

(2)对撞指针:主要运用于处理数组和字符串的索引问题.
eg-1. 两数之和 II - 输入有序数组(leetcode 第167题 - 难度 easy)
(twoSum问题也可以用HashMap 或者 HashSet 帮助我们处理?序数组相关的简单问题)

public int[] twoSum(int[] numbers, int target) {
        int len = numbers.length;
        int left = 0;
        int right = len - 1;
        while(left < right){
            if(numbers[left] + numbers[right] > target){
                right--;
            }
            else if(numbers[left] + numbers[right] < target){
                left++;
            }
            else{
                int[] arr = new int[2];
                arr[0] = left + 1;
                arr[1] = right + 1;
                return arr;
            }
        }
        return null;
    }

思路: 左右两个指针分别指向数组的头和尾, 若 (两指针指向的值的和) > (target) 则让右指针左移一位, 若 (两指针指向的值的和) < (target) 则让左指针右移一位,找到target值后最终返回 左右指针的索引.

eg-2. 验证回文字符串(leetcode 第167题 - 难度 easy)

public boolean isPalindrome(String s) {
        String str = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
        char[] arr = str.toCharArray();
        int len = arr.length;
        int left = 0;
        int right = len - 1;
        while(left < right){
            if(arr[left] != arr[right]){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

都差不多,这里就不多赘述,要注意一下replaceAll的使用和正则表达式.

  数据结构与算法 最新文章
寒假第一周总结
蓝桥杯python(题目思路即解答(笔记,持续
堆排序的理解
如何获得数组长度
NC61 两数之和
简谈ArrayList特有的方法
剑指offer - 调整数组顺序使奇数位于偶数前
【力扣】难度【简单】20. 有效的括号
LeetCode | 373. Find K Pairs with Smalle
链表中为什么要设置虚拟头结点dummy?
上一篇文章      下一篇文章      查看所有文章
加:2021-08-23 16:56:46  更:2021-08-23 16:58:06 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
360图书馆 购物 三丰科技 阅读网 日历 万年历 2022年1日历 -2022/1/20 0:38:50-
图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码