程序员面试题

实现一个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)