Site safety

XSS cross-site scripting attacks

Js script: Injection script execution, can get your local cookies, etc.

Prevention: input filtering, output encoding, cookie theft (encoding, binding with IP)

CSRF cross-site request forgery

Impersonate your identity to perform the operation.

Man machine recognition, verification code.

Network request

Limit n fetch at a time and ensure maximum speed

function limitPromise(callbacks, n){ const len = callbacks.length; let count = 0; let result = []; return new Promise((resolve,reject)=>{ try{ while(count<n){ fetch(); } function fetch(){ if(count>=len && result.length===n) return resolve(result); If (count<n){fetch count++; Promise(callbacks[count]()). Then (res=>{result.push(res); fetch(); return res; }) } } } catch(err){ reject(err); }})}Copy the code

The front-end algorithm

The tree

Example 1: Output a mirror image of a tree

Queue stores left/right interchangeably

queue=[root];  
while(queue.length){ 
    r=queue.shift(); 
    r.left=r.right; 
    r.right=r.left;
    queue.push(r.right); 
    queue.push(r.left);
}
root
Copy the code

Case 2: Determine if a tree is symmetric

recursive

root===null return true; compare(left,right){ ! left && ! right true; ! left || ! right false; left.val! ==right.val false; return compare(left.left,right.right) && compare(left.right,right.left) } compare(root.left,root.right);Copy the code

Case 3: Whether t1B T2 nodes coincide

The two Pointers, each go their own way and return to the other’s starting point, will meet again at the place where we first met

function getpose(t1, t2){ const node1=t1; const node2=t2; while(node1 ! == node2){ if(node1===null || node2===null){return null; } node1=node1? node.next:t1; node2=node2? node2.next:t2; } return node1; }Copy the code

bfs

case

