冲冲冲，力扣刷题——数组总结

陆陆续续把数组的力扣经典题刷完了，刷完后还是会出现忘记的情况，先对刷过的题进行总结，好记性不如烂笔头，冲冲冲~

1.二分查找

力扣704题:二分查找

这个题的关键点在于升序数组和无重复,这种题最适合用二分法，用二分法的一个重要技术点就是边界问题，这里需要注意的是区间不变量，比如，下面的解法就是坚持left>=right，即我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right]

/*** @param {number[]} nums* @param {number} target* @return {number}*/
var search = function(nums, target) {var left=0;var right=nums.length-1;var mid=0;while(left<=right){mid=left+((right-left)>>1);if(nums[mid]==target){return mid;}else if(nums[mid]>target){right=mid-1;}else{left=mid+1;}}return -1;
};

35.搜索插入位置

这个题和上面的题很类似：

/**
/*** @param {number[]} nums* @param {number} target* @return {number}*/
var searchInsert = function(nums, target) {var left=0;var right=nums.length-1;var mid=0;while(left<=right){mid=left+((right-left)>>1);if(nums[mid]==target){return mid;}else if(nums[mid]>target){right=mid-1;}else{left=mid+1;}}return left;
};

34.在排序数组中查找元素的第一个和最后一个位置

这个题的关键词：非递减顺序和有重复:

/*** @param {number[]} nums* @param {number} target* @return {number[]}*/
var searchRange = function(nums, target) {var left=0;var right=nums.length-1;var resultNums=[];var mid=0;while(left<=right){mid=left+((right-left)>>1);if(nums[mid]==target){var i=midwhile(nums[i]==nums[i-1]){i--;}resultNums[0]=i;while(nums[i]==nums[i+1]){i++;}resultNums[1]=i;return resultNums;}else if(nums[mid]>target){right=mid-1;}else{left=mid+1;}}return [-1,-1];
};

69.x 的平方根

虽然这个题不是数组了，但是整体结构还是像数组，数组的二分法思想照样可以用在这里；

/*** @param {number} x* @return {number}*/
var mySqrt = function(x) {var left=0;var right=x;var mid=0;while(left<=right){mid=left+((right-left)>>1);if(mid*mid==x){return mid;}else if(mid*mid>x){right=mid-1;}else{left=mid+1;}}return right;
};

367. 有效的完全平方数

/*** @param {number} num* @return {boolean}*/
var isPerfectSquare = function(num) {var left=0;var right=num;var mid=0;while(left<=right){mid=left+((right-left)>>1);if(mid*mid==num){return true;}else if(mid*mid>num){right=mid-1;}else{left=mid+1;}}return false;
};

2.双指针法

双指针法（快慢指针法）：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

• 暴力解法时间复杂度：O(n^2)
• 双指针时间复杂度：O(n)

27. 移除元素

解法借用代码随想录中的图解：

/*** @param {number[]} nums* @param {number} val* @return {number}*/
var removeElement = function(nums, val) {var slowIndex=0;var fastIndex=0;for(fastIndex;fastIndex<nums.length;fastIndex++){if(nums[fastIndex]!=val){var temp=nums[fastIndex];nums[slowIndex]=temp;slowIndex++;}}return slowIndex;
};

26. 删除有序数组中的重复项

这个题的关键词是升序排列(这个题我老是出错，mark一下~)

/*** @param {number[]} nums* @return {number}*/
var removeDuplicates = function(nums) {var slowIndex=0var fastIndex=1for(fastIndex=0;fastIndex<nums.length;fastIndex++){if(nums[slowIndex]!=nums[fastIndex]){nums[++slowIndex]=nums[fastIndex]}}return slowIndex+1
};

283.移动零

/*** @param {number[]} nums* @return {void} Do not return anything, modify nums in-place instead.*/
var moveZeroes = function(nums) {var fastIndex=0;var slowIndex=0;for(fastIndex;fastIndex<nums.length;fastIndex++){if(nums[fastIndex]!=0){nums[slowIndex]=nums[fastIndex];slowIndex++;}}for(slowIndex;slowIndex<nums.length;slowIndex++){nums[slowIndex]=0;}return nums;
};

844. 比较含退格的字符串

写这个题的时候卡了超级久，原因是审题错了，刚开始我一直以为退格的意思就是删掉前面所有的字符，然后重新输入，导致一直通过不了，浪费了大量时间，哎，以后一定要吸取教训，认真看官方给的案例！！！
这里遇到了一个坑，刚开始我写的代码是这样的：

/*** @param {string} s* @param {string} t* @return {boolean}*/
var backspaceCompare = function(s, t) {function shuangzhizhen(s){var slowIndex=0;var fastIndex=0;for(fastIndex;fastIndex<s.length;fastIndex++){if(s[fastIndex]!='#'){var temp=s[fastIndex];s[slowIndex]=temp;slowIndex++;}else if(slowIndex!=0){slowIndex--;}}s=s.substring(0,slowIndex)return s}s=shuangzhizhen(s);t=shuangzhizhen(t);return s==t;
};

