数组
疾速排序
function quickSort(arr, left, right) { if (left >= right) return const base = arr[left] let p = left, q = right while (p < q) { while (arr[q] > base && q >= p) { q-- } while (arr[p] < base && p <= q) { p++ } const temp = arr[q] arr[q] = arr[p] arr[p] = temp } arr[p] = base quickSort(arr, left, p) quickSort(arr, p + 1, right)}
归并排序
function mergeSort(arr) { if (arr.length <= 1) return arr const mid = Math.floor(arr.length / 2) const left = arr.slice(0, mid) const right = arr.slice(mid) const leftArr = mergeSort(left) const rightArr = mergeSort(right) const result = [] while (leftArr.length > 0 && rightArr.length > 0) { if (leftArr[0] < rightArr[0]) { result.push(leftArr.shift()) } else { result.push(rightArr.shift()) } } return result.concat(leftArr).concat(rightArr)}
两数之和
var twoSum = function (nums, target) { let hash = {}; for (let i = 0; i < nums.length; i++) { if (hash[target - nums[i]] !== undefined) { return [i, hash[target - nums[i]]]; } hash[nums[i]] = i; } return []; };
三数之和
var threeSum = function(nums) { const len = nums.length; if(len < 3) return []; nums.sort((a, b) => a - b); const resSet = new Set(); for(let i = 0; i < len - 2; i++) { if(nums[i] > 0) break; let l = i + 1, r = len - 1; while(l < r) { const sum = nums[i] + nums[l] + nums[r]; if(sum < 0) { l++; continue }; if(sum > 0) { r--; continue }; resSet.add(`${nums[i]},${nums[l]},${nums[r]}`); l++; r--; } } return Array.from(resSet).map(i => i.split(","));};
二分查找
var search = function(nums, target) { let left = 0, right = nums.length - 1; // 应用左闭右闭区间 while (left <= right) { let mid = left + Math.floor((right - left)/2); if (nums[mid] > target) { right = mid - 1; // 去右面闭区间寻找 } else if (nums[mid] < target) { left = mid + 1; // 去右面闭区间寻找 } else { return mid; } } return -1;};
螺旋矩阵遍历
var generateMatrix = function(n) { let startX = startY = 0; // 起始地位 let loop = Math.floor(n/2); // 旋转圈数 let mid = Math.floor(n/2); // 两头地位 let offset = 1; // 管制每一层填充元素个数 let count = 1; // 更新填充数字 let res = new Array(n).fill(0).map(() => new Array(n).fill(0)); while (loop--) { let row = startX, col = startY; // 上行从左到右（左闭右开） for (; col < startY + n - offset; col++) { res[row][col] = count++; } // 右列从上到下（左闭右开） for (; row < startX + n - offset; row++) { res[row][col] = count++; } // 上行从右到左（左闭右开） for (; col > startX; col--) { res[row][col] = count++; } // 左列做下到上（左闭右开） for (; row > startY; row--) { res[row][col] = count++; } // 更新起始地位 startX++; startY++; // 更新offset offset += 2; } // 如果n为奇数的话，须要独自给矩阵最两头的地位赋值 if (n % 2 === 1) { res[mid][mid] = count; } return res;};
合并两个有序数组
var merge = function(nums1, m, nums2, n) { let p1 = m - 1, p2 = n - 1; let tail = m + n - 1; var cur; while (p1 >= 0 || p2 >= 0) { if (p1 === -1) { cur = nums2[p2--]; } else if (p2 === -1) { cur = nums1[p1--]; } else if (nums1[p1] > nums2[p2]) { cur = nums1[p1--]; } else { cur = nums2[p2--]; } nums1[tail--] = cur; }};
随机排序
function shuffle(arr) { var i, j, temp; for (i = arr.length - 1; i > 0; i--) { j = Math.floor(Math.random() * (i + 1)); temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } return arr;}// 这个实现有问题 function shuffle(arr){ return arr.sort(function(){ return Math.random() - 0.5; });}
字符串
两数之和
var addStrings = function (num1, num2) { const result = [] let p = num1.length - 1 let q = num2.length - 1 let add = 0 while (p >= 0 || q >= 0 || add) { const x = p >= 0 ? Number(num1[p]) : 0 const y = q >= 0 ? Number(num2[q]) : 0 const sum = x + y + add result.unshift(sum % 10) add = Math.floor(sum / 10) p-- q-- } return result.join('')};
千分符格式化
var thousandSeparator = function(n) { let res = '' let count = 0 const str = n.toString() const len = str.length for(let i = len - 1; i >= 0; i--) { count++ if (count % 3 === 0 && i !== 0) { res = '.' + str[i] + res } else { res = str[i] + res } } return res};
无效括号
var isValid = function(s) { const n = s.length; if (n % 2 === 1) { return false; } const pairs = new Map([ [')', '('], [']', '['], ['}', '{'] ]); const stk = []; for (let ch of s){ if (pairs.has(ch)) { if (!stk.length || stk[stk.length - 1] !== pairs.get(ch)) { return false; } stk.pop(); } else { stk.push(ch); } }; return !stk.length;};
链表
反转链表
var reverseList = function(head) { let pre = null let cur = head while(cur !== null) { const temp = cur.next cur.next = pre pre = cur cur = temp } return pre};
删除链表倒数第N个结点
var removeNthFromEnd = function(head, n) { let ret = new ListNode() ret.next = head let p = ret, q = ret // p 先后退N while(n--) { p = p.next } // p 遍历到尾结点 while(p.next !== null) { p = p.next q = q.next } q.next = q.next.next return ret.next};
合并两个有序链表
var mergeTwoLists = function(l1, l2) { const prehead = new ListNode(-1); let prev = prehead; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { prev.next = l1; l1 = l1.next; } else { prev.next = l2; l2 = l2.next; } prev = prev.next; } // 合并后 l1 和 l2 最多只有一个还未被合并完，咱们间接将链表开端指向未合并完的链表即可 prev.next = l1 === null ? l2 : l1; return prehead.next;};
二叉树
深度优先遍历（递归和迭代）
// 递归var preorderTraversal = function(root) { let res=[]; const dfs=function(root){ if(root===null)return ; //先序遍历所以从父节点开始 res.push(root.val); //递归左子树 dfs(root.left); //递归右子树 dfs(root.right); } //只应用一个参数 应用闭包进行存储后果 dfs(root); return res;};// 迭代var preorderTraversal = function(root, res = []) { if(!root) return res; const stack = [root]; let cur = null; while(stack.length) { cur = stack.pop(); res.push(cur.val); cur.right && stack.push(cur.right); cur.left && stack.push(cur.left); } return res;};
档次遍历
var levelOrder = function(root) { //二叉树的层序遍历 let res=[],queue=[]; queue.push(root); if(root===null){ return res; } while(queue.length!==0){ // 记录以后层级节点数 let length=queue.length; //寄存每一层的节点 let curLevel=[]; for(let i=0;i<length;i++){ let node=queue.shift(); curLevel.push(node.val); // 寄存以后层下一层的节点 node.left&&queue.push(node.left); node.right&&queue.push(node.right); } //把每一层的后果放到后果数组 res.push(curLevel); } return res;};
最大深度
var maxdepth = function(root) { if (!root) return root return 1 + math.max(maxdepth(root.left), maxdepth(root.right))};
最近公共先人
var lowestCommonAncestor = function(root, p, q) { // 应用递归的办法 // 须要从下到上，所以应用后序遍历 // 1. 确定递归的函数 const travelTree = function(root,p,q) { // 2. 确定递归终止条件 if(root === null || root === p||root === q) { return root; } // 3. 确定递归单层逻辑 let left = travelTree(root.left,p,q); let right = travelTree(root.right,p,q); if(left !== null&&right !== null) { return root; } if(left ===null) { return right; } return left; } return travelTree(root,p,q);};
对称二叉树
var isSymmetric = function(root) { //应用递归遍历左右子树 递归三部曲 // 1. 确定递归的参数 root.left root.right和返回值true false const compareNode=function(left,right){ //2. 确定终止条件 空的状况 if(left===null&&right!==null||left!==null&&right===null){ return false; }else if(left===null&&right===null){ return true; }else if(left.val!==right.val){ return false; } //3. 确定单层递归逻辑 let outSide=compareNode(left.left,right.right); let inSide=compareNode(left.right,right.left); return outSide&&inSide; } if(root===null){ return true; } return compareNode(root.left,root.right);};
动静布局
最长重复子数组
// 输出： A: [1,2,3,2,1] B: [3,2,1,4,7] 输入：3 解释： 长度最长的公共子数组是 [3, 2, 1] 。const findLength = (A, B) => { // A、B数组的长度 const [m, n] = [A.length, B.length]; // dp数组初始化，都初始化为0 const dp = new Array(m + 1).fill(0).map(x => new Array(n + 1).fill(0)); // 初始化最大长度为0 let res = 0; for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { // 遇到A[i - 1] === B[j - 1]，则更新dp数组 if (A[i - 1] === B[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } // 更新res res = dp[i][j] > res ? dp[i][j] : res; } } // 遍历实现，返回res return res;};
最长公共子序列
// 输出：text1 = "abcde", text2 = "ace" 输入：3 解释：最长公共子序列是 "ace"，它的长度为 3。const longestCommonSubsequence = (text1, text2) => { let dp = Array.from(Array(text1.length+1), () => Array(text2.length+1).fill(0)); for(let i = 1; i <= text1.length; i++) { for(let j = 1; j <= text2.length; j++) { if(text1[i-1] === text2[j-1]) { dp[i][j] = dp[i-1][j-1] +1;; } else { dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) } } } return dp[text1.length][text2.length];};
最长间断递增序列
const findLengthOfLCIS = (nums) => { let dp = Array(nums.length).fill(1); for(let i = 0; i < nums.length - 1; i++) { if(nums[i+1] > nums[i]) { dp[i+1] = dp[i]+ 1; } } return Math.max(...dp);};
最大回文子串
var longestPalindrome = function (s) { const len = s.length if (len < 2) return s let max = 0 let str = s[0] const dp = Array.from(new Array(len), () => new Array(len)) for(let j=0; j< len; j++) { for(let i=0; i<j; i++) { dp[i][j] = s[i] === s[j] && (j - i < 3 || dp[i+1][j-1]) if(dp[i][j] && j -i + 1 > max) { max = j - i + 1 str = s.substring(i, j+1) } } } return str }
最长回文子序列
const longestPalindromeSubseq = (s) => { const strLen = s.length; let dp = Array.from(Array(strLen), () => Array(strLen).fill(0)); for(let i = 0; i < strLen; i++) { dp[i][i] = 1; } for(let i = strLen - 1; i >= 0; i--) { for(let j = i + 1; j < strLen; j++) { if(s[i] === s[j]) { dp[i][j] = dp[i+1][j-1] + 2; } else { dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]); } } } return dp[0][strLen - 1];};
无重复子数组最大长度 (滑动窗口）
function sub(arr) { let max = 0 let base = 0 const has = new Map() for(let i = 0; i < arr.length; i++) { const cur = arr[i] if (hash.hash(cur)) { base = Math.max(base, has.get(cur) + 1) } hast.set(cur, i) max = Math.max(max, i - base + 1) } return max}
子数组乘积最大
function largestSum(arr) { let max = Number.MIN_SAFE_INTEGER, fmin = arr[0], fmax= arr[0] for(let num of arr) { if (num < 0) { const temp = fmax fmax = fmin fmin = temp } fmin = Math.min(fmin*num, num) fmax = Math.max(fmax*num, num) max = Math.max(max, fmax) } return max}
最小费用
function minCount(days, cost) { const len = days.length let maxDay = days[len - 1], minDay = days[0] let dp = new Array(maxDay + 31).fill(0) for(let d = maxDay, i = len -1; d >= minDay; d-- ) { if (days[i] === d) { dp[d] = Math.min(dp[d + 1] + cost[0], dp[d+7] + cost[1], dp[d+30]+cost[2]) i-- } else { dp[d] = dp[d+1] } } return dp[minDay]}