1.两数之和
思路一：两个for循环
var twoSum = function(nums, target) { for(let i=0;i<nums.length;i++){ for(let j=i+1;j<nums.length;j++){ if(nums[i]+nums[j]==target){ return [i,j] } } } };
思路二：使用map存储
var twoSum = function(nums,target){ const map=new Map; for(let i=0;i<nums.length;i++){ const complement=target -nums[i]; if(map.has(complement)){ return [map.get(complement),i] }else{ map.set(nums[i],i); } } }
2.两数相加
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */ var addTwoNumbers = function(l1, l2) { let dummy=new ListNode();//dummy节点是用来定义一个新的节点，把加进来的东西往它后面穿 let cur=dummy; let carry=0; while(l1!==null||l2!=null){ let sum=0; if(l1!==null){ sum+=l1.val; l1=l1.next; } if(l2!==null){ sum+=l2.val; l2=l2.next; } sum+=carry; cur.next=new ListNode(sum%10); carry=Math.floor(sum/10); cur=cur.next; } if(carry>0){ cur.next=new ListNode(carry); } return dummy.next; };
3.无重复字符的最长字符串
var lengthOfLongestSubstring = function (s) { let start=0; let arr=[]; let max=0; for(start;start<s.length;start++){ if(!arr.includes(s[start])){ arr.push(s[start]) max = Math.max(max,arr.length) }else{ while(arr.includes(s[start])){ arr.shift(); } arr.push(s[start]) } } return max; };
4.寻找两个正序数组的中位数
var findMedianSortedArrays = function(nums1, nums2) { var arr=[...nums1,...nums2]; arr=arr.sort((a,b)=>{return a-b}) if((arr.length)%2==1){ return arr[(arr.length-1)/2] } if((arr.length)%2==0){ return (arr[(arr.length)/2]+arr[(arr.length)/2-1])/2 } };
5.最长回文字符串
笨法：
var longestPalindrome = function(s) { let arr=[]; let maxarr=[]; for(let i=0;i<s.length;i++){ if(s[i]==s[i+1]){ let arr=[s[i],s[i+1]]; maxarr.length>arr.length?(maxarr=maxarr):(maxarr=arr); let m=i-1;let n=i+2; while(m>=0&&n<s.length){ if(s[m]==s[n]){ arr=[s[m],...arr,s[n]]; maxarr.length>arr.length?(maxarr=maxarr):(maxarr=arr); }else{ break; } m--; n++; } } if(s[i]==s[i+2]){ let arr=[s[i],s[i+1],s[i+2]]; maxarr.length>arr.length?(maxarr=maxarr):(maxarr=arr); let m=i-1;let n=i+3; while(m>=0&&n<s.length){ if(s[m]==s[n]){ arr=[s[m],...arr,s[n]]; maxarr.length>arr.length?(maxarr=maxarr):(maxarr=arr); }else{ break; } m--; n++; } } } if(maxarr.length==0&&s){ return s[0]; } return maxarr.join(""); };
扩展：输出最长回文字符串的长度
var longestPalindrome = function(s) { let max=0; for(let i=0;i<s.length;i++){ for(let j=i+1;j<s.length;j++){ if(s[i]==s[j]){ let num=2; max=Math.max(num,max); let m=i-1;let n=j+1; while(m>=0&&n<s.length){ if(s[m]==s[n]){ num+=2; max=Math.max(num,max); }else{ break; } m--; n++; } } if(s[i]==s[j+1]){ let num=3; max=Math.max(num,max); let m=i-1;let n=j+1; while(m>=0&&n<s.length){ if(s[m]==s[n]){ num+=2; max=Math.max(num,max); }else{ break; } m--; n++; } } } } return max; };
6.N字形变化
var convert = function(s, numRows) { if (numRows === 1) return s; const rows = new Array(numRows).fill(""); const n = 2 * numRows - 2; for(let i = 0; i < s.length; i++) { const x = i % n; rows[Math.min(x, n - x)] += s[i]; } return rows.join(""); };
7.整数反转
var reverse = function(x) { if(x>Math.pow(2,32)-1||x<-Math.pow(2,31)){ return 0; } if(x<0){ x=x+""; x=x.split("").slice(1).reverse().join(""); x="-"+x; } else{ x=x+""; x=x.split("").reverse().join(""); } x=Number(x); if(x>Math.pow(2,31)-1||x<-Math.pow(2,31)){ return 0; } return x; };
8.字符串转换整数 (atoi)
/** * @param {string} s * @return {number} * 注意isNaN 的使用，它判定isNaN(" ")为false */ var myAtoi = function(s) { s=s.trim(); if(s[0]!="+"&&s[0]!="-"&&isNaN(s[0])){ return 0; } if(s[0]==="-"){ if(isNaN(s[1])||s[1]==" "){ return 0; }else{ for(let i=1;i<s.length;i++){ if(isNaN(s[i])||s[i]==" "){ return s.slice(0,i)>-1*Math.pow(2,31)?s.slice(0,i):-1*Math.pow(2,31); } } return s>-1*Math.pow(2,31)?s:-1*Math.pow(2,31); } } if(s[0]==="+"){ if(isNaN(s[1])||s[1]==" "){ return 0; }else{ for(let i=1;i<s.length;i++){ if(isNaN(s[i])||s[i]==" "){ return s.slice(0,i)>Math.pow(2,31)-1?Math.pow(2,31)-1:s.slice(0,i); } } return s>Math.pow(2,31)?Math.pow(2,31)-1:s; } } for(let i=0;i<s.length;i++){ if(isNaN(s[i])||s[i]==" "){ return s.slice(0,i)>Math.pow(2,31)?Math.pow(2,31)-1:s.slice(0,i); } } if(!isNaN(s)){ return s>Math.pow(2,31)-1?Math.pow(2,31)-1:s; } };
9.回文数
var isPalindrome = function(x) { x=x+""; // x.split("").reverse().join("")===x.split("").join("")?return true:return false; if( x.split("").reverse().join("")===x.split("").join("")){ return true; }else{ return false; } };
19.删除链表的倒数第N个节点
/* 链表中，定义dummy节点（哨兵节点）的作用： 1.作为新链表的头节点 2.处理一些极端情况 */
var removeNthFromEnd = function(head, n) { let dummy=new ListNode(); dummy.next=head; let n1=dummy; let n2=dummy; for(let i=0;i<=n;i++){ n2=n2.next; } while(n2!=null){ n1=n1.next; n2=n2.next; } n1.next=n1.next.next; return dummy.next; };
链接：
dp（动态规划）
思想：
感觉很像时高中数列的思想，给出首项，以及一个递推式子，让你求任意项的值。
步骤基本是： 寻找状态转移方程 => 建立合适的数据结构表 => 填表
var climbStairs = function(n) { let dp=[0,1,2]; for(let i=3;i<=n;i++){ dp[i]=dp[i-2]+dp[i-1]; } return dp[n]; };
var rob = function(nums) { if(nums.length === 0) return 0; if(nums.length === 1) return nums[0]; if(nums.length === 2) return Math.max(nums[0],nums[1]); let dp=[nums[0],Math.max(nums[0],nums[1])]; for(let i=2;i<nums.length;i++){ dp[i]=Math.max(dp[i-1],nums[i]+dp[i-2]) } return Math.max(dp[nums.length-1],dp[nums.length-2]) };
var rob = function(nums) { if(nums.length === 0) return 0; if(nums.length === 1) return nums[0]; if(nums.length === 2) return Math.max(nums[0],nums[1]); let dp=[nums[0],Math.max(nums[0],nums[1])]; for(let i=2;i<nums.length;i++){ dp[i]=Math.max(dp[i-1],nums[i]+dp[i-2]) } return Math.max(dp[nums.length-1],dp[nums.length-2]) };
var coinChange = function(coins, amount) { let dp = new Array( amount + 1 ).fill( Infinity ); dp[0] = 0; for (let i = 1; i <= amount; i++) { for (let coin of coins) { if (i - coin >= 0) { dp[i] = Math.min(dp[i], dp[i - coin] + 1); } } } return dp[amount] === Infinity ? -1 : dp[amount]; }
var uniquePaths = function(m, n) { let arr=[]; for(let i=0;i<n;i++){ arr.push([]); } for(let row=0;row<n;row++){ arr[row][0]=1; } for(let col=0;col<m;col++){ arr[0][col]=1; } for(let row=1;row<n;row++){ for(let col=1;col<m;col++){ arr[row][col]=arr[row-1][col]+arr[row][col-1]; } } return arr[n-1][m-1]; };
var maxProfit = function(prices) { let minPrices=prices[0]; let maxProfit=0; for(let i=0;i<prices.length;i++){ if(prices[i]<minPrices){ minPrices=prices[i] }else if((prices[i]-minPrices)>maxProfit){ maxProfit=prices[i]-minPrices; } } return maxProfit; };
var maxProfit = function(prices) { let profit = 0; for (let i = 0; i < prices.length - 1; i++) { if (prices[i + 1] > prices[i]){ profit += prices[i + 1] - prices[i]; } } return profit; };
二叉树
//递归
// var preorderTraversal = function(root) { // let arr=[]; // function pre(root){ // if(!root) return root; // arr.push(root.val); // pre(root.left); // pre(root.right); // } // pre(root); // return arr; // };
//非递归用迭代
var preorderTraversal = function(root) { if(root === null) return []; let res = [],stack = []; stack.push(root); while (stack.length){ let node = stack.pop(); res.push(node.val); node.right && stack.push(node.right); node.left && stack.push(node.left); } return res; };
//递归 // var postorderTraversal = function(root) { // let arr=[]; // function post(root){ // if(root==null) return root; // post(root.left); // post(root.right); // arr.push(root.val) // } // post(root); // return arr; // }; //非递归 var postorderTraversal = function(root) { if(root===null) return []; let stack=[]; let arr=[]; stack.push(root); while(stack.length){ let node=stack.pop(); arr.push(node.val); node.left&&stack.push(node.left); node.right&&stack.push(node.right); } return arr.reverse(); };
//递归 // var inorderTraversal = function(root) { // let arr=[]; // function post(root){ // if(root==null) return root; // post(root.left); // arr.push(root.val); // post(root.right); // } // post(root); // return arr; // }; //非递归 var inorderTraversal = function(root) { if(root === null) return []; let res = [],stack = []; stack.push(root); while (stack.length){ while(root !== null){ stack.push(root); root = root.left; } let node = stack.pop() res.push(node.val); root = node.right; } //根节点添加了两次 return res.slice(0,res.length-1); };