感觉关于JavaScript的题解不太多,所以就写一个,给自己总结用。
https://www.programmercarl.com/
704. 二分查找
>>
位运算移动,因为直接/2会产生小数mid+1
和mid-1
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. 移除元素
var removeElement = function(nums, val) {// i>=jlet i=0,j=0;for(;iif(nums[i]!=val){nums[j++]=nums[i]; }}return j;
};
977. 有序数组的平方
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. 长度最小的子数组
ans=min(ans,当前长度)
(于是会保存所有长度的最小长度),然后另l++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
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. 搜索插入位置
i<=j
j i
,此时跳出循环,i为答案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. 在排序数组中查找元素的第一个和最后一个位置
一道细节比较多的题:
最后一个小于目标的位置
分别对应getLeft
和getRight
。
注意:
target是否在范围内
target是否存在
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 的平方根
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. 有效的完全平方数
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;
};
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. 移动零
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. 比较含退格的字符串
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. 水果成篮
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. 最小覆盖子串