计划：算法只刷codeTop前端部分前60题与一些补充题
场景手撕根据后续题单刷
全部题目都是最简单好记的最优解法
day2 共8道力扣
5. 最长回文子串 - 力扣（LeetCode）
/** * @param {string} s * @return {string} */ var longestPalindrome = function(s) { //回文子串，中间向两边扩散，分为奇数个和偶数个 let ans = ''; //遍历字符，分别进行奇偶扩散 for(let i = 0;i<s.length;i++){ help(i,i); help(i,i+1); } return ans; function help(m,n){ //正常情况下进行扩散 while(m>=0&&n<=s.length&&s[m]===s[n]){ m--;n++; } //扩散结束后，回文子串位置在m+1~n-1的范围内 //比较长度后选择更新ans if(n-m-1>ans.length){ ans = s.slice(m+1,n); } } };21. 合并两个有序链表 - 力扣（LeetCode）
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} list1 * @param {ListNode} list2 * @return {ListNode} */ var mergeTwoLists = function(list1, list2) { //两个升序链表合并为一个升序链表 //注意：此处list1和list2都是节点！！ //有剪枝内容：当一个链表处理完后，另一个可以直接放在后面 let head = new ListNode(); let cur = head;//当前处理的新的位置 //当两个节点都存在时 while(list1&&list2){ if(list1.val>list2.val){ cur.next = list2; list2 = list2.next; }else{ cur.next = list1; list1 = list1.next; } //更新cur的位置 cur = cur.next; } //处理剩余的 cur.next = list1===null?list2:list1; return head.next; };102. 二叉树的层序遍历 - 力扣（LeetCode）
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number[][]} */ var levelOrder = function(root) { //bfs 两个数组模拟队列 if(root === null)return []; const ans = []; let cur = [root];//当前处理的节点 while(cur.length!==0){ //只要cur还没有处理完 let val = [];//存放val答案 let next = [];//处理这一层的全部的子节点 //遍历每一个cur for(const node of cur){ if(node.left){ next.push(node.left); } if(node.right){ next.push(node.right); } val.push(node.val); } ans.push(val); cur = next; } return ans; };200. 岛屿数量 - 力扣（LeetCode）
/** * @param {character[][]} grid * @return {number} */ var numIslands = function(grid) { //岛屿——上下左右都是水 岛屿问题常用dfs深度优先算法来解决 //如何判断某几个陆地是同一个岛屿？ //沉岛法-每发现一个1就把整个岛屿变成2，就能排除掉周围同属一片岛屿的其他陆地 //'1'指陆地 '2'指岛屿 '0'指海水 const m = grid.length;//行数 const n = grid[0].length;//列数 let ans = 0; for(let i = 0;i<m;i++){ for(let j = 0;j<n;j++){ if(grid[i][j] === '1'){ ans++; dfs(i,j); } } } return ans; function dfs(i,j){ //到达边界 if(i<0||j<0||i>=m||j>=n||grid[i][j]!=='1'){ return ; } //正常情况下:是陆地 grid[i][j] = '2'; //进行四面探索直到整个连接的陆地全部变成岛屿 dfs(i+1,j); dfs(i-1,j); dfs(i,j+1); dfs(i,j-1); } };33. 搜索旋转排序数组 - 力扣（LeetCode）
/** * @param {number[]} nums * @param {number} target * @return {number} */ var search = function(nums, target) { //原先升序排列 从某个下标为起点 前面的数放到后面去了 //要求 时间复杂度logn 比直接扫描比较的n要快 查找某个数——对时间复杂度进行优化 //二分法查找+剪枝？ //二分法找有序侧 //升序螺旋 mid左右至少有一侧是有序 //按照大小比较，按道理左边应该比右边大，来判断哪边有序 let ans = -1; let left = 0; let right = nums.length-1; //进入二分 while(left<=right){ let mid = Math.floor(left + (right - left) / 2); //特殊情况 if(nums[mid] === target)return mid; //右边有序 if(nums[mid]<=nums[right]){ //寻找target if(target>nums[mid]&&target<=nums[right]){ //缩小范围到除掉原mid left = mid+1; }else{ right = mid-1; } } else if(nums[mid]>=nums[left]){ if(target<nums[mid]&&target>=nums[left]){ right = mid-1; }else{ left = mid+1; } } } return ans; };1. 两数之和 - 力扣（LeetCode）
/** * @param {number[]} nums * @param {number} target * @return {number[]} */ //一边找一边存 var twoSum = function(nums, target) { //时间复杂度<n^2 空间换时间 //哈希表存储 const map = new Map(); //遍历进行逐个存储与查找 for(let i = 0;i<nums.length;i++){ if(map.has(target-nums[i])){ return [i,map.get(target-nums[i])]; } map.set(nums[i],i); } };46. 全排列 - 力扣（LeetCode）
/** * @param {number[]} nums * @return {number[][]} */ var permute = function(nums) { //全排列-回溯-dfs深度优先 const n = nums.length; //ans 已经生成结束的path数组进行slice后加入？ const ans = []; //path 当前正在生成的路径 const path = new Array().fill(0); //used 表示一个过程中已经使用后的标记 const used = new Array(n).fill(false); dfs(0); return ans; function dfs(i){ //对第i个位置进行回溯的填入 //若是某个数字没被使用过-状态改为used-放入path-进行剩下的回溯-恢复现场，还原回没被使用过 //全部位置都处理完了 if(i === n){ ans.push(path.slice()); return ; } //一般情况下，遍历寻找没被处理过的数字 for(let a = 0;a<n;a++){ if(used[a]===false){ used[a] = true; path[i] = nums[a]; dfs(i+1); used[a] = false; } } } };88. 合并两个有序数组 - 力扣（LeetCode）
/** * @param {number[]} nums1 * @param {number} m * @param {number[]} nums2 * @param {number} n * @return {void} Do not return anything, modify nums1 in-place instead. */ var merge = function(nums1, m, nums2, n) { //递增顺序的数组，合并后全在nums1中 //因为nums1初始长度为m+n，从后面倒数来进行摆放，就不会将原来的数字覆盖了 let cur = m+n-1; let a = m-1; let b = n-1; while(a>=0&&b>=0){ //当两个数组都还没处理完时，进行比较，任何一个处理完后，剩余的直接放入前面位置 if(nums1[a]>=nums2[b]){ nums1[cur] = nums1[a]; cur--;a--; }else{ nums1[cur] = nums2[b]; cur--;b--; } } //任何一个被处理完，若是nums2没被处理完，将其放入前面 if(b>=0){ for(let k = 0;k<=b;k++){ nums1[k] = nums2[k]; } } };
