精华内容
下载资源
问答
  • 双指针

    千次阅读 2020-10-06 16:34:31
    双指针的应用 链表,数组 所谓双指针,指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向或者相反方向的指针进行扫描,从而达到相应的目的。 注:这里的指针,并非专指c中指针的概念...

    双指针的应用

    链表,数组

    所谓双指针,指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向或者相反方向的指针进行扫描,从而达到相应的目的。
    注:这里的指针,并非专指c中指针的概念,而是指索引,游标或指针,可迭代对象等

    这类算法包括:
    1.给定一个有序递增数组,在数组中找到满足条件的两个数,使得这两个数的和为某一给定的值。如果有多对数,只输出一对即可。

    对于这种问题,常见的算法思路不外乎遍历,回溯,但这里,双指针遍历法是一个很有效的方法。具体思路是:初始化两个指针,一个指向数组的第一个元素,另外一个指向数组的最后一个元素,在两个指针相遇之前,指针1只能向前移动,指针2 只能向后移动。比较当前两个指针所指元素和与给定数字的大小,如果和较大,指针2向后移动,如果和较小,指针1向前移动。最终的结果是找到两个满足条件的数或者不存在这样的两个数字。

    2.快排

    3.奇偶排序。忘记是哪个公司的面试题了。题目大意是这样的,给定一个数组,数组中元素有奇数有偶数。要求对数组进行处理,使得数组的左边为奇数,右边为偶数

    4.双指针法的应用之四:求单链表的中间元素。

    这个大家应该都比较熟悉了。对于单链表求中间元素的问题,经典的作法是采用两个指针,初始化都指向链表表头,移动开始时,快指针移动两步,慢指针移动一步。当快指针的next为null或者快指针为null的时候,慢指针所指的就是单链表的中间元素(注意奇数个元素和偶数个元素的处理)

    LeetCode26

    题目描述
    给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

    不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

    public int removeDuplicates(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int p = 0;
        int q = 1;
        while(q < nums.length){
            if(nums[p] != nums[q]){
                if(q - p > 1){
                    nums[p + 1] = nums[q];
                }
                p++;
            }
            q++;
        }
        return p + 1;
    }
    
    优化思路
    注意:数组之间交换是需要时间的,所以可以判断 p 与 q 差值是否为1,
    可以省去数组交换时间限制。还可以
    p++;
    nums[p] = nums[q];
    且 nums[p] 与 nums[q] 指向同一地址,复制就不会增加更多负担。故其实还是可以减少一次 if。
    
    
    展开全文
  • 双指针算法

    2020-12-06 11:26:44
    双指针算法 双指针算法算法思想经典使用场景1:搜索旋转排序数组题目AC 代码解法及解析2:串联所有单词的字串题目代码解法及解析3:最长无重复字符串题目代码解法及解析参考资料 双指针算法 算法思想 双指针,指的...

    双指针算法

    算法思想

    双指针,指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向(快慢指针)或者相反方向(对撞指针)的指针进行扫描,从而达到相应的目的。
    换言之,双指针法充分使用了数组有序这一特征,从而在某些情况下能够简化一些运算。

    经典使用场景

    1:搜索旋转排序数组

    题目

    给你一个整数数组 nums ,和一个整数 target 。
    该整数数组原本是按升序排列,但输入时在预先未知的某个点上进行了旋转。(例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
    请你在数组中搜索 target ,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。

    示例 1:
    输入:nums = [4,5,6,7,0,1,2], target = 0
    输出:4

    示例 2:
    输入:nums = [4,5,6,7,0,1,2], target = 3
    输出:-1

    示例 3:
    输入:nums = [1], target = 0
    输出:-1

    AC 代码

    /*
    双指针-对撞指针
    1:由于该数组两部分都有序,满足双指针的使用场景
    2:最终终止条件 左索引大于右索引
    3:由于左边是递增的,如果目标值小于第一个索引值,左边索引增长结束。
    4:右边部分是从右往左,为递减,如果右边索引值小于目标值,右减少结束。
    5:弹出条件,两边中至少一边的索引值等于目标值,弹出索引。
    6:两边索引无变化,那不存在,返回-1;
    */
    int search(vector<int>& nums, int target) {
    	//双指针
    	if (nums.size() < 1) return -1;
    	int right = nums.size() - 1;
    	int left = 0;
    	while (right>=left)
    	{
    		if (nums[right]<target&&nums[left]>target) return -1; //6:两边索引无变化,那不存在,返回 - 1;
    		if (nums[right] == target) return right;//5:弹出条件,两边中至少一边的索引值等于目标值,弹出索引。
    		if (nums[left] == target) return left;//5:弹出条件,两边中至少一边的索引值等于目标值,弹出索引。
    		if (nums[right]>target) right--;//7:如果还满足条件,索引继续变化
    		if (nums[left]<target) left++;//7:如果还满足条件,索引继续变化
    	}
    	return -1;
    }
    

    解法及解析

    思路:在有序的数组中,满足双指针的遍历情况,使用双指针能使得时间复杂度/2。使用该基础算法不难,只需要认真思考题几口,
    通俗讲–双指针就是两边同时进行访问遍历,达到减少循环次数。

    2:串联所有单词的字串

    题目

    代码

    解法及解析

    3:最长无重复字符串

    题目

    代码

    解法及解析

    参考资料

    展开全文
  • C++双指针示例

    2017-11-11 14:57:09
    C++双指针的展示,想进阶C++的可以看一下,如果看懂了对指针的理解会有一个新的高度
  • 双指针讲解

    2011-12-05 14:32:24
    主要讲述c语言中双指针的应用,能帮助大家对双指针的理解
  • 本代码为通过highcharts制作的双盘双指针仪表盘; 本代码为通过highcharts制作的双盘双指针仪表盘;
  • 双指针技巧

    千次阅读 多人点赞 2021-01-26 20:15:36
    双指针技巧可以分为两类,一类是「快慢指针」,一类是「左右指针」。前者解决主要解决链表中的问题,比如典型的判定链表中是否包含环;后者主要解决数组(或者字符串)中的问题,比如二分查找。 一、快慢指针的常见...

    双指针技巧可以分为两类,一类是「快慢指针」,一类是「左右指针」。前者解决主要解决链表中的问题,比如典型的判定链表中是否包含环;后者主要解决数组(或者字符串)中的问题,比如二分查找。

    一、快慢指针的常见算法

    快慢指针一般都初始化指向链表的头结点 head,前进时快指针 fast 在前,慢指针 slow 在后,巧妙解决一些链表中的问题。

    1、判定链表中是否含有环

    单链表的特点是每个节点只知道下一个节点,所以一个指针的话无法判断链表中是否含有环的。

    如果链表中不含环,那么这个指针最终会遇到空指针 null 表示链表到头了,这还好说,可以判断该链表不含环。

    public boolean hasCycle(ListNode head) {
        while (head != null){
            head = head.next;
        }
        return false;
    }
    

    但是如果链表中含有环,那么这个指针就会陷入死循环,因为环形数组中没有 null 指针作为尾部节点。

    经典解法就是用两个指针,一个每次前进两步,一个每次前进一步。如果不含有环,跑得快的那个指针最终会遇到 null,说明链表不含环;如果含有环,快指针最终会超慢指针一圈,和慢指针相遇,说明链表含有环。

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

    2、已知链表中含有环,返回这个环的起始位置

    public static ListNode detectCycle(ListNode head) {
            ListNode fast = head;
            ListNode slow = head;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast) {
                    ListNode index1 = fast;
                    ListNode index2 = head;
                    while (index1 != index2) {
                        index1 = index1.next;
                        index2 = index2.next;
                    }
                    return index2;
                }
            }
            return null;
        }
    

    3、寻找链表的中点

    类似上面的思路,我们还可以让快指针一次前进两步,慢指针一次前进一步,当快指针到达链表尽头时,慢指针就处于链表的中间位置。

    public static ListNode findMid(ListNode head) {
        ListNode slow, fast;
        slow = fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;// slow 就在中间位置
    }    
    

    当链表的长度是奇数时,slow 恰巧停在中点位置;如果长度是偶数,slow 最终的位置是中间偏右。

    寻找链表中点的一个重要作用是对链表进行归并排序。

    回想数组的归并排序:求中点索引递归地把数组二分,最后合并两个有序数组。对于链表,合并两个有序链表是很简单的,难点就在于二分。

    但是现在你学会了找到链表的中点,就能实现链表的二分了。

    4、寻找链表的倒数第 k 个元素

    我们的思路还是使用快慢指针,让快指针先走 k 步,然后快慢指针开始同速前进。这样当快指针走到链表末尾 null 时,慢指针所在的位置就是倒数第 k 个链表节点(为了简化,假设 k 不会超过链表长度):

    public static ListNode findK(ListNode head, int k) {
        ListNode slow, fast;
        slow = fast = head;
        while (k-- > 0){
            fast = fast.next;
        } 
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
    

    应用比如:力扣第 19 题「删除链表的倒数第n个元素」

    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode slow = head;
            ListNode fast = head;
            for(int i = 0; i < n; i++){
                fast = fast.next;
            }
            if(fast == null){// 如果此时快指针走到头了,说明倒数第 n 个节点就是第一个结点
                return head.next;
            }
            while(fast != null && fast.next != null){// 让慢指针和快指针同步向前
                slow = slow.next;
                fast = fast.next;
            }
            slow.next = slow.next.next;// slow.next 就是倒数第 n 个节点,删除它
            return head;
        }
    }
    

    二、左右指针的常用算法

    左右指针在数组中实际是指两个索引值,一般初始化为 left = 0, right = nums.length - 1 。

    1、二分查找

    前文 二分查找算法详解 有详细讲解,这里只写最简单的二分算法,旨在突出它的双指针特性:

    int binarySearch(int[] nums, int target) {
        int left = 0; 
        int right = nums.length - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target)
                return mid; 
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
            }
        return -1;
    }
    

    2、两数之和

    直接看一道 LeetCode 题目吧:

    图示

    只要数组有序,就应该想到双指针技巧。这道题的解法有点类似二分查找,通过调节 left 和 right 可以调整 sum 的大小:

    int twoSum(int[] nums, int target) {
        int left = 0; 
        int right = nums.length - 1;
        while(left < right) {
            int sum = nums[left] + nums[right];
            if(sum == target)
                return new int[]{left + 1, right + 1}; 
            else if (sum < target)
                left++;
            else if (sum > target)
                right--;
            }
        return -1;
    }
    

    3、反转数组

    public void reverse(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            // swap(nums[left], nums[right])
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++; right--;
        }
    }
    

    4、滑动窗口算法

    /* 滑动窗口算法框架 */
    void slidingWindow(string s, string t) {
        unordered_map<char, int> need, window;
        for (char c : t) need[c]++;
    
        int left = 0, right = 0;
        int valid = 0; 
        while (right < s.size()) {
            // c 是将移入窗口的字符
            char c = s[right];
            // 右移窗口
            right++;
            // 进行窗口内数据的一系列更新
            ...
    
            /*** debug 输出的位置 ***/
            printf("window: [%d, %d)\n", left, right);
            /********************/
    
            // 判断左侧窗口是否要收缩
            while (window needs shrink) {
                // d 是将移出窗口的字符
                char d = s[left];
                // 左移窗口
                left++;
                // 进行窗口内数据的一系列更新
                ...
            }
        }
    }
    

    其中两处…表示的更新窗口数据的地方,到时候直接往里面填就行了。

    而且,这两个…处的操作分别是右移和左移窗口更新操作,等会你会发现它们操作是完全对称的。

    注:把索引左闭右开区间[left, right)称为一个窗口。

    展开全文
  • 深入理解双指针

    2012-11-01 16:42:39
    深入理解双指针 对于C语言的参数传递都是值传递,当传传递一个指针给函数的时,其实质 上还是值传递,除非使用双指针。 在讲双指针之前,还是先讲讲关于C语言函数调用的本质。
  • 算法技巧——双指针算法

    千次阅读 多人点赞 2020-05-23 12:22:17
    双指针指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向(快慢指针)或者相反方向(对撞指针)的指针进行扫描,从而达到相应的目的。 双指针问题套路 通俗的说,就是在数组遍历中...

    前置知识

    C 和 C++ 的数组、指针。

    什么是双指针

    严格的来说,双指针只能说是是算法中的一种技巧。

    双指针指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向(快慢指针)或者相反方向(对撞指针)的指针进行扫描,从而达到相应的目的。

    双指针问题套路

    通俗的说,就是在数组遍历中,我们使用两个指针进行操作。所以双指针问题基本有以下几个细节:

    1、双指针的初始位置。根据双指针的分类,有两种可能。具体看下面的介绍。

    2、双指针的移动方法。根据双指针的分类,有两种可能。具体看下面的介绍。

    3、遍历的结束条件。根据双指针的分类,有两种可能。具体看下面的介绍。

    对撞指针

    对撞指针是指在数组中,将指向最左侧的索引定义为左指针(left),最右侧的定义为右指针(right),然后从两头向中间进行数组遍历。快速排序就是典型的双指针问题。

    我们假设数组名字为 nums,数组长度为 n,数组首元素对应的位置为 0。

    代码细节

    指针初始位置

    左指针(left)一般指向数组的第一个元素。即 left = 0。

    右指针(right)一般指向数组的第一个元素。即 right = n-1。

    指针移动方法

    左指针(left)向右边👉移动,一般每次移动一个位置,即 left++。

    右指针(right)向左边👈移动,一般每次移动一个位置,即 right--。

    结束条件

    左指针(left)位置和右指针(right)位置逆序。

    从上面的描述可知,开始的时候,right >= left。因此结束的条件就是 right < left。

    伪代码

    function fn(int list[], int len) {
      int left = 0;
      int right = len - 1;
    
      //遍历数组
      while (left <= right) {
        left++;
        // 一些条件判断 和处理
        ... ...
        right--;
      }
    }

    例题

    我们使用 LeetCode 881 救生艇为例,https://leetcode-cn.com/problems/boats-to-save-people/

    解题大致思路为:

    1、排序。

    2、初始化双指针。

    3、遍历。每次都用一个最重的和一个最轻的进行配对,如果二人重量小于 Limit,则此时的最轻的上船,left++。不管最轻的是否上船,最重的都要上船,right--。并且所需船数量加一,num++。

    AC 参考代码

    class Solution {
    public:
        int numRescueBoats(vector<int>& people, int limit) {
            sort(people.begin(), people.end());//排序
    
            int ans = 0;//答案
            int left = 0;//左指针
            int right = people.size() - 1;//右指针
            while (left<=right) {
                if (people[left]+people[right]<=limit) {
                    left++;
                }
                right--;
                ans++;
            }
    
            return ans;
        }
    };

    快慢指针

    快慢指针是两个指针从同一侧开始遍历数组,将这两个指针分别定义为快指针(fast)慢指针(slow),两个指针以不同的策略移动,直到两个指针的值相等(或其他特殊条件)为止,如快指针(fast)每次增长两个,慢指针(slow)每次增长一个。

    一般来说,快慢指针常用于判断链表等数据结构中是否有环。比如下图所示的一个链表。

    图解

    下面我们用一系列图像说明,快慢指针查找环的过程。

    初始位置

    如下图所示,慢指针(slow)和快指针(fast)同时指向第一个元素。

     

    移动一次

    慢指针(slow)向后移动一个位置,快指针(fast)向后移动两个位置,如下图所示。

    移动两次

    慢指针(slow)向后移动一个位置,快指针(fast)向后移动两个位置,如下图所示。

    移动三次

    慢指针(slow)向后移动一个位置,快指针(fast)向后移动两个位置,如下图所示。我们发现慢指针(slow)和快指针(fast)重合,说明有环。

    代码细节

    指针初始位置

    慢指针(slow)一般指向数组的第一个元素。即 slow = 0。

    快指针(fast)一般指向数组的第一个元素。即 fast = 1。

    指针移动方法

    慢指针(slow)向右边👉移动,一般每次移动一个位置,即 slow++。

    快指针(fast)向右边👉移动,一般每次移动两个个位置,即 fast += 2。

    结束条件

    慢指针(slow)位置和快指针(fast)位置重合;快指针(fast)达到数组的最后一个元素。

    特别注意,要判断达到最后一个元素。否则会出现死循环。

    伪代码

    注意:伪代码只是表示一种结构。

    function fn(LinkList *list, int len) {
      int slow = 0;
      int fast = 1;
    
      //遍历数组
      while (slow != fast) {
        slow++;
        // 一些条件判断 和处理
        ... ...
        fast+=2;
      }
    }

    例题

    我们使用 LeetCode 141 环形链表为例,https://leetcode-cn.com/problems/linked-list-cycle/

    解题大致思路为:

    1、排序。

    2、初始化双指针。

    3、遍历。

    AC 参考代码

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        bool hasCycle(ListNode *head) {
            ListNode *slow = head;//慢指针
            ListNode *fast = head;//快指针
            while (NULL!=fast && NULL!=fast->next && NULL!=fast->next->next) {
                //修改位置
                slow = slow->next;
                fast = fast->next->next;
                //判断有环
                if (slow==fast) {
                    return true;
                }
            }
    
            //无环
            return false;
        }
    };

    展开全文
  • 左右双指针; 有序数组; 两数之和。 题目举例: 已知一个递增的数组nums[],一个目标值target。 判断数组中是否存在两个值nums[i],nums[j], 使得nums[i]+nums[j]=target。 参考代码(Java) public boolean ...
  • JAVA双指针

    2020-03-31 09:59:07
    双指针主要分为快慢指针和左右指针两种。 快慢指针解决链表含环问题以及相差问题。 左右指针解决数组问题,左=0,右=length-1,二分查找等问题。 快慢指针 1.判断有无环:快指针一步走两个,慢指针一步一个,如果...
  • 双指针实现交换

    2013-07-06 09:37:02
    可以用但指针实现交换,双指针也是可以实现交换的,只要搞懂他们在内存中是怎么存储的
  • 双指针简单总结.docx

    2020-06-26 09:23:09
    利用Python编程,双指针的简单应用,包括对撞指针,快慢指针,对其应用进行简单剖析,附带代码示例,举例子解释指针用法
  • 本篇文章是对双指针的两种用法进行了详细的分析介绍,需要的朋友参考下
  • python算法-双指针问题一、数组合并1. 使用模拟指针和并两个有序数组2.模拟指针说明:二、二分法(折半查找法)1.有序数组的二分法查找2. 二分法说明三、链表(双链表和单链表区别) 一、数组合并 1. 使用模拟指针和...
  • 详解双指针算法

    2019-12-09 00:23:50
    一、双指针算法 ​ 双指针算法是指利用两个指针遍历数组(链表),左右指针相向前进或同向前进,在遍历过程中根据某种限制条件进行筛选,通常可以把时间复杂度降低至O(n)。 二、双指针题目 2.1 leetcode80-删除排序...
  • 双指针技巧 一 双指针技巧 —— 情景一 问题:反转数组中的元素。 分析:其思想是将第一个元素与末尾进行交换,再向前移动到下一个元素,并不断地交换,直到它到达中间位置。我们可以同时使用两个指针来完成迭代:...
  • 双指针 双指针比较灵活,可以大大降低时间复杂度,可用在数组,单链表等数据结构中。 快慢指针:一快一慢,步长一大一小,看慢指针是否能追上快指针。例如,是否有环问题,单链表找中间节点问题。 对撞指针:一左...
  • 双指针算法详解

    2020-05-09 20:37:32
    首先有两种双指针算法的形式: 1:对于一个序列,两个指针维护着一段区间。比如快排算法。 2:对于两个序列,维护某种次序。如归并排序中合并两个有序序列的操作。 对双指针算法的理解: 对于需要n^2次暴力搜索算法...
  • 链表 双指针技巧

    千次阅读 2019-04-27 19:35:18
    链表 双指针技巧 在我们做题中,若只是一个指针遍历链表可能无法达到我们的需求。那么我们就可以定义两个指针,例如本篇博客要引入的双指针。主要是一个快指针,一个慢指针,来解决问题。 来,我们主要从一些题中来...
  • 双指针类型题目

    千次阅读 2020-08-18 16:48:39
    使用双指针的思想, 关键在于两个指针的初始化, 左指针取零, 右指针区target的平方根. class Solution { public boolean judgeSquareSum(int c) { int num1=0; //此处注意, 取值为c的平方根, c过大时,c*c超出int...
  • 397,双指针求接雨水问题.pdf
  • 本篇归纳双指针算法:1、快慢指针,主要是成环问题;2、左右指针,数组和字符串问题;3、滑动窗口,主要是子串问题
  • js算法双指针

    2021-03-09 17:13:53
    左右双指针 1.求和 function sum(arr,target){ let left = 0,right = arr.length-1 while(left<right){ if(arr[left]+arr[right]>target){ right-- }else if(arr[left]+arr[right]<target){ left++ ...
  • 双指针总结

    千次阅读 多人点赞 2021-06-23 06:22:58
    双指针总结 双指针总共列举了 7 题目: 有序数组的 Two Sum 两数平方和 反转字符串中的元音字符 回文字符串 归并两个有序数组 判断链表是否存在环 最长子序列 通过这 7 题大概就对双指针的用法有了...
  • 双指针原理和应用

    千次阅读 2020-06-02 10:48:13
    双指针 双指针算法思想 实用i,j两个变量,不会退的扫描一个数组 常规写法 for(int i=0,j=0,i<n;i++){ while(j<i&&check(i,j)) j++; } 这是i,j分别两端的写法 int i=0,j=n-1; while(i<j){ if...
  • 盛最多水的容器——图解双指针.pptx

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 304,931
精华内容 121,972
关键字:

双指针