本文介绍: 前面已经写了两篇关于算法方面的文章,这几天想了下,决定把这个算法整理一个系列,除了是帮助自己巩固算法知识外,还能够自己总结的每种算法的套路保存下来并分享大家,这样以后即使是哪天想要重拾起来,也是能够根据这些算法套路快速重拾。那么好,这道题可能很多小伙伴会说太简单了,如果双指针只有这水平,那大家可以洗洗睡了,还在算法的题海里面挣扎个什么劲。但是现在嘛,首尾指针给它安排上,两个指针指向数值比较小的往对方靠拢(为什么这样自己去想想),记录一个最大值,不断刷新满足条件的值,直到两个指针相遇,结束

       前面已经写了两篇关于算法方面的文章,这几天想了下,决定把这个算法整理一个系列,除了是帮助自己巩固算法知识外,还能够自己总结的每种算法的套路保存下来并分享大家,这样以后即使是哪天想要重拾起来,也是能够根据这些算法套路快速重拾。

        我想了下,算法这块主要分为五大块,分别是双指针、栈(单调栈)、深度优先搜索(DFS)、广度优先搜索(BFS)、动态规划今天就从双指针开始,从双指针算法概述、套路模板,以及根据这个模板,进行几道算法题的讲解,从简单到难,让小白也能由浅入深了解这个算法。

        双指针,是一种通过设置两个指针不断进行单向移动解决问题的算法思想。一般包含两种形式:一、两个指针指向同一个序列。二、两个指针分别指向不同序列指向同一序列比较常见代表快慢指针首尾指针固定间距指针等。指向不同序列的双指针代表归并排序这种,需要合并时用双指针或者多指针。

        说得那么概念可能大家反而没什么感觉,不就是两个指针,根据一定的条件触发两个指针的移动然后把满足一定条件结果作为最终结果嘛。但是,下面,来点干货,套路模板来了,不管什么样的算法题,只要是双指针的题目记住下面这个套路模板然后微调整下边界值,就可以直接往上套了,以不变应万变:

public Type twoPoints() {
        int left;
        int right;
        Type result
        while (满足继续循环条件) {
            if (满足左指针移动) {
                left++;
				if(满足更新result条件) 更新result;
            } else {
                right++/right--;
				if(满足更新result条件呢) 更新result;
            }
        }
        return result;
    }

那么好,看到上面这个模板我就想立马给各种类型的双指针场景给安排上,让我试一试这把刀锋不锋利,首先来第一种,快慢指针,我在leetcode上一下子就找到了,看看这题目怎么描述的:

3. 无重复字符的最长子串

 

知道是不是刷题刷多了,看到题就会大概猜到这道题要用什么算法,我相信很多人都有这种感觉,一看到这题目,就知道这肯定是双指针,并且是快慢指针就能搞定。那么好,我们直接模板,把代码写出来:

public int lengthOfLongestSubstring(String s) {
        Set<Character&gt; containString = new HashSet<&gt;();// 子串包含的所有字符
        char[] sChar = s.toCharArray();
        int left = 0;
        int right = 0;
        int max = 0;
        while (right < sChar.length) {// 右指针走到最右端的时候,循环就可以结束if (!containString.contains(sChar[right])) {// 满足右指针继续右移条件
                containString.add(sChar[right]);
                max = max > right - left + 1 ? max : right - left + 1;
                right++;
            } else {// 满足左指针右移条件
                while (containString.contains(sChar[right])) {
                    containString.remove(sChar[left]);
                    left++;
                }
            }
        }
        return max;
    }

那么好,这道题可能很多小伙伴会说太简单了,如果双指针只有这水平,那大家可以洗洗睡了,还在算法的题海里面挣扎个什么劲。我们接着往下看第二种,收尾指针,刚好也有一道比较经典的题:

11. 盛最多水的容器

如果放在几年前,在我功力还不是那么深厚的时候,我一看这题目,果断给他来个双层循环,暴力计算出所有两个坐标之间的面积,记录一个最大值然后比较更新,10分钟代码我就给它撸完。然后一跑,尴尬了,暴力的居然还能过,只是这速度内存使用情况,有点不太好看

但是现在嘛,首尾指针给它安排上,两个指针指向数值比较小的往对方靠拢(为什么这样自己去想想),记录一个最大值,不断刷新满足条件的值,直到两个指针相遇,结束

public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int max = 0; // 记录中间过程满足条件最大值
        while (left < height.length &amp;&amp; right > left) {// 满足指针继续移动
            int curretn = (height[left] > height[right] ? height[right] : height[left]) * (right - left);
            max = curretn > max ? curretn : max;
            if (height[left] >= height[right]) {// 右指针左移
                right--;
            } else { // 左指针右移
                left++;
            }
        }
        return max;
    }

好,前面两种都介绍完了,下面就轮到固定间距双指针了,但是尴尬的是我居然没找到相关类型的题目,额,先跳过,这种类型的题目一般是滑动窗口会用的比较多,下次遇到了我再更新这里来,我们先看下两个指针指向不同序列这种类型,这个比较有意思,刚好之前也遇过:

56. 合并区间

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) {
            return intervals;
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) {
                    return o1[1] - o2[1];
                }
                return o1[0] - o2[0];
            }
        });

        int min = intervals[0][0];
        int max = intervals[0][1];
        List<int[]> resultList = new ArrayList<>();
        for (int i = 1; i < intervals.length; i++) {
            if (max >= intervals[i][0]) {
                // 存在交集,合并
                max = max > intervals[i][1] ? max : intervals[i][1];
                continue;
            } else {
                // 不存在交集,将min和max先入结果集,然后重置min和max
                int[] tempResult = {min, max};
                resultList.add(tempResult);
                min = intervals[i][0];
                max = intervals[i][1];
            }
        }
        resultList.add(new int[] {min, max});

        return resultList.toArray(new int[resultList.size()][2]);
    }
}

两个指针min和max,指向不同的列,找出相交集合,并返回

双指针的题目一般情况下都不会很难,从我刷的题目经验来看,顶多中等题吧,关键在于有双指针解题的思想(就是看到问题第一时间能够知道使用双指针解题思路),下面列一下在leetCode使用双指针思想解题的题目,供大家练手:
5. 最长回文子串
11. 盛最多水的容器
15. 三数之和
18. 四数之和
26. 删除有序数组中的重复
27. 移除元素
31. 下一个排列
83. 删除排序链表中的重复元素
160. 相交链表
283. 移动
392. 判断子序列
821. 字符的最短距离
870. 优势洗牌
905. 按奇偶排序数组
986. 区间列表的交集

 

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注