可信赖的网站建设推广,网站设计与开发的基本步骤包括哪些,wordpress分类页面添加幻灯片,进出口采购网力扣javascript刷题——数组总结冲冲冲#xff0c;力扣刷题——数组总结1.二分查找力扣704题:二分查找35.搜索插入位置34.在排序数组中查找元素的第一个和最后一个位置69.x 的平方根367. 有效的完全平方数2.双指针法27. 移除元素26. 删除有序数组中的重复项283.移动零844. 比较…
力扣javascript刷题——数组总结冲冲冲力扣刷题——数组总结1.二分查找力扣704题:二分查找35.搜索插入位置34.在排序数组中查找元素的第一个和最后一个位置69.x 的平方根367. 有效的完全平方数2.双指针法27. 移除元素26. 删除有序数组中的重复项283.移动零844. 比较含退格的字符串977. 有序数组的平方3.滑动窗口209.长度最小的子数组904.水果成篮努力理解中...)76.最小覆盖子串(未解决)4.模拟行为54.螺旋矩阵冲冲冲力扣刷题——数组总结
陆陆续续把数组的力扣经典题刷完了刷完后还是会出现忘记的情况先对刷过的题进行总结好记性不如烂笔头冲冲冲~
1.二分查找
力扣704题:二分查找 这个题的关键点在于升序数组和无重复,这种题最适合用二分法用二分法的一个重要技术点就是边界问题这里需要注意的是区间不变量比如下面的解法就是坚持leftright即我们定义 target 是在一个在左闭右闭的区间里也就是[left, right]
/*** param {number[]} nums* param {number} target* return {number}*/
var search function(nums, target) {var left0;var rightnums.length-1;var mid0;while(leftright){midleft((right-left)1);if(nums[mid]target){return mid;}else if(nums[mid]target){rightmid-1;}else{leftmid1;}}return -1;
};35.搜索插入位置 这个题和上面的题很类似
/**
/*** param {number[]} nums* param {number} target* return {number}*/
var searchInsert function(nums, target) {var left0;var rightnums.length-1;var mid0;while(leftright){midleft((right-left)1);if(nums[mid]target){return mid;}else if(nums[mid]target){rightmid-1;}else{leftmid1;}}return left;
};34.在排序数组中查找元素的第一个和最后一个位置 这个题的关键词非递减顺序和有重复:
/*** param {number[]} nums* param {number} target* return {number[]}*/
var searchRange function(nums, target) {var left0;var rightnums.length-1;var resultNums[];var mid0;while(leftright){midleft((right-left)1);if(nums[mid]target){var imidwhile(nums[i]nums[i-1]){i--;}resultNums[0]i;while(nums[i]nums[i1]){i;}resultNums[1]i;return resultNums;}else if(nums[mid]target){rightmid-1;}else{leftmid1;}}return [-1,-1];
};69.x 的平方根 虽然这个题不是数组了但是整体结构还是像数组数组的二分法思想照样可以用在这里
/*** param {number} x* return {number}*/
var mySqrt function(x) {var left0;var rightx;var mid0;while(leftright){midleft((right-left)1);if(mid*midx){return mid;}else if(mid*midx){rightmid-1;}else{leftmid1;}}return right;
};367. 有效的完全平方数 /*** param {number} num* return {boolean}*/
var isPerfectSquare function(num) {var left0;var rightnum;var mid0;while(leftright){midleft((right-left)1);if(mid*midnum){return true;}else if(mid*midnum){rightmid-1;}else{leftmid1;}}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 slowIndex0;var fastIndex0;for(fastIndex;fastIndexnums.length;fastIndex){if(nums[fastIndex]!val){var tempnums[fastIndex];nums[slowIndex]temp;slowIndex;}}return slowIndex;
};26. 删除有序数组中的重复项 这个题的关键词是升序排列(这个题我老是出错mark一下~)
/*** param {number[]} nums* return {number}*/
var removeDuplicates function(nums) {var slowIndex0var fastIndex1for(fastIndex0;fastIndexnums.length;fastIndex){if(nums[slowIndex]!nums[fastIndex]){nums[slowIndex]nums[fastIndex]}}return slowIndex1
};283.移动零 /*** param {number[]} nums* return {void} Do not return anything, modify nums in-place instead.*/
var moveZeroes function(nums) {var fastIndex0;var slowIndex0;for(fastIndex;fastIndexnums.length;fastIndex){if(nums[fastIndex]!0){nums[slowIndex]nums[fastIndex];slowIndex;}}for(slowIndex;slowIndexnums.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 slowIndex0;var fastIndex0;for(fastIndex;fastIndexs.length;fastIndex){if(s[fastIndex]!#){var temps[fastIndex];s[slowIndex]temp;slowIndex;}else if(slowIndex!0){slowIndex--;}}ss.substring(0,slowIndex)return s}sshuangzhizhen(s);tshuangzhizhen(t);return st;
};按理说逻辑上是没有错误的但是一直通不过案例为什么呢查阅文献才发现,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 slowIndex0;var fastIndex0;var temp[];var i0;for(fastIndex;fastIndexs.length;fastIndex){if(s[fastIndex]!#){temp[slowIndex]s[fastIndex];slowIndex;}else if(slowIndex!0){slowIndex--;}} return temp.toString().substring(0,slowIndex)}sshuangzhizhen(s);tshuangzhizhen(t);return st;
};977. 有序数组的平方 这个题的技巧在于它是按照非递减顺序排列的所以平方的最大值应该是在两边出现
/*** param {number[]} nums* return {number[]}*/
var sortedSquares function(nums) {var index10;var index2nums.length-1;var inums.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 resnums.length1;var Sum0;var index0;for(var i0;inums.length;i){SumSumnums[i];while(Sumtarget){if(res(i-index1)){resi-index1;}SumSum-nums[index];index;}}if(resnums.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-l1)//更新滑动窗口的最大值}return maxLen
};这个题其实到现在也还是一知半解的在努力理解了…
76.最小覆盖子串(未解决) 这是道hard题我发现我之前刷题的时候漏掉这道题了今天整理这个文档花费太多时间了平时还要应付科研暂时先放一放明天或者后天把这个题克服掉,mark一下…
4.模拟行为
54.螺旋矩阵 /*** param {number} n* return {number[][]}*/
var generateMatrix function(n) {var matrix1new Array(n);for(var i0;in;i){matrix1[i]new Array(n);}var left0;var rightn-1;var top0;var buttomn-1;var num1;while(leftrighttopbuttom){for(var ileft;iright;i){matrix1[top][i]num;num;}top;for(var itop;ibuttom;i){matrix1[i][right]num;num;}right--;for(var iright;ileft;i--){matrix1[buttom][i]num;num;}buttom--;for(var ibuttom;itop;i--){matrix1[i][left]num;num;}left;}return matrix1
};这个题目难点在于写着写着就不知道逻辑到哪里去了然后容易出错其他倒没啥问题。
今天就总结到这里吧今天总结了一下午加晚上两个小时才总结完能把算法刷熟练的人都不容易我平时科研任务比较重本来学习时间就很短以后一定要记得一周总结一次不然真的很累一次性总结这么多┭┮﹏┭┮
