做网站案例,养老院服务质量建设专项网站,自学学网页设计,哪些网站做的好看一、背景知识 双指针#xff08;Two Pointers#xff09;#xff1a;指的是在遍历元素的过程中#xff0c;不是使用单个指针进行访问#xff0c;而是使用两个指针进行访问#xff0c;从而达到相应的目的。对撞时针#xff1a; 两个指针方向相反对撞指针一般用来解决有序…一、背景知识 双指针Two Pointers指的是在遍历元素的过程中不是使用单个指针进行访问而是使用两个指针进行访问从而达到相应的目的。对撞时针 两个指针方向相反对撞指针一般用来解决有序数组或者字符串问题快慢指针 两个指针方向相同速度不同。移动快的指针被称为 「快指针fast」移动慢的指针被称为「慢指针slow」快慢指针一般用于处理数组中的移动、删除元素问题或者链表中的判断是否有环、长度问题。分离双指针 两个指针分别属于不同的数组 / 链表分离双指针一般用于处理有序数组合并求交集、并集问题。 滑动窗口法 两个指针一前一后组成滑动窗口并计算滑动窗口中的元素的问题。一般是右端向右扩充达到停止条件后右端不动左端向右端逼近逼近达到停止条件后左端不动右端继续扩充。 滑动窗口法一般用于处理字符串匹配问题和子数组问题时间复杂度 二、例题 总结 要移动多个指针的情况可以分解成双指针的情况1n关键是什么条件下移动哪个指针分开思考一起走就容易乱 1、移动零快慢指针 突破点右指针是贴着左指针开始往右移的不是从数组右端往左移因为那样会搅乱数组元素的相对顺序 class Solution {public void moveZeroes(int[] nums) {int l0;//左指针int r0;//右指针int count0;//计算0的个数while(rnums.length){if(nums[r]!0 nums[l]0){//找到0交换后左右指针都往右移nums[l]nums[r];nums[r]0;count;l;}if(nums[l]!0){//没找到0左右指针都往右移l;}//前两种情况都有r; 所以把它提到外面大家都能用r;//如果只有左指针找到0右指针继续往右移}}
} 代码优化封装方法
class Solution {public void moveZeroes(int[] nums) {int n nums.length, left 0, right 0;while (right n) {if (nums[right] ! 0) {swap(nums, left, right);left;}right;}}public void swap(int[] nums, int left, int right) {int temp nums[left];nums[left] nums[right];nums[right] temp;}
}2、盛最多水的容器对撞指针 突破点不是同时移动两个指针而是只移动较小的那个因为较小的值改变会影响整体面积 public class Solution {public int maxArea(int[] height) {int l 0, r height.length - 1;//左右指针分别指向数组的头尾int ans 0;//维护一个最大值while (l r) {int area Math.min(height[l], height[r]) * (r - l);//当前面积不一定是最大值ans Math.max(ans, area);//移动数字较小的那个指针整体面积才会发生变化 if (height[l] height[r]) {l;}else {--r;}}return ans;}
}3、三数之和对撞指针 突破点三个指针的相对方位不会改变一左一中一右 它们也不会走对方走过的路因为它们三个实际上是相同的 如果改变了方位就会出现重复的三元组 class Solution {public ListListInteger threeSum(int[] nums) {int n nums.length;Arrays.sort(nums);ListListInteger ans new ArrayListListInteger();// 枚举 afor (int first 0; first n; first) {// 需要和上一次枚举的数不相同if (first 0 nums[first] nums[first - 1]) {continue;}// c 对应的指针初始指向数组的最右端int third n - 1;int target -nums[first];// 枚举 bfor (int second first 1; second n; second) {// 需要和上一次枚举的数不相同if (second first 1 nums[second] nums[second - 1]) {continue;}// 需要保证 b 的指针在 c 的指针的左侧// 因为当b走到c的右边时相当于原来的c会有重复的三元组产生while (second third nums[second] nums[third] target) {//b和c之和大于targetb是往右走值是增大的所以要移动c指针往左走--third;}// 如果指针重合随着 b 后续的增加// 就不会有满足 abc0 并且 bc 的 c 了可以退出循环if (second third) {break;}//找到了 if (nums[second] nums[third] target) {ListInteger list new ArrayListInteger();list.add(nums[first]);list.add(nums[second]);list.add(nums[third]);ans.add(list);}}}return ans;}
}4、接雨水对撞指针 突破点是从两边向中间逼近而非从左到右 class Solution {public int trap(int[] height) {int ans0;int left0,rightheight.length-1;//左右指针分别指向数组的头尾端int leftMax0,rightMax0;while(leftright){//指针未相撞leftMaxMath.max(leftMax,height[left]);rightMaxMath.max(rightMax,height[right]);if(height[left]height[right]){ansleftMax-height[left];//当前height[left]夹在leftMax和rightMax中间所以它的存水量受制于最小值left;//移动最小值才会改变可存水量}else{ansrightMax-height[right];--right;}}}
}
