2020秋招笔试/面试编程题小记

自己对秋招过程中的一些算法题、编程题的一些复盘（非网络搜集）

一、图的遍历

1. 求带权图的最大路径

问题描述

图（A、B、C、D、E、F、G）

A B 100
B D 100
D E 50
A C 200
C G 300
A F 100

A->B->D->E 250

A->C->G 500

A->F 100

B->D->E 150

C->G 300

找到权重最大的路径，输出出来（如果有多条一样的，全部都输出）

解题方案

// 路径遍历
let read_line = (function (){
    let i = 0
    data = [
        'A B 100',
        'B D 100',
        'D E 50',
        'A C 200',
        'C G 300',
        'A F 500',
    ]
    return function (){
        return data[i++]
    }
})()

function main(){
    // 定义路径树,最终将会生成如下：
    /*
     { A: { B: 100, C: 200, F: 100 },
       B: { D: 100 },
       D: { E: 50 },
      C: { G: 300 } }*/
     
    let TREE = {}

    let MaxValue = 0 , MaxRoads = []

    let read  = read_line()

    while(read){
        let p = read.split(' ')
        let begin = p[0],end = p[1],value = parseInt(p[2])
        // 生成路径树
        TREE[begin] = {...TREE[begin],[end]:value}
        read = read_line()
    }
    /**
     * 回溯函数
     * @param {String} begin 起点键值
     * @param {Object} tree 路径树
     * @param {Number} value 当前路径权值 
     * @param {String} road 已走过的路径
     */
    function resolve(begin,tree,value,road){
        if(!tree[begin])return
        
        for (const end in tree[begin]) {
            if (tree[begin].hasOwnProperty(end)) {
                const element = tree[begin][end];
               
                let currentValue = value+element,currentRoad = road+'->'+end
               
                if(!TREE[end] && currentValue > MaxValue){
                    // 抵达终点，当前值比之前的最大值还要大，更新MaxValue和路径数组
                    MaxValue = currentValue
                    MaxRoads = [currentRoad]
                    continue
                }else if(!TREE[end] && currentValue == MaxValue){
                    // 抵达终点，当前值等于之前的最大值，路径数组新增路径
                    MaxRoads.push(currentRoad)
                }else if(TREE[end]){
                    // 还没有抵达终点，继续向下走
                    resolve(end,tree,currentValue,currentRoad)
                }
            }
        }
    }
    for (const begin in TREE) {
        if (TREE.hasOwnProperty(begin)) {
            // 遍历路径树下的各个起点，开始路径计算
            resolve(begin,TREE,0,begin)
        }
    }
    MaxRoads.map(road=>console.log(road,MaxValue))
}

main()

2. 小D去旅游

问题描述

小D要在某个时间点要从A点到B点，A到B有可能有多种不同的路径方案，计算小D走花费时间最小路径到达B点后的时间。

输入第一行 N:节点个数，M:边的个数

输入之后的M行都是 节点begin 节点end 需要花费的时间(小时)

最后一行再输入 小D要出发的点 到达的点 起始时间（起始时间格式：month.day/hour）

输出 小D抵达的时间month.day/hour

样例1：

输入：
4 4
1 2 5
1 3 6
2 4 8
3 4 6
1 4 7.9/8

输出：
7.9/20 
注：1->3->4 = 12小时

样例2：

输入：
4 4
1 2 25
1 3 18
2 4 28
3 4 22
1 4 7.9/8

输出：
7.11/0
注：1->3->4 = 40小时

解决方案

let read_line = (function (){
    let i = 0
    let data = [
        '4 4',
        '1 2 25',
        '1 3 18',
        '2 4 28',
        '3 4 22',
        '1 4 7.9/8',
        ]
    // let data = [
    //     '4 4',
    //     '1 2 5',
    //     '1 3 6',
    //     '2 4 8',
    //     '3 4 6',
    //     '1 4 7.9/8',
    //     ]
    return function (){
        return data[i++]
    }
})()

function main(){
    let args = read_line().split(' ')
    let N = args[0]
    let M = args[1]

    // 默认为最大time
    let result = 1000000000000000
    let TREE = {}
    for(let i=0;i<M;i++){
        let p = read_line().split(' ').map(e=>parseInt(e))
        let begin = p[0],end = p[1],time = p[2]
        if(TREE[begin])TREE[begin][end] = time
        else{
            TREE[begin] = {
                [end]:time
            }
        }
    }
    
    // 获取起点、终点和时间
    let p = read_line().split(' ')
    let Begin = p[0],End = p[1],BeginTime = p[2]
    // 构建回溯函数
    function resolve(begin,end,tree,price){
        if(!tree[begin])return 
        for (const key in tree[begin]) {
            if (tree[begin].hasOwnProperty(key)) {
                const element = tree[begin][key];
                // 找到终点
                if(key == end && price+element<result){
                    result = price+element
                    continue
                }
                if(key != end && price+element < result){
                    resolve(key,end,tree,price+element)
                }
            }
        }
    }
    // 获取最小需要花费的时间 => result
    resolve(Begin,End,TREE,0)

    // 返回值为加了result时间后的时间字符串
    function addHour(time,hours){
        let [month,day,hour] = time.split(/[\.\/]/)
        let resHour = parseInt(hour)+parseInt(hours)
        let a = new Date(2020,month-1,parseInt(day)+parseInt(resHour/24),resHour%24)
        return `${a.getMonth()+1}.${a.getDate()}/${a.getHours()}`

    }
    console.log(addHour(BeginTime,result))

}
main()