<div id="roottag"> <div> <span>1</span> <span>2</span> <div> <span>3</span> <span>4</span> </div> </div> <div> <span>5</span> <span>6</span> </div> </div> function bfs(root){ const nodelist=[]; let queue=[root]; While (queue length > 0) {const parent = queue. The splice (0, 1) [0]. nodelist.push(parent); for(var i=0; i<parent.children.length; i++){ queue.push(parent.children[i]); } //if(parent. Children) queue=queue. Concat (parent. Children) children; }Copy the code

Knapsack problem

Dynamic programming

Key points:

1. Confirm the last question

2. Identify sub-questions

3. Find the state transition function

4. Confirm the calculation sequence

Calculate the length of the maximum increasing subsequence eg: input: array[2,3,1,5,6] output: 4

function maxLengthList(array){ let dp=[0]; for(let i=1; i<array.length; i++){ dp[i]=1; for(let j=0; j<i; j++){ array[i]>array[j] && (dp[i]=Math.max(dp[i] + dp[j]+1)); } } return Math.max(... dp); }Copy the code

back

Main points: 1. Path 2. Termination condition return recursion 3. Optional array selection

1. Try the path path from I to the end and record the path (res.push([…path])).

2. Go to I and start other paths

Case 1: Take an array and return the set of all possible isometric arrays of its elements

Function backtrack(array){let res=[]; function backtrack(array){let res=[]; Let temppath = []; Function DFS (path){if(temppath. Length ===array.length){return res.push([...temppath]); } for(var I =0; i<array.length; i++){ temppath.push(array[i]); // path to join a node DFS (temppath); // Continue temppath. Pop () from this node; }} DFS ([]); return res; }Copy the code

Case 2: Take an array and return a subset of it

function sonarray(array) { const res = []; const path = []; function dfs(path, start) { if(path.length===array.length) return; // The subset is smaller than the parent set res.push([...path]); // add for (var I = start; i < array.length; If (path.indexof (array[I])! ==-1) continue; path.push(array[i]); dfs(path, i); path.pop(); } } dfs(path,0); return res; }Copy the code

Case 3: Enter an array and find the combination of elements and target

function cacula(array, target) { const res = []; const path = []; If (target>sum(array)) return 'empty'; function sum(array) { if (array.length === 0) return 0; Return array.reduce((cur, next) => {return cur + next})} If (sum(path) === target) {res.push([...path]); return; } if (sum(path) > target) return pathTotal = 0; for (var i = start; i < array.length; i++) { path.push(array[i]); console.log(1); deps(path, i + 1); path.pop(); } } deps([], 0); return res; }Copy the code

Reverse a linked list

Case 1: Reverse a linked list

Double pointer method

pre cur  {next=cur.next cur.next=pre   pre=cur   cur=cur.next}
cur
Copy the code

Case 2: Intercept the last KTH bit of the list to the end of the list

Double pointer method

slow; fast; for(i++<k) {fast=fast.next} while(fase) {slow=slow.next; fase=fase.next; } slowCopy the code

Case 3: Merge two increment lists, and then not completely increment

head = new nodelist; h=head; 
while(l1 && l2){ l1.val<l2.val head.next=l1 l1=l1.next  head=head.next};
if(l1/l2) head.next=l1/l2;
h
Copy the code

Monotonous stack

1. Monotonically increasing or decreasing from the top to the bottom of the stack

2. Will not conform to the monotonicity of the stack

Function monstack(array){const stack = []; const len = array.length; for(var i=0; i<len; I ++){//while(stack.length && array[I] > stack[stack.length-1]){// Increment stack while(stack.length && array[I] < Stack [stack.length-1]){// decrement stack stack.pop(); continue; } stack.push(array[i]); } return stack; }Copy the code

Bubble sort

1, I +1…. Let’s compare len-1 to len-1, put it in the right order and then go on to the next two

2. Stop until there is no need to switch places

function bublesort(array){ const len = array.length; for(var i=0; i<len; i++){ for(var j=i+1; j<len; j++){ let cache = 0; if(array[i]>array[j]){ cache = array[i]; array[i] = array[j]; array[j] = cache; } } } return array; }Copy the code

Quick sort

1. Select an intermediate value and extract the intermediate value key from the array

2. Iterate over the remaining array, placing the larger one on right and the smaller one on right

3. Perform quicksort on the left and right in sequence. return left.concat([key],right)

function quiksort(array){ if(array.length<=1) return array; // Const index = math.floor ((array.length-1)/2); // index const key = array.splice(index,1)[0]; Let left=[],right =[]; for(var i=0; i<array.length; i++){ const item = array[i]; if(item<=key){left.push(item); }if(item>key){right.push(item); } } return quiksort(left).concat([key],quiksort(right)); }Copy the code

Insertion sort

1. Combine the current bit with the left (current-1… 0) Put current after the smaller element for comparison

2. Current starts from 1

3. If there is no smaller, insert into the head

function insertsort(array){ const len = array.length; for(var i=1; i<len; I ++){// const temp = array[I]; array.splice(i,1); for(var j=i-1; j>=0; J -) {if (array [j] {< temp) array. The splice (j + 1, 0, temp); break; {} the if (j = = = 0) array. The splice (0, 0, temp); }} return array; }Copy the code

Binary search

1. Use the above sort as array sort. Suggest quiksort

2. Compare search with array[middle] If search>array[middle] compares the right side of search and middle

3. Wait until the search is complete

// Array is an sorted array or array = quiksort(array) // Use the double-pointer method function binarySearch (key,array){const len = array.length; let left = 0,right = len-1; while(left<=right){ const middle=Math.floor((left+right)/2); if(key===array[middle]){return middle; } if(key<array[middle]){right=middle-1; } if(key>array[middle]){left=middle+1; } } return false; }Copy the code

Type judgment

WhatType = function (arg) {/ / null undefined direct return the corresponding string if (arg = = = null | | arg = = = undefined) {return string (arg); } / / object classification array object if (typeof arg = = = 'object') {const name = object. The prototype. The toString. Call (arg). Slice (7); //'[object Array]' if(name.includes('Array')){ return 'array'; Return typeof arg; return typeof arg; }Copy the code

Deep copy

Key points:

1. If it is a base type, this parameter is returned

2. The application types are array and Object

const cloneLoop = function(source) { let res; if(typeof source ! == 'object'){ return source; } if(typeof source === 'object' && source ! == null){ res = Array.isArray(source) ? [] : {}; For (var k in source){// Iterator iterates if(source.hasownProperty (k)){// If (source.hasownProperty (k)){ If (typeof source[k] === 'object'){res[k] = cloneLoop(source[k]); } else{ res[k] = source[k]; }} return res; // return the result of the deep copy}Copy the code

If the throttle

Key points:

Execute only once at a time; Perform at regular intervals; Both need to store the state of the last execution

Const tt = function(fn, delay){let timer=null; return function(){ clearTimeout(timer); timer=setTimeout(fn,delay); }} const ll = function(fn, delay){let start=new Date().gettime (); return function(){ const end = new Date().getTime(); if(end-start>delay){ setTimeout(fn,delay); start=end; }}}Copy the code

Js data structure

Stack of js data structures

1. First in, last out

2. Operations are at the top of the stack

3. Unstack elements remain on the stack: retrieve deleted data

4. You can load and unload the stack, obtain the length of the stack, view the top element of the stack, and clear the stack

class stack{ top = 0; State = []; Pop = function(){return this.top? this.state[--this.top] : 'empty'; Push = function(arg){const top = this.top; this.state[top] = arg; return ++this.top; Peek = function(){return this.state[this.top-1]; GetLength = function(){return this.top; getLength = function(){return this.top; } clear = function(){this.state=[]; this.top=0; return true; }} // Use const stacky = new stack(); stacky.push(1); / /...Copy the code

Case 1:

Determines whether a string is palindrome

const isRe = function(string){ if(typeof string ! == 'string') return 'Please enter a string'; const pre = new stack(); For (var I =0 in string){// Assuming 12321 const len = math.floor (string.length/2); // Two strings of length 2 const middle = string.length%2 === 1? len : 0; // Index =2 if(I <len){pre.push(string[I]); }else{ if(middle===0 || Number(i)! ==middle){// No middle number/no middle number if(pre-.pop ()! ==string[i]) return false; } } } return true; } / / note: for in return for the string / / using isRe (' ') / / true isRe (' 1 ') / / false isRe (' 121 '); //trueCopy the code

Case 2: Conversion between number systems

Key points:

Num %base specifies the current bit value. Math.floor(num/base) = math.floor (num/base)

const transform = function(num, base){ const stacknum = new stack(); // use stack let data=''; // save the converted digit while(num! ==0){stacknum.push(num%base); num=Math.floor(num/base); } const len = stacknum.getLength(); For (let I =0; i<len; i++){ data+=String(stacknum.pop()); } return Number(data); } // use ttransform(32,2) //100000Copy the code

List of js data structures

Contains a list of properties and methods

2, the basic operation similar to array can be directly used array encapsulation. I won’t go into too much…

const list = ()=>{ this.listSize = 0; This. pos = 0; // The initialization position is 0 this.dataStore = []; // Initialize the empty array to hold the list element this.clear = clear; this.find = find; This.tostring = toString; // Display elements in the list this.insert = insert; this.append = append; this.remove = remove; this.front = front; this.end = end; this.prev = prev; this.next = next; this.length = length; This. currPos = currPos; this.moveTo = moveTo; this.getElement = getElement; this.contains = contains; // Check whether the given value is in the list}Copy the code

Linked list of js data structures

Js linked list and array difference: array is a piece of continuous memory space to store, memory requirements are relatively high. Linked lists, on the other hand, do not require a contiguous memory space. A linked list is a series of discrete blocks of memory connected by Pointers.

1. The smallest unit of a linked list is an element. An element keeps itself and its next element or its previous element

2. A linked list that stores only the next element is a one-way linked list. A linked list that has both the previous and the next element is a bidirectional list

Head =null; this.head=null; this.count=0; You can add, delete, change and check.

class Node { constructor(element){ this.element = element; this.next = undefined; } } class LinkedList { constructor(){ this.head = null; this.count = 0; } // Add element push(element){const Nodes = new Node(element); let current=this.head; if(this.head===null){ this.head = nodes; }else{ while(current.next){ current = this.head.next; } current.next = nodes; } this.count++; } removeAt(position){ //[position-1].next=[position].next let current = this.head; If (position>this.count-1){return false; } if(position===0){this.head = this.head.next || null; return true; } for(let i=0; i<position-1; I++){// current = current. Next; } current.next = current.next.next; // Next of position-1 points to position's next return true; } remove(element){ console.log('12'); if(this.head.element === element) { this.head = this.head.next; return true; } let current = this.head; while(current.next){ if(current.next.element===element){ current.next=current.next.next; // Add element's next to Element's next return true; } current=current.next; } return false; } insert(position, element){//0; Next = [position-1]. Next = element. Next = [position-1]. Next (record position's next) Element = new Node(element); let next; if(position===0){ next = this.head; this.head = element; this.head.next = next; return true; } let current = this.head; for(let i=0; i < position-1; i++){ if(current === undefined && i<position-1){ return false; } current=current.next; } next = current.next; current.next = element; element.next = next; this.count++; return true; }}Copy the code

Queue of js data structures

First in, first out

Join the team at the back, leave the team at the head

class Queue { #data=[]; Enqueue (item){// Insert this.#data.push(item); return true; } dequeue(){// queue first queue if(! this.#getLength()) return 'empty'; this.#data.reverse().pop(); // Shifit is O(n) to avoid this.#data.reverse(); // return true; } front(){if(this.isempty ()) return 'empty'; return this.#data[0]; } back(){if(this.isempty ()) return 'empty'; return this.#data[this.#getLength()-1]; } // Clear the queue clear(){this.#data = []; ToString (){return this.#data.join()} // Check whether isEmpty(){return! this.#data.length; } // Use the function inside the private variable to return the length of the queue #getLength(){return this.#data.length; }}Copy the code

Tree of js data structures

Binary tree full binary tree complete binary tree

1. Each root node has only two child nodes: root left right

2. There is an order between nodes: left<root<right

Binary tree storage mode:

Class Node {current: ", left: null, right: null} class Node {current: ", left: null, right: null} left=2*i; right=2*i + 1;Copy the code

Traversal: front, middle and back

Before the order

1. Root starts

Root.left. Left if root. Right does not exist

// former root left right const preOrder=(root)=>{let stack = []; r(root); return order; function r(root){ if(root) return; stack.push(root.val); root.left && r(root.left); // Traverses the left subtree root.right && r(root.right); }} left root right const centerOrder=(root)=>{stack=[]; r(root); return stack; function r(root){ if(root) return; root.left && r(root.left); stack.push(root.val); root.left && r(root.right); } // left right root const nextOrder=(root)=>{const stack=[]; r(root); return stack; function r(root){ if(! root) return; root.left && r(root.left); root.right && r(root.right); stack.push(root); Function levelOrder() {if (this.root == null) return ""; let a = [], left, right; a.push(this.root); // The node is enqueued, and the pointer points to the header element, if it has left/right, enqueued. // Move the pointer back, continue the same step... Until the pointer goes behind the end of the queue... for(let i = 0; i < a.length; Left = a[I].left; left = a[I].left; if (left) a.push(left); right = a[i].right; if (right) a.push(right); } return a.map(item => item.val).join(','); }Copy the code

dfs bfs

3. Depth traversal:

//BFS bread-first-search function bfs(root){ const stack=[]; Const queue = []; queue=[root]; While (queue length > 0) stack. Push (queue. Splice (0, 1) [0]). root.children && queue=queue.concat(root.children); }} function DFS (root){const nodelist=[]; function r(root){ if(! root) return; nodelist.push(root); for(leti=0; i<root.children.length; i++){ r(root.children[i]); } } return nodeList; } function DFS (root){const nodelist=[]; const nodelist=[]; const queue=[]; queue=[root]; while(queue.length>0){ rootitem=queue.pop(); / / after a nodelist. Push (rootitem); for(let i=rootitem.children.length-1; i>0; Queue. Push (rootitem.children[I]) {// queue. Push (rootitem.children[I]); }}}Copy the code

Design patterns

Observer and publish subscribe

Key points:

1. Observer mode Multiple observers correspond to one observed, and the two are directly related. The observer provides binding and triggering functions, and the observer uses its binding functions

2. Publish and subscribe can be many-to-many, and an intermediate data manager is introduced. The two objects only publish and subscribe to the data management center

Observer pattern diagram :(from zhihu)

Publish and subscribe model diagram :(from zhihu)

Class Subject{MSG =[]; subscribe(callback){ if(this.msg.includes(callback)) return false; this.msg.push(callback); } publish(args){ if(this.msg.length===0) return; this.msg.map(handle => handle.apply(null, args)) } } const subject = new Subject(); Const observer1 = subject.subscribe((... Args)=>{console.log(' observer 1 observed change: '+args); }); const observer2 = subject.subscribe((... Args)=>{console.log(' Observer 2 observed change: '+args)}); subject.publish('hahaha'); Class EventCenter{MSG = {}; class EventCenter{MSG = {}; class EventCenter{MSG = {}; Emit (event,... Args){// The event triggers if(! this.msg[event]) return false; this.msg[event].forEach(item=>{ item.apply(null, args) }); } on(event, callback){// If (! this.msg[event]){ this.msg[event] = [callback]; return true; } this.msg[event].push(callback); } remove(event, callback){// if(! this.msg[event]) return false; this.msg[event].filter(item=>item ! == callback)} once(event,callback){remove const wrapFunc = (... args) => { callback.apply(args); this.off(event, callback); } this.on(event, callback); } } const manerger = new EventCenter(); // Create manager const obServer1 = (arg) => {console.log(111+arg)} const observer2 = (arg) => {console.log(222+arg)} // Publisher const  publisher = (()=>{ return {update1: ()=>{ manerger.emit('update', observer1); manerger.emit('update', observer2); }}}) () / / subscriber const subscriber = (() = > {return {update: () = {ob. On (' update 'observer1); ob.on('update', observer2); }} })() subscriber.update(); // Publish publisher.update1(' Subscription triggered! '); // Subscription triggersCopy the code

To be continued…