高阶函数实现AOP(面向切面编程)
Function.prototype.before = function (beforefn) {
let _self = this; // 缓存原函数的引用
return function () { // 代理函数
beforefn.apply(this, arguments); // 执行前置函数
return _self.apply(this, arguments); // 执行原函数
}
}
Function.prototype.after = function (afterfn) {
let _self = this;
return function () {
let set = _self.apply(this, arguments);
afterfn.apply(this, arguments);
return set;
}
}
let func = () => console.log('func');
func = func.before(() => {
console.log('===before===');
}).after(() => {
console.log('===after===');
});
func();
输出结果:
===before===
func
===after===
阶乘
JS中文网 – 前端进阶资源教程 www.javascriptC.com
一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
const factorial1 = n => {
if (n <= 1) return 1
return n * factorial1(n - 1)
}
// 尾递归优化
const factorial2 = (n, total = 1) => {
if (n <= 1) return total
return factorial2(n - 1, total * n)
}
console.log(factorial1(3)) // 6
console.log(factorial2(3)) // 6
console.log(factorial1(5)) // 120
console.log(factorial2(5)) // 120
二分查找
//循环不变式 guess 等于l r中间位置
const bsearch = (A, x) => {
let l = 0
let r = A.length - 1
let guess
while (l <= r) {
console.log('find')
guess = Math.floor((l + r) / 2)
if (A[guess] === x) return guess
if (A[guess] > x) r = guess - 1
else l = guess + 1
}
return -1
}
let arr = [1, 2, 3, 4, 5, 6, 7, 8]
console.log(bsearch(arr, 6)) // 5
斐波那契数列
斐波那契数列从第三项开始,每一项都等于前两项之和。指的是这样一个数列:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 …
得到数列中第n项指向的数值是多少
1.递归
function fib(n) {
if (n === 1 || n === 2) return n - 1;
return fib(n - 1) + fib(n - 2)
}
console.log(fib(10)); // 34
时间复杂度为O(2^n)
2.非递归
function fib(n) {
let a = 0;
let b = 1;
let c = a + b;
for (let i = 3; i < n; i++) {
a = b;
b = c;
c = a + b;
}
return c;
}
console.log(fib(10)); // 34
时间复杂度为O(n)
实现栈结构
const Stack = (() => {
const wm = new WeakMap()
class Stack {
constructor() {
wm.set(this, [])
this.top = 0
}
push(...nums) {
let list = wm.get(this)
nums.forEach(item => {
list[this.top++] = item
})
}
pop() {
let list = wm.get(this)
let last = list[--this.top]
list.length = this.top
return last
}
peek() {
let list = wm.get(this)
return list[this.top - 1]
}
clear() {
let list = wm.get(this)
list.length = 0
}
size() {
return this.top
}
output() {
return wm.get(this)
}
isEmpty() {
return wm.get(this).length === 0
}
}
return Stack
})()
let s = new Stack()
s.push(1, 2, 3, 4, 5)
console.log(s.output()) // [ 1, 2, 3, 4, 5 ]
十进制转化为其他进制 (利用栈)
function divideBy2(decNumber, base = 2) {
let remStack = new Stack()
let rem
let binaryString = ''
let digits = '0123456789ABCDEF' //Js中文网 - 前端进阶资源分享(https://www.javascriptc.com/)
while (decNumber > 0) {
rem = Math.floor(decNumber % base)
remStack.push(rem)
decNumber = Math.floor(decNumber / base)
}
while (!remStack.isEmpty()) {
binaryString += digits[remStack.pop()].toString()
}
return binaryString
}
// 将十进制转换成其他进制
let num = 100345
num.toString(2) // "11000011111111001"
num.toString(8) // "303771"
console.log(divideBy2(num, 2)) // "11000011111111001"
console.log(divideBy2(num, 8)) // "303771"
一道关于Array push的JS题
// 类数组
let obj = {
'1': 'a',
'2': 'b',
length: 2,
push: Array.prototype.push
};
// Array.prototype.push.call(obj, 'c');
obj.push('c')
console.log(obj); // { '1': 'a', '2': 'c', length: 3 }
JS中文网 – 前端进阶资源教程 www.javascriptC.com
一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
push和pop实现
Array的push底层实现是依赖于 数组的length属性的
Array.prototype.push2 = function(...rest){
this.splice(this.length, 0, ...rest)
return this.length;
}
对于 pop也是一样
Array.prototype.pop2 = function(){
return this.splice(this.length - 1, 1)[0];
}
算法题
1.在一个数组中 找出里面其中两项相加后的和为num,如果存在就返回两个数的索引位置,否则false
function fn(num = 0, ary = []) {
for (let i = 0; i < ary.length; i++) {
let diff = num - ary[i];
let diffIndex = ary.indexOf(diff);
if (diffIndex !== -1 && diffIndex !== i) {
return [i, diffIndex];
}
}
return false;
}
let num = 3;
let arr = [-1, 4, 6, 2];
console.log(fn(num, arr)); // [0, 1]
2. 将两个有序数组合并为一个排好序的大数组
function mergeAry(left = [], right = []) {
const result = [];
while (left.length && right.length) {
result.push(left[0] <= right[0] ? left.shift() : right.shift());
}
return result.concat(left, right); Js中文网 - 前端进阶资源分享(https://www.javascriptc.com/)
}
console.log(mergeAry([1, 2, 3], [1, 4, 8, 9])); // [ 1, 1, 2, 3, 4, 8, 9 ]
3.在数组中找到三个不同元素 其中两项的和当于第三项 arr[x] + arr[y] = arr[z] 如果数组中存在返回true 否则返回false
如:
[1, 18, 3, 2] => 1 + 2 = 3 => true;
[3, 11, 2, 7] => false
let a1 = [2, 99, 3, 5]
let a2 = [1, 2, 10, 5]
function find(arr) {
arr.sort((a, b) => a - b)
for (let i = 0; i < arr.length - 1; i++) {
let cur = arr[i]
for (let k = i + 1; k < arr.length; k++) {
let next = arr[k]
let diff = next - cur
if (![cur, next].includes(diff) && arr.includes(diff)) {
return true
}
}
}
return false
}
console.log(find(a1)) // true
console.log(find(a2)) // false
字符串repeat实现
// 原生repeat
'ni'.repeat(3); // 'ninini'
// 实现一
String.prototype.repeatString1 = function (n) {
return Array(n + 1).join(this);
}
console.log('ni'.repeatString1(3));
// 实现二
String.prototype.repeatString2 = function (n) {
return Array(n).fill(this).join('');
}
console.log('ni'.repeatString2(3));
当我们 new 一个类的时候 都发生了什么
/**
* new2 new关键字的代码实现演示 Js中文网 - 前端进阶资源分享(https://www.javascriptc.com/)
* @param {function} func 被new的类 (构造函数)
*/
function new2(func) {
// 创建了一个实例对象 o,并且这个对象__proto__指向func这个类的原型对象
let o = Object.create(func.prototype);
// (在构造函数中this指向当前实例)让这个类作为普通函数值行 并且里面this为实例对象
let k = func.call(o);
// 最后再将实例对象返回 如果你在类中显示指定返回值k,
// 注意如果返回的是引用类型则将默认返回的实例对象o替代掉
return typeof k === 'object' ? k : o;
}
// 实验
function M() { // 即将被new的类
this.name = 'liwenli';
}
let m = new2(M); // 等价于 new M 这里只是模拟
console.log(m instanceof M); // instanceof 检测实例
console.log(m instanceof Object);
console.log(m.__proto__.constructor === M);
this/bind
let obj = { a: 1};
function fn() {
this.b = 100;
return this.a;
}
let fe = fn.bind(obj);
console.log(fe()); // 1 里面this是obj
console.log(obj); // { a: 1, b: 100 }
console.log(new fe()); // 里面this是当前创建实例对象 { b: 100 }
Object.create 兼容实现
let obj1 = {id: 1};
Object._create = (o) => {
let Fn = function() {}; // 临时的构造函数
Fn.prototype = o;
return new Fn;
}
let obj2 = Object._create(obj1);
console.log(obj2.__proto__ === obj1); // true
console.log(obj2.id); // 1
// 原生的Object.create Js中文网 - 前端进阶资源分享(https://www.javascriptc.com/)
let obj3 = Object.create(obj1);
console.log(obj3.__proto__ === obj1); // true
console.log(obj3.id); // 1
一道面试题
解法一
JS中文网 – 前端进阶资源教程 www.javascriptC.com
一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
function CodingMan(name) { // 主要考察的是 面向对象以及JS运行机制(同步 异步 任务队列 事件循环)
function Man(name) {
setTimeout(() => { // 异步
console.log(`Hi! This is ${name}`);
}, 0);
}
Man.prototype.sleep = function(time) {
let curTime = new Date();
let delay = time * 1000;
setTimeout(() => { // 异步
while (new Date() - curTime < delay) {} // 阻塞当前主线程
console.log(`Wake up after ${time}`);
}, 0);
return this;
}
Man.prototype.sleepFirst = function(time) {
let curTime = new Date();
let delay = time * 1000;
while (new Date() - curTime < delay) {} // 阻塞当前主线程
console.log(`Wake up after ${time}`);
return this;
}
Man.prototype.eat = function(food) {
setTimeout(() => { // 异步
console.log(`Eat ${food}~~`);
}, 0)
return this;
}
return new Man(name);
}
// CodingMan('Peter');
// CodingMan('Peter').sleep(3).eat('dinner');
// CodingMan('Peter').eat('dinner').eat('supper');
// CodingMan('Peter').sleepFirst(5).eat('supper');
解法二
function CodingMan(name) {
function fe() {
fe.flag = true;
console.log(`Hi! This is ${name}`);
}
fe.flag = false;
fe.timer = setTimeout(() => {
clearTimeout(fe.timer);
if (!fe.flag) fe();
}, 0);
return fe;
}
Function.prototype.sleep = function (delay) {
this()
this.await(delay);
return this;
}
Function.prototype.sleepFirst = function (delay) {
this.await(delay);
this();
return this;
}
Function.prototype.eat = function (dinner) {
setTimeout(() => {
console.log(`Eat ${dinner}~`);
});
return this;
};
Function.prototype.await = function (delay) {
delay = isNaN(delay) ? 0 : delay;
let startTime = new Date();
let delayTime = delay * 1000;
while (new Date() - startTime <= delayTime) {
}
console.log(`Wake up after ${delayTime}ms`);
}
// CodingMan('peter')
// CodingMan('peter').sleep(2).eat('hanbao');
// CodingMan('peter').sleepFirst(2).eat('hanbao');
CodingMan('peter').eat('haha').eat('hanbao');
currying 函数柯理化
bind 柯理化
function add(a, b, c) {
return a + b + c;
}
let f1 = add.bind(undefined, 100);
console.log(f1(2, 3)); // 105 = 100 + 2 + 3
let f2 = f1.bind(undefined, 200);
console.log(f2(3)); // 303 = 100 + 200 + 3
curry 柯理化的实现(递归调用 + valueOf)
知识点:对象的valueOf浏览器环境下 隐式转化为基本数据类型(一元操作符+object/字符串拼接 ”+object)时,会调用自身的valueOf方法取值,如果自身也存在toString方法 先调用valueOf 如果valueOf返回值不是基本数据类型 则调用toString, toString的返回值也不是基本数据类型就报错。
valueOf调用场景
let obj = { x: 1, y: 2 };
obj.toString = function() {
return this.x + this.y;
}
obj.valueOf = function() {
return this.x + this.y + 100;
}
// 以下情况下自身valueOf被调用
console.log('' + obj); // 103
console.log(+obj); // 103
function fn() {};
fn.valueOf = () => console.log('valueof');
console.log(fn); // valueof
const mul = x => {
const result = y => mul(x * y); // 递归调用mul
result.valueOf = () => x;
return result;
}
console.log(mul(2)(3)); // 6
// 在上面mul每执行一次,就会返回一个valueOf被改写后的新函数result 并且result执行会在里面调用mul(x * y)
// 在result函数的valueOf里保存着 由上一次x * y 传进来的结果x, 也就是上一次x*y 会作为这一次的输出 依然叫x
// 第一次mul(2) 此时 x为2 return result
result 为 result = y => mul(2 * y);
// 第二次 mul(2)(3) 等价于 第一个mul返回的result(3), result执行 => mul(2 * 3) 再次调用mul 将2*3 = 6 的结果作为mul参数
// 最后mul(6) x = 6 在返回一个新函数result 此时result的valueOf = () => 6
// log(mul(2)(3)) 相当于log的最后返回的result 隐式调用valueOf 返回 6
curry 将多参数函数转换为接收单一参数的函数
function fe(a, b, c) {
return a + b + c;
}
function curry(fe) {
let args = []; // 参数集合
let len = args.length;
return function bar() {
args = [...args, ...arguments]; // 收集参数
if (args.length >= fe.length) {
return fe.apply(this, args);
}
return bar;
}
}
console.log(curry(fe)(1)(2)(3)); // 6
currying 部分求值
// currying 函数柯理化
let currying = function(fn) {
let args = [];
return function fe() {
if (arguments.length === 0) {
return fn.apply(this, args);
}
[].push.apply(args, arguments);
return fe;
}
}
let count = currying(function (...rest) {
return rest.reduce((prev, cur) => prev + cur, 0);
});
console.log(count(100)(200)(10)()); // 310
收集参数 延迟执行 到达指定次数才执行
// 参数收集 指定次数后执行
function fn(...rest) {console.log(rest);};
function after(fn, time = 1) {
let params = [];
return function(...rest) {
params = [...params, ...rest];
if (--time === 0) {
fn.apply(this, params);
}
}
}
let newFn = after(fn, 3); // 执行3次 内部fn才会执行
newFn(2);
newFn(3);
newFn(4);
函数节流
throttle 策略的电梯。保证如果电梯第一个人进来后,50毫秒后准时运送一次,不等待。如果没有人,则待机。
let throttle = (fn, delay = 50) => { // 节流 控制执行间隔时间 防止频繁触发 scroll resize mousemove
let stattime = 0;
return function (...args) {
let curTime = new Date();
if (curTime - stattime >= delay) {
fn.apply(this, args);
stattime = curTime;
}
}
}
正则效验 必须包含数字、字母大小写
// 同时包含 数字 字母大小写
// let reg = /^(?!([a-zA-Z]+|\d+)$)[a-zA-Z\d]{8,15}$/
// ^(?![0-9]+$)(?![a-zA-Z]+$)[0-9A-Za-z]
let reg = /^(?!([a-zA-Z]+|[a-z\d]+|[A-Z\d]+)$)[a-zA-Z\d]{8,15}$/
console.log(reg.test('lolABC123')) // true
console.log(reg.test('lol12313123')) // false
console.log(reg.test('ADF12313123')) // false
console.log(reg.test('12312313123')) // false
console.log(reg.test('LLLLLLLLLL')) // false
console.log(reg.test('aaaaaaass')) // fals
函数防抖完全版
/**
* @desc 函数防抖
* @param func 函数
* @param wait 延迟执行毫秒数
* @param immediate true 表立即执行,false 表非立即执行
*/
function debounce(func,wait,immediate) {
var timeout;
return function () {
var context = this;
var args = arguments;
if (timeout) clearTimeout(timeout);
if (immediate) {
var callNow = !timeout;
timeout = setTimeout(function(){
timeout = null;
}, wait)
if (callNow) func.apply(context, args)
}
else {
timeout = setTimeout(function(){
func.apply(context, args)
}, wait);
}
}
}
防抖动
debounce 策略的电梯。如果电梯里有人进来,等待50毫秒。如果又人进来,50毫秒等待重新计时,直到50毫秒超时,开始运送。
let debounce = (fn, time = 50) => { // 防抖动 控制空闲时间 用户输入频繁
let timer;
return function (...args) {
let that = this;
clearTimeout(timer);
timer = setTimeout(fn.bind(that, ...args), time);
}
}
深度拷贝兼容写法(不包括原型属性)
function deepCopy(obj) {
if (typeof obj !== 'object') return obj;
if (typeof window !== 'undefined' && window.JSON) { // 浏览器环境下 并支持window.JSON 则使用 JSON
return JSON.parse(JSON.stringify(obj));
} else {
let newObj = obj.constructor === Array ? [] : {};
for(let key in obj) {
newObj[key] = typeof obj[key] === 'object' ? deepCopy(obj[key]) : obj[key];
}
return newObj;
}
}
let obj = {a: 1, b: [12]};
let newObj = deepCopy(obj);
newObj.b[1] = 100;
console.log(obj);
console.log(newObj);
深度克隆加强版
function cloneDeep(obj) {
let type = isType(obj)
if (type === 'Array' || type === 'Object') {
return cloneObj(obj)
} else if (type === 'Date') {
return obj.constructor(obj)
} else {
return obj
}
}
function cloneObj(obj) {
let newObj = obj instanceof Array ? [] : {};
for (let key in obj) {
newObj[key] = typeof obj[key] === 'object' ? cloneObj(obj[key]) : obj[key]
}
return newObj;
}
function isType(o) {
return /\[object\s(.*?)\]/.exec(Object.prototype.toString.call(o))[1]
}
let fn = function () {
return 123
}
var a = [[1, 2, 3], [4, 5, 6, 7, fn]];
// let c = new Date();
// var b = cloneDeep(c);
var b = cloneDeep(a);
console.log(b[0], a[0]);
console.log(b[0] === a[0]);
原生数据类型检测简易封装
Object.prototype.isType = function (type) {
return function (params) {
return Object.prototype.toString.call(params) === `[object ${type}]`
}
}
let isString = Object.isType('String')
let isArray = Object.isType('Array')
console.log(isString(1)) // false
console.log(isString('hello')) // true
console.log(isArray(2)) // false
console.log(isArray(['hello'])) // true
Array的reduce实现
Array.prototype._reduce = function (callback, initVal) {
let i = 0
let result = initVal
if (typeof initVal === 'undefined') {
result = this[0]
i++
}
for (i; i < this.length; i++) {
result = callback(result, this[i])
}
return result
}
const arr = [1, 2, 3]
let result = arr._reduce((a, b) => {
return a + b
}, 0)
console.log(result) // 6
Function的bind实现
1.es5
Function.prototype._bind = function(context) {
let func = this;
let params = [].slice.call(arguments, 1);
let Fnop = function() {};
let fbound = function() {
params = params.concat([].slice.call(arguments, 0));
return func.apply(this instanceof Fnop ?
this : context, params);
}
Fnop.prototype = this.prototype;
fbound.prototype = new Fnop();
return fbound;
}
function foo() {
this.b = 100;
return this.a;
}
let fe = foo._bind({ a: 1 });
console.log(fe()); // 1
console.log(new fe()); // 实例 {b: 100}
2.es6
Function.prototype.mybind = function(context, ...rest) {
return (...params) => this.call(context, ...rest, ...params);
}
函数组合串联compose(reduce中间件)
// 组合串联
let fn1 = (a) => a + 1;
let fn2 = (b) => b + 2;
let fn3 = (c) => c + 3;
let funs = [fn1, fn2, fn3];
let compose = (func) => {
return arg => func.reduceRight((composed, fn) => fn(composed), arg);
}
console.log(compose(funs)(100)); // 相当于fn1(fn2(fn3(100)))
redux 源码中compose实现(github.com/reduxjs/red…)
export default function compose(...funcs) {
if (funcs.length === 0) {
return arg => arg
}
if (funcs.length === 1) {
return funcs[0]
}
return funcs.reduce((a, b) => (...args) => a(b(...args)))
}
koa-compose 实现
function compose(middleware) {
return function(ctx, next) {
let index = -1;
return dispatch(0)
function dispatch(i) {
if(i <= index) return Promise.reject(new Error('next() called multiple times'));
index = i;
let fn = middleware[i]
if (i === middleware.length) fn = next
if (!fn) return Promise.resolve()
try {
return Promise.resolve(fn(ctx, dispatch.bind(null, i + 1)))
} catch(e) {
return Promise.reject(e)
}
}
}
}
let mid1 = (ctx, next) => {
console.log('ctx1', ctx);
next()
}
let mid2 = (ctx, next) => {
console.log('ctx2', ctx);
next()
}
let mid3 = (ctx, next) => {
console.log('ctx3', ctx);
}
let co = compose([mid1, mid2, mid3])
co('ctx')
co函数
function *fn(a = 0) {
console.log('a', a)
const b = yield 2
console.log('b', b)
const c = yield Promise.resolve(3)
console.log('c', c)
return a + b + c
}
// const it = fn(1)
// it.next()
// it.next(2)
// it.next(3)
// co(fn, 1)
function fe() {
return 100
}
run(fn, 10).then(res => {
console.log(res)
})
function run(gen) {
const slice = [].slice
const args = slice.call(arguments, 1)
return new Promise((resolve, reject) => {
const ite = (typeof gen === 'function') && gen.apply(this, args)
if (!ite || typeof ite.next !== 'function') return resolve(ite)
function next(res) {
const { value, done } = ite.next(res)
if (done) {
resolve(value)
} else if (value instanceof Promise) {
value.then(next)
} else {
next(value)
}
}
next()
})
}
es6简版 promise
class Promise {
constructor(fn) {
this.status = 'Pending'
setTimeout(() => {
fn((data) => {
this.resolve(data)
}, (error) => {
this.reject(error)
})
})
}
resolve(data) {
if (this.status === 'Pending') {
this.success(data)
this.status = 'Fulfilled'
}
}
reject(error) {
if (this.status === 'Pending') {
this.error(error)
this.status = 'Rejected'
}
}
then(success, error) {
this.success = success
this.error = error
}
}
let p1 = new Promise((resolve, reject) => {
// reject('hello error');
setTimeout(() => {
resolve('hello promise')
}, 1000)
})
p1.then((data) => console.log(data), (err) => console.log(err))
如何主动中止Promise调用链
const p1 = new Promise((resolve, reject) => {
setTimeout(() => { // 异步操作
resolve('start')
}, 1000);
});
p1.then((result) => {
console.log('a', result);
return Promise.reject('中断后续调用'); // 此时rejected的状态将直接跳到catch里,剩下的调用不会再继续
}).then(result => {
console.log('b', result);
}).then(result => {
console.log('c', result);
}).catch(err => {
console.log(err);
});
// a start
// 中断后续调用
bluebird.promisify实现(将异步回调函数api 转换为promise形式)
// promisify.js
module.exports = {
promisify(fn){
return function () {
var args = Array.from(arguments);
return new Promise(function (resolve, reject) {
fn.apply(null, args.concat(function (err) {
if (err) {
reject(err);
} else {
resolve(arguments[1])
}
}));
})
}
}
}
// main.js
const fs = require('fs');
const {promisify} = require('./promisify.js');
const readFile = promisify('fs.readFile'); // 转换异步读取
// 异步文件 由回调函数形式变成promise形式
readFile('./1.txt', 'utf8').then(data => {
console.log(data);
}).catch(err => {
console.log(err);
});
window.requestAnimationFrame兼容性处理
window._requestAnimationFrame = (function(){
return window.requestAnimationFrame ||
window.webkitRequestAnimationFrame ||
window.mozRequestAnimationFrame ||
function(callback){
window.setTimeout(callback, 1000 / 60);
};
})();
字符串是否符合回文规则
let str = 'My age is 0, 0 si ega ym.';
方法一
function palindrome(params) {
params = params.replace(/[\W\s_]/ig, '');
return params.toLowerCase() === params.split('').reverse().join('').toLowerCase();
}
console.log(palindrome(str));
方法二
function palindrome(params) {
params = params.replace(/[\W\s_]/ig, '').toLowerCase();
for (var i = 0, j = params.length-1; i<j; i++, j--) {
if (params[i] !== params[j]) {
return false;
}
}
return true;
}
解构
// 将 destructuringArray([1, [2, 3], 4], "[a, [b], c]") => {a: 1, b: 2, c: 4}
const targetArray = [1, [2, 3], 4];
const formater = "[a, [b], c]";
const destructuringArray = (values, keys) => {
try {
const obj = {};
if (typeof keys === 'string') {
keys = JSON.parse(keys.replace(/\w+/g, '"$&"'));
}
const iterate = (values, keys) =>
keys.forEach((key, i) => {
if(Array.isArray(key)) iterate(values[i], key)
else obj[key] = values[i]
})
iterate(values, keys)
return obj;
} catch (e) {
console.error(e.message);
}
}
数组展平
将[[1, 2], 3, [[[4], 5]]] 展平为 [1, 2, 3, 4, 5]
let arr = [[1, 2], 3, [[[4], 5]]]; // 数组展平
function flatten(arr) {
return [].concat(
...arr.map(x => Array.isArray(x) ? flatten(x) : x)
)
}
二分查找
const arr = [1, 2, 3, 4, 5, 6, 7, 8];
// 二分查找 递归 由中间开始往两边查找 前提是有序的数组 返回对应的索引位置
function binarySearch1(arr, dest, start = 0, end = data.length) {
if (start > end) {
return -1
}
let midIndex = Math.floor((start + end) / 2); // 中间位置索引
let mid = arr[midIndex]; // 中间值
if (mid == dest) {
return midIndex;
}
if (dest < mid) { // 要找的比中间值小 就从中间往开头找 一直到0
return binarySearch1(arr, dest, 0, midIndex - 1);
}
if (dest > mid) { // 要找的比中间值大 就从中间往后找 一直到end结束
return binarySearch1(arr, dest, midIndex + 1, end);
}
return -1; // 找不到返回-1
}
console.log(binarySearch1(arr, 7, 3, 6)); // 6
// 非递归 arr前提有序数组 (从小到大)返回对应的索引位置
function binarySearch2(arr, dest) {
let max = arr.length - 1;
let min = 0;
while (min <= max) {
let mid = Math.floor((max + min) / 2); // mid中间位置索引
if (dest < arr[mid]) { // 如果要找的这项比中间项还要小 说明应该在mid中间位置前面 修改最大边界值max=mid-1
max = mid - 1;
} else if (dest > arr[mid]) { // 如果要找的这项比中间项还要大 说明应该在mid中间位置的后面 修改最小边界值min=mid+1
min = mid + 1;
} else {
return mid;
}
}
return -1; // 找不到返回-1
}
console.log(binarySearch2(arr, 3)); // 2
二分查找题
在一个二维数组中,每一行都按照从左到右递增,每一列都从上到下递增的顺序排序,完成一个函数,输入这个二维数组和一个整数,判断数组中是否含有该整数
思路是一样的,只不过从一维变成了二维,我们遍历思路可以这样子:
- 选取第一行的最后一个进行判断(这个是第一行中最大的)
- 如果目标大于该值,行数加1,遍历第二行(因为每列都是递增的)
- 如果目标小于该值,则在这一行中进行查找
循环以上步骤
function findTarget(arr,target) {
let i = 0; // i代表行
let j = arr[i].length -1; // j每行中每项索引位置 从最后项开始比较
while(i < arr.length && j>=0) {
if(target < arr[i][j]) {
j--;
} else if (target > arr[i][j]) {
i++;
} else {
return `找到了,位置在${i},${j}`
}
}
return `(${i},${j})`
}
let arr = [
[1,2,3,4],
[5,9,10,11],
[13,20,21,23]
] //测试
找出数组中重复出现过的元素
// 例如:[1,2,4,4,3,3,1,5,3]
// 输出:[1,3,4]
let arr = [1, 2, 4, 4, 3, 3, 1, 5, 3];
// 方法一
function repeat1(arr){
var result = [], map = {};
arr.map(function(num){
if(map[num] === 1) result.push(num); // 等于1说明之前出现过一次 这次重复出现了
map[num] = (map[num] || 0) + 1; // 微妙之处 开始第一次出现无值 记为 0 + 1 = 1 下一次从1开始累加
});
return result;
}
console.log(repeat1(arr));
// 方法二
function repeat(arr) {
let result = arr.filter((x, i, self) => {
return self.indexOf(x) === i && self.lastIndexOf(x) !== i
}); //
return result;
}
console.log(repeat(arr));
根据数组中数字重复出现的次数排序
// 如果次数相同 则按照值排序 比如 2, 2, 2和 1, 1, 1 应排序为 [1, 1, 1, 2, 2, 2]
// 比如 [1, 2, 1, 2, 1, 3, 4, 5, 4, 5, 5, 2, 2] => [3, 4, 4, 1, 1, 1, 5, 5, 5, 2, 2, 2, 2]
const repeatTimeSort = arr => {
arr.sort((a, b) => a - b)
let ary = []
while (arr.length > 0) {
let a = arr[0]
let start = arr.indexOf(a)
let end = arr.lastIndexOf(a) + 1
ary.push(arr.splice(start, end - start))
}
ary.sort((a, b) => a.length - b.length)
return ary.reduce((prev, cur) => prev.concat(cur), [])
}
// [ 12, 13, 13, 11, 11, 11 ]
console.log(repeatTimeSort([11, 12, 13, 11, 11, 13]))
// [ 3, 4, 4, 1, 1, 1, 5, 5, 5, 2, 2, 2, 2 ]
console.log(repeatTimeSort([1, 2, 1, 2, 1, 3, 4, 5, 4, 5, 5, 2, 2]))
不用循环,创建一个长度为 100 的数组,并且每个元素的值等于它的下标。
// 方法一 递归写法
function createArray(len, arr = []) {
if (len > 0) {
arr[--len] = len;
createArray(len, arr);
}
return arr;
}
console.log(createArray(100));
// 方法二
// 下面评论中@MaDivH 提供的实现方法 长度为 100 的数组
Array(100).fill().map((_,i)=>i+1);
// 方法三
[...Array(100).keys()]
将数组转换成关联结构树
const roles = [
{ id: 1, name: 'a', parentId: 0},
{ id: 2, name: 'b', parentId: 0},
{ id: 3, name: 'c', parentId: 1},
{ id: 4, name: 'd', parentId: 1},
{ id: 5, name: 'e', parentId: 2},
{ id: 6, name: 'f', parentId: 2}
]
// const output = [{
// id: 1,
// name: 'a',
// parentId: 0,
// children: [
// { id: 3, name: 'c', parentId: 1, children: [] },
// { id: 4, name: 'd', parentId: 1, children: [] }
// ]
// },
// {
// id: 2,
// name: 'b',
// parentId: 0,
// children: [
// { id: 5, name: 'e', parentId: 2 },
// { id: 6, name: 'f', parentId: 2 }
// ]
// }
// ]
function convert(roles) {
const root = []
const dict = {}
roles.forEach(item => {
if (item.parentId === 0) {
root.push(item)
}
item.children = []
dict[item.id] = item
})
roles.forEach(item => {
if (item.parentId !== 0) {
dict[item.parentId].children.push(item)
}
})
return root
}
console.log(convert(roles))
根据关键词找出 所在对象id
var docs = [
{
id: 1,
words: ['hello', "world"]
}, {
id: 2,
words: ['hello', "hihi"]
}, {
id: 3,
words: ['haha', "hello"]
}, {
id: 4,
words: ['world', "nihao"]
}
];
findDocList(docs, ['hello']) // 文档id1,文档id2,文档id3
findDocList(docs, ['hello', 'world']) // 文档id1
function findDocList(docs, word = []) {
if (word.constructor !== Array) return;
let ids = [];
for (let i = 0; i < docs.length; i++) {
let {id, words} = docs[i];
let flag = word.every((item) => {
return words.indexOf(item) > -1;
});
flag && ids.push(id);
}
return ids;
}
findDocList(docs, ['hello', 'world']);
全排列
const permute = function(nums) {
if (nums.length <= 1) return [nums]
const permutes = []
for (let i = 0; i < nums.length; i++) {
const num = nums[i]
const others = nums.slice(0, i).concat(nums.slice(i + 1))
const list = permute(others)
list.forEach(item => {
permutes.push([num].concat(item))
})
}
return permutes
};
const arr = [1, 2, 3]
console.log(permute(arr))
getElementsByClassName 兼容写法
function getByClass(cName) {
if ('getElementsByClassName' in this) {
return this.getElementsByClassName(cName);
}
cName = cName.replace(/(^\s+|\s+$)/g, '').split(/\s+/g);
let eles = this.getElementsByTagName('*');
for (let i = 0; i < cName.length; i++) {
let reg = new RegExp(`(^| )${cName[i]}( |$)`);
let temp = [];
for (let j = 0; j < eles.length; j++) {
let cur = eles[j];
let {className} = cur;
if (reg.test(className)) {
temp.push(cur);
}
}
eles = temp;
}
return eles;
}
console.log(content.getByClass('c1 c2 '));
插入排序
插入排序 从后往前比较 直到碰到比当前项 还要小的前一项时 将这一项插入到前一项的后面
function insertSort(arr) {
let len = arr.length;
let preIndex, current;
for (let i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i]; // 当前项
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex]; // 如果前一项大于当前项 则把前一项往后挪一位
preIndex-- // 用当前项继续和前面值进行比较
}
arr[preIndex + 1] = current; // 如果前一项小于当前项则 循环结束 则将当前项放到 前一项的后面
}
return arr;
}
function insert(arr, i, x) {
let prev = i - 1;
while(prev >= 0 && arr[prev] > x) {
arr[prev + 1] = arr[prev];
prev--;
}
arr[prev + 1] = x;
}
function insert_sort(arr) {
for (let i = 1; i < arr.length; i++) {
insert(arr, i, arr[i]);
}
return arr;
}
console.log(insert_sort([1, 10, 3, 0]));
选择排序
选择排序 每次拿当前项与后面其他项进行比较 得到最小值的索引位置 然后把最小值和当前项交换位置
function selectSort(arr) {
let len = arr.length;
let temp = null;
let minIndex = null;
for (let i = 0; i < len - 1; i++) { // 把当前值的索引作为最小值的索引一次去比较
minIndex = i; // 假设当前项索引 为最小值索引
for (let j = i + 1; j < len; j++) { // 当前项后面向一次比小
if (arr[j] < arr[minIndex]) { // 比假设的值还要小 则保留最小值索引
minIndex = j; // 找到最小值的索引位置
}
}
// 将当前值和比较出的最小值交换位置
if (i !== minIndex) {
temp = arr[i]
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
return arr;
}
冒泡排序
冒泡排序 相邻两项进行比较 如果当前值大于后一项 则交换位置
冒泡1
function swap(arr, i, j) {
[arr[i], arr[j]] = [arr[j], arr[i]]
}
function bubleSort(arr) {
let length = arr.length;
let temp = null;
for (let i = 0; i < length - 1; i++) { // 控制轮数
let flag = false; // 当前这轮是否交换过标识
for (let l = 0; l < length - i - 1; l++) { // 控制每轮比较次数
if (arr[l] > arr[l + 1]) {
// temp = arr[l];
// arr[l] = arr[l + 1];
// arr[l + 1] = temp;
swap(arr, l, l + 1);
flag = true; // 如果发生过交换flag则为true
}
}
if (!flag) { // 优化 如果从头到尾比较一轮后 flag依然为false说明 已经排好序了 没必要在继续下去
temp = null;
return arr;
}
}
return arr;
}
冒泡2
function swap(arr, i, j) {
[arr[i], arr[j]] = [arr[j], arr[i]]
}
function bubble_sort(arr) {
for (let i = arr.length - 1; i >= 1; i--) {
for (let j = 1; j <= i; j++) {
arr[j - 1] > arr[j] && swap(arr, j - 1, j)
}
}
return arr;
}
console.log(bubble_sort([1, 10, 3, 0]));
快速排序(阮一峰版)
function quickSort(arr) {
if (arr.length <= 1) return arr;
let midIndex = Math.floor(arr.length / 2);
let midNum = arr.splice(midIndex, 1)[0];
let left = [];
let right = [];
for(let i = 0; i < arr.length; i++) {
let cur = arr[i];
if (cur <= midNum) {
left.push(cur);
} else {
right.push(cur);
}
}
return quickSort(left).concat(midNum, quickSort(right));
}
let arr = [2, 4, 12, 9, 22, 10, 18, 6];
quickSort(arr);
快速排序 第二版
let array = [9, 6, 20, 3, 2];
// let array = [15, 13, 20, 21, 29];
function quickSort(arr, left = 0, right = arr.length - 1) {
let len = arr.length;
let partitionIndex;
// left = typeof left != 'number' ? 0 : left;
// right = typeof right != 'number' ? len - 1 : right;
if (left < right) {
partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
return arr;
}
function partition(arr, left, right) {
let pivot = left;
let index = pivot + 1;
for (let i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index - 1;
}
function swap(arr, i, index) {
[arr[i], arr[index]] = [arr[index], arr[i]];
}
console.log(quickSort(array));
归并排序
let array = [5, 13, 20, 3, 2];
// let array = [15, 13, 20, 21, 29];
function mergeSort(array) {
let arr = array.slice(0);
let len = arr.length;
if (len < 2) {
return arr;
}
let midIndex = Math.floor(len / 2);
let left = arr.slice(0, midIndex);
let right = arr.slice(midIndex);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let result = [];
while(left.length && right.length) {
result.push(left[0] < right[0] ? left.shift() : right.shift());
}
if (left.length && !right.length) {
result = result.concat(left);
}
if (right.length && !left.length) {
result = result.concat(right);
}
return result;
}
console.log(mergeSort(array));
数组去重几种方法
const arr = [1, 2, 1, 2, 3, 4, 2, 1, 3];
// 1 ES6
let newArr = [...new Set(arr)];
// 2
const arr = [1, 2, 1, 2, 3, 4, 'l', 2, 1, 3, 'l'];
const newArr = arr.filter(function(ele, index, array) {
return index === array.indexOf(ele)
});
console.log(newArr); // [ 1, 2, 3, 4, 'l' ]
// 3
Array.prototype.unique2 = function() {
let newArr = [];
let len = this.length;
for(let i = 0; i < len; i++) {
let cur = this[i];
if(newArr.indexOf(cur) === -1) {
newArr[newArr.length] = cur;
}
}
return newArr;
}
console.log(arr.unique1());
// 4
Array.prototype.unique3 = function() {
let newArr = this.slice(0);
let len = this.length;
let obj = {};
for(let i = 0; i < len; i++) {
let cur = newArr[i];
if(obj[cur]) {
newArr[i] = newArr[newArr.length - 1];
newArr.length--;
i--;
continue;
}
obj[cur] = cur;
}
return newArr;
}
console.log(arr.unique3());
// 5
Array.prototype.unique4 = function() {
let json = {}, newArr = [], len = this.length;
for(var i = 0; i < len; i++) {
let cur = this[i];
if (typeof json[cur] == "undefined") {
json[cur] = true;
newArr.push(cur)
}
}
return newArr;
}
console.log(arr.unique4());
千分符
方法一
// 处理数字
let str1 = 2123456789;
let str2 = 2123456789.12;
console.log(str1.toLocaleString()); // 2,123,456,789
console.log(str2.toLocaleString()); // 2,123,456,789.12
方法二
// 处理字符串
let str1 = '2123456789';
let str2 = '2123456789.12';
// 利用正向预查 匹配 开头一个数字\d 后面匹配这个数字后面必须是三个数字为一组为结尾或小数为结尾
function thousandth(str) {
let reg = /\d(?=(?:\d{3})+(?:\.\d+|$))/g;
return str.replace(reg, '$&,');
}
console.log(thousandth(str1)); // 2,123,456,789
console.log(thousandth(str2)); // 2,123,456,789.12
求a的值 什么情况下 满足if (a == 1 & a == 2 & a == 3)这个条件
var a = {
a: 1,
valueOf() {
return this.a++
}
}
if (a == 1 & a == 2 & a == 3) {
console.log(1)
}
在一个数组中 如a、b两项, 要保证a和b两项的差 与 a和b两项索引的差 的相加后的结果max 是数组中其他两项max 中的最大值 找出符合条件两项a, b的值 (不可以排序 或改变数组位置) 如:
let max = (a – b) + (a的索引- b的索引); 求a b
答案:
// 思路:其实也就是找出数组中当前的每一项与自身索引相加后的和的最大值以及与索引相加后的最小值的和 找出符合条件的两项即可 如 let result = (maxItem-minItem) + (maxIndex-minIndex) 等价于 (maxItem+maxIndex) - (minItem+minIndex)
// let arr = [1, 2, 3, 4, 5, 6]; // 最简单的测试数组 最小项1 最大项6
// 很显然这个数组中最大值6与索引相加(6+5)是当中最大值11 1与索引相加(1+0)为当中的最小值1(6 + 5)-(1+0)= 10
// 假设法
let arr = [2, 10, 9, 1, 8, 3, 4];
let minItem = arr[0]; // 假设第一项与自身索引的和是最小值 索引为0因此省略
let maxItem = arr[0]; // 假设第一项与自身索引的和是最大值 索引为0因此省略
let min = minItem; // 最小项
let max = maxItem; // 最大项
let minIndex = 0; // 最小项索引
let maxIndex = 0; // 最大项索引
for(let i = 1; i < arr.length; i++) {
let cur = arr[i] + i; // 当前项和自身索引的和
cur < minItem ? (minItem = cur, min = arr[i], minIndex = i) : null;
cur > maxItem ? (maxItem = cur, max = arr[i], maxIndex = i) : null;
}
console.log(maxItem, minItem); // 最大项与索引的和 最小项与索引的和
console.log(max, min); // 最大项 最小项
console.log(maxIndex, minIndex); // 最大项的索引 最小项的索引
检测 字符串中括号表达式是否平衡
// 如 balance('[()') = false; balance('[()()()]') = true
// 一
function match(a, b) {
return (a === '(' && b === ')') || (a === ')' && b === '(') || (a === '[' && b === ']') || (a === ']' && b === '[');
}
function balance(str) {
if (str.length % 2 === 0) {
let len = str.length;
for (let i = 0, j = len - 1; i < len / 2; i++, j--) {
if (!match(str[i], str[j])) {
return false;
}
}
return true;
}
return false;
}
console.log(balance('[()()()]')); // true
console.log(balance('[()')); // false
console.log(balance('[]()')); // false
// 二
function is_balance(str) {
return [...str].reduce((stack, c) => {
match(stack[stack.length - 1], c) ?
stack.pop() : stack.push(c);
return stack;
}, []).length === 0;
}
console.log(is_balance('[()()()]')); // true
console.log(is_balance('[()')); // false
console.log(is_balance('[]()')); // false
求相邻两项最大和
// 一
let arr1 = [-1, 3, 1, -5, 2]; // 如 [2, 4, -4, -3] => 4
function sum(arr) {
let prev = arr[0];
let sumArr = [];
let len = arr.length;
for(let i = 1; i < len; i++) {
let cur = arr[i];
sumArr.push(cur + prev);
prev = cur;
}
return Math.max(...sumArr);
}
console.log(sum(arr1));
// 二
function maxsum(arr) {
const M = [arr[0]];
let max = M[0];
for(let i = 1; i < arr.length; i++) {
M[i] = Math.max(arr[i], M[i - 1] + arr[i]);
max = Math.max(M[i], max);
}
return max;
}
字符串去除相邻的重复项 如:’aabbccddeexxxxaa’ => ‘abcdexa’
// 正则表达式
let str = 'aabbccddeexxxxaa';
function uniq1(str) {
// return str.replace(/([a-z])(\1){1,}/g, '$1');
return str.replace(/(.)(?=\1)/g, '');
}
console.log(uniq1(str));
// 数组方式
function uniq2(str) {
let arr = str.split('');
let newArr = [arr[0]];
for(let i = 1; i < arr.length; i++) {
let cur = arr[i];
if (cur !== newArr[newArr.length - 1]) {
newArr.push(cur);
}
}
return newArr.join('');
}
console.log(uniq2(str));
资源分享
JavaScript基础在线教程文档
Github一些原理实现
- 二叉搜索树 中序、先序、后序遍历 搜索树中的值
- vue设计原理简单实现:数据劫持、依赖收集、模板编译、双向绑定、计算属性
- spa单页路由设计简单实现
- 浏览器缓存交互实现
- npm发布li-server静态服务器编写
- node events模块实现 发布订阅
JavaScript数据结构与算法pdf资源
百度网盘 密码:ll8d
害怕手写代码 😨 只能硬着头皮
欢迎大家和我一起来补充 上面很多也都是可以优化的 我还是一个成长中的小白,只是分享和记录下自己碰到的问题 后续会持续更新…
链接:https://juejin.im/post/5aa7d82c6fb9a028c522de43
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程
本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com