????傳送門????
寒冬期前端準(zhǔn)備總結(jié)---JS篇
寒冬期前端準(zhǔn)備總結(jié)---瀏覽器篇
寒冬期前端準(zhǔn)備總結(jié)---服務(wù)器和網(wǎng)絡(luò)篇
寒冬期前端準(zhǔn)備總結(jié)---CSS篇
寒冬期前端準(zhǔn)備總結(jié)---框架篇
[寒冬期前端準(zhǔn)備總結(jié)---算法篇]
- 排序算法
冒泡排序：O2（第一位和第二位比較详羡，第二位和第三位比較）
選擇排序：O2（每次遍歷數(shù)組找到最小值先煎，放在數(shù)組前面）
插入排序：O2（每次遍歷比較在前面數(shù)組的位置幕庐，并插入到新的位置）
快速排序：復(fù)雜度nlogn（找到中間值屁柏，左右放置吓妆，遞歸，每次比較結(jié)束數(shù)組長(zhǎng)度-1）
- 二叉樹
深度遍歷（前序抒线、中序垢乙、后序）：遞歸和非遞歸實(shí)現(xiàn)
廣度遍歷：遞歸和非遞歸實(shí)現(xiàn)
深度遍歷
// 遞歸
var result = [];
var dfs1 = function(nodes) {
if(nodes.node) {
result.push(nodes.node);
nodes.left && dfs1(nodes.left);
nodes.right && dfs1(nodes.right);
}
}
dfs(nodes);
// 非遞歸
var dfs2 = function(nodes) {
var result = [];
var stack = [];
stack.push(nodes);
while (stack.length) {
var item = stack.pop();
result.push(item.node);
item.right && stack.push(item.right);
item.left && stack.push(item.left);
}
return result;
}
廣度遍歷
var bfs = function(nodes) {
var result = []
var queue = []
var pointer = 0
queue.push(nodes)
while(pointer < queue.length) {
var item = queue[pointer++] // 這里不使用 shift 方法（復(fù)雜度高）查近，用一個(gè)指針代替
result.push(item.node);
item.left && queue.push(item.left);
item.right && queue.push(item.right);
}
return result;
}
- 冒泡排序
function Bubble(arr) {
for (let i = 0; i < arr.length - 1; i++) {
for (let j = i + 1; j < arr.length - 1; j++) {
if (arr[i] > arr[j]) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
- 快速排序
function quickSort(arr) {
if (arr.length <= 1) return arr;
let arrLeft = [], arrRight = [];
let mid = arr[0];
for (let i = 1; i < arr.length - 1; i++) {
if (arr[i] <= mid) { arrLeft.push(arr[i]); }
if (arr[i] > mid) { arrRight.push(arr[i]); }
}
return [].concat(quickSort(arrLeft), [mid], quickSort(arrRight));
}
- promise、async實(shí)現(xiàn)循環(huán)打印1-10
function count(num) {
return new Promise((resolve) => {
setTimeout(() => {
console.log('a', num);
resolve(num);
}, 1000);
})
}
async function printNum() {
for (let i = 1; i <= 10; i++) {
await count(i);
console.log('b', i);
}
}
- 手寫Promise
function Promise(executor) {
let self = this;
self.status = 'pending';
self.value = undefined;// 成功值
self.errValue = undefined;// 失敗值
self.onResolved = [];// 用來保存then 方法中挤忙，第一個(gè)參數(shù)
self.onRejected = [];// 用來保存then 方法中嗦嗡，第二個(gè)參數(shù)
function resolve(value) {
if (self.status === 'pending') {
self.status = 'fulfilled';
self.value = value;
self.onResolved.forEach(fn => fn());
}
}
function reject(value) {
if (self.status === 'pending') {
self.status = 'rejected';
self.errValue = value;
self.onRejected.forEach(fn => fn());
}
}
try {
executor(resolve, reject);
} catch (e) {
reject(e);
}
}
Promise.prototype.then = function (onfulfilled, onrejected) {
let self = this;
return new Promise((resolve, reject) => {
if (self.status === 'fulfilled') {
resolve(onfulfilled(self.value));
}
if (self.status === 'rejected') {
reject(onrejected(self.errValue));
}
if (self.status === 'pending') {
self.onResolved.push(function () {
try {
let x = onfulfilled(self.value);
resolve(x)
} catch (e) {
reject(e)
}
})
self.onRejected.push(function () {
try {
let x = onrejected(self.errValue);
resolve(x)
} catch (e) {
reject(e)
}
})
}
});
}
Promise.prototype.catch = function (onfulfilled, onrejected) {
let self = this;
return new Promise((resolve, reject) => reject(onrejected(self.errValue)));
}
let p = new Promise((resolve, reject) => {
// resolve('111');
setTimeout(function () {
resolve('222');
}, 500)
})
p.then((value) => {
return value;
}, (reason) => {
console.log('err1', reason);
}).then((data) => {
console.log(data);
}, (reason) => {
console.log('err2', reason);
})
