前端经典算法题
javascript
算法
实现一个bind方法
Function.prototype._bind = function(ctx){
let self = this;
return function(){
self.call(ctx, ...arguments)
}
}
function a(m,n,o){
console.log(this.name + ' ' + m + ' ' + n + ' ' + o);
}
var b = {
name: 'kong'
};
a._bind(b)(7,8,9)
实现一个clone函数
Object.prototype.clone = function(){
// 此处用构造函数是为了兼容对象和数组
let o = new this.constructor();
for(let i in this){
if(this.hasOwnProperty(i)){
if (typeof this[i] == 'object') {
o[i] = this[i].clone()
} else {
o[i] = this[i]
}
}
}
return o;
}
let obj = {
a: 1,
b: 2,
c: {
m: 3,
n: 4
},
d: [1,3,5]
};
let t = obj.clone();
t.c.m = 'ss';
console.log(obj);
console.log(t)
二叉树相关
//
class Node {
constructor(value = null, left = null, right = null){
this.value = value;
this.left = left;
this.right = right
}
}
const N = function(value, left = null, right = null) {
return new Node(value, left, right)
}
var tree = N(
'a',
N('b', N('c')),
N('d', N('e'), N('f', N('g'), N('h',N('i'),N('j'))))
)
// 前序
function preOrder(tree){
if(tree != null) {
console.log(tree.value)
preOrder(tree.left)
preOrder(tree.right)
}
}
// preOrder(tree)
// 中序 cbaedgfh
function inOrder(tree) {
if(tree != null) {
inOrder(tree.left)
console.log(tree.value)
inOrder(tree.right)
}
}
// inOrder(tree)
// 后序 cbeghfda
function postOrder(tree){
if(tree != null) {
postOrder(tree.left)
postOrder(tree.right)
console.log(tree.value)
}
}
// postOrder(tree)
// 求最大深度
function depth(tree) {
if(tree == null) return 0;
let maxDepth = Math.max(depth(tree.left),depth(tree.right))
return maxDepth+1
}
// console.log(depth(tree))
/**
* 最大宽度
* 先对树的每个节点进行添加编号,根节点为0 , 左子叶为 根节点*2+1,右子叶为 根节点*2+2
* @param {[type]} tree [description]
* @return {[type]} [description]
*/
function getWidth(tree){
if(tree == null) return 0;
let arr = [];
let maxWidth = 0;
d(tree,0,0)
return maxWidth;
function d(tree, level, num) {
if (arr[level]) {
arr[level].push(num)
} else {
arr[level] = [num]
}
if(tree.left) {
d(tree.left,level+1, num*2 + 1)
}
if(tree.right) {
d(tree.right, level+1, num*2 + 2)
}
maxWidth = Math.max(maxWidth, num - arr[level][0] + 1)
}
}
console.log(getWidth(tree))
// 反转二叉树
function reverse(tree){
if(tree) {
let temp = tree.left;
tree.left = tree.right;
tree.right = temp;
reverse(tree.left)
reverse(tree.right)
}
}
// reverse(tree)
// console.log(tree)
// 反转二叉树
function reverse2(tree){
if(!tree) return null;
if (!tree.right && !tree.left) return tree;
return N(tree.value, reverse2(tree.right), reverse2(tree.left))
}
// console.log(reverse2(tree))
// 二叉树路径总和是否包含某个数
function hasTotal(tree, sum){
if (tree == null) return false;
if(tree.left == null && tree.right == null) {
return sum - tree.value == 0;
}
return hasTotal(tree.left, sum - tree.value) || hasTotal(tree.right, sum - tree.value)
}
let t2 = N(1,N(2),N(3,N(4),N(5)))
// console.log(hasTotal(t2,8))
// 二叉数所有路径总合的数组
let allArr = [];
function total(tree, arr = []){
if(tree == null) return false;
arr.push(tree.value);
if (tree.left !=null) total(tree.left, [...arr])
if (tree.right !=null) total(tree.right, [...arr])
if(tree.left == null && tree.right ==null){
allArr.push(arr);
}
}
total(tree, []);
console.log(allArr)
冒泡排序
/**
* [sort description] 循环数组的每一个元素,分别和后面的元素做比较,如果大于后面的元素,则调换两元素的值
* @param {[type]} arr [description]
* @return {[type]} [description]
*/
function sort(arr) {
let len = arr.length,temp;
for (let i = 0; i < len; i++) {
for (let j = 0; j < len - i; j++) {
if(arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
let arr = [7,3,4.1,1,3,34,12,21,9,7.3,16];
console.log(sort(arr));
函数节流
function throttle(fn, interval = 500){
let timer = null;
return function(...args){
let ctx = this;
if(timer) return;
timer = setTimeout(function(){
clearTimeout(timer)
timer = null;
fn.apply(ctx, args)
}, interval)
}
}
function test(){
console.log(new Date())
}
document.addEventListener('scroll',throttle(test, 100))
函数防抖
const debounce = function(fn, delay) {
// 此处timer用到了闭包,防止timer被释放掉
let timer = null;
return function(...args){
clearTimeout(timer)
timer = setTimeout(() => {
fn.apply(this, args);
}, delay)
}
}
function test(){
console.log(new Date())
}
document.addEventListener('scroll',debounce(test, 500))
字符串有效
let str = '({sdf(sdf[dsf]dg)sldf})()';
function test(str) {
str = str.trim();
let temp = str.split(''),
arr = [],
calcObj = {
'(':')',
'[':']',
'{':'}'
}
temp.map((item) => {
if(Object.keys(calcObj).includes(item) || Object.values(calcObj).includes(item)) arr.push(item);
})
// 如果长为奇数,则无效
if(arr.length%2 == 1) return false;
return calc(arr)
function calc(arr){
let preLength = arr.length;
if(arr.length == 0) return true;
let rel = [];
for(let i = 0; i < arr.length-1; i++){
if(calcObj[arr[i]] == arr[i+1]) {
arr.splice(i,2)
break;
}
}
if(arr.length != preLength) {
return calc(arr)
} else {
return arr.length == 0
}
}
}
let str2 = '{}[{}([{()}])][]';
function test2(str) {
str = str.trim();
function calc(str){
let preLength = str.length;
str = str.split('()').join('');
str = str.split('[]').join('');
str = str.split('{}').join('');
if(str.length != preLength){
return calc(str)
} else {
return str.length == 0
}
}
return calc(str);
}
console.log(test2(str2))
快速排序
/**
* 从数组中抽取任意一个元素做为基准元素;
* 循环抽离基准元素后的数组,比基准元素值大的放在next数组中,其余则放在左pre数组中;
* 然后对pre和nex数组做递归调用,如果数组中只有一个元素,且返回当前数组,否则,返回 sort(pre).concat(split, sort(next))
*
* @param {[type]} arr [description]
* @return {[type]} [description]
*/
function sort(arr) {
if(arr.length <= 1) {
return arr;
}
let split = arr.splice(0,1), pre = [], next = [];
arr.forEach( item=> {
if (item <= split) {
pre.push(item)
} else {
next.push(item)
}
})
return sort(pre).concat(split,sort(next))
}
let arr = [7,3,4.1,1,3,34,12,21,9,7.3,16];
console.log(sort(arr));
排列组合
let arr = [['a','b'],['1','2'],['m','n']];
// 组合
function comb(arr) {
let resultArr = [];
function get(array, index = 0, subArr = []) {
if(!array[index]) {
resultArr.push(subArr.join(''));
return;
};
array[index].forEach((v, i) => {
get(array, index + 1, index === 0 ? [v] : [...subArr,v])
})
}
get(arr);
return resultArr;
}
// 组合
function comb2(arr) {
let rel = [];
function ct(arr, index = 0, neecCount = arr.length, subArr = []){
if(neecCount == 0){
rel.push(subArr.join(''))
return;
}
arr[index].forEach( (item, i) => {
ct(arr, index + 1, neecCount - 1, [...subArr, item])
} )
}
ct(arr)
return rel;
}
console.log(comb2(arr))
let data = ['a','b','c','d'];
// 全组合
function all(arr, index = 0, group = []) {
if(index == arr.length) return group;
let temp = [];
temp.push(arr[index]);
for(let i = 0; i < group.length; i++) {
temp.push(group[i] + arr[index])
}
group = [...group, ...temp]
return all(arr, index+1, group)
}
console.log(all(data))
// 全排列
function allSort(arr, index = 0, group = []){
if(index == arr.length) return group;
let temp = [];
temp.push(arr[index]);
for(let i = 0; i < group.length; i++) {
temp.push(group[i] + arr[index])
temp.push(arr[index] + group[i])
}
group = [...group, ...temp]
return allSort(arr, index+1, group)
}
console.log(allSort(data))
插入排序
/**
* 循环数组,当第i次循环时,取第i次之后的元素作为参考元素,再循环和前面的值做比较
* 如果前面的值比参考元素大,则将前面的值赋给后面的元素,否则,将参考元素的值赋给比较的元素
* @param {[type]} arr [description]
* @return {[type]} [description]
*/
function sort(arr) {
if(arr.length <= 1) {
return arr;
}
let len = arr.length;
for(let i = 0; i < len-1; i++) {
let preIndex = i; curr = arr[i+1];
while(preIndex >=0 && arr[preIndex] > curr){
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = curr;
}
return arr;
}
let arr = [7,3,4.1,1,3,34,12,21,9,7.3,16];
console.log(sort(arr));
数字千分位
function split(value){
let str = value.toString(),
endArr = [];
let temp = str.split('.'),
arr = temp[0].split('');
for(let i = arr.length-1; i >= 2; i -= 3) {
endArr.unshift( arr[i-2] + arr[i-1] + arr[i])
endArr.unshift( arr[i-2] + arr[i-1] + arr[i])
}
let pre = str.slice(0, arr.length%3);
if (pre) endArr.unshift(pre);
let endStr = endArr.join(',')
if(temp.length > 1) {
endStr = endStr + '.' + temp[1]
}
return endStr;
}
function split2(value){
let arr = value.toString().split('').reverse();
let temp = [];
for(let i = 0; i < arr.length; i += 3){
temp.push(arr.slice(i, i + 3).join(''));
}
return temp.join(',').split('').reverse().join('');
}
// 1
function split5(val){
let a = val.toString().split('').reverse(),
arr = [];
for(let i = 0; i < a.length; i += 3){
arr.push(a.slice(i,i+3).reverse().join(''))
}
return arr.reverse().join(',');
}
function split3(value) {
return value.toLocaleString()
}
function split4(value) {
let str = value.toString();
let reg = /(\d{1,3})(?=(\d{3})+$)/g;
return str.replace(reg, "$1,")
}
let s = 1234567
console.log(s,s.toString().length)
console.log(split4(s))
数组最大深度
function depth(arr){
if(typeof arr != 'object') return 0;
let a = []
arr.forEach( (item, i) =>{
a.push(depth(item))
})
let maxDepth = Math.max(...a)
return maxDepth+1;
}
let arr = [1, 2, [3, [5,[6],[7,[8]]],[4]]]
console.log(depth(arr))
数组随机组合
var arr = [1,3,4,6,7];
var result = [];
function pick(arr, beginIndex = 0, needCount = 3, subResult = []){
if(needCount == 0) {
result.push(subResult)
return;
}
for(var i = beginIndex; i< arr.length; i++) {
var num = arr[i];
var temp = [...subResult, num]
pick(arr,i+1, needCount-1, temp)
}
}
pick(arr)
console.log(result)
// 数组求和
function sum(arr){
return arr.reduce((pre, next) => {
return pre + next;
})
}
let s = 0;
function sum2(arr){
arr.map((item) => {
s += item;
})
}
柯里化
function add(a,b,c) {
return a + b + c;
}
/**
* [curry] 柯里化函数,实现原理是递归调用,当参数和原函数的参数个数相同时,则执行原函数,并返回结果,哪果参数个数小于原函数时,则返回柯里化函数自身
* @param {Function} fn [description]
* @param {[type]} args [description]
* @return {[type]}
* 如果param数组的长度和fn参数的长度一至时,执行fn方法,返回计算结果;
* 如果param数组的长度小于fn参数的长度时,递归调用cur,继续拼装params。
*/
var curry = function(fn, args){ //1
return function(){
let param = [...arguments];
if(args !== undefined) {
// param = param.concat(args);
param = [...param, ...args];
}
if(param.length < fn.length) {
return curry(fn, param)
}
return fn.apply(null, param)
}
}
let adds = curry(add);
console.log(adds(1,2,4))
console.log(adds(1)(2)(3))
console.log(adds(2)(3)(4))
版本号排序
function sort(arr){
arr.sort( (an, bn) => {
let arrA = an.split('.'),arrB = bn.split('.'), r;
for(let i in arrA){
let a = arrA[i], b = arrB[i];
if(a == b) continue;
r = a - b;
break;
}
return r;
})
return arr;
}
var arr = ['1.5','1.45','1.3.2','1.0.2','3.0.2','2.0.2']
console.log( sort(arr))
虚拟dom
let demoNode = {
tagName: 'ul',
props: {'class': 'users','id': 'u'},
children: [
{tagName: 'li', children: ['xiaozi']},
{tagName: 'li', children: ['jack']},
{
tagName: 'li',
props: {'class': 'me'},
children: [
{ tagName: 'a', children: ['click']},
{ tagName: 'span', children: ['tips']}
]
}
]
};
function Factory({tagName, props, children}){
if (!(this instanceof Factory)) {
return new Factory({tagName, props, children})
}
this.tagName = tagName
this.props = props || {}
this.children = children || []
this.props.aaa = 44
children.forEach( (item, index) => {
if(Object.prototype.toString.call(item) === '[object Object]') {
children[index] = Factory(item);
}
})
}
Factory.prototype.render = function(){
let el = document.createElement(this.tagName)
for (let i in this.props) {
if(this.props.hasOwnProperty(i)){
el.setAttribute(i, this.props[i])
}
}
this.children.forEach( child => {
let childEl;
if(child instanceof Factory) {
childEl = child.render()
} else {
childEl = document.createTextNode(child)
}
el.appendChild(childEl)
})
return el;
}
// var em = Factory(JSON.parse(JSON.stringify(demoNode)));
var em = Factory(demoNode);
console.log(em.render())
选择排序
/**
* 循环数组,确定第i次循环中最小值的位置minIndex; 第i次循环里面的循环是从[i,arr.length-1],这是因为i前面的都在前面的循环中比对过了,所以从i开始
* 比较minIndex和i位置元素的大小,如果i值小,则不变,如果i的值大,则两位置上的值相互调换
*
* @param {[type]} arr [description]
* @return {[type]} [description]
*/
function sort(arr) {
let len = arr.length,minIndex;
for(let i = 0; i < len; i++) {
minIndex = i;
for (let j = i; j < len; j++) {
if(arr[minIndex] > arr[j]) {
minIndex = j;
}
}
if(i != minIndex) {
let temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
return arr;
}
let arr = [7,3,4.1,1,3,34,12,21,9,7.3,16];
console.log(sort(arr));
链表
// 单链表
class Node {
constructor(value = null, next = null) {
this.value = value;
this.next = next;
}
}
function N(value, next) {
return new Node(value, next)
}
class List {
constructor() {
this.head = N('head');
}
// 查找结点
find(item){
let curr = this.head;
while (curr.value != item) {
curr = curr.next
}
return curr;
}
// 在已知元素后面插入新节点
inset(item, value){
let node = N(value);
var curr = this.find(item);
node.next = curr.next;
curr.next = node;
}
findPre(item){
let curr = this.head;
while(curr.next!=null && curr.next.value != item) {
curr = curr.next
}
return curr
}
remove(item){
let pre = this.findPre(item);
if(pre.next != null) {
pre.next = pre.next.next;
}
}
}
let l = new List();
l.inset('head', 'a');
l.inset('a', 'b');
l.inset('b', 'c');
l.inset('c', 'd');
l.inset('d', 'e');
l.inset('e', 'f');
console.log(l.find('b'))
console.log(l.findPre('b'))
l.remove('d')
console.log(l)
链表双
// 链表
class Node {
constructor(value = null, pre = null, next = null) {
this.value = value;
this.pre = pre;
this.next = next;
}
}
function N(value, pre, next) {
return new Node(value, pre, next)
}
class List {
constructor(){
this.head = N('head')
this.tail = N('tail')
this.head.next = this.tail;
this.tail.pre = this.head;
}
find(item){
let curr = this.head;
while(curr.value != item){
curr = curr.next;
}
return curr;
}
insert(item, value) {
let node = N(value);
let curr = this.find(item);
node.next = curr.next;
curr.next.pre = node;
curr.next = node;
node.pre = curr;
}
remove(item){
let curr = this.find(item);
if(curr.next) {
curr.pre.next = curr.next;
curr.next.pre = curr.pre;
curr.pree = null
curr.next = null
}
}
}
let l = new List();
l.insert('head','a')
l.insert('a','b')
l.insert('b','c')
l.insert('c','d')
l.remove('b')
console.log(l)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
交流请添加微信: qian-qianyu