【LeetCode与《代码随想录》】数组篇:做题笔记与总结-JavaScript版
创始人
2024-04-08 16:36:33
0

感觉关于JavaScript的题解不太多,所以就写一个,给自己总结用。

文章目录

    • 代码随想录
    • 主要题目
      • 704. 二分查找(二分)
      • 27. 移除元素(双指针)
      • 977. 有序数组的平方(双指针)
      • 209. 长度最小的子数组(滑动窗口)
      • 59.螺旋矩阵II(模拟)
    • 相关题目推荐
      • 35. 搜索插入位置(二分)
      • 34. 在排序数组中查找元素的第一个和最后一个位置(二分)
      • 69. x 的平方根 (二分)
      • 367. 有效的完全平方数(重复)
      • 26. 删除有序数组中的重复项(双指针)
      • 283. 移动零(双指针)
      • 844. 比较含退格的字符串(模拟)
      • 904. 水果成篮(滑动窗口)
      • 76. 最小覆盖子串(滑动窗口)

代码随想录

https://www.programmercarl.com/

主要题目

704. 二分查找(二分)

704. 二分查找

  • 经典二分
  • 注意,取中点要用>>位运算移动,因为直接/2会产生小数
  • 这里的范围是左闭右闭,因此如果在循环中mid取不到答案的话,left和right的更新分别是mid+1mid-1
  • 对上句话的解释:如果在mid取不到的情况下还更新为mid,那范围就是开(左闭右开/左开右闭)
  • 关于范围:题目中说n的范围是10000。而js中let是Number,是64位的,不会爆。
  • 若是会爆:left+(right-left)>>1
var search = function(nums, target) {let left=0,right=nums.length-1;let mid=(left+right)>>1;while(left<=right){if(nums[mid]===target){return mid;}else{if(nums[mid]left=mid+1;}else{right=mid-1;}}mid=(left+right)>>1;}return -1;
};

27. 移除元素(双指针)

27. 移除元素

  • 双指针:i是快指针,遍历数组;j是慢指针,填入答案
  • i一定比j快(或等于)
  • j是下标,但返回的是数组长度,数组的答案部分是[0,j-1],长度为j
var removeElement = function(nums, val) {// i>=jlet i=0,j=0;for(;iif(nums[i]!=val){nums[j++]=nums[i];         }}return j;
};

977. 有序数组的平方(双指针)

977. 有序数组的平方

  • 双指针
  • 非递减:递增有相同
  • 若是全正或全负,数组的平方是单调的
  • 若有正有负,数组的平方是点减后增:两端大,中间小
  • 双指针ij,一头一尾,大的进答案
var sortedSquares = function(nums) {// 非递减:递增有相同let n=nums.length;let ans=new Array(n).fill(0);for(let i=0,j=n-1,k=n-1;i<=j;k--){let ii=nums[i]*nums[i];let jj=nums[j]*nums[j];if(ii>=jj){ans[k]=ii;i++;}else{ans[k]=jj;j--;}}return ans;
};

209. 长度最小的子数组(滑动窗口)

209. 长度最小的子数组

  • 双指针:滑动窗口
  • 窗口为从l到r
  • 但凡当前sum>=target,保存ans=min(ans,当前长度)(于是会保存所有长度的最小长度),然后另l++
  • 若sum=target的条件)
