建站多少钱一个,2021最火营销方案,松岗网站的建设,什么是企业网站营销前面已经写了两篇关于算法方面的文章#xff0c;这几天想了下#xff0c;决定把这个算法整理成一个系列#xff0c;除了是帮助自己巩固算法知识外#xff0c;还能够把自己总结的每种算法的套路保存下来并分享给大家#xff0c;这样以后即使是哪天想要重拾起来#xff0c;… 前面已经写了两篇关于算法方面的文章这几天想了下决定把这个算法整理成一个系列除了是帮助自己巩固算法知识外还能够把自己总结的每种算法的套路保存下来并分享给大家这样以后即使是哪天想要重拾起来也是能够根据这些算法套路快速重拾。 我想了下算法这块主要分为五大块分别是双指针、栈单调栈、深度优先搜索DFS、广度优先搜索BFS、动态规划。今天就从双指针开始从双指针算法概述、套路模板以及根据这个模板进行几道算法题的讲解从简单到难让小白也能由浅入深了解这个算法。 双指针是一种通过设置两个指针不断进行单向移动来解决问题的算法思想。一般包含两种形式一、两个指针指向同一个序列。二、两个指针分别指向不同的序列。指向同一序列的比较常见代表有快慢指针首尾指针固定间距指针等。指向不同序列的双指针代表有归并排序这种需要合并时用双指针或者多指针。 说得那么概念可能大家反而没什么感觉不就是两个指针根据一定的条件触发两个指针的移动然后把满足一定条件的结果作为最终结果嘛。但是下面来点干货套路模板来了不管什么样的算法题只要是双指针的题目记住下面这个套路模板然后稍微调整下边界值就可以直接往上套了以不变应万变
public Type twoPoints() {int left;int right;Type resultwhile (满足继续循环条件) {if (满足左指针移动) {left;if(满足更新result条件) 更新result;} else {right/right--;if(满足更新result条件呢) 更新result;}}return result;}
那么好看到上面这个模板我就想立马给各种类型的双指针场景给安排上让我试一试这把刀锋不锋利首先来第一种快慢指针我在leetcode上一下子就找到了看看这题目怎么描述的
3. 无重复字符的最长子串
不知道是不是刷题刷多了看到题就会大概猜到这道题要用什么算法我相信很多人都有这种感觉一看到这题目就知道这肯定是双指针并且是快慢指针就能搞定。那么好我们直接套模板把代码写出来
public int lengthOfLongestSubstring(String s) {SetCharacter containString new HashSet();// 子串中包含的所有字符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 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 Comparatorint[]() {Overridepublic 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];Listint[] 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和maxint[] 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. 区间列表的交集