3. 省钱造桥术

问题描述

城市管理者要把若干岛屿造桥连接起来，并限定造每条桥的最大成本，设计程序查看是否能在这种情况下把所有岛屿连接起来。

第一行输入T 代表组数

第二行输入第一组的 N节点数 M边数 最大成本K

接下来的M行 ： 小岛begin 小岛end 需要的花费

再输入第二组 ...

输出Yes或者No代表是否将所有岛屿连接起来

样例：

2
4 3 400
1 2 200
1 3 400
3 4 300
3 3 400
1 2 500
1 3 600
2 3 700

Yes
No

解决方案

let read_line = (function (){
    let i = 0
    let data = [
        '2',
        '4 3 400',
        '1 2 200',
        '1 3 400',
        '3 4 300',
        '3 3 400',
        '1 2 500',
        '1 3 600',
        '2 3 700',
        ]
    return function (){
        return data[i++]
    }
})()
main()
function main(args){
    let T = read_line()
    for(let i=0;i<T;i++){
        console.log(resolve())
    }
}

function resolve(){
    let args = read_line().split(' ').map(e=>parseInt(e))
    let N = args[0] // 小岛数目
    let M = args[1] // 边数
    let maxPrice = args[2] //最大成本
    
    // 定义数据树 { '1': { '2': 500, '3': 600 }, '2': { '3': 700 } }
    let TREE = {}
    for (let index = 0; index < M; index++) {
        let p = read_line().split(' ').map(e=>parseInt(e))
        let begin = p[0],end = p[1],price = p[2]
        if(TREE[begin]) TREE[begin][end] = price
        else{
            TREE[begin] = {
                [end]:price
            }
        }
    }
    // 结果状态树，存放满足最大成本的小岛为key
    let result = {}
    // 存放当前的已构建的桥数
    let sideCount = 0
    // 根据数据树 遍历小岛起点
    for (const begin in TREE) {
        if (TREE.hasOwnProperty(begin)) {
            const ends = TREE[begin]
            // 遍历小岛终点
            for (const end in ends) {
                if (ends.hasOwnProperty(end)) {
                    const element = ends[end]
                    
                    if(element <= maxPrice){ //小于等于最大成本
                        // 将两个小岛都存放到结果树中
                        result[begin] = result[end] = true
                        // 增加桥数
                        sideCount++
                        // 如果当前结果树中，节点个数正好与N要求一致，并且边数正好是节点个数减一（防止1->2,3->4出现的错误） 则返回"Yes"
                        if(Object.keys(result).length === N && sideCount == N-1) return "Yes"
                    }
                }
            }
        }
    }
    return "No"
}

二、其他

1. 字符串全排列

题目描述

*全排列 'abc' -> ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

解题方案

function permutation(str) {
    let ans = []
    function Search(str = '',result = ''){
        if(str.length === 0)return ans.push(result)
        let arr = str.split('')
        for(let i = 0;i < arr.length;i++){
            let t = arr[i]
            arr[i] = ''
            Search(arr.join(''),result+t)
            arr[i] = t
        }
    }
    Search(str,"")
    return ans
}

2. 异步控制

题1

题目描述

function asyncAdd(a, b, callback) {

setTimeout(() => callbacl(null, a + b), 0);

}

asyncAdd(1, 2, function (err, result) {

if (err) throw err;

console.log(result); // 3

});

-- 题目

有一个数列：[1, 2, 3, ...., N]

基于 asyncAdd 完成数列的求和操作。

function sum(list) {

// TODO

}

sum([1, 2, 3, 4]).then(v => console.log(v)); // 10

解题方案

function asyncAdd(a, b, callback) {
    setTimeout(() => callback(null, a + b), 0);
}

function sum(list = []){
    return new Promise((resolve,reject)=>{
        if(list.length > 2){
            sum(list.slice(1)).then(data=>{
                asyncAdd(list[0],data,(err,data)=>{
                    resolve(data)
                })
            })
        }else{
            asyncAdd(list[0],list[1],(err,data)=>{
                resolve(data)
            })
        }
    })
}

sum([1,2,3,4]).then(console.log)

题2

题目描述

let tasks = [task1, task2, ..., taskN];

function seq(tasks) {

}

promise.then()

task1().then(() => task2()).then(() => task3())

模拟tasks

function asyncPrint(str){
    return function(){
        return new Promise((resolve,reject)=>{
            setTimeout(()=>{
                console.log(str)
                resolve()
            },Math.random()*1000)
        })
    }
} 

let tasks = [ asyncPrint("task1"), asyncPrint("task2"), asyncPrint("task3")]

解题步骤

解1：

function seq(tasks) {
    return tasks.reduce((pre,cur)=>{
        return pre.then(cur)
    },Promise.resolve())
}

解2：

function seq(tasks) {
    if(tasks.length == 0)return
    tasks[0]().then(()=>{
        seq(tasks.slice(1))
    })
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,271评论 5赞 476
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,275评论 2赞 380
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,151评论 0赞 336
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,550评论 1赞 273
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,553评论 5赞 365
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,559评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,924评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,580评论 0赞 257
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,826评论 1赞 297
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,578评论 2赞 320
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,661评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,363评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,940评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,926评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,156评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,872评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,391评论 2赞 342