var minSubArrayLen = function(target, nums) {const n=nums.length;let l=0,r=0,sum=0,ans=n+1;while(rsum+=nums[r++];while(sum>=target){// 让窗口变小:左闭右开if(r-l

59.螺旋矩阵II(模拟)

59.螺旋矩阵II

var generateMatrix = function (n) {// 二维数组let ans = new Array(n).fill(0).map(() => new Array(n).fill(0));let x = 0, y = -1;let now = 1;while (now <= n * n) {// 右while (y + 1 < n && ans[x][y + 1] === 0) {ans[x][y + 1] = now++;y++;}if (now > n * n) break;// 下while (x + 1 < n && ans[x + 1][y] === 0) {ans[x + 1][y] = now++;x++;}if (now > n * n) break;// 左while (y - 1 >= 0 && ans[x][y - 1] === 0) {ans[x][y - 1] = now++;y--;}if (now > n * n) break;// 上while (x - 1 >= 0 && ans[x - 1][y] === 0) {ans[x - 1][y] = now++;x--;}}return ans;
};

相关题目推荐

都是和“主要题目”相似的题目。

35. 搜索插入位置(二分)

35. 搜索插入位置

  • 二分
  • 要先判断范围:最大与最小:目标值不在数组中
  • 这里是左闭右闭,所以while循环条件为i<=j
  • 若没有找到,则一定是i++到了j的位置或j- -到了i
  • 即:没找到之前一定ij重叠
  • 若目标值大于ij所指向的值,则i=mid+1,即:j i,此时跳出循环,i为答案
  • 若小于:不可能存在这种情况,原因:
  • 除法会向下取整,且题目说明数组无重复
  • 如:在[1 3]中找2,mid指向的会是1,而不会是2
  • 又如:在[0 1]、[3 4]中找2,显然我们在找2时不会找到这样的区间
  • ps:若强行存在目标值小于ij重叠所指向的值,只可能是在数组范围外(即目标值是最小值)
  • 省流:
  • 先判断目标值大小是否在数组区间中
  • 判断目标值是否在数组中存在,若存在可以直接二分找到
  • 否则:ij一定会重叠,由于目标值大小在数组区间中,即:ij 目标值,此时i++,跳出循环,为答案
var searchInsert = function(nums, target) {let n=nums.length-1;if(target>nums[n]){return n+1;}if(targetreturn 0;}let i=0,j=n;let mid=(i+j)>>1;while(i<=j){if(nums[mid]===target){return mid;}if(nums[mid]>target){j=mid-1;}else{i=mid+1;}mid=(i+j)>>1;}// 走到这里说明没有且i>jreturn i;
};

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

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

一道细节比较多的题:

  • 二分
  • 分类讨论:target在数组区间范围外;target在数组区间范围内(target数组中,target不在数组中)
  • 若存在:
  • 想要找到target的第一个位置和最后一个位置:相当于找到最后一个小于target和第一个大于target的位置(也可以直接找,不需要+1-1,在本题末尾)
  • 最后一个小于target的位置:
  • 第一个target位置-1
  • 想象:一个数组,分为小于target和大于等于target的,则第一个等于target的位置-1就是最后一个小于目标的位置
  • 满足>=每次都会更新,最后留下来的一定是第一个等于的-1
  • 第一个大于target的位置:同理
  • 每一次<=都会更新,最后留下来的是最后一个=target的位置+1

分别对应getLeftgetRight

注意:

target是否在范围内

  • 要初始化一个值来验证target是否在范围内
  • 此值要小于等于-2
  • 因为-1可能是有mid为0,ans更新为mid-1得到
  • 左右边界但凡有一个ans为-2则表示target不在范围内

target是否存在

  • 如[1 3]中找2,left指向1,right指向3,right-left=1
  • 若right-left>1则存在,否则不存在

getLeft

const getLeft=function(nums,target){let l=0,r=nums.length-1;let mid=(l+r)>>1;let ans=-2;while(l<=r){mid=(l+r)>>1;if(nums[mid]>=target){r=mid-1;// 大于等于都要变,留下的是最右边的小于ans=r;}else{l=mid+1;}}return ans;
}

getRight

// 找右边界:第一个大于target的
const getRight=function(nums,target){let l=0,r=nums.length-1;let mid=(l+r)>>1;let ans=-2;while(l<=r){mid=(l+r)>>1;if(nums[mid]>target){r=mid-1;}else{l=mid+1;// 小于等于都要变,最后留下的是最左边的大于ans=l;}}return ans;
}

总体代码:

var searchRange = function(nums, target) {// 找左边界:最后一个小于target的const getLeft=function(nums,target){let l=0,r=nums.length-1;let mid=(l+r)>>1;let ans=-2;while(l<=r){mid=(l+r)>>1;if(nums[mid]>=target){r=mid-1;// 大于等于都要变,留下的是最右边的小于ans=r;}else{l=mid+1;}}return ans;}// 找右边界:第一个大于target的const getRight=function(nums,target){let l=0,r=nums.length-1;let mid=(l+r)>>1;let ans=-2;while(l<=r){mid=(l+r)>>1;if(nums[mid]>target){r=mid-1;}else{l=mid+1;// 小于等于都要变,最后留下的是最左边的大于ans=l;}}return ans;}let left=getLeft(nums,target);let right=getRight(nums,target);// 范围外if(left===-2||right===-2){return [-1,-1]}// 存在if(right-left>1) {return[left+1,right-1];}// 不存在return [-1,-1]};

直接找第一个和最后一个target也可以:但感觉上面的方法边界的差异感强一些,更好理解。

var searchRange = function(nums, target) {// 找左边界:最后一个小于target的const getLeft=function(nums,target){let l=0,r=nums.length-1;let mid=(l+r)>>1;let ans=-2;while(l<=r){mid=(l+r)>>1;if(nums[mid]>=target){r=mid-1;// 大于等于都要变,留下的是第一个targetans=r+1;}else{l=mid+1;}}return ans;}// 找右边界:第一个大于target的const getRight=function(nums,target){let l=0,r=nums.length-1;let mid=(l+r)>>1;let ans=-2;while(l<=r){mid=(l+r)>>1;if(nums[mid]>target){r=mid-1;}else{l=mid+1;// 小于等于都要变,最后留下的是最后一个targetans=l-1;}}return ans;}let left=getLeft(nums,target);let right=getRight(nums,target);console.log(left,right)// 范围外if(left===-2||right===-2){return [-1,-1]}// 存在if(right-left>=0) {return[left,right];}// 不存在return [-1,-1]};

69. x 的平方根 (二分)

69. x 的平方根

  • 要求算术平方根,且去掉小数
  • 其实就是答案向下取整,即:
  • mid x mid<=x都要存在ans中,最后一次ans的赋值一定是 平方等于x的数 或 刚好小于x的数
var mySqrt = function(x) {let l=0,r=47000;let ans,mid;while(l<=r){mid=(l+r)>>1;// 小于等于都要存,最后保存的是最近的小于或直接等于if(mid*mid<=x){ans=mid;l=mid+1;}else {r=mid-1;}}return ans;
};

367. 有效的完全平方数(重复)

367. 有效的完全平方数

  • 跟上一题一样
var isPerfectSquare = function(num) {let l=0,r=47000;let mid,ans;while(l<=r){mid=(l+r)>>1;if(mid*mid<=num){ans=mid;l=mid+1;}else{r=mid-1;}}if(ans*ans===num) return true;else return false;
};

26. 删除有序数组中的重复项(双指针)

https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

  • 双指针
var removeDuplicates = function(nums) {let n=nums.length-1;let i=1,j=0;for(;i<=n;i++){if(nums[i]!=nums[j]){nums[++j]=nums[i];}}return j+1;
};

283. 移动零(双指针)

283. 移动零

  • 双指针
var moveZeroes = function(nums) {let n=nums.length-1;let i=0,j=0;for(;i<=n;i++){if(nums[i]){nums[j++]=nums[i];}}for(;j<=n;j++){nums[j]=0;}return nums;
};

844. 比较含退格的字符串(模拟)

844. 比较含退格的字符串

  • 模拟
  • cnt表示要还有多少#
var backspaceCompare = function(s, t) {let ss='',tt='';let cnt=0;for(let i=s.length-1;i>=0;i--){if(cnt){if(s[i]==='#'){cnt++;}else{cnt--;}}else{if(s[i]==='#'){cnt++;}else{ss+=s[i];}}}cnt=0;for(let i=t.length-1;i>=0;i--){if(cnt){if(t[i]==='#'){cnt++;}else{cnt--;}}else{if(t[i]==='#'){cnt++;}else{tt+=t[i];}}}// console.log(ss,tt)if(ss===tt) return true;else return false;
};

904. 水果成篮(滑动窗口)

904. 水果成篮

  • 滑动窗口
  • 跟209很像,加上了Map的运用
var totalFruit = function(fruits) {const n=fruits.length;const map=new Map();let l=0,r=0,ans=0;for(;r// 放新的map.set(fruits[r],(map.get(fruits[r])||0)+1);if(map.size>2){map.set(fruits[l],map.get(fruits[l])-1);if(map.get(fruits[l])===0){map.delete(fruits[l])}l++;          }ans=Math.max(ans,r-l+1);}return ans;
};

76. 最小覆盖子串(滑动窗口)

76. 最小覆盖子串

相关内容

热门资讯

喜欢穿一身黑的男生性格(喜欢穿... 今天百科达人给各位分享喜欢穿一身黑的男生性格的知识,其中也会对喜欢穿一身黑衣服的男人人好相处吗进行解...
发春是什么意思(思春和发春是什... 本篇文章极速百科给大家谈谈发春是什么意思,以及思春和发春是什么意思对应的知识点,希望对各位有所帮助,...
网络用语zl是什么意思(zl是... 今天给各位分享网络用语zl是什么意思的知识,其中也会对zl是啥意思是什么网络用语进行解释,如果能碰巧...
为什么酷狗音乐自己唱的歌不能下... 本篇文章极速百科小编给大家谈谈为什么酷狗音乐自己唱的歌不能下载到本地?,以及为什么酷狗下载的歌曲不是...
家里可以做假山养金鱼吗(假山能... 今天百科达人给各位分享家里可以做假山养金鱼吗的知识,其中也会对假山能放鱼缸里吗进行解释,如果能碰巧解...
华为下载未安装的文件去哪找(华... 今天百科达人给各位分享华为下载未安装的文件去哪找的知识,其中也会对华为下载未安装的文件去哪找到进行解...
四分五裂是什么生肖什么动物(四... 本篇文章极速百科小编给大家谈谈四分五裂是什么生肖什么动物,以及四分五裂打一生肖是什么对应的知识点,希...
怎么往应用助手里添加应用(应用... 今天百科达人给各位分享怎么往应用助手里添加应用的知识,其中也会对应用助手怎么添加微信进行解释,如果能...
客厅放八骏马摆件可以吗(家里摆... 今天给各位分享客厅放八骏马摆件可以吗的知识,其中也会对家里摆八骏马摆件好吗进行解释,如果能碰巧解决你...
苏州离哪个飞机场近(苏州离哪个... 本篇文章极速百科小编给大家谈谈苏州离哪个飞机场近,以及苏州离哪个飞机场近点对应的知识点,希望对各位有...