Introduction to the
Readers are expected to build their own knowledge tree (mind map)
Lazy: Refer to my own summary mind map: click here
Rip code Address: address
Bonus: Frequent interview question accumulation documentation. From (senior students, Niuke.com and other platforms)
I developed my blog address: zxinc520.com
Github address: Click
The interview is very easy to do.
1. Promise (A+ specification), then, all methods
/* Promise: constructs the Promise function object excutor: executes the constructor (synchronously executes) */
function Promise(excutor) {
const _that = this
_that.status = 'pending' // Assign the status attribute to the Promise object, starting with pending
_that.data = undefined // Give the Promise object a property to store the result data
_that.callbacks = [] // This is a big pity (){}, onforget (){}}
function resolve(value) {
// If the current state is not pending, terminate
if(_that.status ! = ='pending') return
// Change the status to Resolved
_that.status = 'resolved'
// Save value data
_that.data = value
// If the callback function needs to be executed, execute the callback function asynchronously
if (_that.callbacks.length > 0) {
setTimeout((a)= > {
_that.callbacks.forEach(callbacksObj= > {
callbacksObj.onFulfilled(value)
})
})
}
}
function reject(reason) {
// If the current state is not pending, terminate
if(_that.status ! = ='pending') return
// Change the status to Rejected
_that.status = 'rejected'
// Save value data
_that.data = reason
// If the callback function needs to be executed, execute the callback function asynchronously
if (_that.callbacks.length > 0) {
setTimeout((a)= > {
_that.callbacks.forEach(callbacksObj= > {
callbacksObj.onRejected(reason)
})
})
}
}
// Execute excutor immediately
try {
excutor(resolve, reject)
} catch (error) { // If the actuator throws an exception, the Promise object changes to the Rejected state
reject(error)
}
}
/ / this is a big pity/onpromise (); / / This is a big pity/onPromise (); / / This is a big pity /onRejected () Ondepressing /onRejected () */
Promise.prototype.then = function (onFulfilled, onRejected) {
onFulfilled = typeof onFulfilled === 'function' ? onFulfilled : reason= > reason // Pass a successful value backwards
// Specify the default failed callback (key point to achieve error/exception penetration)
onRejected = typeof onRejected === 'function' ? onRejected : reason= > { // Pass back the reason for the failure
throw reason
}
const _that = this
// Return a new Promise object
return new Promise((resolve, reject) = > {
/* Call the specified callback and change the state of the return promise */ based on the result of the execution
function handle(callback) {
/* if you throw an exception, the promise of the return will fail. Reason is error. If the callback returns anything other than a promise, the promise of the return is successful, and value is the returned value 3. If the callback returns a promise, the return promise is the result of that promise */
try {
const result = callback(_that.data)
// 3. If the callback returns a promise, the return promise is the result of that promise
if (result instanceof Promise) {
// result.then(
// resolve => resolve(value), // If result succeeds, make the return promise succeed as well
// reason => reject(reason) // When result fails, make the return promise fail too
// )
result.then(resolve, reject)
} else {
// 2. If the callback does not return a promise, the promise of return will succeed, and value is the returned value
resolve(result)
}
} catch (error) {
//1. If an exception is thrown, the promise of return will fail. Reason is error
reject(error)
}
}
if (_that.status === 'pending') {
// If the current state is still pending, save the callback function
_that.callbacks.push({
onFulfilled(value) {
handle(onFulfilled) // This is a big pity
},
onRejected(reason) {
handle(onRejected) // Change the promise state to onRejected}})}else if (_that.status === 'resolved') { // If this is resolved, asynchronously execute onResolved and change the promise state for return
setTimeout((a)= > {
handle(onFulfilled)
})
} else { //onRejected
setTimeout((a)= > { // If the state is Rejected, asynchronously implement onRejected and change the promise state of return
handle(onRejected)
})
}
})
}
/* The catch() of the Promise prototype object specifies that the failed callback returns a new Promise object */
Promise.prototype.catch = function (onRejected) {
return this.then(undefined, onRejected)
}
Promise.prototype.finally = function (callback) {
return this.then(value= > {
Promise.resolve(callback(value))
}, reason => {
Promise.resolve(callback(reason))
})
}
/* The resolve() of the Promise function object returns the "success" Promise object */ for the specified result
Promise.resolve = function (value) {
// Return a success/failure promise
return new Promise((resolve, reject) = > {
if (value instanceof Promise) { // Use the result of value as the result of promise
value.then(resolve, reject)
} else { //value is not promise => Promise becomes success, data is value
resolve(value)
}
})
}
Reject () of the Promise object returns a "failed" Promise object */ for the specified result
Promise.reject = function (reason) {
// Return a failed promise
return new Promise((resolve, reject) = > {
reject(reason)
})
}
/* The all() of the Promise function object returns a Promise that will succeed only if all promises succeed, or if only one fails */
Promise.all = function (promises) {
const values = Array.apply(null, {length: promises.length})// An array to hold all successful values
let resolvedCount = 0
return new Promise((resolve, reject) = > {
// Iterate over the result of each promise
promises.forEach((p, index) = > {
Promise.resolve(p).then(
//p if yes, save the successful value to values
// values.push(value) =
value => {
resolvedCount++ // The number of successes
values[index] = value
// If all returns are successful, change the return promise to success
if (resolvedCount === promises.length) {
resolve(values)
}
},
reason => { // If one fails, the return promise fails
reject(reason)
}
)
})
})
}
/* The Promise function object's race() returns a Promise, the result of which is determined by the first completed Promise */
Promise.race = function (promises) {
return new Promise((resolve, reject) = > {
// Iterate over the result of each promise
promises.forEach((p, index) = > {
Promise.resolve(p).then(
value= > { // Change return to failure once it succeeds
resolve(value)
},
reason => { // If one fails, the return promise fails
reject(reason)
}
)
})
})
}
Copy the code2, Handwritten call apply bind
// Define the apply function
Function.prototype.apply1 = function (obj, arg) {
// Set the default value when context is null or undefined
if(! obj) { obj =typeof window= = ='undefined' ? global : window
}
obj.fn = this
let result = null
//undefined or null is not an Iterator and cannot be...
if (arg === undefined || arg === null) {
result = obj.fn(arg)
} else{ result = obj.fn(... arg) }delete obj.fn
return result
}
// Customize the call function
Function.prototype.call1 = function (obj, ... arg) {
if(! obj) { obj =typeof window= = ='undefined' ? global : window
}
obj.fn = this
let result = nullresult = obj.fn(... arg)delete obj.fn
return result
}
// Customize bind
Function.prototype.bind = function (obj, ... arg) {
if(! obj) { obj =typeof window= = ='undefined' ? global : window
}
let self = this
let args = arg
function f() {}
f.prototype = this.prototype
let bound = function () {
let res = [...args, ...arguments]
let obj = this instanceof f ? this : obj
return self.apply(obj, res)
}
bound.prototype = new f()
return bound
}
Copy the codePromise encapsulates Ajax methods
function ajax(url, methods,data) {
return new Promise((resolve, reject) = > {
let xhr = new XMLHttpRequest()
xhr.open(methods, url, true)
xhr.send(data)
xhr.onreadystatechange = function () {
if (xhr.readyState === 4 && xhr.status === 200) {
resolve(xhr.responseText)
}else{
reject(xhr.status)
}
}
})
}
Copy the code4. Load images asynchronously
function loadImageAsync(url) {
return new Promise(function(resolve, reject) {
const image = new Image();
image.onload = function() {
resolve(image);
};
image.onerror = function() {
reject(new Error('Could not load image at ' + url));
};
image.src = url;
});
}
Copy the code5, shake, throttling
/ / image stabilization
function debounce(fn, delay) {
let timeout = null
return function () {
clearTimeout(timeout)
timeout = setTimeout((a)= > {
fn.apply(this.arguments)
}, delay)
}
}
/ / throttling
function throttle(fn,delay) {
let canRun = true
return function () {
if(! canRun)return
canRun = false
setTimeout((a)= >{
fn.apply(this.arguments)
canRun = true
},delay)
}
}
Copy the codeThe Holy Grail, flying wings
The holy grail
<style>* {padding: 0;
margin: 0;
}
.container{
overflow: hidden;
padding: 0 100px 0 100px;
}
.middle..left..right{
position: relative;
float: left;
}
.left{
width: 100px;
height: 100px;
background: red;
margin-left: -100%;
left: -100px;
}
.right{
width: 100px;
height: 100px;
background: green;
margin-left: -100px;
right: -100px;
}
.middle{
background: blue;
width: 100%;
height: 300px;
}
</style>
</head>
<body>
<div class="container">
<div class="middle"></div>
<div class="left"></div>
<div class="right"></div>
</div>
Copy the codeThreesome wing
<style>
.container {
overflow: hidden;
}
.middle..left..right {
float: left;
height: 100px;
}
.left {
width: 100px;
background: red;
margin-left: -100%;
}
.right {
width: 100px;
background: blue;
margin-left: -100px;
}
.middle {
width: 100%;
background: aqua;
}
.inner {
margin: 0 100px;
}
</style>
</head>
<body>
<div class="container">
<div class="middle">
<div class="inner">middle</div>
</div>
<div class="left">left</div>
<div class="right">right</div>
</div>
Copy the code7. Inheritance
7.1 Prototype chain inheritance
-
The basic idea of stereotype chain inheritance is to use stereotypes to make one reference type inherit the properties and methods of another.
Subtype.prototype = new SuperType();
function SuperType() { this.name = 'Yvette'; } function SubType() { this.age = 22; } SubType.prototype = new SuperType(); Copy the code -
disadvantages
- When inheritance is implemented through a stereotype, the stereotype becomes an instance of another type, the original instance properties become the current stereotype properties, and the reference type properties of the stereotype are shared by all instances
- When creating an instance of a subtype, arguments cannot be passed to the constructor of a supertype
7.2. Borrow constructors
-
The basic idea is to call the supertype constructor in the constructor of the subtype.
function SuperType(name) { this.name = name } function SubType(name) { SuperType.call(this, name) } Copy the code -
advantages
- Arguments can be passed to the superclass
- Fixed a problem with stereotypes containing reference type values shared by all instances
-
disadvantages
- Methods are defined in constructors, so function reuse is out of the question
- In addition, methods defined in the supertype stereotype are invisible to subtypes
7.3. Combination Inheritance
-
Combinatorial inheritance refers to an inheritance pattern that combines a stereotype chain and a borrowed constructor technique to give play to the best of both. Basic idea: using the prototype chain to achieve the inheritance of prototype attributes and methods, by borrowing the constructor to achieve the inheritance of instance attributes, not only through defining methods on the prototype to achieve function reuse, but also ensure that each instance has its own attributes.
function SuperType() { this.name = 'zc' this.colors = ['pink'.'blue'.'green']; } function SubType() { SuperType.call(this) } SubType.prototype = new SuperType SubType.prototype.constructor = SubType let a = new SubType() let b = new SubType() a.colors.push('red') console.log(a.colors)//[ 'pink', 'blue', 'green', 'red' ] console.log(b.colors)//[ 'pink', 'blue', 'green' ] Copy the code -
advantages
- Arguments can be passed to the superclass
- Each instance has its own attributes
- Function reuse is realized
-
disadvantages
- In any case, the supertype constructor is called twice: once when the subtype stereotype is created and once inside the subtype constructor.
7.4 Inheritance of original type
-
The basic idea of primitive inheritance is that inside object(), a temporary constructor is created, the passed object is used as a prototype of the constructor, and a new instance of the temporary type is returned. In essence, Object () makes a shallow copy of the passed object.
ECMAScript5 normalizes old-style inheritance by adding the object.create () method. This method takes two parameters: an Object to be used as a prototype for the new Object and (optionally) an Object that defines additional properties for the new Object (which can override properties of the same name on the prototype Object). In the case of one parameter, the object.create () and Object () methods behave the same.
function object(o) { function F() { } F.prototype = o; return new F(); } Copy the code -
disadvantages
- As with stereotype chain implementation inheritance, attributes containing reference type values are shared by all instances
7.5. Parasitic inheritance
-
Parasitic inheritance is closely related to original inheritance. The idea of parasitic inheritance is similar to that of the parasitic constructor and factory pattern, which is to create a function that just encapsulates the inheritance process, internally enhances the object in some way, and finally returns the object as if it had really done all the work.
function object(o) { function F() { } F.prototype = o; return new F(); } function createAnother(original) { var clone = object(original);Create a new object by calling the function clone.sayHi = function () {// Enhance the object in some way console.log('hi'); }; return clone;// Return this object } Copy the code -
advantages
- A new object is returned based on Person – — person2, which not only has all the attributes and methods of Person, but also has its own sayHi() method. Parasitic inheritance is also a useful pattern when considering objects rather than custom types and constructors.
-
disadvantages
- Using parasitic inheritance to add functions to an object is inefficient because functions cannot be reused.
- As with stereotype chain implementation inheritance, attributes containing reference type values are shared by all instances.
7.6. Parasitic combined inheritance
-
The so-called parasitic combinatorial inheritance refers to inheriting attributes by borrowing constructors and inheriting methods through the mixed form of prototype chains. The basic idea is as follows:
Instead of calling the constructor of the supertype to specify the stereotype of the subtype, all we need is a copy of the stereotype of the supertype, essentially inheriting the stereotype of the supertype using parasitic inheritance and then assigning the result to the stereotype of the subtype.
function inheritPrototype(subType, superType) { var prototype = object(superType.prototype); // Create an object prototype.constructor = subType;// Enhance objects subType.prototype = prototype;// Specify the object } function SuperType(name) { this.name = name; this.colors = ['pink'.'blue'.'green']; } function SuberType(name, age) { SuperType.call(this, name); this.age = age; } inheritPrototype(SuberType, SuperType); Copy the code -
steps
Step 1: Create a copy of the supertype stereotype
Step 2: Add the constructor attribute to the created copy
Step 3: Assign the newly created object to the prototype of the subtype
-
advantages
- The superclass constructor is called only once, which is more efficient. Avoid creating unnecessary, redundant attributes on suberType. prototype, while keeping the prototype chain intact. Therefore, parasitic combinatorial inheritance is the most rational inheritance paradigm for reference types.
7.7 ES6 Inheritance
-
Class can be inherited through the extends keyword
class SuperType { constructor(age) { this.age = age; } getAge() { console.log(this.age); }}class SubType extends SuperType { constructor(age, name) { super(age); // Call parent constructor(x, y) this.name = name; } getName() { console.log(this.name); }}Copy the code -
The following points need to be made about ES6 classes
- Class declarations are promoted, but assignments are not initialized. Foo enters a temporary dead zone, similar to let, const declaration variables.
- Class declares that strict mode is enabled internally.
- All methods of class, including static and instance methods, are not enumerable.
- All methods of class (static and instance methods) have no prototype object, so there is no [[construct]] to call with new.
- Class must be called using new
- Class names cannot be overridden inside class
Implementing inheritance using the extends keyword has a few special caveats
- Subclasses must call the super method from constructor or they will get an error when creating a new instance. If no subclasses define a constructor method, this method is added by default. In the constructor of a subclass, the this keyword can only be used after super is called, otherwise an error is reported. This is because subclass instances are built on superclass instances, and only super methods can call superclass instances.
- ES5 inheritance essentially creates an instance object of the subclass, this, and then adds the Parent class’s methods to this (parent.apply (this)). ES6 has a completely different inheritance mechanism, essentially adding the properties and methods of the superclass instance object to this (so the super method must be called first), and then modifying this with the constructor of the subclass
8. Customize the new procedure
function _new(fn,... arg) {
let obj = {}
obj.__proto__= fn.prototype
let ret= fn.apply(obj,arg)
return ret instanceof Object ? ret:obj
}
Copy the code9, handwritten recursive method to achieve deep copy
// Write deep copy
function checkedType(target) {
return Object.prototype.toString.call(target).slice(8.- 1)}function clone(target) {
let targrtType = checkedType(target)
let result = null
if (targrtType === "Object") {
result = {}
} else if (targrtType === "Array") {
result = []
} else {
return target
}
for (let item in target) {
let value = target[item]
if (checkedType(value) === 'Object' || checkedType(value) === 'Array') {
result[item] = clone(value)
} else {
result[item] = value
}
}
return result
}
Copy the codeImplement a Currization function
/ / ES5 writing
const currying = function (fn,... args) {
if(args.length < fn.length){
return function () {
returncurrying(fn, ... args, ... arguments) } }else{
returnfn(... args) } }/ / ES6 writing
const currying =(fn,... args) = >
args.length < fn.length?(. argments) = >currying(fn,... args,... argments):fn(... args)Copy the code11. Bidirectional binding (handwritten)
/ / Object. DefineProperty writing
let vm = {}
let obj = {
name: 'zc'.age: '123'
}
for (let key in obj) {
if (obj.hasOwnProperty(key)) {
Object.defineProperty(vm, key, {
get: function () {
return obj[key]
},
set: function (newvalue) {
obj[key] = newvalue
}
})
}
}
obj.age ='111'
vm.age ='112221'
console.log(vm.age)
console.log(obj.age)
Copy the code/ / Proxy
let vm = new Proxy(obj,{
get: function (target, propKey, receiver) {
console.log(`getting ${propKey}! `);
return Reflect.get(target, propKey, receiver);
},
set: function (target, propKey, value, receiver) {
console.log(`setting ${propKey}! `);
return Reflect.set(target, propKey, value, receiver); }})Copy the codeJS publish and subscribe mode
let pubSub = {
list: {},
subscribe: function (key, fn) { / / subscribe
if (!this.list[key]) {
this.list[key] = []
}
this.list[key].push(fn)
},
publish: function (key, ... args) { / / release
for (let fn of this.list[key]) {
fn.apply(this, args)
}
},
unSubscribe: function (key, fn) { // Unsubscribe
let fnlist = this.list[key]
if(! fnlist)return
if(! fn) { fnlist.length =0
} else {
fnlist.forEach((item, index) = > {
if (item === index) {
fnlist.splice(index, 1)
}
})
}
}
}
pubSub.subscribe('onwork', time => {
console.log('Go to work:${time}`);
})
pubSub.subscribe('offwork', time => {
console.log('Off duty:${time}`);
})
pubSub.subscribe('launch', time => {
console.log('Have dinner:${time}`);
})
/ / / / release
pubSub.publish('offwork'.'18:00:00');
pubSub.publish('launch'.'12:00:00');
pubSub.unSubscribe('onwork');
pubSub.publish('onwork'.'1222:00:00');
Copy the codeJS gets url parameters
let test='? ie=utf-8&f=8&rsv_bp=1&rsv_idx=1&tn=baidu&wd=21331&rsv_pq=b8627e62001efbb9&rsv_t=eef5sqIQ98s66yOwueYH5BWlFUARj0PkHBdCA4ah bSVYQA5qO9MBoZPC0mU&rqlang=cn&rsv_enter=1&rsv_dl=tb&rsv_sug3=5&rsv_sug1=1&rsv_sug7=100&rsv_sug2=0&inputT=509&rsv_sug4=50 9 '
function f(str) {
let str1 = str.slice(1)
let arr=str1.split('&')
console.log(arr)
let map = new Map()
arr.map(item= >{
const [key,value] = item.split('=')
map.set(key,decodeURIComponent(value))
})
return map
}
for (let item of f(test)) {
console.log(item)
}
Copy the code12. Binary tree
// count the number of nodes in the binary tree
function getNodenum(root) {
if (root == null) {
return
}
return getNodenum(root.left) + getNodenum(root.right) + 1
}
// find the maximum depth of the binary tree
function maxDepth(root) {
if (root == null) {
return
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
}
//3. The minimum depth of a binary tree
function minDepth(root) {
if (root == null) return
let left = minDepth(root.left)
let right = minDepth(root.right)
return (left == 0 || right == 0)? left + right +1 : Math.min(left, right) + 1
}
//4.
function preroot(root, callback) {
if(root ! =null) {
callback(root.key)
preroot(root.left, callback)
preroot(root.right, callback)
}
}
// Sequential traversal (non-recursive)
function preroot(root) {
let stack = [],
result = []
if(root ! =null) {
stack.push(root)
}
while(stack.length ! =0) {
let temp = stack.pop()
result.push(temp.key)
if(temp.left ! =null) {
stack.push(temp.left)
}
if(temp.right ! =null) {
stack.push(temp.right)
}
}
return result
}
//5.
function middleroot(root, callback) {
if(root ! =null) {
preroot(root.left, callback)
callback(root.key)
preroot(root.right, callback)
}
}
//5.1 Order traversal (non-recursive)
function middleroot(root) {
let stack = [],
result = []
while (true) {
while(root ! =null) {
stack.push(root)
root = root.left
}
if (stack.length == 0) {
break
}
let temp = stack.pop()
result.push(temp.key)
stack.push(temp.right)
}
return result
}
// Layer traversal (recursion)
function bfs(root) {
let queue = [],
result = []
let pointer = 0
if(root ! =null) {
queue.push(root)
}
let bfsFun = function () {
let temp = queue[pointer]
if (temp) {
result.push(temp.key)
if (temp.left) {
queue.push(temp.left)
}
if (temp.right) {
queue.push(temp.right)
}
pointer++
bfsFun()
}
}
bfsFun()
return result
}
// layer traversal (non-recursive)
function bfs(root) {
let queue = [],
result = []
if(root ! = =null) {
queue.push(root)
}
let pointer = 0
while (pointer < queue.length) {
let temp = queue[pointer++]
result.push(temp.key)
temp.left && queue.push(temp.left)
temp.right && queue.push(temp.right)
}
return result
}
// Prints the binary tree in glyph order
function zhiRoot(root) {
let stack1 = [],
stack2 = [],
result = []
if(root ! =null) {
stack1.push(root)
}
let flag = 1
while(stack1.length ! =0|| stack2.length ! =0) {
const list = []
if (flag % 2) {
while(stack1.length ! =0) {
let temp = stack2.pop()
list.push(temp.key)
temp.left && stack2.push(temp.left)
temp.right && stack2.push(temp.right)
}
} else {
while(stack2.length ! =0) {
let temp = stack1.pop()
list.push(temp.key)
temp.left && stack1.push(temp.left)
temp.right && stack1.push(temp.right)
}
}
i++
result.push(list)
}
return result
}
function Print(root) {
const result = [];
if (root === null) {
return result;
}
const stack1 = [];
const stack2 = [];
stack1.push(root);
let flag = 1;
while(stack1.length ! = =0|| stack2.length ! = =0) {
const list = [];
if (flag % 2) {
while(stack1.length ! = =0) {
const temp = stack2.pop()
list.push(temp.val);
temp.left && stack2.push(temp.left)
temp.right && stack2.push(temp.right)
}
} else {
while(stack2.length ! = =0) {
const temp = stack1.pop()
list.push(tmp.val);
temp.left && stack1.push(temp.left)
temp.right && stack1.push(temp.right)
}
}
i++;
result.push(list);
}
return result;
}
// find the number of nodes at layer K of binary tree
function getknum(root, k) {
if (root == null || k < 0) {
return
}
if(root ! = =null && k == 1) {
return 1
}
return getknum(root.left, k - 1) + getknum(root.right, k - 1)}//8. Find the number of leaves at layer K of the binary tree
function getksonnum(root, k) {
if (root == null || k < 0) {
return
}
if(root ! =null && k == 1) {
if (root.left == null && root.right == null) {
return 1
} else {
return 0}}return getksonnum(root, k - 1) + getksonnum(root, k - 1)}// Invert the binary tree
function reverseRoot(root) {
if (root == null) {
return
}
let temp = root.left
root.left = reverseRoot(root.right)
root.right = reverseRoot(temp)
return root
}
// Find the diameter of the binary tree
function longerlength(root) {
let path = 0
getlongerlength(root)
return path
function getlongerlength(root) {
if (root == null) {
return
}
let left = longerlength(root.left)
let right = longerlength(root.right)
path = Math.max(path, left + right)
return Math.max(left, right) + 1}}// Binary tree neutralizes a path with a certain value
function getPath(root, target) {
let result = []
if (root) {
findPath(root, target, [], 0, result)
}
return result
function findPath(root, target, stack, sum, result) {
stack.push(root.key)
sum += root.key
if(! root.left && ! root.right && sum === target) { result.push(stack.slice(0))}if (root.left) {
findPath(root.left, target, stack, sum, result)
}
if (root.right) {
findPath(root.right, target, stack, sum, result)
}
stack.pop()
}
}
// Given a binary search tree, find the KTH smallest node. (Middle order traversal + k small)
Copy the codeImplement a linked list
function linkedList() {
function node(data) {
this.data = data
this.next = null
}
this.head = null
this.length = 0
linkedList.prototype.append = function (data) {
let newnode = new node(data)
if (this.head == null) {
this.head = newnode
} else {
let current = this.head
while (current.next) {
current = current.next
}
current.next = newnode
this.length++
}
}
linkedList.prototype.find =function(data){
let current = this.head
while(current.next){
if(current.data ===data){
break
}
current = current.next
}
return current
}
linkedList.prototype.fixed=function(data,newdata){
let current= this.find(data)
current.data= newdata
}
linkedList.prototype.prefind =function(data){
let current = this.head
while(current.next){
if(current.next.data ===data){
break
}
current = current.next
}
return current
}
linkedList.prototype.delete = function (data) {
if(this.head.data === data){
this.head = this.head.next
return
}
let prenode=this.prefind(data)
let current=this.find(data)
prenode = current.next
}
linkedList.prototype.toString = function () {
let result = ' '
let current = this.head
while (current) {
result += current.data + "- >"
current = current.next
}
return result
}
}
let a = new linkedList()
a.append('abc')
a.append('abcd')
a.append('abcde')
console.log(a.toString())
a.fixed('abc'.11111)
console.log(a.toString())
Copy the codeHash table
// chain address method
// Load factor (0.25, 0.75)
function HashTable() {
/ / property
this.storage = [] // Storage location
this.count = 0 / / the number of
this.limit = 7 // Finally limit the size of the array
/ / method
// hash function
HashTable.prototype.hashFunc = function (str, size) {
// define the hashCode variable
let hashCode = 0
for (let i = 0; i < str.length; i++) {
//2, Horner algorithm, to calculate the value of hashCode
hashCode = 37 * hashCode + str.charCodeAt(i)
}
//3
let index = hashCode % size
return index
}
// Insert & modify operations
HashTable.prototype.put = function (key, value) {
//1. Obtain the corresponding index based on the key
let index = this.hashFunc(key, this.limit)
// select * from bucket; // select * from bucket
let bucket = this.storage[index]
// check whether the bucket is empty
if (bucket == null) {
bucket = []
this.storage[index] = bucket
}
//4. Check whether the data is modified
for (let i = 0; i < bucket.length; i++) {
let tuple = bucket[i]
if (tuple[0] == key) {
tuple[1] = value
return}}//5. Add operations
bucket.push([key, value])
this.count++
// Determine whether capacity expansion is required
if (this.count > this.limit * 0.75) {
this.resize(this.limit * 2)}}// Get operation
HashTable.prototype.get = function (key) {
let index = this.hashFunc(key, this.limit)
let bucket = this.storage[index]
if (bucket == null) {
return false
}
for (let i = 0; i < bucket.length; i++) {
let tuple = bucket[i]
if (tuple[0] === key) {
return tuple[1]
}
}
}
HashTable.prototype.remove = function (key) {
let index = this.hashFunc(key, this.limit)
let bucket = this.storage[index]
if (bucket == null) {
return null
}
for (let i = 0; i < bucket.length; i++) {
let tuple = bucket[i]
if (tuple[0] == key) {
bucket.splice(i, 1)
this.count--
// Shrink the capacity
if (this.limit > 7 && this.count < this.limit * 0.75) {
this.resize(Math.floor(this.limit / 2))}return tuple[1]}}return null
}
// Hash table expansion,
HashTable.prototype.resize = function (newLimit) {
//1. Save the old data content
let oldStorage = this.storage
//2. Reset all attributes
this.storage = []
this.count = 0
this.limit = newLimit
//3. Walk through all buckets of oldStorage
for (let i = 0; i < oldStorage.length; i++) {
let bucket = oldStorage[i]
if (bucket == null) {
continue
}
for (let j = 0; j < bucket.length; j++) {
let tuple = bucket[i]
this.put(tuple[0], tuple[1])}}}}let a = new HashTable()
a.put('zc'.'15')
a.put('zc1'.'115')
a.put('z1'.'115')
a.put('asd'.'115')
a.put('wew'.'115')
a.remove('wew')
console.log(a.get('wew'))
Copy the code15,
function Queue() {
// Attributes in the stack
this.items = []
//1. Push ()
Queue.prototype.enqueue = function (. element) {
this.items.push(... element) }//2. Remove the front element from the queue
Queue.prototype.dequeue = function () {
return this.items.shift()
}
//3. Take a look at the front-end elements
Queue.prototype.front = function () {
return this.items[0]}//4. Check whether the stack is empty
Queue.prototype.isEmpty = function () {
return this.items.length === 0
}
//5. Get the number of elements in the stack
Queue.prototype.size = function () {
return this.items.length
}
/ / 6. ToString method
Queue.prototype.toString = function () {
return this.items.toString().split(', ').join(' ')}}function Graph() {
// Attributes: vertices (array)/edges (dictionary)
this.vertexes = [] / / the vertices
this.edges = new Map(a)/ / edge
/ / method
// Add the corresponding vertex method
Graph.prototype.addVertex = function (v) {
this.vertexes.push(v)
this.edges.set(v, [])
}
Graph.prototype.addEdge = function (v1, v2) {
this.edges.get(v1).push(v2)
this.edges.get(v2).push(v1)
}
// Implement the toString method
Graph.prototype.toString = function () {
// Define the character rotation to save the final structure
let resultString = ""
for (let i = 0; i < this.vertexes.length; i++) {
resultString += this.vertexes[i] + '- >'
let vEdges = this.edges.get(this.vertexes[i])
for (let j = 0; j < vEdges.length; j++) {
resultString += vEdges[j] + ' '
}
resultString += "\n"
}
return resultString
}
// Graph traversal
// Initialize the state color
Graph.prototype.initializeColor = function () {
let colors = []
for (let i = 0; i < this.vertexes.length; i++) {
colors[this.vertexes[i]] = 'white'
}
return colors
}
// Breadth-first search algorithm (BFS) is done based on queues
Graph.prototype.bfs = function (initV, handler) {
//1. Initialize the color
let colors = this.initializeColor()
//2. Create queues
let queue = new Queue()
//3. Queue vertices
queue.enqueue(initV)
//4. Loop to fetch elements from the queue
while(! queue.isEmpty()) {Fetch a vertex from the queue
let v = queue.dequeue()
//4.2 Get another vertex connected to the vertex
let vList = this.edges.get(v)
//4.3 Set the color of v to grey
colors[v] = 'gray'
//4.4 Traverse all vertices and join the queue
for (let i = 0; i < vList.length; i++) {
let e = vList[i]
if (colors[e] == 'white') {
colors[e] = 'gray'
queue.enqueue(e)
}
}
//4.5 Vertex access
handler(v)
//4.6 Set vertices to black
colors[v] = 'black'}}// Breadth-first search algorithm (DFS)
Graph.prototype.dfs = function (initV, handler) {
let colors = this.initializeColor()
// Recursive access
this.dfsVisit(initV, colors, handler)
}
Graph.prototype.dfsVisit = function (v, colors, handler) {
//1. Set the color to gray
colors[v] = 'gray'
//2. Process node V
handler(v)
//3. Access vertices connected by v
let vList = this.edges.get(v)
for (let i = 0; i < vList.length; i++) {
let e = vList[i]
if (colors[e] === 'white') {
this.dfsVisit(e, colors, handler)
}
}
//4. Set v to black
colors[v] = 'black'}}Copy the codeImplementation of several sorting algorithms
function ArrayList() {
this.array = []
ArrayList.prototype.insert = function (item) {
this.array.push(item)
}
ArrayList.prototype.toString = function () {
return this.array.join(The '-')
}
ArrayList.prototype.swap = function (m, n) {
let temp = this.array[m]
this.array[m] = this.array[n]
this.array[n] = temp
}
// Implement the sorting algorithm
// Bubble sort
ArrayList.prototype.bubbles = function () {
if (this.array === null || this.array.length < 2) return this.array
let length = this.array.length
for (let i = length - 1; i >= 0; i--) {
for (let j = 0; j < i; j++) {
if (this.array[j] > this.array[j + 1]) {
this.swap(j, j + 1)}}}}// Select sort
ArrayList.prototype.selectSort = function () {
if (this.array === null || this.array.length < 2) return this.array
let length = this.array.length
for (let i = 0; i < length - 1; i++) {
let min = i
for (let j = i + 1; j < length; j++) {
if (this.array[min] > this.array[j]) {
min = j
}
}
this.swap(min, i)
}
}
// Insert sort
ArrayList.prototype.insertSort = function () {
if (this.array === null || this.array.length < 2) return this.array
let length = this.array.length
for (let i = 1; i < length; i++) {
var temp = this.array[i]
let j = i
while (this.array[j - 1] > temp && j > 0) {
this.array[j] = this.array[j - 1]
j--
}
this.array[j] = temp
}
}
// Advanced sort
// Hill sort (upgrade to insert sort)
ArrayList.prototype.shellSort = function () {
if (this.array === null || this.array.length < 2) return this.array
let length = this.array.length
// Initialize the increment
var gap = Math.floor(length / 2)
/ / whlie cycle
while (gap > 1) {
for (let i = gap; i < length; i++) {
let temp = this.array[i]
let j = i
while (this.array[j - gap] > temp && j > gap - 1) {
this.array[j] = this.array[j - gap]
j -= gap
}
this.array[j] = temp
}
gap = Math.floor(gap / 2)}}}Copy the code/ / fast row
function median(arr, left, right) {
let center = Math.floor(left + (right - left) / 2)
if (arr[left] > arr[center]) {
swap(arr, left, right)
}
if (arr[center] > arr[right]) {
swap(arr, center, right)
}
if (arr[left] > arr[right]) {
swap(arr, left, right)
}
swap(center, right - 1)
return arr[right - 1]}function swap(arr, m, n) {
let temp = arr[m]
arr[m] = arr[n]
arr[n] = temp
}
function quickSort(arr) {
if(arr.length<=1) {return arr
}
return quickSortFun(arr, 0, arr.length - 1)}function quickSortFun(arr, left, right) {
if(left<right){
let pivot = median(arr, left, right)
let i = 0
let j = right - 1
while (true) {
while (arr[++i] < pivot) {
}
while (arr[--j] > pivot && j>left) {
}
if (i < j) {
swap(arr, i, j)
} else {
break}}if(i<right){
swap(arr, i, right - 1)
}
quickSortFun(arr, left, i - 1)
quickSortFun(arr, i + 1, right)
}
return arr
}
console.log(quickSort([1.4.2.3.1]))
Copy the code17. Handwritten iterators
var it = makeIterator(["a"."b"]);
console.log(it.next())
console.log(it.next())
console.log(it.next())
function makeIterator(array) {
let nextindex=0
return{
next:function () {
if(nextindex<array.length){
return {value:array[nextindex++],done:false}}else{
return {value: undefined.done: true}
}
}
}
}
Copy the code18. Maximum continuous subsequence
let arr = [1.- 5.8.3.4 -.15.- 8 -]
// function getNum(arr) {
// let length = arr.length
// let maxmun=0
// for (let i = 0; i
// let sum=arr[i]
// for (let j = i+1; j < length; j++) {
// sum+=arr[j]
// if(sum>maxmun){
// maxmun = sum
/ /}
//
/ /}
/ /}
// return maxmun
// }
function getNum(arr) {
let max = 0
let sum = 0
for (let num of arr) {
if (sum < 0) {
sum = 0
}
sum += num
max = Math.max(max, sum)
}
return max
}
console.log(getNum(arr))
Copy the codeImplement an EventListener class containing on, OFF, and EMIT methods
// Implement an EventListener class containing on, off, and EMIT methods
class EventListener {
constructor() {
this.list = {}
}
on(key, fn) {
if (!this.list[key]) {
this.list[key] = []
}
this.list[key].push(fn) } emit(key, ... args) {for (let fn of this.list[key]) {
fn.apply(this, args)
}
}
off(key, fn) {
let fnlist = this.list[key]
if(! fnlist)return
if(! fn) { fnlist.length =0
} else {
fnlist.forEach((item, index) = > {
if (item === fn) {
fnlist.splice(index, 1)}})}}}let obj1 = new EventListener()
obj1.on('work', value => {
console.log(I was `${value}Ah `)
})
obj1.on('eat', value => {
console.log(I in `${value}Ah `)
})
obj1.emit('work'.'zc')
obj1.off('eat')
obj1.emit('eat'.'Eat watermelon')
Copy the code20. Sleep function
Write a delay function with promise
function sleep(time) {
return new Promise((resolve,reject) = >{
setTimeout(resolve,time)
})
}
sleep(1000).then(value= >{
console.log('11111')})Copy the codeHandwriting Fibonacci
/ / recursion
function getnum(num) {
if(num<=1) return 1
return getnum(num- 1)+getnum(num2 -)}console.log(getnum(2))
// ----------------------------------
// Dynamic programming
function getnum(n) {
let temp=[]
if(n==1||n==2) {return 1
}else{
temp[1] =1
temp[2] =2
for (let i = 3; i <n ; i++) {
temp[i] = temp[i- 1] + temp[i2 -]}return temp[i- 1]}}Copy the code22, only contains ‘(‘, ‘)’, ‘[‘, ‘]’, ‘{‘, ‘}’ string, check whether valid.
var isValid = function(s) {
var rightSymbols = [];
for (var i = 0; i < s.length; i++) {
if(s[i] == "("){
rightSymbols.push(")");
}else if(s[i] == "{"){
rightSymbols.push("}");
}else if(s[i] == "["){
rightSymbols.push("]");
}else if(rightSymbols.pop() ! = s[i] ){return false; }}return! rightSymbols.length; };Copy the code23. A number that appears only once in an array
let arr=[1.2.3.4.3.2.1]
const p=arr.reduce((a,b) = >{
return a^b
})
console.log(p)
Copy the code24. Maximum depth of array
let arr = [1[1[3].2].2[1].3.4]
let count = 0
function getDep(arr) {
let p = false
p = arr.some(item= > {
return item.length > 0
})
if (p) {
count++
getDep(arr.flat())
} else {
return count
}
}
console.log(getDep(arr))
Copy the codeRecursive array flattening
let arr= [1.2.3.2[2.3], [2[1].2]]
function wrap() {
let ret=[]
return function flatten(arr) {
for(let item of arr){
if(item.constructor === Array){
ret.concat(flatten(item))
}else{
ret.push(item)
}
}
return ret
}
}
console.log(wrap()(arr))
Copy the code26, simulation JS precision loss problem
The IEEE 754 standard
function add(num1, num2) {
const num1Digits = (num1.toString().split('. ') [1] | |' ').length;
const num2Digits = (num2.toString().split('. ') [1] | |' ').length;
const baseNum = Math.pow(10.Math.max(num1Digits, num2Digits));
return (num1 * baseNum + num2 * baseNum) / baseNum;
}
console.log(add(0.1.0.2))
Copy the code27. Singleton mode
// The singleton pattern is opaque
function singleTon(name) {
this.name = name
this.instance = null
}
singleTon.prototype.getName=function () {
console.log(this.name)
}
singleTon.getInstance = function (name) {
if(!this.instance){
this.instance = new singleTon(name)
}
return this.instance
}
var b = singleTon.getInstance('bbbbb')
var a = singleTon.getInstance('a')
console.log(a)
console.log(b)
// ----------------------------------
// The singleton pattern is opaque (closure)
function singleTon(name) {
this.name = name
}
singleTon.prototype.getName=function () {
console.log(this.name)
}
singleTon.getInstance = (function () {
let instance = null
return function (name) {
return instance || (instance = new singleTon(name))
}
})()
var a = singleTon.getInstance('a')
var b = singleTon.getInstance('bbbbb')
var c = singleTon.getInstance('cccccc')
console.log(a)
console.log(b)
console.log(c)
Copy the code// The singleton is transparent
let getInstance = (function () {
let instance = null
return function (name) {
if(! instance){this.name = name
return instance=this
}
return instance
}
})()
let a= new getInstance('aa')
let b= new getInstance('bbbb')
console.log(a)
console.log(b)
Copy the code// let getSingle = function (fn) {
// let result= null
// return function () {
// return result || (result = fn.call(this,... arguments))
/ /}
// }
// A generic singleton validation method
const getSingle = function (fn){
let result;
return function (){
return result || (result = fn.apply(this.arguments));
};
};
function a(name) {
this.name = name
}
var b = getSingle(a)
var d = b('bbb'.'xxx'.'yyyyy')
var c = b('aaa')
console.log(d)
console.log(c)
Copy the code28. Strategy mode
// Policy class (developer)
var Strategies = {
"backend": function(task) {
console.log('Performing back-end tasks:', task);
},
"frontend": function(task) {
console.log('Perform front-end tasks:', task);
},
"testend": function(task) {
console.log('Perform a test task:', task); }};// Environment class (Development team leader)
var Context = function(type, task) {
typeof Strategies[type] === 'function' && Strategies[type](task);
}
Copy the code29. Proxy mode
// [image preloading -- proxy mode]
// Define ontology
let myImg=(function () {
var img = new Image()
document.body.append(img)
return {
setsrc(src){
this.src=src
}
}
})()
// proxy function
let Proxysetimg = (function () {
var img = new Image()
img.onload =function () {
myImg.setsrc(this.src)
}
return{
setsrc(src){
myImg.setsrc('./loading.gif')
img.src = src
}
}
})()
Proxysetimg('./111.png')
Copy the codeObserver mode
// Target class
class Subject {
constructor() {
this.observers = []; // List of observers
}
/ / add
add(observer) {
this.observers.push(observer);
}
/ / delete
remove(observer) {
let idx = this.observers.findIndex(item= > item === observer);
idx > - 1 && this.observers.splice(idx, 1);
}
/ / notice
notify() {
for (let observer of this.observers) { observer.update(); }}}// Observer class
class Observer {
constructor(name) {
this.name = name;
}
// The callback triggered when the target object is updated
update() {
console.log('The target informed me of the update. I am:The ${this.name}`); }}// instantiate the target
let subject = new Subject();
// Instantiate two observers
let obs1 = new Observer('Front-end Developer');
let obs2 = new Observer('Backend Developer');
// Add an observer to the target
subject.add(obs1);
subject.add(obs2);
// Target notification update
subject.notify();
/ / output:
// The target notified me of the update. I am a front-end developer
// The target notified me of the update. I am a backend developer
Copy the code31. Command mode
class Receiver { // Receiver class
execute() {
console.log('Receiver performs request'); }}class Command { // Command object class
constructor(receiver) {
this.receiver = receiver;
}
execute () { // The call receiver is executed on the interface
console.log('Command Object -> Receiver -> Interface execution');
this.receiver.execute(); }}class Invoker { // Publisher class
constructor(command) {
this.command = command;
}
invoke() { // Issue the request to invoke the command object
console.log('Publisher publishes request');
this.command.execute(); }}const warehouse = new Receiver(); / / warehouse
const order = new Command(warehouse); / / order
const client = new Invoker(order); / / customer
client.invoke();
Copy the code32. Promise handles file reads
const fs = require('fs')
const path = require('path');
const readfile = function (filename) {
return new Promise((resolve, reject) = > {
fs.readFile(path.join(__dirname, filename), 'utf-8'.function (error, data) {
if (error) return reject(error)
resolve(data)
})
})
}
readfile('./01.txt')
.then(value= > {
console.log(value)
return readfile('./02.txt')
})
.then(value= > {
console.log(value)
return readfile('./03.txt')
})
.then(value= > {
console.log(value)
}).catch(reason= > {
console.log(reason)
})
Copy the codeGenerator function file read
const fs = require('fs')
const path = require('path');
const readfile = function (filename) {
return new Promise((resolve, reject) = > {
fs.readFile(path.join(__dirname, filename), 'utf8'.function (error, data) {
if (error) return reject(error)
resolve(data)
})
})
}
function* gen() {
yield readfile('./01.txt')
yield readfile('./02.txt')
yield readfile('./03.txt')}const result = gen()
result.next().value.then(value= >{
console.log(value)
return result.next().value
}).then(value= > {
console.log(value)
return result.next().value
}).then(value= > {
console.log(value)
}).catch(reason= > {
console.log(reason)
})
Copy the codeAsync function file reading
const fs = require('fs')
const path = require('path');
const readfile = function (filename) {
return new Promise((resolve, reject) = > {
fs.readFile(path.join(__dirname, filename), 'utf8'.function (error, data) {
if (error) return reject(error)
resolve(data)
})
})
}
async function gen() {
try{
const f1=await readfile('./01.txt')
const f2=await readfile('./02.txt')
const f3 = await readfile('./03.txt')
console.log(f1)
console.log(f2)
console.log(f3)
}catch (e) {
console.log(e)
}
}
gen()
Copy the code