js算法题库及答案

js算法题库及答案数组与哈希表1.两数之和题目：给定一个整数数组nums和一个整数目标值target，找出数组中和为target的两个整数的下标，返回它们的数组下标。假设每个输入只存在一个有效答案，且同一元素不能重复使用。思路：使用哈希表存储已遍历元素及其下标。遍历数组时，计算当前元素与目标值的差值，若差值存在于哈希表中，则返回对应下标；否则将当前元素存入哈希表。代码：```javascriptfunctiontwoSum(nums,target){constmap=newMap();for(leti=0;i<nums.length;i++){constcomplement=targetnums[i];if(map.has(complement)){return[map.get(complement),i];}map.set(nums[i],i);}return[];}```2.数组去重（保留顺序）题目：给定一个可能包含重复元素的数组，返回去重后的数组，要求保留元素出现的顺序。思路：使用Set记录已出现的元素，遍历数组，若元素未在Set中则加入结果数组，并将元素存入Set。代码：```javascriptfunctionuniqueArray(arr){constseen=newSet();constres=[];for(constitemofarr){if(!seen.has(item)){seen.add(item);res.push(item);}}returnres;}```3.最长无重复字符的子串题目：给定一个字符串s，找出其中不包含重复字符的最长子串的长度。思路：滑动窗口法。用左右指针表示窗口的左右边界，哈希表记录字符最后出现的位置。右指针遍历字符串，若当前字符在窗口内重复（即其最后出现位置≥左指针），则将左指针移动到重复位置的下一位。每次更新窗口的最大长度。代码：```javascriptfunctionlengthOfLongestSubstring(s){letmaxLen=0;letleft=0;constmap=newMap();for(letright=0;right<s.length;right++){constchar=s[right];if(map.has(char)&&map.get(char)>=left){left=map.get(char)+1;}map.set(char,right);maxLen=Math.max(maxLen,rightleft+1);}returnmaxLen;}```4.接雨水题目：给定n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子能接多少雨水。思路：双指针法。维护左右指针和左右最大高度。左指针从左往右，右指针从右往左。若左最大高度小于右最大高度，处理左指针（当前左高度小于左最大则累加雨水，否则更新左最大）；反之处理右指针。代码：```javascriptfunctiontrap(height){letleft=0,right=height.length1;letleftMax=0,rightMax=0;letres=0;while(left<right){leftMax=Math.max(leftMax,height[left]);rightMax=Math.max(rightMax,height[right]);if(leftMax<rightMax){res+=leftMaxheight[left];left++;}else{res+=rightMaxheight[right];right--;}}returnres;}```字符串操作1.最长回文子串题目：给定一个字符串s，找到s中最长的回文子串。思路：中心扩展法。遍历每个字符（奇数长度中心）和每对字符（偶数长度中心），向两边扩展直到无法形成回文，记录最长回文的起始位置和长度。代码：```javascriptfunctionlongestPalindrome(s){if(s.length<2)returns;letstart=0,maxLen=0;//扩展函数constexpand=(left,right)=>{while(left>=0&&right<s.length&&s[left]===s[right]){if(rightleft+1>maxLen){maxLen=rightleft+1;start=left;}left--;right++;}};for(leti=0;i<s.length;i++){expand(i,i);//奇数长度expand(i,i+1);//偶数长度}returns.substring(start,start+maxLen);}```2.有效的括号题目：给定一个只包含'()[]{}'的字符串s，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合，且顺序正确。思路：栈结构。遍历字符串，遇到左括号入栈；遇到右括号时，若栈为空或栈顶左括号不匹配则返回false，否则出栈。最后检查栈是否为空。代码：```javascriptfunctionisValid(s){conststack=[];constmap={')':'(',']':'[','}':'{'};for(constcharofs){if(Object.values(map).includes(char)){stack.push(char);}else{if(stack.length===0||stack[stack.length1]!==map[char]){returnfalse;}stack.pop();}}returnstack.length===0;}```3.字符串转换整数(atoi)题目：实现一个将字符串转换为整数的函数，需处理以下情况：忽略前导空格，判断符号，读取数字字符直到非数字字符，转换为整数（超出范围则返回±2^31）。思路：逐字符处理。跳过空格，确定符号，遍历数字字符累加值，每次检查是否溢出。代码：```javascriptfunctionmyAtoi(s){leti=0,sign=1,res=0;constlen=s.length;//跳过空格while(s[i]==='')i++;//处理符号if(s[i]==='+'||s[i]==='-'){sign=s[i]==='-'?-1:1;i++;}//处理数字constmax=2311,min=-(231);while(i<len&&/\d/.test(s[i])){res=res10+Number(s[i]);//检查溢出if(res>max){returnsign===1?max:min;}i++;}returnressign;}```链表操作1.反转链表题目：反转一个单链表。思路：迭代法。维护三个指针：prev（前一个节点）、curr（当前节点）、next（下一个节点）。遍历链表时，将当前节点的next指向prev，然后更新prev、curr为当前节点和原next。代码：```javascriptfunctionreverseList(head){letprev=null,curr=head;while(curr){constnext=curr.next;curr.next=prev;prev=curr;curr=next;}returnprev;}```2.合并两个有序链表题目：将两个升序链表合并为一个新的升序链表并返回。思路：递归法。比较两个链表头节点的值，将较小值的节点作为当前节点，递归合并剩余部分。代码：```javascriptfunctionmergeTwoLists(l1,l2){if(!l1)returnl2;if(!l2)returnl1;if(l1.val<l2.val){l1.next=mergeTwoLists(l1.next,l2);returnl1;}else{l2.next=mergeTwoLists(l1,l2.next);returnl2;}}```3.环形链表题目：判断链表中是否有环。思路：快慢指针法。快指针每次走两步，慢指针每次走一步。若存在环，快慢指针会相遇；否则快指针会到达链表末尾。代码：```javascriptfunctionhasCycle(head){if(!head||!head.next)returnfalse;letslow=head,fast=head.next;while(slow!==fast){if(!fast||!fast.next)returnfalse;slow=slow.next;fast=fast.next.next;}returntrue;}```树与二叉树1.二叉树的中序遍历题目：给定二叉树的根节点root，返回它的中序遍历（左-根-右）。思路：迭代法。使用栈模拟递归过程。遍历左子树直到最左节点，弹出栈顶节点并访问，然后转向右子树。代码：```javascriptfunctioninorderTraversal(root){constres=[];conststack=[];letcurr=root;while(curr||stack.length){while(curr){stack.push(curr);curr=curr.left;}curr=stack.pop();res.push(curr.val);curr=curr.right;}returnres;}```2.二叉树的最大深度题目：给定二叉树的根节点root，返回其最大深度（根节点到最远叶子节点的最长路径上的节点数）。思路：递归法。最大深度为左子树和右子树的最大深度加1（当前节点）。代码：```javascriptfunctionmaxDepth(root){if(!root)return0;returnMath.max(maxDepth(root.left),maxDepth(root.right))+1;}```3.对称二叉树题目：判断二叉树是否是对称的（即根节点的左右子树镜像对称）。思路：递归法。比较左右子树的外侧节点和内侧节点是否相等。代码：```javascriptfunctionisSymmetric(root){if(!root)returntrue;constcheck=(left,right)=>{if(!left&&!right)returntrue;if(!left||!right)returnfalse;returnleft.val===right.val&&check(left.left,right.right)&&check(left.right,right.left);};returncheck(root.left,root.right);}```动态规划1.爬楼梯题目：假设你正在爬楼梯，需要n阶才能到达楼顶。每次可以爬1或2阶，有多少种不同的方法爬到楼顶？思路：动态规划。dp[i]表示爬到第i阶的方法数。状态转移方程：dp[i]=dp[i-1]+dp[i-2]（最后一步爬1阶或2阶）。代码：```javascriptfunctionclimbStairs(n){if(n<=2)returnn;leta=1,b=2,c;for(leti=3;i<=n;i++){c=a+b;a=b;b=c;}returnb;}```2.最长递增子序列题目：给定一个整数数组nums，找到其中最长递增子序列的长度。思路：动态规划。dp[i]表示以nums[i]结尾的最长递增子序列长度。遍历每个元素，对于每个元素，遍历其之前的元素，若nums[j]<nums[i]，则dp[i]=max(dp[i],dp[j]+1)。代码：```javascriptfunctionlengthOfLIS(nums){constdp=newArray(nums.length).fill(1);letmaxLen=1;for(leti=1;i<nums.length;i++){for(letj=0;j<i;j++){if(nums[j]<nums[i]){dp[i]=Math.max(dp[i],dp[j]+1);}}maxLen=Math.max(maxLen,dp[i]);}returnmaxLen;}```3.最小路径和题目：给定一个包含非负整数的mxn网格grid，找出一条从左上角到右下角的路径（只能向右或向下移动），使得路径上的数字总和最小。思路：动态规划。dp[i][j]表示到达(i,j)的最小路径和。初始化首行和首列（只能从左边或上边到达），状态转移方程：dp[i][j]=grid[i][j]+min(dp[i-1][j],dp[i][j-1])。代码：```javascriptfunctionminPathSum(grid){constm=grid.length,n=grid[0].length;constdp=Array.from({length:m},()=>newArray(n).fill(0));dp[0][0]=grid[0][0];//初始化首行for(letj=1;j<n;j++){dp[0][j]=dp[0][j-1]+grid[0][j];}//初始化首列for(leti=1;i<m;i++){dp[i][0]=dp[i-1][0]+grid[i][0];}//填充剩余部分for(leti=1;i<m;i++){for(letj=1;j<n;j++){dp[i][j]=grid[i][j]+Math.min(dp[i-1][j],dp[i][j-1]);}}returndp[m-1][n-1];}```排序与查找1.快速排序题目：实现快速排序算法，对数组进行升序排序。思路：分治法。选择基准值（如数组中间元素），将数组分为小于基准和大于基准的两部分，递归排序两部分。代码：```java