前端面试算法总结

1.合并有序数组
方法一:清空符合条件的原数组

function merge(l1,l2){
    let res = [];
    while(l1.length && l2.length){
        if(l1[0]<l2[0]){
            res.push(l1.shift())
        }else{
            res.push(l2.shift())
        }
    }
    res = res.concat(l1,l2);
    return res
}

方法二:双指针

function merge(l1,l2){
    let res = [];
    let i=0;j=0
    while(i<l1.length && j<l2.length){
        if(l1[i]<l2[j]){
            res.push(l1[i])
            i++;
        }else{
            res.push(l2[j])
            j++
        }
    }
    while(i<l1.length){
        res.push(l1[i])
        i++;
    }
    while(j<l2.length){
        res.push(l2[j])
        j++;
    }
    return res
}
let l1 = [1,4,5,23];
let l2 = [0,2,3,6,7,8];
console.log(merge(l1,l2))

2.用指定数组内容按照数字顺序替换占位符@1@,@2@
例子:str = 你好@1@,天气@2@ arr = ['李明','晴'] =》你好李明,天气晴

function cusReplce(str,repArr){
    for(let i=0; i<repArr.length; i++){
         str = str.replace(new RegExp('@'+(i+1)+'@'),repArr[i])
    }
   return str;
}
let str = '你好@1@,天气@2@';
let arr = ['李明','晴朗'];
console.log(cusReplce(str,arr))

3.多维数组扁平化

function flatter(list){
   if(Array.isArray(list)){
       return list.reduce((a,b)=>{
           return [...a, ...flatter(b)]
       },[])
   }
   return [list];
}
let arr = [1,2,[3,[4,5]]];
console.log(flatter(arr))

4.M*N的棋盘从左上角到右下角总共有多少种走法,要求不能回头

function chess(m,n){
   if(m<1||n<1) return 0;
   if(m==1 && n!==1){
       return n+1;
   }
   if(m!=1 && n==1){
       return m+1;
   }
   return chess(m-1,n)+chess(m,n-1)
}

5.二叉树是否存在路径总和等于目标值

function path(root,target){
   if(!root){
       return false
   }
   if(!root.left&&!root.right){
     return root.value == target;
   }
   return path(root.left,target-root.value) || path(root.right,target-root.value);
}

6.var locationList = [
{ id: 0, name: "中国" },
{ id: 1, pid: 0, name: "广东省" },
{ id: 2, pid: 1, name: "深圳市" },
{ id: 3, pid: 1, name: "广州市" },
{ id: 4, pid: 0, name: "陕西省" },
]
变为
[{
id: 0,
name: "中国" ,
children:[
{ id: 1,
pid: 0,
name: "广东省",
children:
[
{ id: 2, pid: 1, name: "深圳市" ,children:[]},
{ id: 3, pid: 1, name: "广州市",children:[] }
]
},
{ id: 4, pid: 0, name: "陕西省" ,children:[]},
]
}].

function buildLocationTree(list){
   let map = {};
   for(let i=0; i<list.length;i++){
       let id = list[i]['id'];
       map[id] = list[i]
   }
   let res = [];
   for(let i=0; i<list.length;i++){
       let item = list[i];
       let pid = item['pid'];
       if(pid !== undefined && map[pid]){
           if(map[pid].children){
               map[pid].children.push(item)
           }else{
               map[pid].children = [item]
           }   
       }else{
           res.push(item)
       }
   }
   return res;
}

7.树的遍历

let tree =  [{"id":0,"name":"中国","children":[{"id":1,"pid":0,"name":"广东省","children":[{"id":2,"pid":1,"name":"深圳市"},{"id":3,"pid":1,"name":"广州市"}]},{"id":4,"pid":0,"name":"陕西省"}]}]
找出指定id的name
function dfs(list,id){
    for(let i=0;i<list.length;i++){
        let item = list[i];
        if(item.id == id){
            return item.name;
        }
        else if(item.children && item.children.length>0){
            dfs(item.children,id)
        }
        else{
            return -1
        }
    }
}

function find(lists,id){
    if(lists.id == id){
        return lists.name;
    }
    else{
        if(lists.children && lists.children.length>0){
            return dfs(lists.children,id)
        }
    }
}
console.log(find(tree,6))

8.add(1,2)(2)() // 5

function add(){
    let args = [...arguments];
    let res = 0;
    for(let i = 0; i<args.length;i++){
        res += args[i];
    }
    return function F(...args1){
        if(args1.length){
            return add(...args,...args1)
        }
        else{
            return res;
        }
    }
}
console.log(add(1,2)(4)())

9.实现一个console和setTimeout链式调用

class A{
    constructor(){
        this.promise = Promise.resolve()
    }

    console(v){
        this.promise = this.promise.then(()=>{
            console.log(v)
        })
        return this;
    }

    setTimeout(wait){
        this.promise = this.promise.then(()=>{
            return new Promise((resolve)=>{
                setTimeout(()=>{
                    resolve()
                },wait)
            })
        })
        return this;
    }
}
let a = new A()
a.console('1').setTimeout(1000).console('2')

10.实现一个sleep

function sleep(wait){
    return new Promise((resolve,reject)=>{
        setTimeout(resolve,wait)
    })
}
async function init(wait){
    let res = await sleep(wait)
    console.log(3)
    return res;
}
console.log(1)
init(3000)

11.实现compose函数

function compose(...args){
    let len = args.length;
    let count = len-1;
    let res = '';
    return function F(...args1){
        res = args[count].apply(this,args1);
        if(count <= 0){
            return res
        }else{
            count--;
            return F(res)
        }
    }
}
let test = (x,y) => x+y
let uppcase = (x) => x.toUpperCase()
let add = (x) => x+'123'
let re = compose(add, uppcase,test)('hello','world')
console.log(re)
  1. fn([['a', 'b'], ['n', 'm'], ['0', '1']]) => ['an0', 'am0', 'an1', 'am1', 'bn0', 'bm0', 'bn1', 'bm0']
function dfs(result, tempRes, curIndex, list){
    if(tempRes.length === list.length){
       result.push(tempRes.join(''));
       return;
    }
    for(let i=0;i<list[curIndex].length;i++){
        tempRes.push(list[curIndex][i]);
        dfs(result,tempRes,curIndex+1,list);
        tempRes.pop()
    }
}
function composeList(list){
    let len = list.length;
    let result = [];
    dfs(result,[],0,list);
    return result;
}
let term = composeList([['a', 'b'], ['n', 'm'], ['0', '1']]) 
console.log(term)

13.给数组中的字符串编号,f(['ab', 'c', 'd', 'ab', 'c']) => ['ab1', 'c1', 'd', 'ab2', 'c2']

function fn(list){
    let map = {};
    for(let i=0;i<list.length;i++){
        if(map[list[i]]){
            map[list[i]]++;
        }
        else{
            map[list[i]] = 1;
           
        }
        list[i] = list[i]+map[list[i]]
    }
    return list;
}
let list = fn(['ab', 'c', 'd', 'ab', 'c'])
console.log(list)
  1. 判断链表有环
1.快慢双指针 相遇则有环
function circle(head){
    let p1 = head;
    let p2 = head;
    while(p2 && p2.next){
        p1 = p1.next;
        p2 = p2.next.next
        if(p1 === p2){
            return true;
        }  
    }
    return false;
}
2.使用set判断节点有没有加入过,有的话则有环
function circle(head){
    let set = new Set();
    while(head){
        if(set.has(head)) return true
        set.add(head)
        head = head.next;
    }
    return false;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。