美国电话号码生成器_设计网页布局的常用方法有哪三种_小程序推广引流_石家庄网站建设培训

题目描述：给定一个有序数组（含非正整数），要求输出平方后的顺序新数组。
暴力解法就是先平方再排序就好了
双指针解法是采用首尾两个指针对向移动，依次比较，较小的一边的对边需要往里靠一个，结束的条件就是start>end

class Solution {public int[] sortedSquares(int[] nums) {int length = nums.length;int[] new_nums = new int[length];int start = 0,end = length-1,index = length-1;while(start<=end){if(nums[start]*nums[start]<nums[end]*nums[end]){new_nums[index--] = nums[end]*nums[end--];}else{new_nums[index--]=nums[start]*nums[start++];}}return new_nums;}
}

题目描述：如题
从这题可以看出数组增删操作的不便，还是链表在这方面好操作，遍历一次，改变节点指向就行，数组操作需要借助快慢指针优化时间复杂度。

• 暴力解法

暴力解法就是双循环，先找到待删除的元素，因为是在数组中，元素内存连续，所以需要赋值覆盖。
注意 (1) 内循环边界判断j不要越界 (2) 每次找到覆盖后，外循环的索引i应该不动，继续判断是否是连续相同待删除数值元素

class Solution {public int removeElement(int[] nums, int val) {int count = 0;for(int i = 0;i<nums.length-count;i++){if(nums[i]==val){count++;for(int j = i+1;j<nums.length;j++){nums[j-1]=nums[j];}i--;}}return nums.length-count;}
}

• 快慢指针法

利用快指针遍历，找到不同于val的元素则赋值给慢指针的新数组，相同则跳过进入下一次遍历寻找

class Solution {public int removeElement(int[] nums, int val) {int slow = 0;for(int fast = 0;fast<nums.length;fast++){if(nums[fast]!= val){nums[slow++]=nums[fast];}}return slow;}
}

题目描述：如题，但还是上一个数组删除元素的题目，只不过现在val是变化的。
注意 慢指针数组赋值时，需要提前++，因为慢指针默认有第一个元素，也就是原数组的第一个元素，后续索引从1开始，有新元素则赋值给慢指针数组，这时候需要提前移动一位。

class Solution {public int removeDuplicates(int[] nums) {int slow = 0;for(int fast = 1;fast<nums.length;fast++){if(nums[fast]!=nums[slow]){nums[++slow]=nums[fast];}}return slow+1;}
}

题目描述：将数组中的零移动到数组的后面。
用快慢指针的方法，那么这个和27.数组删除元素的题目一样，这个找非零元素存起来就行，不过还需要一个额外的操作，剩余的元素置零。

class Solution {public void moveZeroes(int[] nums) {int slow = 0;for(int fast=0;fast<nums.length;fast++){if(nums[fast]!=0){nums[slow++]=nums[fast];}}for(int count = slow++;count<nums.length;count++){nums[count]= 0;}}
}

题目描述：如题
快指针比慢指针多走n步即可，同样的还有求有序链表的中位数的（fast=fast.next.next;slow=slow.next;）

题目描述：验证链表是否有环，有的话输出入口点。
追击相遇问题，快指针比慢指针快一步就可以在环里追上，入口点取决于相遇点和头结点。

题目描述：如题
左右两个窗口指针同向移动，右指针负责引入元素构造窗口，当窗口符合缩小条件时，左指针移动缩小窗口
结束条件是右指针出去数组。对于数组【1,7,1】,target=7的单子数组情况，虽然while循环结束后左指针>右指针,但结束完while后，一次for循环也结束了，此时两指针都同时指向下一个点，所以不用考虑左指针超限的情况，只需要考虑右指针就可以。

 class Solution {public int minSubArrayLen(int target, int[] nums) {int sum = 0;int min = Integer.MAX_VALUE;for(int windowStart = 0,windowEnd = 0;windowEnd<nums.length;windowEnd++){sum +=nums[windowEnd];while(sum>=target){min =min<(windowEnd-windowStart+1)? min:(windowEnd- windowStart+1);sum-=nums[windowStart++];}}return min == Integer.MAX_VALUE ? 0 : min;}
}

题目描述：找到一个最长的连续子数组，这个数组里元素最多有两种。
这是求一个连续子数组问题，所以考虑用滑动窗口，右指针遍历，左指针控制窗口。
本题的数组结构主要有以下几个类型：仅一种元素、两种元素、>两种元素。
一种元素，只需计算数组长度即可，right(数组最后一个元素）-left(数组第一个元素）+1
两种元素，判断出第二个元素，添加到新数组中，后续没有元素与这个新数组的两个元素一致，输出结果
>两种元素，这主要涉及left指针移动，每个合法窗口内都只有两种元素，我的做法是先找到第三种元素，然后left就是第三种元素前的连续元素组的第一个，比如【1,2,1,1,3,1】,第二个窗口的两种元素是这两个，left不一定都挨着第三种元素。

class Solution {public int totalFruit(int[] fruits) {int[] num = new int[2];num[0] = fruits[0];int count = 1;int max = 1;for(int right = 1,left = 0;right<fruits.length;right++){if(count == 1&&fruits[right]!=num[0]){num[1] = fruits[right];count = 2;}if(count == 2&&(fruits[right]!=num[0]&&fruits[right]!=num[1])){left = right-1;while(fruits[left-1]==fruits[left]){left--;}max = (right-left+1)>=max ? (right-left+1):max;num[0] = fruits[left];num[1] = fruits[right];continue;}max = (right-left+1)>=max ? (right-left+1):max;}return max;}
}