数据结构以及某些实现

数据结构

数组

连续子数组的最大和

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;
}

#学习路径#