前端手撕、底层源码
排序升序
// js底层sort是插入和快排结合，arr.length<10插入，否则快排
// 冒泡排序 稳定
function maopao(arr){
let n=arr.length
//外层循环趟数
for (let i = 0; i < n - 1; i++){
// 内层循环每个元素需要的次数
for (let j = 0; j < n - 1 - i; j++){
//相邻数字比较
if (arr[j] > arr[j + 1])[arr[j],arr[j+1]]=[arr[j+1],arr[j]]
}
}
return arr
}
// 插入排序 稳定
function cha(arr){
let n=arr.length
for (let i = 1; i < n; i++){
let temp=arr[i]
for(var j=i;j>0&&temp<arr[j-1];j--){
arr[j]=arr[j-1]
}
arr[j]=temp
}
return arr
}
// 快排 不稳定 O(nlogn)
function quick(arr){
let n=arr.length
if(n<2)return arr
let a1=[]
let a2=[]
for (let i = 1; i < n; i++){
if(arr[i]<arr[0]){
a1.push(arr[i])
}else{
a2.push(arr[i])
}
}
a1=quick(a1)
a2=quick(a2)
return [...a1,arr[0],...a2]
}
// 选择排序 不稳定
查找
// 数组查找 O(1)
// 顺序查找 O(n)
// 二分 O(log2n)
function find(arr,target){
let left=0
let right=arr.length-1
while(left<=right){
let mid=Math.floor((left+right)/2)
if(target===arr[mid])return mid
if(target<arr[mid])right=mid-1
if(target>arr[mid])left=mid+1
}
return -1
}URL参数解析
String.prototype.myQueryUrlParameter=function(){
let obj={}
let arr=this.split('?')[1].split('#')[0].split('&')
arr.map(item=>{
if(item.includes('=')){
let [key,val]=item.split('=');
//判断是否数字
val = /^[0-9]+$/.test(val)? parseInt(val) : val;
obj[key]=obj.hasOwnProperty(key)?obj[key]=[].concat(obj[key],val):val;
}else{
obj[item]=true;
}
})
obj['HASH']=this.split('#')[1]
return obj
}
let url=`http://www.baidu.com?ie=utf-8&lang=en&lang=cn&name=tom&id=123&id=456&enabled#teacher`;
let result=url.myQueryUrlParameter();
console.log(result)
括号匹配
function kuohao(str){
let left=['(','[','{'];
let right=[')',']','}'];
let sc=[];//定义一个栈
for(c of str){
if(left.includes(c))sc.push(c);
if(right.includes(c)){
if(sc.length==0)return false;
let index=right.indexOf(c);
if(sc.pop()!=left[index])return false;
}
}
if(sc.length!=0)return false;
else return true;
}合并有序数组
let a=[2,3,4,5]
let b=[1,2,6,6]
let i=0
let j=0
let res=[]
while(i<a.length&&j<b.length){
if(a[i]<=b[j]){
res.push(a[i++])
}else res.push(b[j++])
}
while(i<a.length)res.push(a[i++])
while(j<b.length)res.push(b[j++])
console.log(res)//1,2,2,3,4,5,6,6数组转树树转数组
const arr = [
{ id: '00', name: '测试', pid: ''},
{ id: '01', name: '张大', pid: ''},
{ id: '02', name: '小亮', pid: '01'},
{ id: '03', name: '小美', pid: '01'},
{ id: '04', name: '小丽', pid: '02'},
{ id: '05', name: '小高', pid: '03'},
]
function transList2TreeData(list, rootValue) {//转树
const deepList = JSON.parse(JSON.stringify(list)) // 深拷贝
const arr = []
deepList.forEach(item => {
if (item.pid === rootValue) {
const children = transList2TreeData(deepList, item.id)
children.length ? (item.children = children) : false
arr.push(item)
}
})
return arr
}
const result = transList2TreeData(arr, '')
console.log(result)
let treeRes = [];
function tree2arr(res) { // 转数组
res.forEach(item => {
if (item.children) {
let tem=JSON.parse(JSON.stringify(item.children))
delete item.children
treeRes.push(item)
tree2arr(tem)
} else {
treeRes.push(item)
}
})
}
tree2arr(result)
console.log(treeRes);随即洗牌
function shuffle(array){
let res = [], random;
while(array.length>0){
random = Math.floor(Math.random()*array.length);
res.push(array[random]);
array.splice(random, 1);
}
return res;
}
console.log(shuffle([1,2,3,4,5]));数组L输出
var arr = [
[1,2,3],
[4,5,6],
[7,8,9]
];
var newArr = []; // L型数组
var length = arr.length; // 后面将替换成 arr.length
var number = 1; // 少掉的下标数
for(var i= length; i > 0; i--){
for(var j = 0; j < i; j++){
var len = length - i;
var value = arr[j][len];
newArr.push(value);
}
var arrSlice = arr[length - number].slice(number);
newArr.push(...arrSlice) // 用展开符把横数组添加到L型数组里
++number;
}
console.log(newArr)//1,4,7,8,9,2,5,6,3统计字符串字符个数
function numstr(str){
let map=new Map()
for(c of str){
map.set(c,map.has(c)?map.get(c)+1:1)
}
map.forEach((val,key)=>console.log(key,val))// 遍历输出key val
}后续可以判断字符个数相等与否，出现最多的字符
大数加法
function solve( s , t ) {
let maxLength = Math.max(s.length,t.length)
s = s.padStart(maxLength , 0);
t = t.padStart(maxLength , 0);
let sum = ""
let f = 0
for(let i = maxLength-1;i>=0;i--){
let a = parseInt(s[i])+parseInt(t[i]) + f
f = Math.floor(a/10)
sum =a%10 + sum
}
if(f==1){
sum = "1"+sum
}
return sum
}dom操作
// 获取元素
var x = document.getElementById("intro");// 获取id名为intro的元素
var x = document.getElementsByTagName("p");// 获取p标签元素，list
var x = document.getElementsByClassName("intro");// 获取class名为intro的元素，list
var x = document.querySelectorAll("p.intro");// 获取p元素下的所有intro，list
var x = document.querySelector("p");// 获取第一个p元素
// 增加元素
var son = document.createElement("p");
var node = document.createTextNode("这是新文本。");
son.appendChild(node);
var parent = document.getElementById("div1");
parent.appendChild(son);
// 删除元素
const elmnt = document.getElementById("p1");
elmnt.remove();
// 修改元素
var para = document.createElement("p");
var node = document.createTextNode("这是新文本。");
para.appendChild(node);
var parent = document.getElementById("div1");
var child = document.getElementById("p1");
parent.replaceChild(para, child);发布订阅
class PublishSubscribe{
subscribes={
a:[],//a事件和回调函数数组
b:[]
}
// 订阅
on(subscribe,callback){
//判断subscribe事件有没有数组[],没创建过就创建[]，创建过了就添加
const subscribeCallbacks=this.subscribes[subscribe]||[];
this.subscribes[subscribe]=[...subscribeCallbacks,callback];//相当于把回调函数放在了订阅事件的数组里面
}
//发布
emit(subscribe,...args){
//拿到该事件所有回调函数
const subscribeCallbacks=this.subscribes[subscribe]||[];
//依次执行
subscribeCallbacks.forEach(callback=>callback(...args))
}
}观察者模式
区别： 观察者模式和发布订阅模式都是为了解耦，减少代码的冗余，不同的是，观察者模式中观察者必须知道被观察者，而发布订阅模式解耦更彻底，订阅者与发布者不需要相互知道，只需要向事件大厅订阅和发布即可。
class Observerd {
constructor(name) {
this.name = name;
this.state = '走路';
this.observers = [];
}
setObserver(observer) {
this.observers.push(observer);
}
setState(state) {
this.state = state;
this.observers.forEach(observer => observer.update(this));
}
}
class Observer {
update(observerd) {
console.log(observerd.name + '正在' + observerd.state);
}
}响应式原理
可以在控制台在修改任意person的属性，都会调用render渲染函数重新渲染页面
for (let key in person) {
let value = person[key]
Object.defineProperty(person, key, {
get() { //必须要有否则值全部变成undefined
return value
},
set(newVal) {
value = newVal
render(ul)
}
})
}reduce
Array.prototype._reduce=function(fu){
if(typeof fu!="function")return;
let prev;
for(let i=0;i<this.length;i++){
if(prev===undefined){
prev=fu(this[i],this[i+1],i+1,this);
++i;
}else{
prev=fu(prev,this[i],i,this);
}
}
return prev;
}深拷贝
const _completeDeepClone = (target) => {
// 1. 基本数据类型直接返回
if (typeof target !== 'object' || target === null) return target
// 2. 函数，正则，日期，ES6新对象，执行构造器，返回新的对象
const constructor = target.constructor
if (/^(Function|RegExp|Date|Map|Set)$/i.test(constructor.name))
return new constructor(target)
// 3.针对数组和对象区分
const cloneTarget = Array.isArray(target) ? [] : {}
Object.keys(target).forEach(key => {
cloneTarget[key] = _completeDeepClone(target[key])
})
return cloneTarget
}
防抖
只执行最后一次
function debounce(f) {
let timeout;
return function () {
if (timeout) clearTimeout(timeout);
timeout = setTimeout(function() {f()}, 1000);
}
}节流
单位时间内触发一次
function throttle(f) {
let timeout;
return function () {
if (!timeout) {
timeout = setTimeout(function () {
timeout = null;
f();
}, 1000)
}
}
}扁平
let res=[]//数组
const flatten = (arr) => {
for(n of arr){
if(typeof n !='object')res.push(n)
else flatten(n)
}
}
flatten([1,2,3,[4,5,6,[7,8,9]]])
console.log(res)
let res={}//对象
const flatten = (obj) => {
for(key in obj){
if(typeof obj[key] !='object' ||obj[key] instanceof Array)res[key]=obj[key]
else flatten(obj[key])
}
}
flatten({'a':1,'b':{'c':3,'d':{'d1':55,'d2':{'d22':[1,2,3]},'d3':99},'f':8},e:5})
console.log(res)setTimeout实现setInterval
setTimeout(function f() {
setTimeout(f, interval);
}, interval)手写ajax（使用promise封装）
function getJSON(url) {
let promise = new Promise((resolve, reject) => {
let xhr = new XMLHttpRequest()
xhr.open("GET", url, true)
xhr.onreadystatechange = function () {
if (this.readyState !== 4) return
if (this.status === 200) {
resolve(this.response)
} else {
reject(new Error(this.statusText))
}
}
xhr.onerror = function () {
reject(new Error(this.statusText))
}
xhr.responseType = "json"
xhr.setRequestHeader("Accept", "application/json")
xhr.send(null)
})
return promise
}
for of
// 创建一个函数，该函数会返回一个迭代器，用于遍历对象的所有属性
function* objectIterator(obj) {
for (let key in obj) {
if (obj.hasOwnProperty(key)) { // 只遍历对象自身的属性，不遍历原型链上的属性
yield [key, obj[key]];
}
}
}
// 将这个函数添加到所有对象的原型上
Object.prototype[Symbol.iterator] = function() {
return objectIterator(this);
};
// 创建一个测试对象
let testObj = {
a: 1,
b: 2,
c: 3
};
// 使用for...of遍历测试对象
for (let [key, value] of testObj) {
console.log(`Key: ${key}, Value: ${value}`);
}promise.all
function promiseAll(promises) {
return new Promise((resolve, reject) => {
if (!Array.isArray(promises)) {
return reject("参数必须为数组");// promises必须是数组
}
let successNum = 0; // 数组中promise对象调用成功的个数
let totalNum = promises.length; // 数组长度
let resultArray = []; // 保存每一个promise对象调用成功后的信息
for (let i = 0; i < totalNum; i++) {
promises[i].then(value => {
successNum++;
resultArray[i] = value;
if (successNum === totalNum) {
return resolve(resultArray); // 都成功，返回信息
}
}, err => {
return reject('数组内文件没有全部读取成功'); // 一旦失败返回失败的回调信息
})
}
})
}全排列（递归）
function permute( num ) {
let data = []
if(num.length == 1) return [num]
for(let i = 0; i < num.length;i++) {
let arr = [...num]
arr.splice(i,1) //const temp = str.slice(0, i) + str.slice(i + 1)
let info = this.permute(arr)
info.forEach(item => {
data.push([num[i],...item])
})
}
return data
}二叉树遍历
// 中序 obj={val:2,left:{val:5},right:{val:3}}
let arr=[]
function inorderTraversal( root ) {
// write code here
if(root==null) return [];
if(root){
inorderTraversal(root.left);
arr.push(root.val);
inorderTraversal(root.right);
}
return arr;
}
// 层序
function levelOrder(root) {
// write code here
let res = [];
let arr = [];
if (root) arr.push(root);
while (arr.length > 0) {
let newArr = [];
let row = [];
arr.forEach((v) => {
row.push(v.val);
v.left && newArr.push(v.left);
v.right && newArr.push(v.right);
});
arr = newArr;
res.push(row);
}
return res;
}链式调用、休眠、类
human.say('hello').sleep(2).say('world').done();
class Human {
constructor() {
this.queue = Promise.resolve();
}
say(word) {
this.queue = this.queue.then(() => {
console.log(word);
return Promise.resolve();
});
console.log(this)
return this;
}
sleep(time) {
this.queue = this.queue.then(() => {
return new Promise(resolve => setTimeout(resolve, time * 1000));
});
return this;
}
done() {
return this.queue;
}
}链表
反转链表
function ReverseList(pHead)
{
let p1 = null
let p2 = pHead
while(p2){
let tmp = p2.next
p2.next = p1
p1 = p2
p2 = tmp
}
return p1
}链表是否有环
function hasCycle( head ) {
while(head!=null){
if(head.flag)return true;
head.flag=true;
head=head.next;
}
return false;
}删除链表重复项
// 1,1,2,3,3,4=>1,2,3,4
function deleteDuplicates(head) {
let cur = head;
while (cur) {
if (!cur.next) break;
cur.val == cur.next.val ? cur.next = cur.next.next : cur = cur.next;
}
return head;
}
// 1,1,2,3,3,4=>2,4
function deleteDuplicates2(head) {
let cur = head;
let map = new Map();
while (cur) {
map.set(cur.val, map.has(cur.val) ? map.get(cur.val) + 1 : 1);
cur = cur.next;
}
let p = head;
while (p && p.next) {
if (map.get(p.next.val) > 1) {
p.next = p.next.next;
} else {
p = p.next;
}
}
// 处理头节点
if (head && map.get(head.val) > 1) {
head = head.next;
}
return head;
}链表排序
function sortInList( head ) {
let arr=[]
let p=head
while(p){
arr.push(p.val)
p=p.next
}
arr.sort((a,b)=>a-b)
let t=new ListNode(arr[0])
let res=t
for(let i=1;i<arr.length;i++){
t.next=new ListNode(arr[i])
t=t.next
}
return res
}无重复字符的最长子串（双指针）
function maxLength(arr) {
const map = new Map();
let left = 0;
let right = 0;
let res = 0;
while (right < arr.length) {
if (map.has(arr[right])) {
map.set(arr[right], map.get(arr[right]) + 1);
} else {
map.set(arr[right], 1);
}
while (map.get(arr[right]) > 1) {
map.set(arr[left], map.get(arr[left]) - 1);
left++;
}
right++;
res = Math.max(res, right - left);
}
return res;
}