当前位置： 首页 > news >正文

LeetCode热题100JS（69/100）第十三天|34|33|153|4|20

news 2025/3/28 19:14:18

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

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

难度：中等

刷题状态：2刷

新知识：

解题过程

思考

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
题解分析

参考题解链接：【视频讲解】二分查找总是写不对？三种写法，一个视频讲透！（Python/Java/C++/C/Go/JS）

放下1刷过程

/*** @param {number[]} nums* @param {number} target* @return {number[]}*/
var searchRange = function(nums, target) {let start=startPos(nums, target)let end=startPos(nums, target+1)-1// console.log('start',start)// console.log('end',end)if(nums[start]!=target){return [-1,-1]}return [start,end]
};
function startPos(nums, target){const n=nums.lengthlet left=0let right=n-1while(left<=right){const mid=Math.floor((left+right)/2)//2/4if(nums[mid]>=target){right=mid-1}else{left=mid+1}}return left
}

手搓答案（无非废话版）

/*** @param {number[]} nums* @param {number} target* @return {number[]}*/var searchRange=function(nums,target){let n=nums.length,start,endfunction startPos(tar){let left=0,right=n-1while(left<=right){let mid=((right-left)>>1)+leftif(nums[mid]<tar){left=mid+1}else{right=mid-1}}return left}start=startPos(target)end=startPos(target+1)-1if(nums[start]!=target) return [-1,-1]return [start,end]}

总结

 注意while(left<=right)这里要判断=的情况也要循环一次

 33. 搜索旋转排序数组

题目链接：33. 搜索旋转排序数组

难度：中等

刷题状态：2刷

新知识：

解题过程

思考

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
题解分析

参考题解链接：搜索旋转排序数组

放下1刷过程

/*** @param {number[]} nums* @param {number} target* @return {number}*/
var search = function(nums, target) {//[4,5,6,7,0,1,2]   5//[5,6,7,0,1,2,4]   5const n=nums.lengthlet min=Math.min(...nums)let max=Math.max(...nums)let left=0let right=n-1let res=-1if(nums[left]==target){return 0}if(nums[right]==target){return n-1}if(n==1){return nums[0]==target?0:-1}while(left+1<right){let mid=((right-left)>>1)+left// console.log('mid',mid)//nums[0]  target nums[mid] max  左边,right=mid//nums[0]  nums[mid] target max  左边,left=mid//min  target nums[mid] nums[n-1]  右边,right=mid//min  nums[mid] target nums[n-1]  右边,left=mid//nums[0]  target max    min nums[mid] nums[n-1]  两边,right=mid//nums[0]  nums[mid] max    min target nums[n-1]  两边,left=midlet targetLr=(nums[0]<=target)&&(target<=nums[mid])&&(nums[0]<=max)let targetLl=(nums[0]<=nums[mid])&&(nums[mid]<=target)&&(target<=max)let targetRr=(min<=target)&&(target<=nums[mid])&&(nums[mid]<=nums[n-1])let targetRl=(min<=nums[mid])&&(nums[mid]<=target)&&(target<=nums[n-1])let targetTr=(nums[0]<=target)&&(target<=max)&&(min<=nums[mid])&&(nums[mid]<=nums[n-1])&&(nums[0]!=min)&&(nums[n-1]!=max)let targetTl=(nums[0]<=nums[mid])&&(nums[mid]<=max)&&(min<=target)&&(target<=nums[n-1])&&(nums[0]!=min)&&(nums[n-1]!=max)// console.log(targetLr,targetLl,targetRr,targetRl,targetTr,targetTl)if(nums[mid]==target){res=midbreak}else if(targetLr||targetRr||targetTr){right=mid}else if(targetLl||targetRl||targetTl){left=mid}else{break}// console.log('left',left)// console.log('right',right)}return res
};

手搓答案（无非废话版）

/*** @param {number[]} nums* @param {number} target* @return {number}*/var search=function(nums,target){let n=nums.lengthif(n==0) return -1if(n==1) return nums[0]==target?0:-1let left=0,right=n-1while(left<=right){//console.log(left,right)let mid=((right-left)>>1)+leftif(nums[mid]==target) return midif(nums[0]<=nums[mid]){if(nums[0]<=target&&target<=nums[mid]){right=mid-1}else{left=mid+1}}else{if(nums[mid]<=target&&target<=nums[n-1]){left=mid+1}else{right=mid-1}}}return -1}

总结

 应该用手搓答案里面的，保证时间复杂度为 O(log n)

 ​​​​​​​​​​​​​​​​​​​​​153. 寻找旋转排序数组中的最小值

题目链接：​​​​​​​153. 寻找旋转排序数组中的最小值

难度：中等

刷题状态：2刷

新知识：

解题过程

思考

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
题解分析

参考题解链接：​​​​​​​和最后一个数比大小，简洁二分（Python/Java/C++/C/Go/JS/Rust）

放下1刷过程

/*** @param {number[]} nums* @return {number}*/
var findMin = function(nums) {//[3,4,5,1,2]//[4,5,1,2,3]const n=nums.lengthlet left=-1let right=n-1//4while(left+1<right){let mid=((right-left)>>1)+left//2if(nums[mid]>nums[n-1]){left=mid}else{right=mid}// console.log('nums[left]',nums[left])// console.log('nums[right]',nums[right])}return nums[right]// return Math.min(...nums)
};

手搓答案（无非废话版）

/*** @param {number[]} nums* @return {number}*/var findMin=function(nums){let n=nums.length,res=nums[0]let left=0,right=n-1while(left<=right){let mid=((right-left)>>1)+leftif(nums[mid]>nums[n-1]){left=mid+1}else{right=mid-1}}return nums[left]}

总结

 拿下

 ​​​​​​​​​​​​​​4. 寻找两个正序数组的中位数

题目链接：​​​​​​​​​​​​​​4. 寻找两个正序数组的中位数

难度：困难

刷题状态：1刷

新知识：

解题过程

思考

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

想不出来，直接看答案

题解分析

参考题解链接：​​​​​​​​​​​​​​详细通俗的思路分析，多解法

详细分析如下

/*** @param {number[]} nums1* @param {number[]} nums2* @return {number}*/
var findMedianSortedArrays = function(nums1, nums2) {let m=nums1.length,n=nums2.length,A=nums1,B=nums2if(m>n) return findMedianSortedArrays(B,A)//初始化二分查找的边界let imin=0,imax=mwhile(imin<=imax){//计算当前的分割点i j//i 是在数组 A 中的分割点索引。它表示在数组 A 中，有 i 个元素位于左半部分，剩下的 m - i 个元素位于右半部分（其中 m 是数组 A 的长度）。j同理let i=Math.floor((imin+imax)/2)
//  i + j = m - i  + n - j  + 1也就是 j = ( m + n + 1) / 2 - ilet j=Math.floor((m+n+1)/2)-i//检查分割是否有效，如果B[j-1]>A[i]，说明要增大iif(j&&i!=m&&B[j-1]>A[i]){imin=i+1} //如果A[i-1]>B[j]，说明要减小ielse if(i&&j!=n&&A[i-1]>B[j]){imax=i-1} //分割有效，处理边界条件else{let macLeft=0//左半部分最大值在B[j-1]if(i==0){maxLeft=B[j-1]} //左半部分最大值在A[i-1]else if(j==0){maxLeft=A[i-1]}//否则，左半部分的最大值是A[i-1],B[j-1]的较大值else{maxLeft=Math.max(A[i-1],B[j-1])}//奇数，返回maxLeftif((m+n)%2==1) return maxLeft//偶数let minRight=0//右半部分最小值在B[j]if(i==m) {minRight=B[j]}//右半部分最小值在A[i]else if(j==n) {minRight=A[i]}//否则，右半部分最大值是A[i],B[j]的较小值else{minRight=Math.min(A[i],B[j])}return (maxLeft+minRight)/2.0}}
};

手搓答案（无非废话版）

/*** @param {number[]} nums1* @param {number[]} nums2* @return {number}*/var findMedianSortedArrays=function(nums1,nums2){let m=nums1.length,n=nums2.length,A=nums1,B=nums2if(m>n) return findMedianSortedArrays(nums2,nums1)let imin=0,imax=mwhile(imin<=imax){let i=Math.floor((imin+imax)/2)let j=Math.floor((m+n+1)/2)-iif(j&&i!=m&&B[j-1]>A[i]) {imin=i+1}else if(i&&j!=n&&A[i-1]>B[j]) {imax=i-1}else{let maxLeft=0if(i==0){maxLeft=B[j-1]}else if(j==0){maxLeft=A[i-1]}else{maxLeft=Math.max(A[i-1],B[j-1])}if((m+n)%2==1) return maxLeftlet minRight=0if(i==m) {minRight=B[j]}else if(j==n) {minRight=A[i]}else{minRight=Math.min(A[i],B[j])}return (maxLeft+minRight)/2.0}}}

总结

不好理解，其实有更简单的方法，但这种方法是字节笔试考过的

 ​​​​​​​​​​​​​​20. 有效的括号

题目链接：​​​​​​​​​​​​​​​​​​​​​20. 有效的括号

难度：简单

刷题状态：1刷

新知识：

解题过程

思考

示例 1：

输入：s = "()"

输出：true

用数组模拟栈

括号必须以正确的顺序闭合：这意味着括号不能交叉匹配。例如，([)] 是无效的

题解分析

参考题解链接：​​​​​​​​​​​​​​有效的括号

详细分析如下

/*** @param {string} s* @return {boolean}*/
var isValid = function(s) {let n=s.length,arr=[]if(n%2==1) return falsefor(let i=0;i<n;i++){if(s[i]=='(') arr.push(')')else if(s[i]=='{') arr.push('}')else if(s[i]=='[') arr.push(']')//核心思想//用数组来模拟栈的表达方式else if(arr.length==0||arr[arr.length-1]!=s[i]){return false}else{arr.pop()}}//如果arr没pop完，说明不符合return arr.length==0
};

手搓答案（无非废话版）

/*** @param {string} s* @return {boolean}*/var isValid=function(s){let n=s.length,arr=[]for(let i=0;i<n;i++){let c=s[i]if(c=='(') {arr.push(')')}else if(c=='{') {arr.push('}')}else if(c=='[') {arr.push(']')}else if(arr.length==0||arr[arr.length-1]!=c){return false}else{ arr.pop()}}return arr.length==0}

总结

拿下


http://www.mrgr.cn/news/95762.html

相关文章：

  • 2025-3-24 leetcode刷题情况（动态规划——01背包）
  • 【HTML5游戏开发教程】零基础入门合成大西瓜游戏实战 | JS物理引擎+Canvas动画+完整源码详解
  • stm32-IIC
  • 运动仿真——phased.Platform
  • 手动创建Electron+React项目框架（建议直接看最后）
  • 项目日记 -云备份 -服务端配置信息模块
  • Spatial Multiplexing Power Save
  • Spring Boot整合SSE实现消息推送：跨域问题解决与前后端联调实战
  • 排序算法（插入，希尔，选择，冒泡，堆，快排，归并）
  • python-58-基于python的两种方式操作windows安装的pg数据库
  • 【江协科技STM32】Unix时间戳（学习笔记）
  • tortoiseSVN、source insignt、J-flash使用
  • python --face_recognition(人脸识别,检测,特征提取,绘制鼻子,眼睛,嘴巴,眉毛)/活体检测
  • 【MySQL】一篇讲懂什么是聚簇索引和非聚簇索引(二级索引)以及什么是回表？
  • 基于PySide6的CATIA自动化工具开发实战——空几何体批量清理系统
  • 矩阵补充，最近邻查找
  • 流程控制语句
  • 【渗透测试】Fastjson 反序列化漏洞原理（一）
  • 算法训练营第二十三天 | 贪心算法（一）
  • GithubPages+自定义域名+Cloudfare加速+浏览器收录（2025最新排坑）