按理说，逻辑上是没有错误的，但是一直通不过案例，为什么呢？查阅文献，才发现,js代码具有不变性，在 JavaScript 中，字符串 的值是 不可变的，这意味着一旦字符串被创建就不能被改变。比如下面的代码：

	var myStr = "Bob";myStr[0] = "J";

是不会把变量myStr的值改变成“Job”的，因为变量myStr是不可变的。
注意，这并不意味着myStr永远不能被改变，只是字符串字面量string literal的各个字符不能被改变。
改变 myStr 中的唯一方法是重新给它赋一个值，我思考了很久，后来还是决定新建一个数组去解决问题：

/*** @param {string} s* @param {string} t* @return {boolean}*/
var backspaceCompare = function(s, t) {function shuangzhizhen(s){var slowIndex=0;var fastIndex=0;var temp=[];var i=0;for(fastIndex;fastIndex<s.length;fastIndex++){if(s[fastIndex]!='#'){temp[slowIndex]=s[fastIndex];slowIndex++;}else if(slowIndex!=0){slowIndex--;}}     return temp.toString().substring(0,slowIndex)}s=shuangzhizhen(s);t=shuangzhizhen(t);return s==t;
};

977. 有序数组的平方

这个题的技巧在于，它是按照非递减顺序排列的，所以平方的最大值应该是在两边出现

/*** @param {number[]} nums* @return {number[]}*/
var sortedSquares = function(nums) {var index1=0;var index2=nums.length-1;var i=nums.length-1;var numsResult=[];while(index2!=index1){if(nums[index1]*nums[index1]>=nums[index2]*nums[index2]){numsResult[i]=nums[index1]*nums[index1];i--;index1++;}else{numsResult[i]=nums[index2]*nums[index2];i--;index2--;}}numsResult[i]=nums[index2]*nums[index2];return numsResult;
};

3.滑动窗口

209.长度最小的子数组

/*** @param {number} target* @param {number[]} nums* @return {number}*/
var minSubArrayLen = function(target, nums) {var res=nums.length+1;var Sum=0;var index=0;for(var i=0;i<nums.length;i++){Sum=Sum+nums[i];while(Sum>=target){if(res>(i-index+1)){res=i-index+1;}Sum=Sum-nums[index];index++;}}if(res>nums.length){return 0;}else{return res;}
};

904.水果成篮（努力理解中…)

这个题还挺复杂┭┮﹏┭┮，刚开始看了好几遍都没看懂，还是看了评论区的答案才知道咋写：

/*** @param {number[]} fruits* @return {number}*/
var totalFruit = function(fruits) {let l = 0;//起始指针let maxLen = 0;//窗口的最大长度 其中最多包涵两种水果let n = 0//前一类水果的结束位置let arr = [fruits[l]]//水果的种类数组for(let r = 0; r < fruits.length; r++){//窗口的右指针不断前进if(!arr.includes(fruits[r])){//如果窗口中不包含 进窗口的水果if(arr.length <= 1){//如果只有一种水果arr[1] = fruits[r]//将这种水果加入arr数组}else{//如果有两种水果l = n//更新窗口的左边界arr[0] = fruits[r-1]//更新arr中水果的种类arr[1] = fruits[r]}}if(fruits[r] !== fruits[n]){//如果进来了一种新的类型的水果 更新前一种水果的位置n = r}maxLen = Math.max(maxLen,r-l+1)//更新滑动窗口的最大值}return maxLen
};

这个题其实到现在也还是一知半解的，在努力理解了…

76.最小覆盖子串(未解决)

这是道hard题，我发现我之前刷题的时候漏掉这道题了，今天整理这个文档花费太多时间了，平时还要应付科研，暂时先放一放，明天或者后天把这个题克服掉,mark一下…

4.模拟行为

54.螺旋矩阵

/*** @param {number} n* @return {number[][]}*/
var generateMatrix = function(n) {var matrix1=new Array(n);for(var i=0;i<n;i++){matrix1[i]=new Array(n);}var left=0;var right=n-1;var top=0;var buttom=n-1;var num=1;while(left<=right&&top<=buttom){for(var i=left;i<=right;i++){matrix1[top][i]=num;num++;}top++;for(var i=top;i<=buttom;i++){matrix1[i][right]=num;num++;}right--;for(var i=right;i>=left;i--){matrix1[buttom][i]=num;num++;}buttom--;for(var i=buttom;i>=top;i--){matrix1[i][left]=num;num++;}left++;}return matrix1
};

这个题目难点在于写着写着就不知道逻辑到哪里去了，然后容易出错，其他倒没啥问题。

今天就总结到这里吧，今天总结了一下午加晚上两个小时才总结完，能把算法刷熟练的人都不容易，我平时科研任务比较重，本来学习时间就很短，以后一定要记得一周总结一次，不然真的很累，一次性总结这么多┭┮﹏┭┮