实现继承
// call方法
// 缺点无法继承原型方法
function Parent () {}
function Child () {
Parent.call(this)
}
// 原型链继承
// 缺点：所有实例共用同一个原型对象
function Parent () {}
function Child () {}
Child.prototype = new Parent()
// 组合形式
function Parent () {}
function Child () {
Parent.call(this)
}
Child.prototype. = Object.create(Parent.prototype)
Child.prototype.constructor = Child
// es6继承
class Parent {}
class Child extends Parent {
constructor() {
super()
}
}
防抖
function debounce (fn, delay) {
let timer = null
return function () {
const that = this
const ars = Array.prototype.slice.call(arguments)
if (timer) {
clearTimeout(timer)
}
timer = setTimeout(() => {
fn.apply(that, ars)
}, delay)
}
节流
function throttle(fn, delay) {
let timer = null
return function () {
const that = this
if (timer) {
return
}
const args = Array.prototype.slice.call(arguments)
timer = setTimerout(() => {
fn.apply(that, args)
timer = null
}, delay)
}
}
reduce实现map
Array.prototype.map = function (cb) {
return this.reduce((acc, cur, index, arr) => {
acc.push(cb.call(null, cur, index, arr))
return acc
}, [])
}
二叉树遍历
// 前序遍历
function visit (node) {
const arr = []
function _v (n) {
if (!n) return
arr.push(n.val)
_v(n.left)
_v(n.right)
}
_v(node)
return arr
}
function visit(node) {
const arr = []
const stack = [node]
while(stack.length) {
const curNode = stack.pop()
arr.push(curNode.val)
if (curNode.right) {
stack.push(node.right)
}
if(curNode.left){
stack.push(node.left)
}
}
return arr
}
// 中续遍历
function visit (node) {
let arr = []
function _v (n) {
if (!n) return
_v(n.left)
arr.push(n.val)
_v(n.right)
}
_v(node)
return arr
}
// 中序遍历 迭代法
var inorderTraversal = function(root) {
const stack = []
const res = []
while(root || stack.length) {
while(root) {
stack.push(root)
root = root.left
}
const curNode = stack.pop()
res.push(curNode.val)
root = curNode.right
}
return res
};
// 后续遍历
function visit (node) {
let arr = []
function _v (n) {
if (!n) return
_v(n.left)
_v(n.right)
arr.push(n.val)
}
_v(node)
return arr
}
// 迭代法 后序遍历
var postorderTraversal = function (root) {
const stack = [root];
const res = [];
while (stack.length > 0) {
const node = stack.pop();
if (node) {
stack.push(node.left, node.right);
res.unshift(node.val);
}
}
return res;
};
// 层序遍历
function solution (root) {
const res = []
if (!root) {
return res
}
const queue = []
queue.push(root)
while (queue.length !== 0) {
const curQueueLength = queue.length
const curArr = []
for (let i = 0; i < curQueueLength; i++) {
const node = queue.shift()
curArr.push(node.val)
node.left && queue.push(node.left)
node.right && queue.push(node.right)
}
res.push(curArr)
}
return res
}
数组去重
function unique (arr) {
if (Array.isArray(arr)) {
return Array.from(new Set(arr))
}
}
function unique (arr) {
let cache = {}
let uniqueArr = []
for (let i = 0; i < arr.length; i++) {
if (arr[i] in cache) {
continue
} else {
cache[arr[i]] = true
uniqueArr.push(arr[i])
}
}
return uniqueArr
}
斐波那契数列
function Fibonacci(j)
{
// n = (n-1)+(n-2)
const cache = {
0: 0,
1: 1
}
function _fibonacci (n) {
if (cache[n] !== undefined) {
return cache[n]
}
cache[n] = _fibonacci(n-1) + _fibonacci(n-2)
return cache[n]
}
return _fibonacci(j)
}
function fbnc (n) {
let cur = new Array(n)
cur[0] = 0
cur[1] = 1
for (let i = 2; i < n; i++) {
cur[i] = cur[i - 1] + cur[i - 2]
}
return cur
}
调度器
//JS实现一个带并发限制的异步调度器Scheduler，保证同时运行的任务最多有两个。完善代码中Scheduler类，使得以下程序能正确输出
class Scheduler {
constructor() {
this.tasks = {}
this.queue = []
this.uid = 0
}
get taskLength() {
return Object.keys(this.tasks).length
}
add(promiseCreator) {
return new Promise((resolve) => {
this.queue.push({
id: this.uid++,
isCreated: false,
promiseCreator,
resolve
})
this.pushTasks()
})
}
pushTasks () {
if (this.taskLength < 2 && this.queue.length > 0) {
const cur = this.queue.shift()
this.tasks[cur.id] = cur
}
this.startTasks()
}
startTasks () {
for(let id in this.tasks) {
const task = this.tasks[id]
if (task.isCreated) {
continue
}
task.isCreated = true
task.promiseCreator().then(() => {
task.resolve()
delete this.tasks[id]
this.pushTasks()
})
}
}
// ...
}
const timeout = (time) => new Promise(resolve => {
setTimeout(resolve, time)
})
const scheduler = new Scheduler()
const addTask = (time, order) => {
scheduler.add(() => timeout(time)).then(() => console.log(order))
}
addTask(1000, '1')
addTask(500, '2')
addTask(300, '3')
addTask(400, '4')
// output: 2 3 1 4
// 一开始，1、2两个任务进入队列
// 500ms时，2完成，输出2，任务3进队
// 800ms时，3完成，输出3，任务4进队
// 1000ms时，1完成，输出1
// 1200ms时，4完成，输出4
数组快排
// 冒泡
var sortArray = function(arr) {
const max = arr.length
for(let i = 0; i < max - 1; i++) {
for (let j = 0; j < max - 1 -i; j++) {
if (arr[j] > arr[j+1]) {
const temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
}
}
}
return arr
};
// 快排
var quickSort = function(arr) {
if (arr.length <= 1) {
return arr;
}
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
};
洗牌算法 （打乱数组）
function randArr (arr) {
const n = arr.length
const randOne = (min, max) => Math.floor(Math.random() * (max - min + 1) + min)
for(let i = 0; i < n; i++) {
const rand = randOne(i, n - 1)
const temp = arr[i]
arr[i] = arr[rand]
arr[rand] = temp
}
return arr
}
二分查找
var search = function(nums, target) {
let l = 0;
let r = nums.length - 1
while(l <= r) {
const m = Math.floor((l + r) / 2)
if(nums[m] == target) {
return m
} else if( target < nums[m]) {
r = m - 1
} else {
l = m + 1
}
}
return -1
};
翻转链表
function ReverseList(pHead)
{
let pre = null
while(pHead) {
const next = pHead.next
pHead.next = pre
pre = pHead
pHead = next
}
return pre
}
sleep
function sleep(delay){
return new Promise((resolve) => {
setTimeout(resolve, delay)
})
}
Emitter
class Emitter {
constructor() {
this.listeners = {}
}
addEventListener (name, fn) {
this.on(name, fn)
}
on(name, fn) {
if (name in this.listeners) {
this.listeners[name].push(fn)
} else {
this.listeners[name] = [fn]
}
}
emit(name, ...args) {
const events = this.listeners[name]
for(let i = 0; i < events.length; i++) {
events[i](args)
}
}
removeListener(name, fn) {
const events = this.listeners[name] || []
const i = events.indexOf(fn)
if (~i) {
events.splice(i, 1)
}
}
once(name, listener) {
const self = this
const fn = function () {
const args = Array.prototype.slice.call(arguments)
listener.apply(null, args)
self.removeListener(name, fn)
}
this.on(name, fn)
}
}
实现两个大数相加 IEEE754
function add(a ,b){
//取两个数字的最大长度
let maxLength = Math.max(a.length, b.length);
//用0去补齐长度
a = a.padStart(maxLength , 0);//"0009007199254740991"
b = b.padStart(maxLength , 0);//"1234567899999999999"
//定义加法过程中需要用到的变量
let t = 0;
let f = 0; //"进位"
let sum = "";
for(let i=maxLength-1 ; i>=0 ; i--){
t = parseInt(a[i]) + parseInt(b[i]) + f;
f = Math.floor(t/10);
sum = t%10 + sum;
}
if(f == 1){
sum = "1" + sum;
}
return sum;
}
深拷贝
function deepClone(raw) {
const type = Object.prototype.toString.call(raw)
if (type == '[object Number]' ||
type == '[object String]' ||
type == '[object Null]' ||
type == '[object Undefined]'
) {
return raw
}
let obj
if(Array.isArray(raw)) {
obj = []
for(let i = 0; i < raw.length; i++) {
obj[i] = deepClone(raw[i])
}
return obj
} else {
obj = {}
Object.keys(raw).forEach(key => {
obj[key] = deepClone(raw[key])
})
return obj
}
}
回文字符串
function judge(str) {
const mid = str.length % 2 ? (str.length + 1) / 2 : str.length / 2
let start = 0;
let end = str.length - 1
let value = true
for (let i = 0; i <= mid; i++) {
if (str[start] == str[end]) {
continue
} else {
value = false
}
}
return value
}
手写bind
function myBind (asThis) {
const fn = this
const slice = Array.prototype.slice
const args = slice.call(arguments, 1)
return function () {
const args2 = slice.call(arguments)
return fn.apply(asThis, args.concat(args2))
}
}
手写promise.all
function promiseAll (arr) {
return new Promise((resolve, reject) => {
const list = []
if (arr.length < 1) {
resolve([])
return
}
for (let i = 0; i < arr.length; i++) {
const item = arr[i]
Promise.resolve(item).then(val => {
list[i] = val
if (i == arr.length) {
resolve(list)
}
}).catch(e => {
reject(e)
})
}
})
}
