网站注册账号,做网站开发公司,应用市场app下载安装,网站建设费用计入什么二级科目欢迎来到啾啾的博客#x1f431;。 记录学习点滴。分享工作思考和实用技巧#xff0c;偶尔也分享一些杂谈#x1f4ac;。 有很多很多不足的地方#xff0c;欢迎评论交流#xff0c;感谢您的阅读和评论#x1f604;。 目录引言1 双指针#xff1a;Two Pointers1.1 左右指… 欢迎来到啾啾的博客。 记录学习点滴。分享工作思考和实用技巧偶尔也分享一些杂谈。 有很多很多不足的地方欢迎评论交流感谢您的阅读和评论。 目录引言1 双指针Two Pointers1.1 左右指针1.2 滑动窗口引言
在刷完代码随想录、了解了基本的数据结构后让我们学算法时隔四个月了。 阅读本篇可对基础的双指针算法有深入理解。
简单来说解决算法问题我们可以遵循一些简单的模板确认步骤、找合适的数据结构解。
1 双指针Two Pointers
什么是“双指针”模式它主要想解决什么问题
双指针核心是减少遍历优化时间复杂度。 主要是为了将暴力解法中 O(n²) 的时间复杂度两层循环优化到 O(n)一层循环。它本身就是一种 O(n) 的解法。
“左右指针”和“快慢指针”这两种方法在使用场景上最大的区别是什么比如一个通常用在什么数据结构上另一个用在什么上一个对原始数据有什么要求
左右指针主要适用于有序数组(不是非要有序数组)适用于搜索精确值。 快慢指针核心在于利用速度差来解决问题用来解决数据结构中位置和环路的问题。 最经典的应用场景是链表而不是数组。
1.1 左右指针
左右指针主要使用与有序数组也通用于数组。 因为左右指针的条件判断对于位置信息有要求需要有效移动位置。
LeetCode: 125. 验证回文串 简单的回文字符串判断。利用双指针快速遍历优化时间复杂度。
11. 盛最多水的容器 明白移动短板是收益最高的选项后利用双指针移动短板。 这里除了双指正还需要注意的是我们写解答时要尽量分开状态处理和状态转移。
错误示例
class Solution {/**移动短板因为短板没有潜力了*/public int maxArea(int[] height) {int length height.length;int left 0;int right length-1;int currentArea Math.min(height[left],height[right]) * ( right-left);;while(left right){if(height[left] height[right]){left ;}else{right --;}int tempArea Math.min(height[left],height[right]) * ( right-left);currentArea tempArea currentArea? tempArea:currentArea;}return currentArea;}
}正确示例
class Solution {public int maxArea(int[] height) {int maxArea 0;int left 0;int right height.length - 1;while (left right) {// 1. 先用当前的 left 和 right 计算面积int currentWidth right - left;int currentHeight Math.min(height[left], height[right]);int currentArea currentWidth * currentHeight;// 2. 更新历史最大面积maxArea Math.max(maxArea, currentArea);// 3. 然后再根据短板移动指针为下一次循环做准备if (height[left] height[right]) {left;} else {right--;}}return maxArea;}
}这样修改后循环体内部的逻辑非常纯粹对于当前的 left 和 right 状态我们先计算它的面积并更新 maxArea然后再决定下一步怎么走。每一步都处理一个独立的状态非常清晰。
1.2 滑动窗口
滑动窗口模式顾名思义就像有一个大小可变的“窗口”在一个序列通常是数组或字符串上滑动。它也是用两个指针来定义的通常我们叫它们 left 和 right但这里的 left 和 right 都从起点开始共同构成一个窗口 [left, right) 或 [left, right]。
这个模式专门用来解决“连续子数组”或“连续子字符串”的相关问题例如
找到满足某条件的最长/最短的连续子串。找到所有满足某条件的连续子数组的数量。
和左右指针定初始位置、判断条件往相反的方向走不同。 滑动窗口是两个指针相同一个方向移动
窗口扩大 不断移动 right 指针让新的元素进入窗口。更新状态 每当新元素进入就更新窗口内的信息例如窗口内元素的和、不同字符的数量等。判断收缩 当窗口内的状态不再满足题目要求时或者说满足了收缩条件时就需要移动 left 指针将元素移出窗口这个过程叫作窗口收缩。持续收缩 持续移动 left 指针直到窗口内的状态再次满足题目要求。重复以上过程直到 right 指针到达序列末尾。
3. 无重复字符的最长子串
import java.util.HashSet;
import java.util.Set;class Solution {public int lengthOfLongestSubstring(String s) {int n s.length();if (n 0) {return 0;}// 1. 初始化SetCharacter charSet new HashSet();int maxLen 0;int left 0; // 窗口左边界int right 0; // 窗口右边界// 2. 循环让 right 指针作为主导探索整个字符串while (right n) {// 3. 尝试扩大窗口检查 right 指向的字符是否已在窗口中char charToadd s.charAt(right);// 4. 如果有重复触发窗口收缩// 注意这里是 while 循环因为可能需要收缩多次while (charSet.contains(charToadd)) {// 从 Set 中移除 left 指向的字符charSet.remove(s.charAt(left));// 收缩窗口left;}// 5. 此时窗口内一定没有重复了可以安全地加入新字符charSet.add(charToadd);// 6. 更新最大长度// 每一次扩大窗口后都计算一下当前长度并尝试更新最大值maxLen Math.max(maxLen, right - left 1);// 7. 真正地扩大窗口为下一次循环做准备right;}return maxLen;}
}还有209. 长度最小的子数组。 拓展leetcode题解与题目汇总powcai滑动窗口题解
