数据结构
数组
连续子数组的最大和
function FindGreatestSumOfSubArray(arr) { const dp = [arr[0]] let max = arr[0]; //dp[i]表示以i结尾的最大连续子序列的和,因此本题要求出dp中的最大数字 for (let i=0;i<arr.length;i++) { dp[i] = dp[i-1]>0?dp[i-1]+arr[i]:arr[i] max = dp[i]>max:dp[i]:max; } return max; }
扑克牌顺子
function IsContinuous(numbers) { // write code here numbers.sort((a,b)=>a-b); let num0 = 0; let num1 = 0; for (let i=0;i<numbers.length;i++) { if (numbers[i]==0) { num0++; } else { if (numbers[i]===numbers[i+1]) return false; if (numbers[i+1]>numbers[i]) num1+=numbers[i+1]-numbers[i]-1; } } return num0>=num1 }
构建乘积数组(不用除法)
function mutiply(arr) { let left = []; let right = []; let res = []; for (let i=0;i<arr.length;i++) { left[i] = i==0?1:left[i-1]*arr[i-1]; } for (let i=arr.length-1;i>=0;i--) { right[i] = i==arr.length-1?1:right[i+1]*arr[i+1]; } for (let i=0;i<arr.length;i++) { res[i] = left[i] *right[i]; } return res; }
二叉树
二叉搜索树
左子节点的值小于根节点,右子节点的值大于根节点,并且左子树和右子树也是二叉搜索树
二叉搜索树的第k小的节点
function KthNode(pRoot,k) { let res = []; const middle = (pRoot) =>{ if (!pRoot) return; middle(pRoot.left); res.push(pRoot); if(res.length>k-1) return; middle(pRoot.right); } return res[k-1]; }
完全二叉树 满二叉树
完全二叉树是从左到右排列的二叉树
满二叉树是2k次方-1个节点的二叉树
平衡二叉树
平衡二叉树是一颗空树或者其左右二叉树的高度差不超过1并且左右子树也是平衡二叉树
判断是否是平衡二叉树
function IsBalanced_Solution(pRoot) { // write code here if (pRoot===null) return true; return (Math.abs(height(pRoot.left)-height(pRoot.right))<2) && IsBalanced_Solution(pRoot.left)&&IsBalanced_Solution(pRoot.right) } function height (root) { if (!root) { return 0; } return Math.max(height(root.left)+1,height(root.right)+1) }
镜像二叉树
function Mirror( pRoot ) { // write code here if (!pRoot) return null; let left = Mirror(pRoot.right); let right = Mirror(pRoot.left); pRoot.left = left; pRoot.right = right; return pRoot; }
按之序列打印二叉树
function print(pRoot) { let arr = []; let res = []; if (!pRoot) return res; arr.push(pRoot); while (arr.length) { let len = arr.length; let tmp = []; let floor = 1; while (len) { let now = arr.shift(); tmp.push(now); if (now.left) arr.push(now.left); if (now.right) arr.push(now.right); len--; } if (floor%2==1) { res.push(tmp); } else { res.push(tmp.reverse()); } } return res; }
二叉树的遍历
中序遍历
function middle(head,arr = []) { if (!head) return; middle(head.left,arr); arr.push(head.val); middle(head.right,arr); }
dfs
function dfs(head) { let arr = []; let res = []; if (!head) return arr; arr.push(head); while (arr.length) { let now = arr.shift(); res.push(now.val); if (now.right) arr.unshift(now.right); if (now.left) arr.unshift(now.left); } return res; }
bfs
function dfs(head) { let arr = []; let res = []; if (!head) return arr; arr.push(head); while (arr.length) { let now = arr.shift(); res.push(now.val); if (now.left) arr.push(now.left); if (now.right) arr.push(now.right); } return res; }
链表
从尾到头的链表
function reverse(head) { let prev = null; let now = head; while (head) { now.next = prev; head = head.next; prev = now; now = head; } return now; }
倒数第k个节点
function number(head,k) { let fast = head; let slow = head; while (k) { fast = fast.next; k--; } while (fast) { fast = fast.next; slow = slow.next; } return slow; }
公共节点
function public(head1,head2) { let p1 = head1; let p2 = head2; while (p1!=p2) { p1 = p1?p1.next:head2; p2 = p2?p2.next:head1; } return p1; }
环的入口
function circleEnter (head) { let fast = head; let slow = head; while (fast&&fast.next&&slow) { fast = fast.next.next; slow = slow.next; } if (fast!=slow) { return } slow = head; while (slow!=fast) { slow = slow.next; fast = fast.next; } return slow; }
axios实现
function axios (method,url,header,params) { return new Promise((reolve,reject)=>{ var xhr = new XMLHttpRequest(); xhr.open(method,url,true); xhr.setRequestHeader(header); xhr.send(params); xhr.onReadyStateChange = ()=>{ if (xhr.readyState=4) { resolve(xhr.responseText); } } }) }
事件监听触发实现
class eventbus { constructor () { this.event = {}; } addEventListener (name,cb) { if (!this.event[name]) { this.event[name] = []; } this.event[name].push(cb); } attchEvent(name) { if (this.event[name]) { this.event[name].forEach((item)=>{ item(); }) } } }
allsettled
function allSettled (promises) { return new Promise((resolve)=>{ let res = []; let len =0; promises.forEach(()=>{ len++; p.then((r)=>{ res.push({status:'resolved',value:r}); }).catch((e)=>{ res.push({status:'rereject',value:e}); }) }) len===promises.length&&resolve(res); }) }
flat
function flat (arr) { let newarr = []; arr.forEach(item=>{ if (Array.isArray(item)) { let flatarr = flat(item); } newarr.concat(flatarr); }) return newarr; }
全部评论
(0) 回帖